An Energy-Efficient Abstraction for Simultaneous Breadth-First Searches. McLaughlin, A., Riedy, J., & Bader, D. A. In The IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, September, 2015. abstract bibtex Optimized GPU kernels are sufficiently complicated to write that they often are specialized to specific input data, target architectures, or applications. This paper presents a multi-search abstraction for computing multiple breadth-first searches in parallel and demonstrates a high-performance, general implementation. Our abstraction removes the burden of orchestrating graph traversal from the user while providing high performance and low energy usage, an often overlooked component of algorithm design. Energy consumption has become a first-class hardware design constraint for both massive and embedded computing platforms. Our abstraction can be applied to such problems as the all-pairs shortest-path problem, community detection, reachability querying, and others. To map graph traversal efficiently to NVIDIA GPUs, our hybrid implementation chooses between processing active vertices with a single thread or an entire warp based on vertex outdegree. For a set of twelve varied graphs, the implementation of our abstraction saves 42% time and 62% energy on average compared to representative implementations of specific applications from existing literature.
@inproceedings{hpec15,
author = {Adam McLaughlin and Jason Riedy and David A. Bader},
title = {An Energy-Efficient Abstraction for Simultaneous Breadth-First Searches},
ejr-withauthor = {Adam McLaughlin and David A. Bader},
opttags = {parallel; graph; energy},
booktitle = {The IEEE High Performance Extreme Computing Conference (HPEC)},
year = 2015,
month = sep,
address = {Waltham, MA},
dom = 17,
role = {proceedings},
abstract = {Optimized GPU kernels are sufficiently complicated to write that they often are specialized to specific input data, target architectures, or applications. This paper presents a multi-search abstraction for computing multiple breadth-first searches in parallel and demonstrates a high-performance, general implementation. Our abstraction removes the burden of orchestrating graph traversal from the user while providing high performance and low energy usage, an often overlooked component of algorithm design. Energy consumption has become a first-class hardware design constraint for both massive and embedded computing platforms. Our abstraction can be applied to such problems as the all-pairs shortest-path problem, community detection, reachability querying, and others. To map graph traversal efficiently to NVIDIA GPUs, our hybrid implementation chooses between processing active vertices with a single thread or an entire warp based on vertex outdegree. For a set of twelve varied graphs, the implementation of our abstraction saves 42\% time and 62\% energy on average compared to representative implementations of specific applications from existing literature.},
file = {material/multi_search_energy.pdf},
projtag = {xscala, grateful, hpda},
keywords = {hpda, graph analysis, parallel algorithm},
ejr-proj = {high-performance-data-analysis, graph-analysis},
ejr-grant = {grateful, xscala}
}
Downloads: 0
{"_id":"jGLnCLLEXmLbEyLgP","bibbaseid":"mclaughlin-riedy-bader-anenergyefficientabstractionforsimultaneousbreadthfirstsearches-2015","downloads":0,"creationDate":"2018-08-21T18:11:53.682Z","title":"An Energy-Efficient Abstraction for Simultaneous Breadth-First Searches","author_short":["McLaughlin, A.","Riedy, J.","Bader, D. A."],"year":2015,"bibtype":"inproceedings","biburl":"http://lovesgoodfood.com/jason/CV/ejr.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Adam"],"propositions":[],"lastnames":["McLaughlin"],"suffixes":[]},{"firstnames":["Jason"],"propositions":[],"lastnames":["Riedy"],"suffixes":[]},{"firstnames":["David","A."],"propositions":[],"lastnames":["Bader"],"suffixes":[]}],"title":"An Energy-Efficient Abstraction for Simultaneous Breadth-First Searches","ejr-withauthor":"Adam McLaughlin and David A. Bader","opttags":"parallel; graph; energy","booktitle":"The IEEE High Performance Extreme Computing Conference (HPEC)","year":"2015","month":"September","address":"Waltham, MA","dom":"17","role":"author","abstract":"Optimized GPU kernels are sufficiently complicated to write that they often are specialized to specific input data, target architectures, or applications. This paper presents a multi-search abstraction for computing multiple breadth-first searches in parallel and demonstrates a high-performance, general implementation. Our abstraction removes the burden of orchestrating graph traversal from the user while providing high performance and low energy usage, an often overlooked component of algorithm design. Energy consumption has become a first-class hardware design constraint for both massive and embedded computing platforms. Our abstraction can be applied to such problems as the all-pairs shortest-path problem, community detection, reachability querying, and others. To map graph traversal efficiently to NVIDIA GPUs, our hybrid implementation chooses between processing active vertices with a single thread or an entire warp based on vertex outdegree. For a set of twelve varied graphs, the implementation of our abstraction saves 42% time and 62% energy on average compared to representative implementations of specific applications from existing literature.","file":"material/multi_search_energy.pdf","projtag":"xscala, grateful, hpda","keywords":"hpda, graph analysis, parallel algorithm","ejr-proj":"high-performance-data-analysis, graph-analysis","ejr-grant":"grateful, xscala","bibtex":"@inproceedings{hpec15,\n author = {Adam McLaughlin and Jason Riedy and David A. Bader},\n title = {An Energy-Efficient Abstraction for Simultaneous Breadth-First Searches},\n ejr-withauthor = {Adam McLaughlin and David A. Bader},\n opttags = {parallel; graph; energy},\n booktitle = {The IEEE High Performance Extreme Computing Conference (HPEC)},\n year = 2015,\n month = sep,\n address = {Waltham, MA},\n dom = 17,\n role = {proceedings},\n abstract = {Optimized GPU kernels are sufficiently complicated to write that they often are specialized to specific input data, target architectures, or applications. This paper presents a multi-search abstraction for computing multiple breadth-first searches in parallel and demonstrates a high-performance, general implementation. Our abstraction removes the burden of orchestrating graph traversal from the user while providing high performance and low energy usage, an often overlooked component of algorithm design. Energy consumption has become a first-class hardware design constraint for both massive and embedded computing platforms. Our abstraction can be applied to such problems as the all-pairs shortest-path problem, community detection, reachability querying, and others. To map graph traversal efficiently to NVIDIA GPUs, our hybrid implementation chooses between processing active vertices with a single thread or an entire warp based on vertex outdegree. For a set of twelve varied graphs, the implementation of our abstraction saves 42\\% time and 62\\% energy on average compared to representative implementations of specific applications from existing literature.},\n file = {material/multi_search_energy.pdf},\n projtag = {xscala, grateful, hpda},\n keywords = {hpda, graph analysis, parallel algorithm},\n ejr-proj = {high-performance-data-analysis, graph-analysis},\n ejr-grant = {grateful, xscala}\n}\n\n","author_short":["McLaughlin, A.","Riedy, J.","Bader, D. A."],"key":"hpec15","id":"hpec15","bibbaseid":"mclaughlin-riedy-bader-anenergyefficientabstractionforsimultaneousbreadthfirstsearches-2015","urls":{},"keyword":["hpda","graph analysis","parallel algorithm"],"metadata":{"authorlinks":{}}},"search_terms":["energy","efficient","abstraction","simultaneous","breadth","first","searches","mclaughlin","riedy","bader"],"keywords":["hpda","graph analysis","parallel algorithm"],"authorIDs":[],"dataSources":["yxjEg4KYBKLdX7BAz","iovMFeXD2oi65krsd"]}