Change search
ReferencesLink to record
Permanent link

Direct link
A Method for Bounding the Minimal Completion Time in Multiprocessors
Responsible organisation
2002 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Blekinge Tekniska Högskola Forskningsrapport, ISSN 1103-1581 ; 3
National Category
Computer Science
URN: urn:nbn:se:bth-00202Local ID: diva2:837588
Available from: 2012-09-18 Created: 2002-02-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(256 kB)26 downloads
File information
File name FULLTEXT01.pdfFile size 256 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lundberg, Lars
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 26 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 31 hits
ReferencesLink to record
Permanent link

Direct link