A Computational Study of Distributed Processing Environments with Parallel Multiperiod Assignment Method: A Dedicated Machine versus a Workstation Cluster

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.