A general data dependence test for dynamic, pointer-based data structures
A general data dependence test for dynamic, pointer-based data structures
复制标题
DOI：
10.1145/178243.178262
复制
发表时间：
1994-06
期刊：
影响因子：
--
通讯作者：
J. Hummel;L. Hendren;A. Nicolau
中科院分区：
文献类型：
--
作者：
J. Hummel;L. Hendren;A. Nicolau
优化编译器需要准确的依赖性测试，以实现众多，性能增强的转换。但是，数据依赖性测试是一个困难的问题，尤其是在指针的情况下。尽管现有方法可以很好地适用于指定记忆位置的指示器（即其他变量），但对于指向未命名的记忆位置的情况，它们过于保守。后者发生在基于动态的，基于指针的数据结构的背景下，这些应用程序在从系统软件到计算几何以及N体和电路模拟的各种应用中。在本文中，我们提出了一种新技术，用于在存在基于动态指针的数据结构的情况下执行更准确的数据依赖性测试。我们将通过打破虚假依赖性来证明其有效性，即现有方法无法实现，并提供结果表明消除这些依赖性的结果可以使真实应用的显着并行化。
Optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. However, data dependence testing is a difficult problem, particularly in the presence of pointers. Though existing approaches work well for pointers to named memory locations (i.e. other variables), they are overly conservative in the case of pointers to unnamed memory locations. The latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to N-body and circuit simulations. In this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. We will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.