Mercator: A GPGPU framework for irregular streaming applications

Stephen V. Cole; Jeremy Buhler

doi:10.1109/HPCS.2017.111

Mercator: A GPGPU framework for irregular streaming applications

Stephen V. Cole, Jeremy Buhler

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Scopus citations

Abstract

GPUs have a natural affinity for streaming applications exhibiting consistent, predictable dataflow. However, many high-impact irregular streaming applications, including sequence pattern matching, decision-tree and decision-cascade evaluation, and large-scale graph processing, exhibit unpredictable dataflow due to data-dependent filtering or expansion of the data stream. Existing GPU frameworks do not support arbitrary irregular streaming dataflow tasks, and developing application-specific optimized implementations for such tasks requires expert GPU knowledge. We introduce MERCATOR, a lightweight framework supporting modular CUDA streaming application development for irregular applications. A developer can use MERCATOR to decompose an irregular application for the GPU without explicitly remapping work to threads at runtime. MERCATOR applications are efficiently parallelized on the GPU through a combination of replication across blocks and queueing between nodes to accommodate irregularity. We quantify the performance impact of MERCATOR's support for irregularity and illustrate its utility by implementing a biological sequence comparison pipeline similar to the well-known NCBI BLASTN algorithm. MERCATOR code is available by request to the first author.

Original language	English
Title of host publication	Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017
Editors	Waleed W. Smari
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	727-736
Number of pages	10
ISBN (Electronic)	9781538632505
DOIs	https://doi.org/10.1109/HPCS.2017.111
State	Published - Sep 12 2017
Event	15th International Conference on High Performance Computing and Simulation, HPCS 2017 - Genoa, Italy Duration: Jul 17 2017 → Jul 21 2017

Publication series

Name	Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017

Conference

Conference	15th International Conference on High Performance Computing and Simulation, HPCS 2017
Country/Territory	Italy
City	Genoa
Period	07/17/17 → 07/21/17

Keywords

GPU
Irregular computation
Parallel computing
SIMD
Streaming dataflow

Access to Document

10.1109/HPCS.2017.111

Cite this

