Abstract
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.
| Original language | American English |
|---|---|
| Journal | Journal of Computing and Information Technology |
| Volume | 5 |
| State | Published - 1997 |
Keywords
- Assignment Problem
- Distributed Computing
- Network Programming
- Parallel Algorithms
Disciplines
- Data Science