Optimizing Algorithms and Data Structures in Multi-Core Environments

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

Due to the growing application of multicore processors these days, the parallelization of algorithms is coming into the spotlight more frequently. The performance of programs running on these architectures can be mainly improved by parallel excecution but there remain significant amounts of unused resources in this area.

In this paper I discuss the topic of sorting, focussing primarily on the problem of parallelization. I will begin by summarzing the most commonly used sorting algortihms. Then I discuss which approaches, regarding two one threaded but greatly parallelizable algorithms, achieve good results and which do not achieve good results. The two algorithms I have chosen are Mergesort and Qiucksort. For the first one I am seeking methods that try to divide the problem as symmetrically as possible to achieve good parallel behaviour. For the second one I adopted a different approach, rather aiming at the working processes (called threads) adapting well to even ill-proportioned problems. To achieve the latter I use a parallel library called the Task Parallel Library which makes thread management for the developer much easier.

Along with the above mentioned algorithms, I am also presenting my own algorithm which uses the results of other (not exclusively sorting) algorithms and which integrates existing sorting algorithms. I compare and contrast the created algorithms with other known algoritms (implemented by other people), and with the built in parallel sorts of the Parallel Patterns Library. The running time, acceleration and scalability are compared based on the different kinds of inputs (integers and character based data).

Regarding character based input I mention the unique properties of Unicode encodings and the great options they offer.

Implementation and measurements were done using C++/CLI and native C++ environment thus I also discuss various aspects of parallel programming in them.

In summary I learnt that although parallel libraries make it easier to create parallel programs, for good results it is also necessary for developers to know the available developement tools and to have a good understanding of algorithm theory.

Downloads

Please sign in to download the files of this thesis.