Exploiting Architectural Factors in Sorting Algorithms

Rajeev Raman

(King's College, London)

We describe some preliminary steps we have taken towards a systematic (re-)evaluation of the practical performance of sorting algorithms for integers and floating-point numbers. This (re-)evaluation is necessitated by the growing importance of architectural factors as a determinant of the real-life run-times of algorithms. We consider two such architectural factors:

* The availability of word-level parallelism (WLP)

WLP refers to the ability of a CPU with word size w to process w-bit data in a SIMD manner in unit time, either indirectly through a standard repertoire of instructions, or directly by means of instructions such as those provided by the Intel MMX processor.

* Cache effects

We describe how to improve upon the performance of a recently-published algorithm for sorting random floating-point numbers.
Tuesday 3rd November 1998, 15:00
Seminar Room 322
Department of Computer Science