Index Translation Schemes for Adaptive Computations on Distributed Memory Multicomputers

Abstract

Current research in parallel programming is focused on closing the gap between globally indexed algorithms and the separate address spaces of processors on distributed memory multicomputers. A set of index translation schemes have been implemented as a part of CHAOS runtime support library, so that the library functions can be used for implementing a global indez space across a collection of separate local index spaces. These schemes include also software-cached translation schemes aimed at adaptive irregular problems as teen as a distributed translation table technique for statically irregular problems. To evaluate and demonstrate the efficiency of the softwDare-cached translation schemes, experiments have been performed with an adaptively irregular loop kernel and a full-fledped 3D DSMC code from NASA Langley on the Intel Paragon and Cray T3D. This paper also discusses and analyzes the operational conditions under which each scheme can produce optimal performance. (Also cross-referenced as UMIACS-TR-95-28)