A library of static and dynamic communication algorithms for parallel computation

Communication efficiency is one of the keys to the broad success of paralle l computation, as one can see by looking at the successes of parallel compu tation, which are currently limited to applications that have small communi cation requirements, or applications that use a small number of processors. In order to use fine grain parallel computation for a broader range of app lications, efficient algorithms to execute the underlying interprocessor co mmunications have to be developed. In this paper we survey several generic static and dynamic communication problems that are important for parallel c omputation, and present some general methodologies for addressing these pro blems. Our objective is to obtain a collection of communication algorithms to execute certain prototype communication tasks that arise often in applic ations. These algorithms can be called as communication primitives by the p rogrammer or the compiler of a multiprocessor computer, in the same way tha t subroutines implementing standard functions are called from a library of functions in a conventional computer. We discuss both algorithms to execute static (deterministic) primitive communication tasks, as well as schemes t hat are appropriate for dynamic (stochastic) environments. Our emphasis is on algorithms that apply to many similar problems and can be used in variou s network topologies.