NDLI: On the Robust Mapping of Dynamic Programming onto a Graphics Processing Unit

Content Provider	IEEE Xplore Digital Library
Author	Shucai Xiao Aji, A.M. Wu-chun Feng
Copyright Year	2009
Abstract	Graphics processing units (GPUs) have been widely used to accelerate algorithms that exhibit massive data parallelism or task parallelism. When such parallelism is not inherent in an algorithm, computational scientists resort to simply replicating the algorithm on every multiprocessor of a NVIDIA GPU, for example, to create such parallelism, resulting in embarrassingly parallel ensemble runs that deliver significant aggregate speed-up. However, the fundamental issue with such ensemble runs is that the problem size to achieve this speed-up is limited to the available shared memory and cache of a GPU multiprocessor. An example of the above is dynamic programming (DP), one of the Berkeley 13 dwarfs. All known DP implementations to date use the coarse-grained approach of embarrassingly parallel ensemble runs because a fine-grained parallelization on the GPU would require extensive communication between the multiprocessors of a GPU, which could easily cripple performance as communication between multiprocessors is not natively supported in a GPU. Consequently, we address the above by proposing a fine-grained parallelization of a single instance of the DP algorithm that is mapped to the GPU. Our parallelization incorporates a set of techniques aimed to substantially improve GPU performance: matrix re-alignment, coalesced memory access, tiling, and GPU (rather than CPU) synchronization. The specific DP algorithm that we parallelize is called Smith-Waterman (SWat), which is an optimal local-sequence alignment algorithm. We then use this SWat algorithm as a baseline to compare our GPU implementation, i.e., CUDA-SWat, to our implementation on the Cell Broadband Engine, i.e., Cell-SWat.
Starting Page	26
Ending Page	33
File Size	2517149
Page Count	8
File Format	PDF
ISBN	9781424457885
ISSN	15219097
e-ISBN	9781424457892
DOI	10.1109/ICPADS.2009.110
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-12-08
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Robustness Dynamic programming Parallel processing Computer architecture Acceleration Concurrent computing Central Processing Unit Synchronization Computer graphics Engines
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture

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

High precision integer multiplication with a graphics processing unit

CellStats: A Tool to Evaluate the Basic Synchronization and Communication Operations of the Cell BE

Graphical Processing Units (GPU) acceleration of finite-difference frequency-domain (FDFD) technique

Parallel data-locality aware stencil computations on modern micro-architectures

Exploiting Computing Power on Graphics Processing Unit

Parallel Computing Experiences with CUDA

SAGA: SystemC acceleration on GPU architectures

String Matching on a Multicore GPU Using CUDA

Multimedia processing on commodity graphics hardware

On the Robust Mapping of Dynamic Programming onto a Graphics Processing Unit

Similar Documents

High precision integer multiplication with a graphics processing unit

CellStats: A Tool to Evaluate the Basic Synchronization and Communication Operations of the Cell BE

Graphical Processing Units (GPU) acceleration of finite-difference frequency-domain (FDFD) technique

Parallel data-locality aware stencil computations on modern micro-architectures

Exploiting Computing Power on Graphics Processing Unit

Parallel Computing Experiences with CUDA

SAGA: SystemC acceleration on GPU architectures

String Matching on a Multicore GPU Using CUDA

Multimedia processing on commodity graphics hardware

On the Robust Mapping of Dynamic Programming onto a Graphics Processing Unit