Transactional Memory and the Birthday Paradox

Zilles, Craig; Rajwar, Ravi

Permalink

https://hdl.handle.net/2142/11305 Copy

Description

Title

Transactional Memory and the Birthday Paradox

Author(s)

• Zilles, Craig
• Rajwar, Ravi

Issue Date

2007-03

Keyword(s)

computer science

Abstract

Transactional Memory (TM) has been proposed as an alternative implementation of mutual exclusion that avoids many of the drawbacks of locks (e.g., deadlock, reliance on the programmer to associate shared data with locks, priority inversion, and failures of threads while holding locks). TM enables the program- mer to denote atomic regions (transactions) that are executed optimistically; if a conflict is detected, the thread is rolled back to the beginning of the transaction. A Software Transactional Memory (STM) im- plements speculative execution (so that a roll back can be performed) and conflict detection by adding additional code to the application. In an STM that tracks mutual exclusion at a word or cache-line granularity, an ownership table is used to keep track of which transactions currently have read and write permissions to which regions of memory. Memory addresses are mapped to ownership table entries by hashing the memory address. A frequently proposed design for ownership tables (used in previous STM and hybrid hardware/software TM proposals) is that of a tagless table, where read and write permissions are granted at the granularity of all addresses that map to a given ownership table entry. When two transactions have memory accesses that map to the same ownership table entry, the tagless nature of this organization requires the STM to conservatively force one transaction to abort if one or more of the aliasing accesses is a write. Using address traces from a multithreaded program, we demonstrate that the frequency of these false conflicts grows superlinearly with both the TM data footprint and concurrency and that increasing the size of the ownership table results in only a sub-linear reduction in conflict rate. These somewhat surprising relationships have a theoretical foundation that is also responsible for the (naively) unintuitive statistical result generally referred to as the .Birthday Paradox.: that in a collection of at least 23 randomly chosen people, the probability is more than 50% that at least two of them will have the same birthday. In layman.s terms, two addresses are likely to map to the ownership table entry long before the table is full. We present an analytical model based on random population of an ownership table by concurrently executing transactions that correctly predicts the trends in measured data. From this study, we conclude that tagless ownership tables are not a robust approach to supporting transactional memories. Even large tables (. 64K entries) are only somewhat effective at mitigating false conflicts in the presence of modest sized transactions (e.g., 20 cache blocks) and modest degrees of concurrency (e.g., 4 simultaneous transactions). In contrast, tagged ownership tables, which record addresses and use chaining to handle aliasing, do not result in false conflicts and, when appropriately sized, only infrequently require chaining. This result is particularly important in the context of hybrid TMs, where the small transactions are likely handled in hardware, leaving only the large ones for the STM.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11305

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections