Please use this identifier to cite or link to this item:
Title: Performance analysis of parallel graph algorithms on heterogeneous processors in OpenCL
Authors: Liu, Xiao
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2015
Abstract: 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.
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
1.09 MBAdobe PDFView/Open

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.