Title :
Data partitioning for networked parallel processing
Author :
Crandall, Phyllis E. ; Quinn, Michael J.
Author_Institution :
Dept. of Comput. Sci., Oregon State Univ., Corvallis, OR, USA
Abstract :
The workstation model of parallel processing presents specific challenges caused by the latency of the communications network and the workload imbalance that arises from the heterogeneity of the nodes. Data partitioning is critically important for parallel processing in this environment. We mathematically characterize the communication costs for four data decomposition schemes: scatter, contiguous point, contiguous row, and block. These methods are analyzed in terms of problem size, number of processors, network speed, and communication pattern. Bounds are established for the performance of these decomposition schemes that can be used to make better-informed data partitioning decisions
Keywords :
communication complexity; distributed memory systems; local area networks; parallel processing; performance evaluation; resource allocation; communication costs; communication pattern; communications network; data partitioning; latency; network speed; networked parallel processing; problem size; workload imbalance; workstation model; Communication networks; Computer architecture; Computer science; Costs; Delay; Ethernet networks; Parallel processing; Pattern analysis; Scattering; Workstations;
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
DOI :
10.1109/SPDP.1993.395508
