Chinese Journal of Computers   Full Text
Title	An Affine Partition Algorithm Based on Representative Element
Authors	ZHANG Wei-Hua WANG Peng ZANG Bin-Yu ZHU Chuan-Qi
Address	(Parallel Processing Institute, Fudan University, Shanghai 201203)
Year	2008
Issue	No.3(400—410)
Abstract &   Background	Abstract Partition is an optimization technique that distributes computations and data onto the different processors of parallel systems to get the maximizing parallelism and minimizing communication. The effect of partition algorithm can directly affect the performance of parallel systems. But there are many obstacles to effective partition in practical programs, such as imperfect loop nests and different array access scope. Previous partition algorithms can only finish the partition of sequences of perfect loop nests or cannot solve data partition consistent problem for different array access scope. This paper presents an affine partition algorithm based on representative element. When constructing the constraint relation for partition, it only remains the array references, which have contributes to partition constraint relation indeed and remove the trivial partition conflicts through discarding redundant array references to same array. This paper also presents a consistent partition algorithm to solve the data partition consistent problem. The algorithms can not only solve more practical partition problems, but also effectively reduce data reorganization communication in data partition. This technique has been implemented in AFT2004 parallel compiling system and can get better results for some practical programs. keywords affine partition; data partition; representative element; imperfect loop; parallel compiling background This work is supported by Specialized Research Fund for the Doctoral Program of Chinese Higher Education under grant No.20050246020. Partition is an optimization technique that distributes computations and data onto different processors of parallel systems to get the maximal usage of parallel systems’computation resources to speedup the programs’ processing time. The effect of partition algorithm directly affects the performance of parallel systems. The partition problems have been always the key problem to high performance computing on distributed memory multi-computers which is the mainstream platform of large-scale scientific calculation. The major goal of partition is to get the maximizing parallelism and minimizing communication. As a research hotspot, there are a lot of researches focusing on partition problems. Some of them deal with perfect loop nest partition, in which it treats all the statements within a loop nest as a single unit. In such a condition, they can only solve the partition for the program where there are only perfect loop nests. Some of them are partition algorithms for statements, in which each statement is the basic partition unit. However, they can not solve the data partition consistent problem when array access stride in different statements are unequal. Some other research is presented to solve read-only data replication problems, alignment problems and so on. At present, MGID type algorithms are widely used to solve different problems in different areas. There are imperfect loop nests and different array access strides in such programs. When these patterns appear in programs, partition especially data partition becomes extremely complex. Such characteristics put great obstacles to effective partition since multiple data access strides would lead to partition conflicts based on those prior partition algorithms. This paper presents an affine partition algorithm based on representative elements. When constructing the constraint relation for partition, it only remains the array references, which have contributes to partition constraint relation indeed and remove the trivial partition conflicts through discarding redundant array references to the same array. This paper also present a consistent partition algorithm to solve the data partition consistent problem. The new algorithms can not only solve more practical partition problems, but also effectively reduce data reorganization communication in data partition. This technique has been implemented in AFT2004 parallel compiling system and can get better results for some practical programs.