Study On Parallel Optimizations For Transactional Memory

A series of fundamental changes to the entire computer community have come withthe sea change from single-core to multi-core processor architecture. Among them, thefirst problem is how to ensure that the future performance of the software can continue togrow in the multi-core era, and this requires the programmer to explicitly usingthread-level-parallelism to write applications to exploit the parallelism in the program.However, this change will significantly increase the burden on the programmer, that maygreatly reduces programmer productivity, especially in the increasing scale of software,to improve programmer productivity of programming behave as a core technology of themodern software development. Transactional memory borrowed the transaction conceptfrom the database community to the parallel programming model. On the one hand, usingthe transaction interface can improve the abstraction level, especially for its nature ofcomposition, which can reduce the burden of the programmer manage concurrent threadscompeting for the shared data; on the other hand, assigning the transactional semantic tothe possibly racing blocks can optimistically run these codes, only when the transactionalconflict is detected in practice, transactional memory invokes the proper function to makethe appropriate treatment, which improves degree of parallelism of the program.Therefore, transactional memory is regarded as an effective tool for parallel programmingin the future multi-core platform, attract a lot of attention from industry and academia,thus becoming a hotspot nowadays.Through analysis and evaluate the existing hardware transactional memory system,we found that along with the number of concurrent executing transactions increased,especially under the coarse-grained and high-contention workloads, due to the constraintof the transaction conflict, leading to concurrent performance dramatically decline ininfluence of application’s concurrent performance. This paper concerntrates onoptimizing the parallelism of the current transactions in transactional memory system, wehave proposed three key techniques to exploit the concurrency of transactions in transactional memory system.Due to the extra data movements exist in the existing version management schemesof transactional memory systems. These data movements will not only extend the time oftransaction execution, but also affect the surrounding concurrent transactions to access tothe shared data, which may bring extra transactional conflicts among the concurrenttransactions. This case will worsen especially under the coarse-grained andhigh-contention transactional workloads, there may cause the system to appear moretransactional conflicts, blocking concurrent transaction execution, and bring more datamovements, thus leading to a vicious cycle to limit the concurrency and hurt theapplication’s performance. Aiming at this problem, we propose a novel single updateversion management scheme to reduce the extra data movements in the versionmanagement scheme, design a hardware-based fully-associative redirect table to managethe old and new versions during a transaction’s execution period, integrate it into theprocessor’s pipeline and analysis transactional workloads’ characterstics to design thetwo-level redirect table to exploit the parallelisms and reduce the hardware costs. Thismethod not only shortens the execution time of each transaction, but also alleviates thepossible interference with the surrounding transactions, thus efficiently improving thetransactional memory system’s concurrency.The composition capability of the transaction interface makes the programmersnaturally write the transactional applications composed by the coarse-grained,high-contention and long-length transactions. However, during the execution process ofeach coarse-grained and long-length transaction, because its execution time is too long,which will greatly increase the probability of transactional conflict occurrence, it is easyto obstruct the execution of concurrent transactions, thus significantly affectingsurrounding transactions’ concurrency. In order to solve this problem, we propose acoarse-grained and long-length transaction’s speculative in parallel execution technique,integrate the thread-level speculation technique into the hardware transactional memorysystem, modify the architecture of transactional memory to support checkingprogram’s.sequential ordering and apply this method to spawn speculative threads from the function call and loop structures to accelerate program’s execution. This method canextract the speculative code segments from a coarse-grained long-length transaction andassign multiple threads to execute them in parallel to accelerate the long transaction’sexecution. Moreover, this method can also reduce the probability of transactional conflictoccurrence with the surrounding transactions to improve the overall transactionalmemory system’s concurrency.Due to the various characterstics of the transaction’s length, read set and write set inthe concurrent transactions, the interaction of these concurrent transactions will lead tovarious behaviors, that makes using the history-based hardware transactional modeselector no longer to accurately choose the proper transactional execution mode. Thewrong choice will not only bring the extra overheads but also interfere the aroundtransactions to hurt the concurrency. To address this problem, we propose a paralleloptimization technique based on the transactions’ behaviors analysis, design asoftware-based module to manage transaction’s schedule, who will collect andstatistically analysis each transaction’s execution information, using these statistical datato mine the behavioral characterstics of the concurrent transactions, and take advantageof this information as the main factor to schedule the transactions’ execution and solvethe transactional conflicts, this auxiliary conflict management component can helpunderneath hardware exploit more concurrency of the concurent transactions. Thismethod can provide a higher predication accuracy to schedule the execution of concurrenttransactions than the hardware-based approach and exploit more performance benefits viamining the behavioral characterstics of the concurrent transactions.In this paper, the single update version management scheme and coarse-grained andlong-length transaction’s speculative in parallel execution technique try to reduce the datamovements and execute the coarse-grained and long-length transaction in parallel toexploit the parallelisms in the transactions. At the same time, the parallel optimizationtechnique based on the transactions’ behaviors analysis tries to collect the behavioralcharacterstics of the concurrent transactions and schedule the execution of the concurrenttransactions to exploit the parallelisms among the concurrent transactions. So, the parallel optimization technique based on the transactions’ behaviors analysis can combine withthe single update version management scheme and coarse-grained and long-lengthtransaction’s speculative in parallel execution technique to exploit both the parallelismsin the transactions and the parallelisms among the concurrent transactions, thusimproving the parallel performance of transactional memory systems.