Slide Number 1Slide Number 2Slide Number 3Slide Number 4Slide Number 5Slide Number 6Slide Number 7Slide Number 8Slide Number 9Slide Number 10Slide Number 11Slide Number 12Slide Number 13Slide Number 14Slide Number 15Slide Number 16Slide Number 171Lecture 8: Eager Transactional Memory• Topics: implementation details of eager TM, variousTM pathologies2“Eager” OverviewTopics:• Logs• Log optimization• Conflict examples• Handling deadlocks• Sticky scenarios• Aborts/commits/parallelismCDirPR WCDirPR WCDirPR WCDirPR WScalable Non-broadcast Interconnect3“Eager” Implementation (Based Primarily on LogTM)• A write is made permanent immediately (we do not waituntil the end of the transaction)• Can’t lose the old value (in case this transaction isaborted) – hence, before the write, we copy the oldvalue into a log (the log is some space in virtual memory-- the log itself may be in cache, so not too expensive)This is eager versioning4Versioning• Every overflowed write first requires a read and a write tolog the old value – the log is maintained in virtual memoryand will likely be found in cache • Aborts are uncommon – typically only when thecontention manager kicks in on a potential deadlock; thelogs are walked through in reverse order• If a block is already marked as being logged (wr-set), thenext write by that transaction can avoid the re-log• Log writes can be placed in a write buffer to reducecontention for L1 cache ports5Conflict Detection and Resolution• Since Transaction-A’s writes are made permanentrightaway, it is possible that another Transaction-B’srd/wr miss is re-directed to Tr-A• At this point, we detect a conflict (neither transaction hasreached its end, hence, eager conflict detection): twotransactions handling the same cache line and at leastone of them does a write• One solution: requester stalls: Tr-A sends a NACK toTr-B; Tr-B waits and re-tries again; hopefully, Tr-A hascommitted and can hand off the latest cache line to BÆ neither transaction needs to abort6Deadlocks• Can lead to deadlocks: each transaction is waiting for theother to finish• Need a separate (hw/sw) contention manager to detectsuch deadlocks and force one of them to abortTr-A Tr-Bwrite X write Y… …read Y read X• Alternatively, every transaction maintains an “age” and a youngtransaction aborts and re-starts if it is keeping an older transactionwaiting and itself receives a nack from an older transaction7Block Replacement• If a block in a transaction’s rd/wr-set is evicted, the datais written back to memory if necessary, but the directorycontinues to maintain a “sticky” pointer to that node(subsequent requests have to confirm that the transactionhas committed before proceeding)• The sticky pointers are lazily removed over time (commitscontinue to be fast)8Paper on TM Pathologies• LL: lazy versioning, lazy conflict detection, committingtransaction wins conflicts• EL: lazy versioning, eager conflict detection, requestersucceeds and others abort• EE: eager versioning, eager conflict detection, requesterstalls9• Two conflicting transactions thatkeep aborting each other• Can do exponential back-off tohandle livelock• Fixable by doing requester stalls?• VM: any• CD: eager• CR: requester winsPathology 1: Friendly Fire10• A writer has to wait for the readerto finish – but if more readers keepshowing up, the writer is starved (note that the directory allows newreaders to proceed by just addingthem to the list of sharers)• VM: any• CD: eager• CR: requester stallsPathology 2: Starving Writer11• If there’s a single commit token,transaction commit is serialized• There are ways to alleviate this problem• VM: lazy• CD: lazy• CR: anyPathology 3: Serialized Commit12• A transaction is stalling on anothertransaction that ultimately aborts andtakes a while to reinstate old values• VM: any• CD: eager• CR: requester stallsPathology 4: Futile Stall13• Small successful transactions cankeep aborting a large transaction• The large transaction can eventuallygrab the token and not release ituntil after it commits• VM: lazy• CD: lazy• CR: committer winsPathology 5: Starving Elder14• A number of similar (conflicting)transactions execute together – onewins, the others all abort – shortly,these transactions all return andrepeat the process• VM: lazy• CD: lazy• CR: committer winsPathology 6: Restart Convoy15• If two transactions both read thesame object and then both decide towrite it, a deadlock is created• Exacerbated by the Futile Stall pathology• Solution?• VM: eager• CD: eager• CR: requester stallsPathology 7: Dueling Upgrades16Four Extensions• Predictor: predict if the read will soon be followed by awrite and acquire write permissions aggressively• Hybrid: if a transaction believes it is a Starving Writer, itcan force other readers to abort; for everything else, userequester stalls• Timestamp: In the EL case, requester wins only if it is theolder transaction (handles Friendly Fire pathology)• Backoff: in the LL case, aborting transactions invokeexponential back-off to prevent convoy formation17Title•