Design, implementation and analysis of algorithms on multi-core systems

www.imm.dtu.dk It was the main task of this thesis to analyze, design and implement a parallel version of a classical sequential algorithms. We have in this thesis selected to parallelize the classical sequential algorithm Push Relabel, using the general parallelization procedure described in [11]. Several different implementations, with or without heuristics, has been considered and tested against each other to get the most efficient algorithm for solving the maximum flow problem. The Push Relabel algorithm has been discussed and parallelized in previous studies (e.g. [2] and [3]), but they utilize the programming language C to implement the actual algorithms. Our thesis differs from previous studies by implementing the algorithms using the widely used object-oriented programming language Java. The main focus of the thesis is therefore not only to develop a parallel implementation of the Push Relabel algorithm but also to study the affect of using the parallelization tools available in Java. Our implementatio