Breadcrumb

 
 

Fast parallel algorithms for sorting and median finding

Title:

Fast parallel algorithms for sorting and median finding

Dachraoui, Taoufik (1996) Fast parallel algorithms for sorting and median finding. Masters thesis, Concordia University.

[img]
Preview
PDF
2631Kb

Abstract

Many sorting algorithms that perform well on uniformly distributed data suffer significant performance degradation on non-random data. Unfortunately many real-world applications require sorting on data that is not uniformly distributed. In this thesis, we propose a new strategy, A-ranksort, for sorting on parallel machines which has a stable behavior on input distributions of different entropies. Our sorting algorithm essentially consists of deterministically computing approximate ranks for the input keys, and using these to route to destinations that are guaranteed to be close to the final destination, and finally using a few steps of odd-even transposition sort to complete the sorting. We implemented A-ranksort, B-flashsort (40), Radix sort (20), and Bitonic sort (6) on a 2048 processor Maspar MP-1. Thearling (73) proposes a test suite of inputs with which to evaluate the performance of sorting algorithms. We tested all the algorithms on a very similar test suite. Using similar ideas, we also designed a new deterministic selection algorithm for integers that is simple and fast. (Abstract shortened by UMI.)

Divisions:Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Dachraoui, Taoufik
Pagination:x, 65 leaves ; 29 cm.
Institution:Concordia University
Degree Name:Theses (M.Comp.Sc.)
Program:Computer Science and Software Engineering
Date:1996
Thesis Supervisor(s):Narayanan, Lata
ID Code:169
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:10
Last Modified:08 Dec 2010 10:13
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Document Downloads

More statistics for this item...

Concordia University - Footer