Title :
Time stamp algorithms for runtime parallelization of DOACROSS loops with dynamic dependences
Author :
Xu, Cheng-Zhong ; Chaudhary, Vipin
Author_Institution :
Dept. of Electr. & Comput. Eng., Wayne State Univ., Detroit, MI, USA
fDate :
5/1/2001 12:00:00 AM
Abstract :
This paper presents a time stamp algorithm for runtime parallelization of general DOACROSS loops that have indirect access patterns. The algorithm follows the INSPECTOR/EXECUTOR scheme and exploits parallelism at a fine-grained memory reference level. It features a parallel inspector and improves upon previous algorithms of the same generality by exploiting parallelism among consecutive reads of the same memory element. Two variants of the algorithm are considered: One allows partially concurrent reads (PCR) and the other allows fully concurrent reads (FCR). Analyses of their time complexities derive a necessary condition with respect to the iteration workload for runtime parallelization. Experimental results for a Gaussian elimination loop, as well as an extensive set of synthetic loops on a 12-way SMP server, show that the time stamp algorithms outperform iteration-level parallelization techniques in most test cases and gain speedups over sequential execution for loops that have heavy iteration workloads. The PCR algorithm performs best because it makes a better trade-off between maximizing the parallelism and minimizing the analysis overhead. For loops with light or unknown iteration loads, an alternative speculative runtime parallelization technique is preferred
Keywords :
computational complexity; parallelising compilers; DOACROSS loops; Gaussian elimination loop; INSPECTOR/EXECUTOR scheme; dynamic dependence; fine-grained memory reference; fully concurrent reads; inspector-executor; iteration workloads; parallelism; parallelizing compiler; runtime parallelization; runtime support; time stamp algorithm; Algorithm design and analysis; Computational fluid dynamics; Computational modeling; Computer Society; Fluid dynamics; Parallel processing; Performance analysis; Runtime; Sequential analysis; Sparse matrices;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on