On-The-Fly parallel decomposition of strongly connected components

Bloemen, V. (2015) On-The-Fly parallel decomposition of strongly connected components.

This is the latest version of this item.

[img] PDF
826kB
Abstract:Several algorithms exist for decomposing strongly connected components (SCCs). To accommodate recent non-reversible trends in hardware, we focus on utilizing multi-core architectures. Specifically, we consider parallelizing SCC algorithms in the setting of an on-the-fly implementation (to be able to detect SCCs while constructing the graph - which is particularly useful for several verification techniques). We show that the current solutions are not capable of scaling efficiently and we propose a new algorithm that is able to do so. Our parallel algorithm is (in contrast to the existing approaches) specifically designed to communicate partially discovered SCCs between workers. This is achieved by using a shared Union-Find structure. This structure has been extended to efficiently keep track of the search paths for each worker in combination with means to iterate and communicate fully explored vertices. We show that the designed algorithm is provably correct and performs in quasi-linear time. Experiments show that it outperforms existing techniques.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:http://purl.utwente.nl/essays/67128
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page