Data-driven versus Topology-driven Irregular Computations on GPUs

被引:68
作者
Nasre, Rupesh [1 ]
Burtscher, Martin [2 ]
Pingali, Keshav [1 ]
机构
[1] Univ Texas Austin, Austin, TX 78712 USA
[2] Texas State Univ, San Marcos, TX USA
来源
IEEE 27TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2013) | 2013年
基金
美国国家科学基金会;
关键词
irregular algorithms; data-driven; topology-driven; algorithmic properties; GPGPU; GRAPH ALGORITHMS; PARALLELISM;
D O I
10.1109/IPDPS.2013.28
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Irregular algorithms are algorithms with complex main data structures such as directed and undirected graphs, trees, etc. A useful abstraction for many irregular algorithms is its operator formulation in which the algorithm is viewed as the iterated application of an operator to certain nodes, called active nodes, in the graph. Each operator application, called an activity, usually touches only a small part of the overall graph, so non-overlapping activities can be performed in parallel. In topology-driven implementations, all nodes are assumed to be active so the operator is applied everywhere in the graph even if there is no work to do at some nodes. In contrast, in data-driven implementations the operator is applied only to nodes at which there might be work to do. Multicore implementations of irregular algorithms are usually data-driven because current multicores only support small numbers of threads and work-efficiency is important. Conversely, many irregular GPU implementations use a topology-driven approach because work inefficiency can be counterbalanced by the large number of GPU threads. In this paper, we study data-driven and topology-driven implementations of six important graph algorithms on GPUs. Our goal is to understand the tradeoffs between these implementations and how to optimize them. We find that data-driven versions are generally faster and scale better despite the cost of maintaining a worklist. However, topology-driven versions can be superior when certain algorithmic properties are exploited to optimize the implementation. These results led us to devise hybrid approaches that combine the two techniques and outperform both of them.
引用
收藏
页码:463 / 474
页数:12
相关论文
共 50 条
  • [41] Data-Driven Granular Cognitive Computing
    Wang, Guoyin
    [J]. ROUGH SETS, 2017, 10313 : 13 - 24
  • [42] Data-driven deep density estimation
    Patrik Puchert
    Pedro Hermosilla
    Tobias Ritschel
    Timo Ropinski
    [J]. Neural Computing and Applications, 2021, 33 : 16773 - 16807
  • [43] On Lyapunov functions and data-driven dissipativity
    Maupong, T. M.
    Mayo-Maldonado, J. C.
    Rapisarda, P.
    [J]. IFAC PAPERSONLINE, 2017, 50 (01): : 7783 - 7788
  • [44] The Difficult Path to Become Data-Driven
    Sdiri B.
    Rigaud L.
    Jemmali R.
    Abdelhedi F.
    [J]. SN Computer Science, 4 (4)
  • [45] Data-driven manufacturing sustainability assessment
    Zhang X.
    Chen J.
    Wang Y.
    Zhang H.
    Jiang Z.
    Cai W.
    [J]. Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, 2022, 28 (08): : 2329 - 2342
  • [46] A Data-Driven Approach to Constraint Optimization
    Wikarek, Jaroslaw
    Sitek, Pawel
    [J]. AUTOMATION 2019: PROGRESS IN AUTOMATION, ROBOTICS AND MEASUREMENT TECHNIQUES, 2020, 920 : 135 - 144
  • [47] A Data-Driven Topology and Parameter Joint Estimation Method in Non-PMU Distribution Networks
    Wang, Xiaoxue
    Zhao, Yikang
    Zhou, Yue
    [J]. IEEE TRANSACTIONS ON POWER SYSTEMS, 2024, 39 (01) : 1681 - 1692
  • [48] Data Consistency for Data-Driven Smart Energy Assessment
    Chicco, Gianfranco
    [J]. FRONTIERS IN BIG DATA, 2021, 4
  • [49] Data-driven Soil Cultivation Promoted by NTT DATA
    Oozeki T.
    Yamane K.
    [J]. NTT Technical Review, 2022, 20 (06): : 26 - 28
  • [50] Model-Driven Feature Engineering for Data-Driven Battery SOH Model
    Alamin, Khaled
    Pagliari, Daniele Jahier
    Chen, Yukai
    Macii, Enrico
    Vinco, Sara
    Poncino, Massimo
    [J]. 2024 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION, DATE, 2024,