Implications of False Conflict Rate Trends for Robust Software Transactional Memory

We demonstrate that a common optimization for reducing the single-thread overhead of word-based Software Transactional Memory (STM) systems can have a significant negative impact on their scalability. Specifically, we find that the use of a tagless ownership table incurs false conflicts at a rate that 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 empirically observed trends are shown to result from the same statistical priniciples responsible for the (so called) "Birthday Paradox," as we demonstrate with an analytical model based on random population of an ownership table by concurrently executing transactions. 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 modestly-sized transactions (e.g., 20 cache blocks) and modest degrees of concurrency (e.g., 4 simultaneous transactions). The practical implications of these results are particularly acute for a hybrid TMs, where the small transactions are likely handled in hardware, leaving only the large ones for the STM. For reasonably-sized tables, a tagless organization will almost guarantee a maximum concurrency of 1 for these overflowed transactions. Using a tagged ownership table completely avoids these false conflict problems.