A Study On Software Transactional Memory For Multicore Architectures

To meet the increasing requirement of computing power, it is no longer possible to improve the performance of uniprocessor systems by increasing the clock frequency of the processor. This leads to the introduction of multicore in industry, on which multiple processors are integrated on a single chip, sharing the same off-chip memory. In multicore systems, with the same clock frequency, the number of instructions executed per second may be multiplied by increasing number of processors on chip. This provides a new solution for the bottleneck problem of improving performance. Meanwhile, multicore has brought us a number of new challenges in parallel programming. A key challenge is to make better use of the computing resources on multicore systems for parallel processing.The concept of transaction comes from database, which has proved to be an effective means of concurrency control. It is introduced into parallel programming, which has formed the theory of transactional memory. Transaction in transactional memory is an atomic read/write operation sequence executed by a thread. The sequence of operations is either completely executed and committed or aborted and recovered back to the state before executing the sequence. This dissertation first provides a survey on existing transactional memory systems, especially systems based on Signature. Then three fundamental functions for software transactional memory systems are studied and improved by novel optimization schemes. Finally the optimized functions are integrated into a Signature-based software transactional memory system. The main research contributions in this dissertation are as follows.(1) A conflict detection algorithm called VHB is studied. Then a new Signature-based conflict detection algorithm named VHTB is presented, with dynamic transformation between lines in Signature, where when addresses are less used, True Bloom mapping information for hash function is stored in the unused memory space. The parallel implementation enables parallel search among lines in the block and thus reduces both latency and the rate of false positives. Using simulation, it is shown that the false positives rate and abort rate in VHTB are reduced significantly compared with VHB.(2) True Bloom and Hash Bloom are two common conflict detection algorithms for transactional memory, with different features. To combine the advantages of both algorithms, the Signature data structure used for conflict detection is divided into two equal-size regions one of which is mapped using True Bloom and the other is mapped using Hash Bloom. This gives rise to a new conflict detection algorithm (named Mix Bloom). Experiments results show that Mix Bloom has lower false positives rate and abort rate than algorithm Hash Bloom.(3) For data version management in software transactional memory, a hybrid data version management strategy is proposed, combining the advantages of existing eager and lazy strategies. The hybrid data version manager allows switching dynamically between the two according to the number of conflicts detected in order to use the data version management most suitable for the current state. Experiment results show that the hybrid data management outperforms the eager and lazy strategies as expected.(4) Based on the existing conflict detection algorithms, an integrated conflict resolution strategy called Synthesized is proposed, which takes the advantages of several conflict resolution strategies including random exponential backoff of Polite, priority of Karma, inheritance priority of Eruption and weight of Justice. Experiments have proved that this strategy has larger amount of transactions committed.(5) A conflict resolution strategy called Comprehensive is proposed. When a conflict occurs between two transactions, one of the transactions will be discarded according to factors including discard cost, retry times and start time. Experiments demonstrate that Comprehensive outperforms existing strategies.(6) Finally a transactional memory system with conflict detection algorithms based on Signature named RingSS (Ring Support Signature) is designed and implemented to study the proposed solutions presented in this dissertation.To summarize, this dissertation presents several novel solutions for conflict detection, data version management and conflict resolution implementing software transactional memory on multicore architectures. Theoretical analysis and extensive experiments have been conducted to demonstrate their effectiveness.