First Advisor

Leonard Shapiro

Date of Publication

2-8-1995

Document Type

Thesis

Degree Name

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

Department

Computer Science

Language

English

Subjects

Sorting (Electronic computers), Multiprocessors

DOI

10.15760/etd.6824

Physical Description

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

Abstract

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.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Comments

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 pdxscholar@pdx.edu and include clear identification of the work, preferably with URL

Persistent Identifier

https://archives.pdx.edu/ds/psu/28656

Download

Share

COinS