Uniform emulations of the shuffle-exchange network

Abstract

Parallel algorithms are normally designed for execution on networks of N processors, with N depending on the size of the problem to be solved. In practice there will be a varying problem size but a fixed network size. In [3] the notion of network emulation was proposed, to obtain a structure preserving simulation of large networks on smaller networks. We analyse the concept for the case of the shuffle-exchange network, a common interconnection network underlying many multiprocessor algorithms.