The Research And Improvement Of The Conflict Detection Algorithm In Transactional Memory System

With the limitations of traditional single-core processors become more and more prominent, people look towards to multi-core architecture to develop Thread-Level-Parallelism (TLP). However, there are many shortcomings such as lock deadlock in the traditional parallel programming model based on mutually exclusive lock, making the development of parallel programming very inefficient. In this case, matters came into Transactional Memory system, which provids a simple and efficient programming environment for parallel program designing.Conflict Detection is one of the three major functions of Transactional Memory system, and the efficiency of the algorithm has an important impact on performance. Signature-based conflict detection algorithms can use a limited array to record unlimited address collection, so it is a promising approach in Transactional Memory system and its rate of false positive has much influence on the performance. This article focuses on how to reduce the rate of false positive of Signature.In this paper, we first analyze the presented signature-based conflict detection algorithms and improved the Hash-Bloom algorithm by omitting a redundant step, and then we propose VHB algorithm and GHB algorithm based on the improved Hash-Bloom algorithm. Experimental results by Monte Carlo Method are presented which show VHB algorithm offers lower false positive rate when the adderss number is low and GHB algorithm offers lower false positive rate in most cases. After that we optimize the GHB algorithm from the viewpoint of the hardware cost, proposing tow PGHB algorithms and using HP's CACTI to evaluate the silicon area.