On the Transportation and Distribution of Data Structures in Parallel and Distributed Systems

Abstract

We present algorithms for the transportation of data in parallel and distributed systems that would enable programmers to transport or distribute a data structure by issuing a function call. Such a functionality is needed if programming distributed memory systems is to become commonplace. The distribution problem is defined as follows. We assume that n records of a data structure are scattered among p processors where processor qi holds ri records, 1 ≤ i ≤ p. The problem is to redistribute the records so that each processor holds [n/p] records. We solve the problem in the minimum number of parallel data-permutation operations possible, for the given initial record distribution. This means that we use max(mxr - [n/p], [n/p] - mnr) parallel data transfer steps, where mxr = max(ri) and mnr = min(ri) for 1 ≤ i ≤ p. Having solved the distribution problem, it then remains to transport the data structure from the memory of one processor to another. In the case of dynamically allocated data structures, we solve the problem of renaming pointers by creating an intermediate name space. We also present a transportation algorithm that attempts to hide the cost of making a local copy for the data structure which, is necessary since the data structure could be scattered in the memory of the sender.