M.S. in Computer Engineering

Sorting is perhaps one of the most widely studied problems of computing. Numerous asymptotically optimal sequential algorithms have been discovered. Asymptotically optimal algorithms have been presented for varying parallel models as well. Parallel sorting algorithms have already been proposed for a variety of MIMD (multiple instruction, multiple data streams) architectures. In this thesis, we present a new parallel sorting algorithm that is suitable for diverse range of MIMD architectures. We successfully adopt the multiway-merge sorting algorithm [1] that is originally designed for product networks, to MIMD architectures. It has good load balancing properties, modest communication needs and well performance. Our algorithm requires only two AAPC (all-to-all personalized communication) and two one-to-one communications independent from the input size. The workload is distributed amongst the processors evenly yielding a perfect load balancing. In addition, the algorithm requires only size of 2N/P local memory for each processor in the worst case, where N is the number of items to be sorted and P is the number of processors. We have implemented the algorithm on PC cluster architecture and in all experiments it achieves good results. The proposed algorithm is not necessarily the best parallel sorting algorithm, but it will achieve good performance on a wide spectrum of MIMD architectures.

DATE: January 22, 2002, Tuesday @ 11:00

PLACE: EA-409