This paper 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 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 counterparts in several case studies.
|Name||Lecture Notes in Computer Science|
|Conference||conference; 26th International Conference on Computer Aided Verification; 2014-07-18; 2014-07-22|
|Period||18/07/14 → 22/07/14|
|Other||26th International Conference on Computer Aided Verification|