| To achieve Exascale computational performance using next generation supercomputers, all aspects of computational models are evolving to support future applications that will execute billions of threads on millions of cores. Graph based applications are a special class of such applications that are common in Big Data type problems such as bio-informatics, social-networks, and cyber-security. A common characteristic of parallel graph applications is that computations using shared data are sparse in nature. In graph applications, two major synchronization policies are used to synchronize operations on shared data. The first one is coarse-grain synchronization which is relatively easy to program but not optimized since it serializes program execution. The second policy is fine-grain synchronization which is notoriously complex to program but provides better performance and scalability. On the other hand, Transactional Memory (TM) is a widely researched and novel synchronization scheme that is easy to program, scalable and non-blocking. TM based applications perform best when there are few conflicts among the transactions. Transactions are regions of codes containing shared data that can be executed concurrently. A Hybrid Transactional Memory (HyTM) scheme uses combinations of Software TM (STM) and Hardware TM (HTM) depending on the characteristics of the application. In this work, we first study the performance of several synchronization schemes used for parallel applications and a variety of transactional memory policies. Then, we propose several Adaptive Hybrid Transactional Memories (AdHyTM) that outperform not only existing state-of-the-art Hybird, Hardware, and Software Transactional Memory but also most of other existing synchronization schemes. Also, our Dynamically Adaptive HyTM (DyAdHyTM) dynamically adapts to application behavior to provide improved performance, particularly in parallel graph applications. For scalibilty, we tested our TM implementations up to 64 cores, 128 GB memory, and for a large graph with 268 millions vertices and 2.147 billion edges. Our DyAdHyTM implementation outperforms coarse-grin lock by upto 8.11X, STM by 2.65X and the next best policy, HTM by 2.15X times in execution time for the computation kernel of a standard benchmark (i.e. SSCA-2) on a 28 core, 64GB memory machine. |
