On the Transportation and Distribution of Data Structures in Parallel and Distributed Systems
View/ Open
Metadata
Show full item recordCitation
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.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#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:26506440
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)