NDLI: GPU accelerate parallel Odd-Even merge sort: An OpenCL method

Content Provider	IEEE Xplore Digital Library
Author	Keliang Zhang Jiajia Li Gang Chen Baifeng Wu
Copyright Year	2011
Description	Author affiliation: School of Computer Science, Fudan University, Shanghai 201203, China (Keliang Zhang; Jiajia Li; Gang Chen; Baifeng Wu)
Abstract	Odd-Even merge sort is a basic problem in computer supported cooperative work in design area. However, it is not effective because of the high complexity $O(nlg^{2}n)$ in CPU platform. In this paper, we present a novel implementation based on the OpenCL programming model on recent GPU (Graphic Processing Unit). Our implementation was based on Knuth's algorithm and do some change. Due to limitations of OpenCL, we utilize a flag variable to make it avoid the direct backward control flow. As results, our implementation achieves 18× speedups compared with the CPU C++ STL quick sort. And it gets almost linear speedup for next generations of GPU because of the complete parallelism in each iteration process. Meanwhile, our approach makes the odd-even merge sort effectively in practice because of the high performance. Furthermore, the approach used in this paper for cooperating thousands of processing units to parallel process can also be used in other cooperation areas.
Starting Page	76
Ending Page	83
File Size	259815
Page Count	8
File Format	PDF
ISBN	9781457703867
e-ISBN	9781457703874
DOI	10.1109/CSCWD.2011.5960058
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-06-08
Publisher Place	Switzerland
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Graphics processing unit Sorting Arrays Computational modeling Complexity theory Instruction sets OpenCL GPGPU GPU Odd-Even Merge Sort
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Analysis of Fast Parallel Sorting Algorithms for GPU Architectures'

OpenCL: Make Ubiquitous Supercomputing Possible

High performance computing and simulations on the GPU using CUDA

A Novel Computational Model for GPUs with Application to I/O Optimal Sorting Algorithms

Sorting Large Multifield Records on a GPU

Barra: A Parallel Functional Simulator for GPGPU

Method of workload balancing in GPU implementation of breadth-first search

An experimental GPU global memory performance estimation and optimization

Parallelization of bitonic sort and radix sort algorithms on many core GPUs

GPU accelerate parallel Odd-Even merge sort: An OpenCL method

Similar Documents

Analysis of Fast Parallel Sorting Algorithms for GPU Architectures'

OpenCL: Make Ubiquitous Supercomputing Possible

High performance computing and simulations on the GPU using CUDA

A Novel Computational Model for GPUs with Application to I/O Optimal Sorting Algorithms

Sorting Large Multifield Records on a GPU

Barra: A Parallel Functional Simulator for GPGPU

Method of workload balancing in GPU implementation of breadth-first search

An experimental GPU global memory performance estimation and optimization

Parallelization of bitonic sort and radix sort algorithms on many core GPUs

GPU accelerate parallel Odd-Even merge sort: An OpenCL method