Parallel Program Execution Model On Data Communication Optimization

Parallel computational model is one of the most important contents in parallel com-puting. Along with the development of high performance computing, the complexity of hardware/software structure in parallel computing has been increasing for decades. The hardware is getting more and more complex, many technologies have been intro-duced to parallel computing, such as multi-core/many-core processors, heterogeneous platforms and various of high-speed networks. At the same time, the software of paral-lel computing is getting more abstract. This leads to the fact that it's difficult to predict and analyze the execution behaviors of parallel programs. The conventional unified parallel computational model has been unable to meet the rapid development of par-allel computing. Layered parallel computational model has been proposed to handle this difficulty, by considering the model into three levels:algorithm design, program implementation and program execution.Parallel program execution model is an essential part in layered parallel compu-tational model. The data communication process is important in parallel program ex-ecution model, because it's related to many other contents in parallel computing, such as the topologies of parallel system, the communication topologies of application, the performance of network, the synchronization and load balance of computing nodes. Based on the study of several parallel applications, this dissertation aims to build a par-allel program execution model on date communication optimization. The main idea is dividing the data communication process into three sub-processes:data preparation pro-cess, communication preparation process and date transmission process, each of which has heavy impact on the efficiency of date communication. These three processes have tight connections between each other, but also have their own independence. We did extensive research on these processes by analyzing three different instances of paral-lel application, from different angle to reveal the optimization methods on data com-munication. Specifically, our major research contribution and main innovation can be summarized as follows:(1) Parallel program execution model on data communication optimization Based on the study of details of data communication in MPI implementation, We sum-marized several factors affecting the efficiency of data communication in parallel programs, divided the data communication process into three subprocesses:data preparation, communication preparation and data transmission, analyzed each pro-cess' contents and characteristic, proposed parallel program execution model on data communication optimization. We also give some discussions about the prop-erties of the model, in the hope of predicting parallel programs' runtime behaviors and helping to optimize the data communication process.(2) Studied optimization in data preparation process, applied execution model to three dimensional fast Fourier transform Data preparation process greatly influ-ences the efficiency of data communication. We use three dimensional fast Fourier transform as an example to study the optimization in data preparation process. In order to reduce the calculation time and increase speedup, we introduced a new partitioning method for computing three dimensional fast Fourier transform in par-allel, rearranging the computing order of x-, y-, z-direction, as well as redesigning communication pattern among nodes and data redistribution. Load balancing and scalability were also considered in our new parallel algorithm.(3) Studied optimization in communication preparation process, applied execu-tion model to image compositing stage in parallel rendering Communication preparation process plays a connecting role in the three processes of data communi-cation. Taking image compositing stage as an example, we studied the optimization methods in communication preparation process. We proposed pipeline method to overlap the rendering time of different frames to achieve high fps in final display. We analyzed the theoretical performance of our methods and take intensive experi-ments. The results show that the pipelining methods are able to achieve interactive frame rates and scale well with both the size of nodes and screen resolution.(4) Studied optimization in data transmission process, applied execution model to dynamic process mapping method Data transmission process is the most com-plex and unpredictable process in data communication. Based on the idea of choos-ing fast link in data transmission process, we proposed dynamic process mapping method to optimize collective communication in MPI. The main idea of dynamic process mapping is changing processes'rank at runtime to change the communica-tion topology of collective operation, so as to optimize the application's communi-cation cost. We presented two strategies to calculate optimal mapping array in order to align the situations we would face in runtime environments. Our work is based on MPICH2, and the experiment results show that dynamic process mapping method behaved better than original implementation in our simulation environments.