Beta 1


Title Design, implementation and analysis of algorithms on multi-core systems
Author Wind, Peter
Hansen, Jonas
Supervisor Fischer, Paul (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Bachelor thesis
Year 2008
Abstract 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 ow 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 implementation also differs from earlier studies by being optimized and tested on public available multi-core computers instead of high-end supercomputers. All developed algorithms has been tested against reference implementations of other well known sequential algorithms, and for testing-purposes, three graph generators has been developed and implemented. The graph generators are inspired by graphs used in previous studies [10] and graphs used in the DIMACS implementation challenges [7]. The developed algorithms performs well in practice, and results in running time decreases proportional to the number of CPU cores. We have, however, discovered that the performance of the algorithms varies a lot depending on the operating system and Java version.
Series IMM-B.Sc.-2008-16
Fulltext
Original PDF bac08_16_net.pdf (1.86 MB)
Admin Creation date: 2008-06-27    Update date: 2008-06-27    Source: dtu    ID: 220951    Original MXD