Efficient Collective Communication Operations in
- 格式：pdf
- 大小：56.15 KB
- 文档页数：6
Efficient Collective Communication Operations inPVMeMassimo BernaschiIBM ECSECGiulio IannelloDipartimento di Informatica e SistemisticaUniversit`a di Napoli Federico II1IntroductionCommunication primitives for message-passing parallel computing may be clas-sified as either point-to-point,involving a single source and a single destination,or collective,involving more than two processes.Even if the collective communication is not strictly necessary for the development of parallel programs it usually plays an important role:simplifies the programming task,facilitates the implementation of efficient communication schemes,and promotes portability.For these and other reasons most of the existing communication libraries includes such primitives.In the case of PVM[9],starting on version3.3,routines are available for the reduce,gather and scatter operations which are typical examples of collective operations.Although an efficient implementation of the collective operations is very often crucial to obtain good performances of parallel applications,public domain PVM has taken a minimalist approach to the problem and the only implemented algorithm for all these operations uses the naive one levelflat spanning tree.This means that,for instance,in the reduce operation the root receives a distinct message from each ofthe other tasks.Specially when short messages are used,for which the startup time of the operation is the crucial factor,this algorithm is inefficient because it does not minimize the number of receive operations that the root task performs.Besides that the one levelflat tree has a linear complexity so it scales poorly on large numbers of tasks.It is pretty clear that more sophisticated algorithms are required to offer PVM collective communication primitives that are scalable and efficient.Luckily several recent studies deal with efficient implementation of basic collective communication operations and a number of results are presently available.Optimal and suboptimal algorithms have been proposed in the framework of the postal model[2] and the LogP model[8]for basic collective operations.All these models assume a fully connected network making algorithms highly portable.However,the proposed algorithms introduce several complications that prevented implementors from using them in currently available libraries.In this scenario,under the assumptions of the postal model,we have used a class of broadcast trees,called-trees,that closely approximate optimal broadcast trees,and significantly reduce that complexity of the implementation.The algorithms presented here are for the reduce and the broadcast operations but with simple modifications they can be used for the gather and scatter operations as well.The algorithms are efficient in space and in time and are uniform with respect to the number of processors. This makes them well suited for collective operations supporting processor groups of various sizes.2Optimal collective algorithmsThe LogP model[8]is an abstract model of a parallel machine which reflects the critical technology trends underlying parallel computers.In the model,processors work asynchronously and communicate by point-to-point messages travelling through a network.When dealing with“communication-only”problems the LogP model can be further simplified leading to the postal model[2].In this model each processor can send afixed-size message and,simultaneously,receive a message of the same size. Furthermore,a message sent out at time incurs a latency and will arrive at the receiving node at time.A distinctive characteristic of the postal model is the assumption that the commu-nication network can be modeled as a complete graph.This complete graph approach has several advantages:(a)it allows designing portable algorithms and(b)it matches the properties of multi-stage interconnection networks and of point-to point networks with virtual cut-through or wormhole routing.This fully-connected model has been widely used and has been adopted in the design of many communication libraries.Efficient algorithms have been proposed,for several collective operations,in the postal model.Algorithms for the broadcast operation using a spanning tree that turns out to be optimal are reported in[2].In[8],are reported optimal algorithms based on the same kind of spanning trees for the all-to-all broadcast,the all-to-all personalized communication,the reduce operation and the global combine operation.More general algorithms for the latter operation are reported also in[3]It is worth noting that all theses algorithms do not correspond directly to practical algorithms,since they require:(a)the knowledge of the latency,which could be difficult to determine,and(b)the construction on thefly of an optimal tree of size (which is of time)for determining which processors have to send messages to which other processors.However,in[5]an attempt is made to bridge the gap between the theoretical modeling and practical implementation.3Practical implementation for PVMThe algorithm proposed in[5]for the broadcast operation is very similar to the recursive doubling algorithm used on hypercubes.Given the number of processors and the latency,the algorithm,that broadcasts a message in an-node set from a source node using an optimal broadcast tree, works as follows.If1,terminates,otherwise it performs four steps:(i) partition S into two subsets and of sizes min1and ,respectively,and such that(Note that is the round-off function);(ii)select a leader;(iii)send the message from to;(iv) perform and concurrently and recursively.The coefficient must be chosen from the range051as a function of and possibly as a function of.In the cited paper,rules are furnished to construct a lookup table of limited size that gives the proper value of in the different cases.However,a further simplification can be introduced in the algorithm provided that we accept to use an approximation in place of the optimal spanning tree.In fact, a closer analysis of the quantitative results reported in[5]suggests the idea that depends mainly from and it is substantially indepentent of.Since in the same paper an effective method is given to determine as a function of the message length, becomes a constant,which makes the implementation of the algorithm straightforward.This simplified algorithm generates a tree whose structure is dependent on the value of.We refer to such a tree in the following with the term-tree.An-tree is wider and shallower than a binomial tree with the same number of nodes,and this difference grows as decreases.Note that when tends to zero an-tree degenerates in a one levelflat tree.Hence,tofind the most appropriate value of,we have to look for the-tree which gives the best approximation of the optimal spanning tree.This can be accomplished by simulating the broadcast operation using a binomial tree and an optimal tree,and then comparing the respective completion times(see[4]for more details).To verify the effectivenes of using a constant value for,we have simulated also a broadcast operation that uses an-tree of appropriate parameter,and compared its completion time with the optimal case.For all the meaningful values of and,the broadcast completion time corresponding to the-tree is within a few time units from the optimal completion time.This means that the-tree is very close to the optimal tree[4].Other collective operations can be implemented by exploiting-trees.In particular, we consider here the reduce operation for the PVM programming model.Reduce is in some respect the inverse problem of broadcast and therefore it can be given an optimal solution simply reversing the direction of messages in optimal broadcast.Unfortunately,the algorithm cannot be immediately used to implement a reduction operation because the latter requires an a priori knowledge of the role that each node plays in the collective operation.However,it is not difficult to recognize that each node can derive this information from its own rank and the number of processors, which are assumed to be available to all collective operations.For space reasons,we do not report here the details of the algorithm.It consists of three phases:(i)determination of the parent;(ii)determination of the children;(iii) receipt of messages from all children,local reduction,and transmission of the result to the parent.Thefirst two phases consist of partitioning the node set repeatedly and they are very similar to the recursive algorithm used to perform the broadcast.Further details can be found in[4]Finally,we wish to point out how the techniques just described can be exploitedalso in the implementation of the other collective primitives included in PVM.For lack of space we report here just a few considerations.The interested reader can refer to[4]for a more detailed discussion.For scatter and gather operations,when the data blocks to be distributed are sufficiently large,the optimal spanning tree is known to be a one levelflat tree. However,for short messages an-tree can give better ing an extended version of LogP for dealing with variable length messages,the optimal value of as a function of the machine parameters and the block length can be determined.For the barrier operation,several approaches are possible.The simpler one is to implement the barrier by performing an empty reduce followed by an empty broadcast. If this solution is selected,an-tree can be used to speedup both steps.An alternative approach,is to use“global”algorithms like those based on circulant graphs[1]or generalized Fibonacci numbers[3].4Experimental resultsIn this section we report some preliminary results produced by the algorithm based on the-trees,in particular for the reduce operation.The value of we selected is0.6which corresponds to the value predicted by using the methods described[4]. We show also the performance obtained for the same operation by using another non trivial algorithm like the binomial tree which can been seen as a special case of-tree with05.The hardware platform we have used to run the tests is an IBM SP2parallel system with up to128computing nodes connected by using both standard LAN(ethernet or token ring)and an high-speed interconnection called High Performance Switch(HPS). It is interesting to notice how the HPS makes,in practice,the performance of any point-to-point communication independent of the sender-receiver pair.This behavior is nicely consistent with assumptions underlying the postal and LogP models.The algorithms have been developed to be included in PVMe,an IBM product [7]which implements the PVM paradigm[9]and it is highly tuned for the9076/SP2 [6].To ease the porting to other PVM implementations we have used as building blocks the basic point-to-point communication primitives of PVM.Moreover all the necessary info(like the group size or the list of the identifiers of the tasks involved in the collective operation)are retrieved by using PVM primitives.The general PVMe buffering scheme has been exploited to avoid the usage of other temporary buffers which are generally required for the implementation of reduce-type operations.Since the value of can be changed by means of environmental variables the user has also the opportunityof tuning the algorithms for instance tofit them to messages of different size.In the tests the reduce operation aimed to computing the sum of double precision numbers.All the timings have been obtained by taking the minimum of a set of,at least,20independent runs.For each run the reduce operation has been performed10 times in a row and we have considered,among all the nodes,the greatest of the total elapsed times.To avoid potential“pipeline”effects the root of the reduce operation changed each time.The results are reported infigures1and2.It is readily apparent that the algorithm based on-trees shows a better performance compared to the binomial tree which is usually considered the best algorithm that can be implemented in a simple way for short messages.5ConclusionsIn this paper we have described an efficient implementation of algorithms for the collective communication primitives defined in PVM.The tests we have run involving up to128processors show that the proposed approach can improve notably the performance of collective operations on state of art parallel machines.Moreover, early experiments on workstation clusters using both Ethernet and high performance interconnects show that the approach is advantageous for a wide range of network structures and even for software running on top of TCP/IP.However,more work has still to be done to improve the proposed algorithms. Firstly,more tests are necessary to pick up the best values of for different message lengths.A second area to be investigated is the application of the same ideas to other collective operations.In particular,we plan to implement the three solutions for the barrier mentioned in section3tofind out which solution is best suited for an efficient implementation.Finally,we intend to perform more extensive experiments to gain a better estimate of the improvements achievable and for validating the models used in[4]to develop the proposed algorithms.References[1]V.Bala,et al.,“CCL:a portable and tunable collective communication library forscalable parallel computers”,Procs.of the8th Int.Conf.on Parallel Processing, IEEE,April1994.[2] A.Bar-Noy and S.Knipis,“Designing Broadcasting Algorithms in the PostalModel for Message-Passing Systems”,Procs.of the4th Annual ACM Symp.on Parallel Algorithms and Architectures,June1992,pp.11–22.[3] A.Bar-Noy J.Bruck,C.T.Ho,S.Knipis,and B.Schieber,“Computing GlobalCombine Operations in the Multi-Port Postal Model”,Procs.of the5th IEEE Symp.on Parallel and Distributed Processing,Dec.1-41993,pp.336–347. [4]M.Bernaschi and G.Iannello,“Quasi-Optimal Collective Communication Al-gorithms in LogP”,Tech.Rep.,DIS,March1995.[5]J.Bruck,l.de Coster,N.Dewulf,C.T.Ho,and R.LLauwereins,“On thedesign and Implementation of Broadcast and global Combine Operations Using the Postal Model”,Procs.of the6th IEEE Symp.on Parallel and Distributed Processing,1994,pp.594–602.[6]M.Bernaschi and G.Richelli,“PVMe:an enhanced implementation of PVMfor the IBM9076SP2”Proceedings of HPCN Europe1995,Bob Hertzberger and Giuseppe Serazzi editors,Springer,1995[7]IBM AIX PVMe User’s Guide and Subroutine Reference,SH23-0019-01[8]R.M.Karp,et al.,“Optimal Broadcast and Summation in the LogP Model”,Procs.of the5th Annual ACM Symp.on Parallel Algorithms and Architectures, June1993,pp.142–153.[9]V.S.Sunderam,G.A.Geist,J.Dongarra and R.Manchek,“The PVM concurrentcomputing system:evolution,experiences and trends”,Parallel Computing,vol.20,n.4,April1994.。
