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.
| Identifer | oai:union.ndltd.org:pdx.edu/oai:pdxscholar.library.pdx.edu:open_access_etds-6020 |
| Date | 08 February 1995 |
| Creators | Ramamoorthy, Sujata V. |
| Publisher | PDXScholar |
| Source Sets | Portland State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations and Theses |
Page generated in 0.0022 seconds