Results of parallel implementations of the selection problem using sisal

Abstract

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 multiprocessor 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.