Open AccessHigh performance CUDA-based implementation for the 2D version of the Maximum Subarray Problem (MSP)
Author(s) -
S. S. SALEH,
Marwan Abdellah,
Ahmed A. Raouf,
Yasser M. Kadah
Publication year - 2012
Publication title -
citeseer x (the pennsylvania state university)
Language(s) - English
Resource type - Conference proceedings
ISSN - 2156-6097
ISBN - 978-1-4673-2800-5
DOI - 10.1109/cibec.2012.6473291
Subject(s) - speedup , cuda , computer science , parallel computing , graphics processing unit , graphics , central processing unit , time complexity , sequence (biology) , general purpose computing on graphics processing units , performance improvement , computational science , algorithm , computer graphics (images) , computer hardware , biology , genetics , operations management , economics
The Maximum Subarray Problem (MSP) finds a segment of an array that has the maximum summation over all the other possible combinations. Different applications for this problem exist in various fields like genomic sequence analysis, data mining and computer vision. Several optimum linear-time solutions exist for the 1D version, however, the known upper bounds for the 2D version are cubic or near-cubic time; which makes it a problem of high complexity. In this work, a stage by stage high performance Graphics Processing Unit (GPU)-based implementation for solving the 2D version of the problem in a linear time relying on the Compute Unified Device Architecture (CUDA) technology is presented. It achieves more than 7X of speedup in performance compared to a single-threaded sequential implementation on the Central Processing Unit (CPU) for an array of size 5122.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom