Improving the efficiency of conflict detection and contention management in hardware transactional memory systems

2012-11-12Chip Multiprocessors (CMPs) are becoming the mainstream due to the physical power limits of process technology. In this parallel era, software applications no longer automatically benefit from improvements in processor performance as they did in past decades. The benefit of CMPs can only be realized by environments that enable efficient creation of parallel applications. ❧ Transactional Memory (TM) is a promising paradigm that aims to simplify parallel programming by providing a programmer-friendly alternative to traditional lock-based synchronization. With TM, programmers just focus on the correctness of their parallel programs by composing applications in units of a transaction, a block of codes that execute atomically and in isolation. The underlying TM system is responsible for enforcing atomicity and extracting performance. By decoupling correctness and performance, TM can make parallel programming much easier and enable better programmer productivity than lock primitives. ❧ TM systems attempt to harvest high performance by executing multiple transactions in parallel. In TM systems, a conflict occurs when a memory block is accessed concurrently by two or more transactions and at least one of them is a write access. Detecting conflicts is critical to the correctness as well as performance of TM systems. In this dissertation, we propose two conflict detection mechanisms, adaptive-grain signatures and unified signatures to improve the efficiency of conflict detection. ❧ Observing that some false positives can be helpful to performance by triggering the early abortion of a transaction which would encounter a true conflict later anyway, we propose an adaptive grain signature to improve performance by dynamically changing the range of address keys based on the history. With the use of adaptive grain signatures, we can increase the number of performance-friendly false positives as well as decrease the number of performance-destructive false positives. ❧ Instead of using separate read- and write-signatures, as is often done in TM systems, we implement a single signature, a unified signature, to track all read- and write-accesses. By merging read- and write-signatures, a unified signature can effectively enlarge the signature coverage without additional overhead. Within the constraints of a given hardware budget, a TM system with a unified signature outperforms a baseline system with the same-sized traditional signatures by reducing the number of falsely detected conflicts. Even though the unified signature scheme incurs read-read dependencies, we show that these false dependencies do not negate the benefit of unified signatures and can effectively be filtered out. A TM system with a 2K-bit unified signature with helper signature scheme achieves speedups of 15% over baseline TM with 33% less area and 49% less power. ❧ How to resolve or prevent the conflicts, or contention management is another building block of TM systems that significantly impacts TM performance. Traditionally, critical sections or transactions have been treated to execute in any order with no weights as long as the atomicity can be maintained. We have observed that some transactions are more important than others with respect to the performance based on the implemented algorithm. Based on this observation, we propose a mileage technique, a software/hardware cooperative approach with new instructions and a new functional unit to exploit performance-criticality among transactions. We propose Mileage-based contention management and can achieve average speedups of 15% over baseline contention management