Files in this item



application/pdfLV-THESIS-2016.pdf (1MB)
(no description provided)PDF


Title:Parallel merge for many-core architectures
Author(s):Lv, Jie
Advisor(s):Hwu, Wen-Mei W
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Graphics processing unit (GPU)
Parallel Merge
Abstract:This thesis proposes a novel GPU implementation for merging two sorted arrays. We consider the problem of merging two arrays A and B into a single array C. Each element in the arrays has a key. An ordering relation denoted by is defined on the keys. Array A and array B have m and n elements, respectively, where m and n do not have to be equal. Both array A and array B are sorted based on the ordering relation. The task is to produce the output array C of size m + n. Array C consists of all the input elements from array A and array B, and is sorted by the ordering relation. We applied several GPU-specific optimizations to a parallel merge algorithm. The optimizations include coordinating the memory access pattern, making full use of the shared memory and reducing the thread divergence. Our implementation achieves up to 10x and 40x speedup on Titan-Z and GTX 980 GPU respectively compared to thrust merge implementation.
Issue Date:2016-04-27
Rights Information:Copyright 2016 Jie Lv
Date Available in IDEALS:2016-07-07
Date Deposited:2016-05

This item appears in the following Collection(s)

Item Statistics