Title :
Global reduction in wormhole k-ary n-cube networks with multidestination exchange worms
Author :
Panda, Dhabaleswar K.
Author_Institution :
Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA
Abstract :
This paper presents a new approach to implement global reduction operations in wormhole k-ary n-cubes. The novelty lies in using multidestination message passing mechanism instead of single destination (unicast) messages. Using pairwise exchange worms along each dimension, it is shown that complete global reduction and barrier synchronization operations, as defined by the Message Passing Interface (MPI) standard, can be implemented with n communication start-ups as compared to 2n [log 2 k] start-ups required with unicast-based message passing. Analytical results for different values of communication startup time, system size, and data size are presented and compared with the unicast-based scheme. The analysis indicates that the proposed framework can be effectively used in wormhole-routed systems to achieve fast global reduction without a separate control network
Keywords :
hypercube networks; message passing; synchronisation; barrier synchronization operations; communication startup time; complete global reduction; data size; fast global reduction; global reduction; message passing interface standard; multidestination exchange worms; multidestination message passing mechanism; pairwise exchange worms; system size; unicast-based message passing; wormhole k-ary n-cube networks; Broadcasting; Communication switching; Computer worms; Delay; Hardware; Information science; Intelligent networks; Message passing; Rail to rail inputs; Unicast;
Conference_Titel :
Parallel Processing Symposium, 1995. Proceedings., 9th International
Conference_Location :
Santa Barbara, CA
Print_ISBN :
0-8186-7074-6
DOI :
10.1109/IPPS.1995.395879