A Method for Bounding the Minimal Completion Time in Multiprocessors

Document type: Researchreports
Full text:
Author(s): Magnus Broberg, Lars Lundberg, Kamilla Klonowska
Title: A Method for Bounding the Minimal Completion Time in Multiprocessors
Series: Research Report
Year: 2002
Issue: 3
ISSN: 1103-1581
Organization: Blekinge Institute of Technology
Department: Department of Software Engineering and Computer Science (Institutionen för programvaruteknik och datavetenskap)
Dept. of Software Engineering and Computer Science S-372 25 Ronneby
+46 455 38 50 00
Authors e-mail: {Magnus.Broberg, Lars.Lundberg, Hakan.Grahn}@bth.se
Language: English
Abstract: The cluster systems used today usually prohibit that a running process on one node is reallocated to another node. A parallel program developer thus has to decide how processes should be allocated to the nodes in the cluster. Finding an allocation that results in minimal completion time is NP-hard and (non-optimal) heuristic algorithms have to be used. One major drawback with heuristics is that we do not know if the result is close to optimal or not.
In this paper we present a method for finding a guaranteed minimal completion time for a given program. The method can be used as a bound that helps the user to determine when it is worth-while to continue the heuristic search. Based on some parameters derived from the program, as well as some parameters describing the hardware platform, the method produces the minimal completion time bound. The method includes an aggressive branch-and-bound algorithm that has been shown to reduce the search space to 0.0004%. A practical demonstration of the method is presented using a tool that automatically derives the necessary program parameters and produces the bound without the need for a multiprocessor. This makes the method accessible for practitioners.
Subject: Computer Science\Computersystems
URN: urn:nbn:se:bth-00202