GPU Acceleration of Graph Algorithms

V této bakalářské práci se budu zabývat akcelerací algoritmu BFS (Breadth-first search) na grafické kartě. Jedná se algoritmus určený k průchodu grafem do šířky. Vysvětlím základní techniky paralelizace rozdělené podle Flynnovy klasifikace. Dále se budu zabývat stávajícími metodami paralelizace BFS na GPU. Následně provedu strukturované experimenty všech přístupů na stejném datasetu, porovnám a zhodnotím výsledky. Pro někoho nového je velice těžké se zorientovat v té to oblasti, z důvodu rozsáhlosti, chtěl jsem vytvořit práci která provede programátora začínajícího s paralelizací na GPU a umožní mu tak snazší vhled do této problematiky. Dále jsem se zaměřil na strukturované testování jednotlivých přístupů z různých prací a zhodnotil je z důvodu přehledu výkonosti přístupů na jednom místě. Čtenář tedy může vidět, který z nich je nejvhodnější pro jeho potřebu. Srozumitelné vysvětlení teorie týkající se technik a problémů paralelizace, popis hardwarového a softwarového konceptu NVDIA Cuda. Představení možností reprezentace grafů v paměti a vysvětlení proč se používá reprezentace grafu za pomocí listu sousednosti. Popis jednotlivých přístupů a jejich testování, na základě výsledků zhodnocení efektivity přístupů.In this bachelor thesis, I will deal with the acceleration of the Breadth-first search (BFS) algorithm on a graphics card. This is an algorithm designed to traverse the graph in breadth. I will explain the basic parallelization techniques divided according to Flynn’s classification. I will also discuss the existing methods of parallelizing BFS on GPU. I will then perform structured experiments of all approaches on the same dataset, compare and evaluate the results. It is very difficult for someone new to the field to navigate through it, due to its vastness, I wanted to create a work that will guide a programmer new to parallelization on GPUs and give them an easier insight into the subject. Furthermore, I focused on structured testing of different approaches from different works and evaluated them for the sake of reviewing the performance of the approaches in one place. Thus, the reader can see which one is most suitable for his/her need. A clear explanation of the theory behind parallelization techniques and problems, and a description of the hardware and software concepts of NVDIA Cuda. An introduction to the possibilities of representing graphs in memory and an explanation of why graph representation using a neighborhood list is used. Description of the different approaches and their testing, based on the results of the evaluation of the effectiveness of the approaches.