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

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 q i holds r i records, 1 i p. The problem is to redistribute the records so that each processor holds bn=pc 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 \Gamma bn=pc; bn=pc \Gamma mnr) parallel data transfer steps, where mxr = max(r i ) and mnr = min(r i ) 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 allo..