Analysing Sorting Algoritms in Multi-core Processing Environment

OData support
Supervisor:
Dr. Juhász Sándor
Department of Automation and Applied Informatics

With the advent of multi-core processors and their widespread adoption even in consumer electronics, it is key that we, as software developers, understand the implications of writing software on this architecture. In my thesis I explore the different aspects of multi-core processors and how they can either decrease or be utilized to improve the performance of algorithms. My examined problem of choice is sorting of arrays containing integers which is a common CPU-intensive problem that has many sequential solutions. Researching these and other common parallel sorting methods, I develop and implement a multi-threaded sorting algorithm, which is optimized for the multi-core environment. The implementation exploits the benefits of multiple cores by partitioning the input as symmetrically as possible and distributing the work so that the threads are idle for the least possible time. The benchmarks are run against the sequential quicksort algorithm found in the .NET framework, a parallel quicksort, and a parallel mergesort. The results prove that my Parallel Partition Sort provides a fourfold increase in performance compared to the sequential quicksort baseline and a 150-200% speed up compared to the parallel sorts.

Downloads

Please sign in to download the files of this thesis.