Extracting task-level parallelism
Extracting task-level parallelism
复制标题
提取任务级并行性
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
C. Polychronopoulos
中科院分区：
文献类型：
--
作者：
M. Girkar;C. Polychronopoulos
在不同级别的程序粒度上自动检测任务级并行性(也称为函数并行性、DAG并行性、非结构化并行性或线程并行性)对于并行化和后端编译器正变得越来越重要。并行化编译器检测迭代级或更粗粒度的并行性，这适用于并行计算机；对于大多数现代微处理器，包括超标量和VLIW体系结构，在语句级或操作级检测并行性是必不可少的。本文研究了任务级并行性的检测、表达和优化问题，其中“任务”指的是任意粒度的程序语句。在顺序程序中优化功能并行性的数量(通过允许任意节点之间的同步)需要结合控制和数据依赖的图中的路径的优先概念。以前曾在不同的背景下定义过优先权；然而，该定义取决于并行执行和时间的概念。我们证明了静态确定优先权的问题是NP-完全的。确定优先关系在查找基本数据依赖项时很有用。我们证明了存在唯一的基本数据依赖的最小集合；找到这个最小集合是NP-难的，也是NP-容易的。我们还提出了一种寻找基本数据依赖集的启发式算法。对一个程序在完美基准下进行了静态分析，并给出了一些实验结果。
Automatic detection of task-level parallelism (also referred to as functional, DAG, unstructured, or thread parallelism) at various levels of program granularity is becoming increasingly important for parallelizing and back-end compilers. Parallelizing compilers detect iteration-level or coarser granularity parallelism which is suitable for parallel computers; detection of parallelism at the statement-or operation-level is essential for most modern microprocessors, including superscalar and VLIW architectures. In this article we study the problem of detecting, expressing, and optimizing task-level parallelism, where “task” refers to a program statement of arbitrary granularity. Optimizing the amount of functional parallelism (by allowing synchronization between arbitrary nodes) in sequential programs requires the notion of precedence in terms of paths in graphs which incorporate control and data dependences. Precedences have been defined before in a different context; however, the definition was dependent on the ideas of parallel execution and time. We show that the problem of determining precedences statically is NP-complete. Determining precedence relationships is useful in finding the essential data dependences. We show that there exists a unique minimum set of essential data dependences; finding this minimum set is NP-hard and NP-easy. We also propose a heuristic algorithm for finding the set of essential data dependences. Static analysis of a program in the Perfect Benchmarks was done, and we present some experimental results.