Prefix Scan and Minimum Spanning Tree with OpenCL

  1. author Sun, Yixin, Department of Computer Science, University of Virginia
  2. author Skadron, Kevin, Department of Computer Science, University of Virginia
Published
Published in: University of Virginia Dept. of Computer Science Tech Report
Publisher: University of Virginia, Department of Computer Science
Abstract

GPUs have been widely used to achieve wide data-parallelism to facilitate the execution of concurrent computations for performance and effciency. A lot of prior work have been done for CUDA, while OpenCL, as an open standard with the advantage of being able to run across multiple GPU platforms, still lacks development and effcient data primitives in its open standard libraries. This report discusses our work on constructing an effcient OpenCL implementation for parallel prefix scan and its improved performance over the scan primitive in the OpenCL standard library CLPP. The report also discusses our work on implementing the minimum spanning tree algorithm in OpenCL using our parallel segmented scan primitive and its improved performance over the original sequential execution.

Language
English