الفهرس 
introductionOnly 14 pages are availabe for public view
 |  | from | 107 |  |  |
| | | from | 107 | | |
Abstract
Sorting is a prohlem of fundamental interest 111 computing science. For n data items. sequential comparison-based sOl1ing I,as a time complexity of Q( n log n). \caving no
possibility for substantial improvements in sequential algorithms. However. significant improvements can be possible through parallelism. Many MIMD parallel s011ing algorithms have been proposed. Some of these algorithms exploit the strenb>ths of the particular machine
. to achieve high performance. In many cases. however. the ~x;sting algorithms can not achieve comparahle performance on other architectll1’es. Parallel S011ing hy Regular Sampling (PSRS)
i!l one of lhe proposed algP1ilillll~ lh:ll i~ sllil;lhk lin a di\l’lse range of 1\111\1D alchitcctll1’l•S. However. its main weakness is the sequelitial bottleneck of its second phase. where p! data elements are sequentially sorted by one of the processors (0 is the number of processors). This
grows worse as the number (If prncessors in<;reases.
This thesis proposes a parallel internal sorting algorithm which preseilt:; sequential bottleneck. By cho(ls;ng medians as samples. (lnly p elements are needed to be sequentially sorted in the second phase. Taking the medians as pivots and assuming that ’f elements fall in created partitions at random. a merging technique is proposed that attempts . to achieve load balancing het\\ een processors dependipg on the expected elements in each
partition.
The computation complt”;;IY and the comm\lnil’?tion complexity were studied for the
proposed algorithm ( and comp;1led t.J the PSRS algorithm) for n diverse range of 1\1lMD
architectures. Performancl’ was also annlyticnlly measured using standard performance metrics of parallel algorithms .. \ simulation s!ucly was carried out to validate analytical assumptions and compare the performance of the proposed algorithm and the PSRS
algorithm for the
centralized ~hared memory architecture under unifmm and normal
. di!;trihution of dnta clements: the etTec! nf inlroc!m;inp. extnt duplicate keys is studied in each case .
It was found that the propc.sed algorithm outperforms the PSRS algorithm for the global shared memory architectures. the mesh architectures, ~nd the hypercube architectures with store and forward routing mechanisms. For distributed memory architectures and hypercube architectures with cut through rnutin~. tlie proposed algorithm outp~rforms the PSRS when n = o(p3) .