Parallel maximum flow solver for multi-core machines
| dc.contributor | Graduate Program in Computer Engineering. | |
| dc.contributor.advisor | Özturan, Can. | |
| dc.contributor.author | Cihan, Selçuk. | |
| dc.date.accessioned | 2023-03-16T10:00:18Z | |
| dc.date.available | 2023-03-16T10:00:18Z | |
| dc.date.issued | 2010. | |
| dc.description.abstract | We provide a parallel algorithm for calculating maximum flow between two nodes, in a capacitated network. The algorithm we propose is based on push-relabel algorithm due to Goldberg and uses a modified first in first out selection strategy together with global relabeling heuristic. Our implementation targets multi-core processors, implements task stealing to balance load between multiple threads of execution and uses fast atomic variables for synchronization instead of costly general purpose locks. We compare our algorithm to other push-relabel based algorithms and demonstrate that it performs well in practice. | |
| dc.format.extent | 30cm. | |
| dc.format.pages | xiii, 58 leaves; | |
| dc.identifier.other | CMPE 2010 C54 | |
| dc.identifier.uri | https://digitalarchive.library.bogazici.edu.tr/handle/123456789/12172 | |
| dc.publisher | Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2010. | |
| dc.relation | Includes appendices. | |
| dc.relation | Includes appendices. | |
| dc.subject.lcsh | Parallel algorithms. | |
| dc.subject.lcsh | Parallel processing (Electronic computers) | |
| dc.subject.lcsh | Graph theory. | |
| dc.title | Parallel maximum flow solver for multi-core machines |