Performance analysis of parallel graph algorithms on heterogeneous processors in OpenCL

Despite the fact that GPU was originally intended to be as a co-processor specializing in graphics rendering, it has recently evolved into a powerful many-core co-processor for general-purpose computation. However, a major obstacle for wide adoption of GPGPU programming is that different GPU vendors have their own programming languages and platforms. To address that issue, Open Computing Language (OpenCL) provides unified programming interface for various parallel computing platforms. OpenCL also enables cross-platform comparison of different hardware resources possible. Inspired by Medusa programming framework on CUDA, we set out to explore the actual speedup between heterogeneous processors for parallel programs and to examine the impact of different data storage layouts. We experimented with OpenCL PageRank algorithm and Breadth-first Search algorithm on Intel and NVIDIA graphic cards, using varied combinations of data storage layouts like Column-major Adjacency Array (CAA), Adjacency Array (AA), Structure of Array (SOA) and Array of Structure (AOS). Our experiment results showed that for graph algorithms GPUs substantially outperform CPUs in executing parallel tasks, and CAA is a more preferred memory layout than AA, especially when GPU is less sophisticated and computation is vertex-oriented. Likewise, SOA is a more preferred memory layout than AOS, especially when GPU is less sophisticated.Bachelor of Engineering (Computer Engineering