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 and Scott's Direct Exchange 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).

There is considerable interest in converting existing production sequential/vector codes into scalable portable parallel message-passing programs. However the task is very tedious and error prone. In this paper we describe a systematic incremental methodology that greatly eases parallelization of stencil codes, by operating in a single address space while addressing data partitioning issues and then transitioning to multiple address spaces to handle communication and synchronization issues. The approach has been successfully used in manually parallelizing a production CFD code. Since the steps in the methodology are formalized as algorithms, the approach is amenable to automation.

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 either the combining or the direct exchange approaches. While combining reduces 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 [6] and Scott's Direct Exchange [5] are studied using analytical models as well as simulation. The results show that hybrids achieve lower completion times than either pure algorithm for a large range of mesh sizes, data block sizes and message startup costs. The analytical models may be used to select the optimum hybrid for any given combination of system parameters (mesh size, startup t...