Performance of multiprocessors and parallel algorithms: Quicksort, a case study

Abstract

Performance of parallel algorithms on multiprocessors has been traditionally analyzed by looking at either the algorithm or the architecture of the multiprocessor system. However, it is important to study the combined effect of both these factors in order to evaluate and predict performance. A different methodology based on approximate trace-driven simulation is adopted in this thesis to study the performance of a class of non-numerical algorithms. Performance of parallel quick-sort and parallel quick-merge sort is investigated in order to demonstrate the methodology as well as develop an understanding of the limitations imposed by a cache-based single bus environment on achievable speedup. A wide range of issues including the effect of cache parameters, coherency protocol, scheduling mechanisms and technology effects are discussed in the context of performance of the two versions of parallel quick-sort.