Experience with Multiprocessor Algorithms

This paper presents results of experiments with parallel algorithms. Several versions of four different programs, each representing a class of applications, were tested. All the experiments were performed on Cm*,l a 50-processor computer with a hierarchical structure. The results show that when the structure of an algorithm corresponds well to the structure of the computer, a close-to-linear speedup may be achieved. An attempt was made to analyze the reference patterns and interprocess cooperation and their influence on the performance of the algorithms. Several still-open questions are formulated in the paper and some further research directions are suggested.