Parallelism for free: efficient and optimal bitvector analyses for parallel programs
Parallelism for free: efficient and optimal bitvector analyses for parallel programs
复制标题
免费并行：并行程序的高效且最佳的位向量分析
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
J. Vollmer
中科院分区：
文献类型：
--
作者：
J. Knoop;Bernhard Steffen;J. Vollmer
我们考虑具有共享内存和交织语义的并行程序，对于这些程序，我们展示了如何为单向位向量问题构造与纯顺序程序一样有效且易于实现的最优分析算法。虽然复杂性的结果是相当明显的，但我们的最优性结果是一个新的Kam/Ullman式重合定理的结果。因此，使用我们的方法，用于顺序程序计算活跃度、可用性、非常繁忙、达到定义、定义使用链的标准算法，或者用于执行代码移动、赋值移动、部分死码消除或强度缩减的分析，可以直接地转移到并行设置，几乎不需要任何代价。
We consider parallel programs with shared memory and interleaving semantics, for which we show how to construct for unidirectional bitvector problems optimal analysis algorithms that are as efficient as their purely sequential counterparts and that can easily be implemented. Whereas the complexity result is rather obvious, our optimality result is a consequence of a new Kam/Ullman-style Coincidence Theorem. Thus using our method, the standard algorithms for sequential programs computing liveness, availability, very busyness, reaching definitions, definition-use chains, or the analyses for performing code motion, assignment motion, partial dead-code elimination or strength reduction, can straightforward be transferred to the parallel setting at almost no cost.