Efficient data parallel implementations of highly irregular problems
Yu Charlie Hu · 1997
This dissertation presents optimization techniques for efficient data parallel formulation /implementation of highly irregular problems, and applies the techniques to O(N) hierarchical N--body methods for large--scale N--body simulations. It demonstrates that highly irregular scientific and engineering problems such as nonadaptive and adaptive O(N) hierarchical N--body methods can be efficiently implemented in high--level data parallel languages such as High Performance Fortran (HPF) on scalable parallel architectures. It also presents an empirical study of the accuracy--cost tradeoffs of O(N) hierarchical N--body methods. This dissertation first develops optimization techniques for efficient data parallel implementation of irregular problems, focusing on minimizing the data movement through careful management of the data distribution and the data references, both between the memories of different nodes, and within the memory hierarchy of each node. For hierarchical N--body methods, ...