University of Twente Student Theses
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]](http://essay.utwente.nl/style/images/fileicons/application_pdf.png) |
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: | https://purl.utwente.nl/essays/67128 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page