View in EDS

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

Saved in:
Bibliographic Details
Title: Application of extreme order statistics to the average-case analysis of parallel algorithms
Authors: Dickinson, Arthur F.
Committee Members: Guha, Ratan
Summary: 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.
URL: https://stars.library.ucf.edu/rtd/3822
Database: OpenDissertations
FullText Text:
  Availability: 0
Header DbId: ddu
DbLabel: OpenDissertations
An: ddu.oai.stars.library.ucf.edu.rtd.4821
AccessLevel: 6
PubType: Dissertation/ Thesis
PubTypeId: dissertation
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Application of extreme order statistics to the average-case analysis of parallel algorithms
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Dickinson%2C+Arthur+F%2E%22">Dickinson, Arthur F.</searchLink>
– Name: Author
  Label: Committee Members
  Group: Au
  Data: <searchLink fieldCode="CO" term="%22Guha%2C+Ratan%22">Guha, Ratan</searchLink>
– Name: Abstract
  Label: Summary
  Group: Ab
  Data: 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.
– Name: URL
  Label: URL
  Group: URL
  Data: <link linkTarget="URL" linkTerm="https://stars.library.ucf.edu/rtd/3822" linkWindow="_blank">https://stars.library.ucf.edu/rtd/3822</link>
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=ddu&AN=ddu.oai.stars.library.ucf.edu.rtd.4821
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    Subjects:
      – SubjectFull: Order statistics estimation
        Type: general
      – SubjectFull: Lattice path model
        Type: general
      – SubjectFull: Median-of-three quicksort
        Type: general
      – SubjectFull: Multinomial sampling distribution
        Type: general
      – SubjectFull: Parallel hashing with chaining and linear probing
        Type: general
      – SubjectFull: Computer Sciences
        Type: general
      – SubjectFull: Physical Sciences and Mathematics
        Type: general
      – SubjectFull: Arts and Sciences -- Dissertations; Academic; Dissertations; Academic -- Arts and Sciences; Parallel algorithms; Parallel processing (Electronic computers)--Mathematical models; Algorithms--Analysis; Parallel processing (Electronic computers)--Evaluation; Mathematical statistics--Research
        Type: general
    Titles:
      – TitleFull: Application of extreme order statistics to the average-case analysis of parallel algorithms
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Dickinson, Arthur F.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Type: published
              Y: 1991
ResultId 1