Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing

Document type: Dissertations
Full text:
Author(s): Kamilla Klonowska
Title: Theoretical Aspects on Performance Bounds and Fault Tolerance in Parallel Computing
Series: Blekinge Institute of Technology Doctoral Dissertation Series
Year: 2007
Issue: 18
Pagination: 169
ISBN: 978-91-7295-126-6
ISSN: 1653-2090
Publisher: Blekinge Institute of Technology
City: Karlskrona
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. of Systems and Software Engineering (Sektionen för teknik – avd. för programvarusystem)
School of Engineering S- 372 25 Ronneby
+46 455 38 50 00
http://www.tek.bth.se/
Authors e-mail: kamilla.klonowska@bth.se
Language: English
Abstract: 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.
Subject: Computer Science\Computersystems
URN: urn:nbn:se:bth-00385
Edit