Graph parameter calculation running time optimization with parallel programing

OData support
Csernai Márton László
Department of Telecommunications and Media Informatics

Nowadays researching graph problems, creating and optimizing algorithms became a very important topic because physical and social networks can be represented by graphs. The parallel programming paradigm became very crucial because running the independent parts of a task in parallel threads reduces the runtime. The tested network’s size can exceed 1 million nodes, so the regular graph algorithms became slow and this is the reason of increased attention of parallel graph algorithms. During my thesis I will show how parallelization works on a processor with a freeware multi-platform thread management library and on graphic cards with the CUDA programming language. I also introduce the reader to the basics of CUDA. I will prepare Visual Studio 2010 to run CUDA and the chosen freeware multi-platform thread management library. I will plan out and create the following algorithms in sequential, parallel processor and parallel graphics card version: degree distribution, calculating clustering coefficient, breadth first search and maximum flow-minimum cut. I will test the algorithms to make sure they are working correctly. I will benchmark the runtime of the sequential and parallel versions of the algorithms. I will show that with the parallelization a 40% reduced runtime can be achieved when calculating the clustering coefficient and the maximum flow.


Please sign in to download the files of this thesis.