1Lecture 5: TM – Lazy Implementations• Topics: TM design (TCC) with lazy conflict detection andlazy versioning, intro to eager conflict detection2Design Space• Data Versioning Eager: based on an undo log Lazy: based on a write bufferTypically, versioning is done in cache;The above two are variants that handle overflow• Conflict Detection Optimistic detection: check for conflicts at commit time(proceed optimistically thru transaction) Pessimistic detection: every read/write checks forconflicts (so you can abort quickly)3Basic Implementation – Lazy, Lazy• Writes can be cached (can’t be written to memory) – if theblock needs to be evicted, flag an overflow (abort transactionfor now) – on an abort, invalidate the written cache lines• Keep track of read-set and write-set (bits in the cache) foreach transaction• When another transaction commits, compare its write setwith your own read set – a match causes an abort• At transaction end, express intent to commit, broadcastwrite-set (transactions can commit in parallel if their write-sets do not intersect)4Lazy OverviewTopics:• Commit order• Overheads, reg chkpt• Wback, WAW• Overflow, I/O, nesting, context-swt• Parallel Commit• Hiding Delay• Deadlock, Livelock, StarvationCPR WCPR WCPR WCPR WMA5“Lazy” Implementation (Partially Based on TCC)• An implementation for a small-scale multiprocessor witha snooping-based protocol• Lazy versioning and lazy conflict detection• Does not allow transactions to commit in parallel6Handling Reads/Writes• When a transaction issues a read, fetch the block inread-only mode (if not already in cache) and set therd-bit for that cache line• When a transaction issues a write, fetch that block inread-only mode (if not already in cache), set the wr-bitfor that cache line and make changes in cache• If a line with wr-bit set is evicted, the transaction mustbe aborted (or must rely on some software mechanismto handle saving overflowed data) (or must acquirecommit permissions)7Commit Process• When a transaction reaches its end, it must now makeits writes permanent• A central arbiter is contacted (easy on a bus-based system),the winning transaction holds on to the bus until all writtencache line addresses are broadcasted (this is the commit)(need not do a writeback until the line is evicted or writtenagain by a transaction – must simply invalidate other readers)• When another transaction (that has not yet begun to commit)sees an invalidation for a line in its rd-set, it realizes itslack of atomicity and aborts (clears its rd- and wr-bits andre-starts)8Miscellaneous Properties• While a transaction is committing, other transactions cancontinue to issue read requests• Writeback after commit can be deferred until the nextwrite to that block by a transactional instruction• If we’re tracking info at block granularity, (for variousreasons), a conflict between write-sets must force an abort9Summary of Properties• Lazy versioning: changes are made locally; overflows are saved in aseparate log – the “master copy” is updated only at the end of the Tx• Lazy conflict detection: we are checking for conflicts only when one ofthe transactions reaches its end• Aborts are quick (must just clear bits in cache, flush pipeline andreinstate a register checkpoint)• Commit is slow (must check for conflicts, all the coherence operationsfor writes are deferred until transaction end)• No fear of deadlock/livelock – the first transaction to acquire the bus willcommit successfully• Starvation is possible – need additional mechanisms10TCC Features• All transactions all the time (the code only definestransaction boundaries): helps get rid of the baselinecoherence protocol• When committing, a transaction must acquire a centraltoken – when I/O, syscall, buffer overflow is encountered,the transaction acquires the token and starts commit• Each cache line maintains a set of “renamed bits” – thisindicates the set of words written by this transaction –reading these words is not a violation and the read-bit isnot set11TCC Features• Lines evicted from the cache are stored in a write buffer;overflow of write buffer leads to acquiring the commit token• Less tolerant of commit delay, but there is a high degreeof “coherence-level parallelism”• To hide the cost of commit delays, it is suggested that acore move on to the next transaction in the meantime –this requires “double buffering” to distinguish betweendata handled by each transaction• An ordering can be imposed upon transactions – useful forspeculative parallelization of a sequential program12Parallel Commits• Writes cannot be rolled back – hence, before allowingtwo transactions to commit in parallel, we must ensurethat they do not conflict with each other• One possible implementation: the central arbiter cancollect signatures from each committing transaction(a compressed representation of all touched addresses)• Arbiter does not grant commit permissions if it detectsa possible conflict with the rd-wr-sets of transactionsthat are in the process of committing• The “lazy” design can also work with directory protocols13Scalable Algorithm – Example (PACT’08 paper)P1T1D1:X ZP2T2YRd XWr XRd YWr ZD2:14Scalable Algorithm – Lazy Implementation• Data is distributed across several nodes/directories• Each node has a token• For a transaction to commit, it must first acquire all tokenscorresponding to the data in its read and write set – this guarantees that an invalidation will not be received whilethis transaction commits• After performing the writes, the tokens are released• Tokens must be acquired in numerically ascending orderfor deadlock avoidance – can also allow older transactionsto steal from younger transactions15Design Space• Data Versioning Eager: based on an undo log Lazy: based on a write bufferTypically, versioning is done in cache;The above two are variants that handle overflow• Conflict Detection Optimistic detection: check for conflicts at commit time(proceed optimistically thru transaction) Pessimistic detection: every read/write checks forconflicts (so you can abort quickly)16“Eager” OverviewTopics:• Logs• Log optimization• Conflict examples• Handling deadlocks• Sticky scenarios• Aborts/commits/parallelismCDirPR WCDirPR WCDirPR WCDirPR WScalable Non-broadcast Interconnect17“Eager”