Global data and control in multicomputers: Operating system primitives and experimentation with a parallel branch‐and‐bound algorithm

Abstract

Abstract The static distribution of work among tasks is not possible in many parallel applications. Therefore, it is essential to implement convenient and efficient abstractions for ‘work sharing’ on multicomputers. This paper compares the utility of two operating system facilities for the implementation of such ‘work sharing’: (1) a system for the migration of processes from heavily to less loaded processors and (2) a more general OS construct for the implementation of arbitrary distributed objects. Both were implemented as extensions to the Intel iPSC/1 operating system on a 32‐node hypercube. Their experimental evaluation is based on a parallel implementation of a branch‐and‐bound algorithm. Two sets of results are attained. First, the necessity of the constructs for dynamic work sharing is demonstrated for applications with dynamic data domains, such as parallel branch‐and‐bound algorithms. This is followed by measurements that demonstrate the acceptable cost of process migration for a specific parallel branch‐and‐bound algorithm. These measurements are then compared with results attained with the construct for the implementation of distributed objects. Second, when using branch‐and‐bound to solve the Travelling Salesperson Problem (TSP), evaluation of the resulting parallel TSP program shows that some analytical and simulation results attained in past, published work may not hold.