Parallel implementations of the selection problem: A case study

The selection problem has been studied extensively on sequential machines. A linear average time solution and a linear worst-case solution are conside red as the standard by most researchers. Theoretical work is also available on parallel models, but it has not been widely implemented on parallel mac hines. This paper presents an in-depth analysis of the implementation of th e standard algorithms, on a number of multiprocessors and supercomputers fr om the entire spectrum of Flynn's classification, using both an imperative (C based languages with vendor specific parallel extensions) and a function al (SISAL) language. Very interesting results were obtained for all of the experiments performed, leading us to the conclusion that the selection prob lem has very efficient parallel implementations. Hand-tuned C programs with parallel extensions provided good efficiency but were time-consuming in te rms of development. On the other hand, the SISAL code is fully portable and the same program a;as used on all the machines. The performances of SISAL implementations were comparable to the ones of the hand-tuned C implementat ions. On all the tests, the routines were able to sustain good speed-up and reasonable efficiency, even with ii large number of processors, In two cas es (one machine using SISAL, and one using a C-based language); we were abl e to obtain an efficiency higher than 80% with a configuration close or equ al to the maximum number of processors.