Compilation-time data decomposition optimization for data parallel programs
Lionel Ming-shuan Ni, Hong Li Xu · 1994
Data decomposition is critical to the performance of data parallel programs on scalable parallel computers. A data decomposition model can be viewed as a two-level mapping of array elements to abstract processors. Data alignment determines what array elements are aligned relative to one another, and data distribution resolves how the group of aligned arrays is distributed onto the processors. Depending on the alignment relationship as within dimension or across dimension, alignment can be classified into base alignment and offset alignment. The purpose of base alignment is to reduce the amount of unstructured communication. In this research, we use the data reference graph model to describe the various reference patterns associated with each array and to resolve the conflict of the compatible alignment requirements. An efficient spanning tree algorithm addresses the fundamental issues in base alignment. Base alignment is further studied with the consideration of the optimal expression evaluation and dataflow analysis. Efficient base alignment algorithms are proposed to reduce the redundant communication and optimize the RHS expression evaluation. These contributions make this research unique from related research. The purpose of offset alignment is to reduce the amount of data shift movement. This thesis successfully models the cost of data shift movement using the piecewise linear function. This cost model solves the accuracy problem in measuring the quantity of data shift movement, an unresolved problem left by other work in this area. Based on this cost model, the optimal post-alignment algorithm is first proposed to exceed the limitation of the owner-computes rule and minimize the amount of data shift movement after offset alignment is determined. The data reference graph model is used to address the problem of offset alignment and develop efficient spanning tree algorithms. The RHS expression evaluation and dataflow optimizations are incorporated with the proposed offset alignment algorithms. The purpose of data distribution is to reduce the impact of data shift movement and increase processor workload balance. Segment distribution is proposed to resolve the conflict between reducing data shift movement and increasing processor workload balance with regard to a particular dimension of the template array. An optimal processor allocation algorithm is introduced to minimize the overall cost of data shift communication across multiple dimensions of the template array. The segment distribution and optimal processor allocation proposed in this thesis provide the best data distribution support for most data parallel programs.