First Advisor

Leonard Shapiro

Date of Publication


Document Type


Degree Name

Master of Science (M.S.) in Computer Science


Computer Science


Sorting (Electronic computers), Multiprocessors



Physical Description

1 online resource (2, vii, 73 p.)


A method to parallelize external sorts on a shared memory multiprocessing system is presented in this thesis. The main goal of the thesis is to develop a sorting package that is scale able and efficient. No prior knowledge of the nature, source or size of the data is assumed for this work. A dynamic load-balancing architecture is used with no static allocation of tasks to processes. The package consists of an interface and a kernel. The interface provides the sort with the following - the sort input, output and temporary work spaces as abstract data types (ADTs), memory available, number of processes available, compare routine to compare records, etc. Only the interface needs to be changed to suit different environments. The kernel implements the parallel sort algorithm. The traditional sort merge technique is used for the external sort as opposed to a distributive sorting technique. Memory-sized runs are first generated and later merged. Parallel binary merges is the technique used for both the run generation and the merge phase. A forecasting table is used to read ahead in the merge phase.


If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to and include clear identification of the work, preferably with URL

Persistent Identifier