Problem-heap: A Paradigm for Multiprocessor Algorithms

Abstract

The problem-heap paradigm has evolved through four years of experiments with the Multi-Maren multiprocessor. Problem-heap algorithms have been formulated for a number of different tasks such as numerical problems, sorting, searching and optimization. Although these tasks are very different, the analyses of the running times of all the problem-heap algorithms are very similar. The problem-heap paradigm is illustrated by algorithms which have been implemented and analyzed using the Multi-Maren multiprocessor.