Results of Parallel Implementations of the Selection Problem Using Sisal

This paper presents an in depth analysis on the parallel implementation of four of the standard selection algorithms using a functional language on a number of multiprocessors and supercomputers. Three of the algorithms: Randomize Search, Binary Search and Divide & Conquer Search are based on the partition paradigm. The fourth one is a modified version of the Batcher sort. All routines were able to sustain good speed-up and high efficiency, even with a large number of processors. Efficiency higher than 86% was obtained with a configuration close to the maximum number of processors. 1 Introduction In the late 19 th century, Lewis Carroll proposed in "Lawn tennis tournament" an algorithm to find both the best and the second best player among all the participants of a tennis tournament in optimal time. This is the first appearance of a selection algorithm in the literature. Given a set X = x 1 : : : x n , there is a permutation oe which will sort the set, i.e: x oe(1) : : : x oe(n) ..