Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing
Blekinge Institute of Technology, School of Engineering, Department of Systems and Software Engineering2007 (English)Doctoral thesis, comprehensive summary (Other academic)
This thesis consists of two parts: performance bounds for scheduling algorithms for parallel programs in multiprocessor systems, and recovery schemes for fault tolerant distributed systems when one or more computers go down. In the first part we deliver tight bounds on the ratio for the minimal completion time of a parallel program executed in a parallel system in two scenarios. Scenario one, the ratio for minimal completion time when processes can be reallocated compared to when they cannot be reallocated to other processors during their execution time. Scenario two, when a schedule is preemptive, the ratio for the minimal completion time when we use two different numbers of preemptions. The second part discusses the problem of redistribution of the load among running computers in a parallel system. The goal is to find a redistribution scheme that maintains high performance even when one or more computers go down. Here we deliver four different redistribution algorithms. In both parts we use theoretical techniques that lead to explicit worst-case programs and scenarios. The correctness is based on mathematical proofs.
Place, publisher, year, edition, pages
Karlskrona: Blekinge Institute of Technology , 2007. , 169 p.
Blekinge Institute of Technology Doctoral Dissertation Series, ISSN 1653-2090 ; 18
IdentifiersURN: urn:nbn:se:bth-00385Local ID: oai:bth.se:forskinfoA46EBB190DFB7CAEC12573A700356D59ISBN: 978-91-7295-126-6OAI: oai:DiVA.org:bth-00385DiVA: diva2:836625