Experiments with Parallel Algorithms for Combinatorial Problems

G.A.P. Kindervater

Centre for Mathematics and Computer Science, Amsterdam

H.W.J.M. Trienekens

Erasmus University, Rotterdam

ABSTRACT

In the last decade many models for parallel computation have been proposed and
many parallel algorithms have been developed. However, few of these models have been realized and most of these algorithms are supposed to run on idealized, unrealistic parallel machines.

The parallel machines constructed so far all use a simple model of parallel computation.
Therefore, not every existing parallel machine is equally well suited for each type of algorithm. The adaptation of a certain algorithm to a specific parallel architecture may severely increase the complexity of the algorithm or severely obscure its essence.

Little is known about the performance of some standard combinatorial algorithms
on existing parallel machines. In this paper we present computational results concerning the solution of knapsack, shortest paths and change-making problems by branch and bound, dynamic programming, and divide and conquer algorithms on the ICL-DAP (an SIMD computer), the Manchester dataflow machine and the CDC-CYBER-205 (a pipeline computer).

1980 Mathematics Subject Classification: 90C27, 68Q10, 68R05.

Key Words & Phrases: parallel computer, SIMD, MIMD, pipelining, dataflow, branch and bound, dynamic programming, divide and conquer, knapsack, shortest paths, change-making.

Note: This paper appeared in European Journal of Operational Research, Vol. 33, pp 65- 81, 1988.

1. Introduction

In the last decade computer scientists have proposed many parallel computers, based on various models of computation and architectures. However, so far only a few of these parallel computers have been built, due to today's technical limitations. All existing parallel computers use the easier models of computation and the easier architectures. Therefore these machines are less powerful than the theoretical models.

In the mean time operations researchers have developed many parallel algorithms for combinatorial problems. Nearly all these algorithms are based on models of parallel computation which are too complicated to be used in today's parallel computers. As a result, few of these algorithms have actually been implemented today simply by lack of the parallel computers needed.
hhhhhhhhhhhhhhhhhh
Report 8550/A
Erasmus University Rotterdam, Econometric Institute
P.O. Box 1738, 3000 DR Rotterdam, The Netherlands