Parallel Processing System Loop Partitioning And Data Distribution Technology Research

With the development of parallel processing technology, more and more attention is paid to the parallel software development. In order to make the programs to run on the parallel machines efficiently, the importance of compiling can't be overestimated. Being one of the key part of the parallelizing compiler, the loop and data partitioning is of critical importance to improve the efficiency of the programs in distributed memory system. The automatic loop and data partitioning shall focus on maximizing the parallelism, minimizing the communication and balancing the workload on the processors. Although there has been a lot of work studying on these problems, few of these have been solved successfully. In this thesis, research has been made in developing automatic loop and data partitioning, which take into account load balance, data movement and the communication based on the underlying architecture of the distributed memory SIMD machine—VE16. Some of our achievements are used in the design and implementation of a parallizing C language compiler targeted on the VE16 machine. The contribution of this thesis is the following:(1) A system model is presented to characterize the VE16 machine. The data movement functions and the communication routines are analyzed to provide a good basis for studying automatic loop and data partitioning .(2) A simple but accurate data movement model is built to determine the number of data movement between the global memory and the local memory for a given loop partitioning.(3) Based on the above model, a loop partitioning algorithm is presented to derive an optimal tiling of the iteration space for minimizing the number of data movement and optimize the synchronization between data movement and computation.(4) A communication cost model is built to estimate the communication under a given loop and data partitioning. It can recognize the regular pattern communication implied in the program.(5) A data and iteration graph is introduced to model affine communication. The data and iteration graph not only formulate the mapping from data and computation to the processors, but also reflects the relations between the data and computation mapping.(6) A heuristic method based on the data and iteration graph is devised to derive an optimal loop and data partitioning for reusing the data across multiple loop nests and optimizing the communication.(7) These ideas are adopted in the design and implementation of a parallelizing compiler targeted on the VE16 machine. The experimental results demonstrate that the optimal loop and data partitioning greatly reduce the cost of data movement and communication and improve the performance of many programs.