Hybrid algorithms for complete exchange in 2D meshes

作     者：Sundar, NS Jayasimha, DN Panda, DK Sadayappan, P 

作者机构：Hewlett Packard Corp Cupertino CA 95014 USA Intel Corp Santa Clara CA 95052 USA Ohio State Univ Dept Comp & Informat Sci Columbus OH 43210 USA 

出 版 物：《IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS》 (IEEE Trans Parallel Distrib Syst)

年 卷 期：2001年第12卷第12期

页      面：1201-1218页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：collective communication complete exchange combining direct exchange hybrid algorithms message contention barrier synchronization mesh topology wormhole routing 

摘      要：Parallel algorithms for several common problems: such as sorting and the FFT involve a personalized exchange of data among all the processors. Past approaches to doing complete exchange have taken one of two broad approaches: direct exchange or the indirect message-combining approaches. While combining approaches reduce the number of message startups, direct exchange minimizes the volume of data transmitted. This paper presents a family of hybrid algorithms for wormhole-routed 2D meshes that can effectively utilize the complementary strengths of these two approaches to complete exchange. The performance of hybrid algorithms using Cyclic Exchange [26] and Scott s Direct Exchange [23] are studied using analytical models, simulation, and implementation on a Cray T3D system. The results show that hybrids achieve lower completion times than either pure algorithm for a range of mesh sizes, data block sizes, and message startup costs. It is also demonstrated that barriers may be used to enhance performance by reducing message contention, whether or not the target system provides hardware support for barrier synchronization. The analytical models are shown useful in selecting the optimum hybrid for any given combination of system parameters (mesh size, message startup time, flit transfer time, and barrier cost) and the problem parameter (data block: size).