Izvorni znanstveni članak
A Computational Study of Distributed Processing Environments with Parallel Multiperiod Assignment Method: A Dedicated Machine versus a Workstation Cluster
Babita Gupta
; California State University, Monterey Bay, Monterey, CA, USA
Jay E. Aronson
; Department of Management, Terry College of Business, The University of Georgia, Athens, GA, USA
Sažetak
We provide a computational study of two of the more commonly distributed processing environments using a robust parallel multiperiod assignment branch and bound im£1ementation running in the Parallel Virtual Machine (PYM) environment. We describe the multiperiod assignment problem (an np-hard, combinatorial, network-based integer programming problem), an efficient parallel algorithm for its sol ution, and implementation details. The algorithm is designed for a large-grain computing environment and uses a Master /Slave (or monitor) configuratio n. Minimal communication among the processes is used. We then describe the PYM software system and the computational platforms being analyzed. We provide a computational comparison of runs on an IBM SP-2 and a cluster of IBM RISC 6000 POWERStations. The results indicate that losses in efficiency occur when employing parallelism in a cluster, but some gains in efficiency can be obtained by a single processor with multiple processes running in a time-shared mode. However, in general, the cluster provides poor parallel performance when compared to the dedicated IBM SP-2 for which linear and superlinear speedups can be routinely obtained. Tbe results may be generalized to any branch and bound method that utilizes a similar tree search strategy.
Ključne riječi
Network Programming; Parallel Algorithms; Assignment Problem; Distributed Computing
Hrčak ID:
150264
URI
Datum izdavanja:
30.6.1997.
Posjeta: 696 *