Cole, S. V., & Buhler, J. (2017). Mercator: A GPGPU framework for irregular streaming applications. In W. W. Smari (Ed.), Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017 (pp. 727-736). Article 8035150 (Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPCS.2017.111

Cole, Stephen V. ; Buhler, Jeremy. / Mercator : A GPGPU framework for irregular streaming applications. Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017. editor / Waleed W. Smari. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 727-736 (Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017).

@inproceedings{b76d2f90d74f4e3cb3b2761985dcd32b,

title = "Mercator: A GPGPU framework for irregular streaming applications",

abstract = "GPUs have a natural affinity for streaming applications exhibiting consistent, predictable dataflow. However, many high-impact irregular streaming applications, including sequence pattern matching, decision-tree and decision-cascade evaluation, and large-scale graph processing, exhibit unpredictable dataflow due to data-dependent filtering or expansion of the data stream. Existing GPU frameworks do not support arbitrary irregular streaming dataflow tasks, and developing application-specific optimized implementations for such tasks requires expert GPU knowledge. We introduce MERCATOR, a lightweight framework supporting modular CUDA streaming application development for irregular applications. A developer can use MERCATOR to decompose an irregular application for the GPU without explicitly remapping work to threads at runtime. MERCATOR applications are efficiently parallelized on the GPU through a combination of replication across blocks and queueing between nodes to accommodate irregularity. We quantify the performance impact of MERCATOR's support for irregularity and illustrate its utility by implementing a biological sequence comparison pipeline similar to the well-known NCBI BLASTN algorithm. MERCATOR code is available by request to the first author.",

keywords = "GPU, Irregular computation, Parallel computing, SIMD, Streaming dataflow",

author = "Cole, {Stephen V.} and Jeremy Buhler",

note = "Funding Information: Work supported by NSF CNS-1500173 and by Exegy, Inc. Publisher Copyright: {\textcopyright} 2017 IEEE.; 15th International Conference on High Performance Computing and Simulation, HPCS 2017 ; Conference date: 17-07-2017 Through 21-07-2017",

year = "2017",

month = sep,

day = "12",

doi = "10.1109/HPCS.2017.111",

language = "English",

series = "Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "727--736",

editor = "Smari, {Waleed W.}",

booktitle = "Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017",

}

Cole, SV & Buhler, J 2017, Mercator: A GPGPU framework for irregular streaming applications. in WW Smari (ed.), Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017., 8035150, Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017, Institute of Electrical and Electronics Engineers Inc., pp. 727-736, 15th International Conference on High Performance Computing and Simulation, HPCS 2017, Genoa, Italy, 07/17/17. https://doi.org/10.1109/HPCS.2017.111

Mercator: A GPGPU framework for irregular streaming applications. / Cole, Stephen V.; Buhler, Jeremy.
Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017. ed. / Waleed W. Smari. Institute of Electrical and Electronics Engineers Inc., 2017. p. 727-736 8035150 (Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Mercator

T2 - 15th International Conference on High Performance Computing and Simulation, HPCS 2017

AU - Cole, Stephen V.

AU - Buhler, Jeremy

PY - 2017/9/12

Y1 - 2017/9/12

N2 - GPUs have a natural affinity for streaming applications exhibiting consistent, predictable dataflow. However, many high-impact irregular streaming applications, including sequence pattern matching, decision-tree and decision-cascade evaluation, and large-scale graph processing, exhibit unpredictable dataflow due to data-dependent filtering or expansion of the data stream. Existing GPU frameworks do not support arbitrary irregular streaming dataflow tasks, and developing application-specific optimized implementations for such tasks requires expert GPU knowledge. We introduce MERCATOR, a lightweight framework supporting modular CUDA streaming application development for irregular applications. A developer can use MERCATOR to decompose an irregular application for the GPU without explicitly remapping work to threads at runtime. MERCATOR applications are efficiently parallelized on the GPU through a combination of replication across blocks and queueing between nodes to accommodate irregularity. We quantify the performance impact of MERCATOR's support for irregularity and illustrate its utility by implementing a biological sequence comparison pipeline similar to the well-known NCBI BLASTN algorithm. MERCATOR code is available by request to the first author.

AB - GPUs have a natural affinity for streaming applications exhibiting consistent, predictable dataflow. However, many high-impact irregular streaming applications, including sequence pattern matching, decision-tree and decision-cascade evaluation, and large-scale graph processing, exhibit unpredictable dataflow due to data-dependent filtering or expansion of the data stream. Existing GPU frameworks do not support arbitrary irregular streaming dataflow tasks, and developing application-specific optimized implementations for such tasks requires expert GPU knowledge. We introduce MERCATOR, a lightweight framework supporting modular CUDA streaming application development for irregular applications. A developer can use MERCATOR to decompose an irregular application for the GPU without explicitly remapping work to threads at runtime. MERCATOR applications are efficiently parallelized on the GPU through a combination of replication across blocks and queueing between nodes to accommodate irregularity. We quantify the performance impact of MERCATOR's support for irregularity and illustrate its utility by implementing a biological sequence comparison pipeline similar to the well-known NCBI BLASTN algorithm. MERCATOR code is available by request to the first author.

KW - GPU

KW - Irregular computation

KW - Parallel computing

KW - SIMD

KW - Streaming dataflow

UR - http://www.scopus.com/inward/record.url?scp=85032376926&partnerID=8YFLogxK

U2 - 10.1109/HPCS.2017.111

DO - 10.1109/HPCS.2017.111

M3 - Conference contribution

AN - SCOPUS:85032376926

T3 - Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017

SP - 727

EP - 736

BT - Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017

A2 - Smari, Waleed W.

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 17 July 2017 through 21 July 2017

ER -

Cole SV, Buhler J. Mercator: A GPGPU framework for irregular streaming applications. In Smari WW, editor, Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 727-736. 8035150. (Proceedings - 2017 International Conference on High Performance Computing and Simulation, HPCS 2017). doi: 10.1109/HPCS.2017.111

Mercator: A GPGPU framework for irregular streaming applications

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this