Optimal loop parallelization for maximizing iteration-level parallelism
Optimal loop parallelization for maximizing iteration-level parallelism
复制标题
用于最大化迭代级并行性的最佳循环并行化
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Jingling Xue
中科院分区：
文献类型：
--
作者：
Duo Liu;Z. Shao;M. Wang;M. Guo;Jingling Xue
本文解决了从一个循环中提取可在芯片多处理器上并行执行的最大迭代次数这一开放性问题。我们的算法通过在两个阶段迁移依赖循环上抑制并行性的依赖权重来实现最优解。首先，我们用重定时对依赖迁移进行建模，并将这种经典的循环并行化表述为一个图优化问题，即找到其节点的重定时值，以使图中的最小非零边权重最大化。我们分三个阶段介绍我们的算法，每个阶段都在前一个阶段的基础上逐步构建。其次，根据在第一阶段找到的循环的重定时图生成循环的最优代码。我们通过使用先前工作中经常使用的一组基准测试，与一些具有代表性的非最优算法进行比较，展示了我们的最优算法的有效性。
This paper solves the open problem of extracting the maximal number of iterations from a loop that can be executed in parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on dependence cycles in two phases. First, we model dependence migration with retiming and formulate this classic loop parallelization into a graph optimization problem, i.e., one of finding retiming values for its nodes so that the minimum non-zero edge weight in the graph is maximized. We present our algorithm in three stages with each being built incrementally on the preceding one. Second, the optimal code for a loop is generated from the retimed graph of the loop found in the first phase. We demonstrate the effectiveness of our optimal algorithm by comparing with a number of representative non-optimal algorithms using a set of benchmarks frequently used in prior work.