Time Stamp Algorithms for Runtime Parallelization of DOACROSS Loops with Dynamic Dependences
Time Stamp Algorithms for Runtime Parallelization of DOACROSS Loops with Dynamic Dependences
复制标题
具有动态依赖性的 DOACROSS 循环运行时并行化的时间戳算法
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
V. Chaudhary
中科院分区：
文献类型：
--
作者：
Chengzhong Xu;V. Chaudhary
本文提出了一种时间戳记算法，用于具有间接访问模式的一般DOACROSS循环的运行时并行化。该算法遵循检查员/执行程序方案，并以细粒度的内存参考级别利用并行性。它具有并行检查器，并通过在同一内存元素的连续读取中利用并行性来改进同一通用性的先前算法。考虑了算法的两个变体：一个允许部分并发读取（PCR），而另一个允许完全并发读取（FCR）。分析其时间复杂性在运行时并行化的迭代工作负载方面得出了必要的条件。高斯消除循环的实验结果，以及12向SMP服务器上的一组综合循环，表明，时间戳记算法优于迭代级别级别的平行技术，在大多数测试用例中，并增强了对循环的速度执行的加速，有次迭代工作负载。 PCR算法表现最好，因为它在最大化并行性和最大程度地降低了分析开销之间做出了更好的权衡。对于具有光或未知迭代载荷的环路，首选替代投机运行时并行化技术。
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.