Handling graph-based models in OpenCL

OData support
Supervisor:
Dr. Mezei Gergely
Department of Automation and Applied Informatics

Nowadays there are more and more area in informatics, where graphs are used to represent challenges and relations between entities. Graph theory is an important research area in mathematics and there are lots of graph theory related problems which has algorithm to solve in finite number of steps. However there are, which are proven to be NP-complete problems. One of these NP-complete problems is finding a balanced partitioning of a graph. Even the relaxed version of the problem is NP-hard.

During my thesis I will present the graph partitioning problem and a possible solution which can solve the relaxed partitioning problem using highly performant graphics cards available nowadays.

In the first part of my thesis I present the graph partitioning problem and the computation potential of current generation GPUs. As next, I present the related work of my research applied in the field of graph partitioning. During this chapter, I focus on those publications which inspired my solution for the problem.

In the rest of the thesis, I present the planning process and the implementation of my partitioner. During these chapters, I present every algorithm and modifications I have made to the original algorithms in my research in detail.

At last, I compare the main characteristics of my partitioner to a broadly used CPU based partitioner and evaluate the results. Finally, I share my experiences and thoughts about my result and I elaborate my suggestions for further development opportunities as the closure of the paper.

Downloads

Please sign in to download the files of this thesis.