The Research And Implementation Of Optimization To Collective Communication In Cluster Computing Environment

As the developing of high-speed network and high performance microprocessor technologies,cluster computing is extended from LAN to campus network and even to WAN. It has been becoming a highly attractive and challenging platform for distributed parallel computing. How to improve the performance of communication,including point-to-point communication and collective communication,is the key technique to make cluster computing applicable. This paper focuses on how to improve the performance of collective communication without modifing the underlying hardware. The performance of collective communication is mainly affected by the performance of computers nodes,the performance and topology of the network,and collective communication routes,etc. Hence optimizing the communication routes is an important means to improve the performance of collective communication,especially for the designer of message passing library. In cluster computing environment,due to the heterogeneity of cluster,large performance gap may exist among computers nodes and among interconnected networks. Besides,network topology is usually irregular. All these make it difficult to optimize the collective communication routes. If the heterogeneity of cluster and irregularity of topology couldn't be considered sufficiently in routes optimization,the result would be poor and in some case,it would cause reverse effect,which can cut down the performance of collective communication. This issue exists in many message-passing libraries. To this issue,we present MGO (Multi-Granularity Optimization) resolution,which includes LobP communication model,HLC (Hierachical Label Cluster) topology model,MGO algorithm,CCSim,and MPICH-MGO. In this paper,from both the theory and practice perspective,we describe systematically the work we have done.Communication model,in which the basic communication procedure is described,is the base of routes optimization for collective communication. By analysis of some exist communication model,we point out their limits and present a new communication model called LobP model.Topology model,in which network topology is described,is an important utility for efficient routes optimization. In this paper,we present HLC topology model,which embodies the character of physical topology and collective communication.Making use of LobP model and HLC topology model,we present MGO (Multi-Granularity Optimization) algorithm. MGO can generate communication routes for broadcast,scatter,gather and all-gather. In MGO,the factors such as the performance of computers nodes,the performance and topology of interconnected network are taken care of sufficiently. As a result,these algorithms are highly suitable for cluster computing environment.We have implemented MPICH-MGO,a collective communication library utilized MGO. MPICH-MGO is based on MPICH,and some modification and extension are made to the original collective communication layer of MPICH. So that the global cluster information can be gathered,and then such global information is used to optimize the collectivecommunication routes,which is used by the collective communication layer to direct the forwarding of related messages.We also implement a simulator CCSim for collective communication in cluster environment. The simulator can generate various cluster configurations. Then it uses these configurations to optimize communication routes,by which it simulates the execution of collective communication. So we can use the simulator to compare the effect of various optimization algorithms on different cluster configuration. CCSim has been an important analyzing toolkit for us to study the optimization to the collective communication in cluster environment.The simulation results show that the effect of MGO algorithm is great. Comparing MGO algorithms with other related algorithms,such as BT,FEF,FCEF and LA,there exist some extent of performance improvement in broadcast,scatter,gather and all-gather operation. Further,the performance improvement ratio is increased as more computers ad...