Design of parallel mergesort and quicksort algorithms.
Item
-
Title
-
Design of parallel mergesort and quicksort algorithms.
-
Identifier
-
AAI9029990
-
identifier
-
9029990
-
Creator
-
Xiong, Renbing.
-
Contributor
-
Adviser: Theodore Brown
-
Date
-
1990
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
This thesis is concerned with improving parallel processing versions of the mergesort and quicksort algorithms on shared memory MIMD or SIMD machine.;To date the Valiant (1975) /Kruskal (1983) merging algorithm is the fastest on a shared memory MIMD machine. We present algorithms to do median splitting, k-splitting, and splitting using a vector of k values. This latter algorithm merges (and sorts) faster than Valiant/Kruskal's when the ratio of the number of values to be sorted to the number of processors is greater than (lg p){dollar}\sp{lcub}1/3.4{rcub}{dollar}. It is also superior in that the partitioned sections it creates for parallel merging are all the same size. We also present an EREW splitting algorithm to determine p equal sized pairs which is faster than Akl's (1987) by a factor of lgp.;A shared memory MIMD version of a quicksort algorithm was suggested by Sedgwick (1978), implemented by Deminet (1982) and Quinn (1988), and analyzed by Evans and Dunbar (1982), and by Evans and Yousif (1985). The algorithm is optimal if p {dollar}\leq{dollar} lg N. Mattel and Gusfield (1989) gives a version of parallel quicksort algorithm in a CRCW random-write PRAM model. Heidelberger, Norton, Robinson, and Watson gives a parallel quicksort algorithm on a CRCW PRAM machine with Fetch-and-Add operation. Reischuk (1985) gives a probabilistic parallel algorithm which sorts N elements by N processors in O(lg N) time with a high probability. We give a quicksort algorithm on EREW MIMD machine which sorts N elements using p processors in O(N lg N/p) time, that is optimal when p {dollar}\leq{dollar} N/(lg N).
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
