Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components

被引：19

作者：

Wijs, Anton ^{[1
]}

Katoen, Joost-Pieter ^{[2
]}

Bosnacki, Dragan ^{[1
]}

机构：

[1] Eindhoven Univ Technol, Eindhoven, Netherlands

[2] Rhein Westfal TH Aachen, Aachen, Germany

来源：

FORMAL METHODS IN SYSTEM DESIGN | 2016年 / 48卷 / 03期

关键词：

Parallel graph algorithms; Strongly connected components; Maximal end components; Probabilistic model checking; Markov decision processes; GPU;

D O I：

10.1007/s10703-016-0246-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This article presents parallel algorithms for component decomposition of graph structures on general purpose graphics processing units (GPUs). In particular, we consider the problem of decomposing sparse graphs into strongly connected components, and decomposing graphs induced by stochastic games (such as Markov decision processes) into maximal end components. These problems are key ingredients of many (probabilistic) model-checking algorithms. We explain the main rationales behind our GPU-algorithms, and show a significant speed-up over the sequential (as well as existing parallel) counterparts in several case studies.

引用

页码：274 / 300

页数：27

共 36 条

[1]

Abraham E., 2010, Proceedings of the 2010 Seventh International Conference on the Quantitative Evaluation of Systems (QEST 2010), P37, DOI 10.1109/QEST.2010.13

[2]

Aiguo Xie, 1999, 1999 IEEE/ACM International Conference on Computer-Aided Design. Digest of Technical Papers (Cat. No.99CH37051), P37, DOI 10.1109/ICCAD.1999.810617

[3]

[Anonymous], THESIS

[4]

[Anonymous], 2012, P 23 ANN ACMSIAM S D, DOI DOI 10.1137/1.9781611973099.109

[5]

Baier C, 2008, PRINCIPLES OF MODEL CHECKING, P1

[6]

Barnat J., 2011, Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2011), P544, DOI 10.1109/IPDPS.2011.59

[7]

Barnat Jiri, 2009, Proceedings of the 2009 IEEE 15th International Conference on Parallel and Distributed Systems (ICPADS 2009), P34, DOI 10.1109/ICPADS.2009.50

[8]

Barnat J, 2007, LECT NOTES COMPUT SC, V4346, P316

[9] An algorithm for strongly connected component analysis in n log n symbolic steps [J].

Bloem, R ;

Gabow, H ;

Somenzi, F .

FORMAL METHODS IN SYSTEM DESIGN, 2006, 28 (01) :37-56

[10]

Bosnacki Dragan, 2010, Proceedings 2010 9th International Workshop on Parallel & Distributed Methods in Verification and 2nd International Workshop on High Performance Computational Systems Biology (PDMC-HiBi 2010), P17, DOI 10.1109/PDMC-HiBi.2010.11

← 1 2 3 4 →