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

DSpace/Manakin Repository

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

Citable link to this page

 

 
Title: On the Transportation and Distribution of Data Structures in Parallel and Distributed Systems
Author: Fahmy, Amr F.; Wagner, Robert A.

Note: Order does not necessarily reflect citation order of authors.

Citation: Fahmy, Amr F. and Robert A. Wagner. 1995. On the Transportation and Distribution of Data Structures in Parallel and Distributed Systems. Harvard Computer Science Group Technical Report TR-27-95.
Full Text & Related Files:
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.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:26506440
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters