Title :
A Data Structure Centric Method and Execution Model for Partitioning Sequential Programs into Multiple Speculative Threads
Author :
Du, Yanning ; Zhao, Yinliang ; Han, Bo ; Li, Yuancheng
Author_Institution :
Dept. of Comput. Sci. & Technol., Xi´´an Jiaotong Univ., Xi´´an, China
Abstract :
Speculative Multithreading (SpMT) approaches have gained wide popularity because they can get more parallelism by allowing two pieces of potentially conflicting code to execute in parallel while ensuring the correctness of the results by recovering from conflicts. However, the dividing-along-the-control-flow-path method employed by the traditional SpMT approach is unsuitable for a number of programs in which operations on different data structures are interleaved in the control flow path. If we linearly divide the program into threads along the control flow path, the operations on the same data structure will be divided among the different threads that are doomed to be prone to conflict when being executed concurrently. To effectively parallelize these programs, we proposed a data structure centric approach, in which the objects of a program are organized into different groups and the operations on the objects within the same group are dispatched to the same thread to be executed, thereby reducing the likelihood of conflict on the same data structure.
Keywords :
data structures; multi-threading; SpMT approach; control flow path; data structure centric method; dividing-along-the-control-flow-path method; execution model; multiple speculative threads; sequential programs partitioning; speculative multithreading approaches; Arrays; Control systems; Message systems; Parallel processing; Runtime; Yarn; SpMT; execution model; partitioning;
Conference_Titel :
High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), 2012 IEEE 14th International Conference on
Conference_Location :
Liverpool
Print_ISBN :
978-1-4673-2164-8
DOI :
10.1109/HPCC.2012.81