Application of extreme order statistics to the average-case analysis of parallel algorithms

Abstract

This thesis presents a study of the application of discrete methods to the analysis of parallel algorithms for distributed memory multicomputers. This analysis requires the determination of the maximum time required by concurrently executing sequential procedures. Two merging algorithms for a linear array are analyzed for worst-case time complexity. An average-case analysis of one of these is then done using a lattice path model of list arrangement. A new parallel sorting algorithm is presented and analyzed. The algorithm consists of a local sorting phase followed by merging of sorted lists. The merging phase uses an estimate of the order statistics for the entire list to determine how keys are to be distributed among the processors. The sorting phase is analyzed using empirical data. The study shows that median-of- three quicksort is the best choice for this phase. A bound on the average-case complexity is obtained using properties of the sampling distribution for order statistic estimation and the multinomial distribution. A local 1nerging step which occurs at the finish of the algorithm is analyzed for average-case behavior and bounds are determined based on the mean, variance and maximum of the execution time distribution. The time for single operations, batch searches and sequences of searches is analyzed for a parallel hashing scheme based on hashing with chaining. The time to perform queries is reduced over sequential hashing by exploiting the larger amount of memory expected to be available on parallel computers. Part of this improvement is lost to communication overhead. If the parallel hash table is sufficiently larger than the sequential table, improvement is still possible. Batch queries provide only moderate improvement over the sequential case. The parallel hash algorithm has smaller queueing delay when handling sequences of queries. The analysis of closed parallel hashing with linear probing leads to expressions for single searches and concurrent searches for two keys.

Notes

This item is only available in print in the UCF Libraries. If this is your thesis or dissertation, you can help us make it available online for use by researchers around the world by STARS for more information.

Graduation Date

1991

Semester

Fall

Advisor

Guha, Ratan

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

101 p.

Language

English

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Location

Orlando (Main) Campus

Identifier

DP0028129

Subjects

Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences

Accessibility Status

Searchable Content

This document is currently not available here.

Share

COinS