Skip to content

GPU Parallel Graph Coloring, Shortness Centrality, BFS & Nearest Neighbor Search - CS 406 Homework

License

Notifications You must be signed in to change notification settings

orancanoren/GPU-CPU-Parallel-Graph-Algorithms

Repository files navigation

CS406 Parallel Computing

Homework & Project of CS406/531 Parallel Computing

This repo contains the homework and our group project for the Parallel Computation course. A detailed report for each homework is provided within their respective folders. A brief overview of the contents of this repo is provided below.

Homework 1 - Parallel BFS

Task: Implement BFS parallelized on CPU with OpenMP
Solution: Implementation uses the idea of direction-optimized BFS. After each frontier expansion, the program decides which approach (top-down or bottom-up) would perform faster for the next round and proceeds until BFS is finished.

Homework 2 - Distance-1 Graph Coloring

Task: Impelement an algorithm, providing accurate distance-1 coloring of the supplied graph that runs on CPU in parallel with OpenMP.
Solution: Moving with the ideas introduced by Deveci et al., the implementation I provide performs three step iterations until each vertex is colored. Each iteration has three steps:
  1. Assign Colors
  2. Detect Conflicts
  3. Forbid Colors

Homework 3 - Shortness Centrality

Task: Implement a GPU parallelized algorithm to compute shortness centrality of a provided graph.
Solution: The implementation assigns each CUDA core a vertex. Each thread is responsible for performing BFS having its assigned vertex as source node. However, memory requirement of my implementation is very high; therefore, the implementation works only for small graphs.

Homework 4 - Nearest Neighbor Search

Task: Provided a set of training and testing points on a 16-dimensional space, find the nearest neighbor among training points of each testing point.
Solution: The implementation assigns each CUDA core a testing point. Afterwards, each core iterates over the training points to find the training point with smallest euclidean distance. CUDA streams were used to overlap computation with communication.

Project - Distance-2 Graph Coloring

Task: Impelement CPU, GPU and Heterogeneous algorithms solving the distance-2 graph coloring problem.
Solution: We have extended the implementation of distance-1 graph coloring to distance-2 with improvements. OpenMP algorithm uses thread-private forbidden arrays and CUDA implementation uses shared block-cache to store bit vectors as forbidden arrays.

About

GPU Parallel Graph Coloring, Shortness Centrality, BFS & Nearest Neighbor Search - CS 406 Homework

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published