Using Recorded Values for Bounding the Minimum Completion Time in Multiprocessors

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Full text:
Author(s): Lars Lundberg, Håkan Lennerstad
Title: Using Recorded Values for Bounding the Minimum Completion Time in Multiprocessors
Journal: IEEE Transactions on Parallel and Distributed Systems
Year: 1998
Volume: 9
Issue: 4
ISSN: 1045-9219
Publisher: IEEE
City: New York, N.Y.
ISI number: 000073300300003
Organization: Blekinge Institute of Technology
Department: Dept. of Computer Science and Business Administration (Institutionen för datavetenskap och ekonomi)
*** Error ***
+46 455 780 00
*** Error ***
Authors e-mail: Lars.Lundberg@ide.hk-r.se
Language: English
Abstract: The way the processes in a parallel program are scheduled on the processors of a multiprocessor system affects the
performance significantly. Finding a schedule of processes to processors which results in minimum completion time is NP-hard.
Therefore, one has to resort to heuristic schedules. However, it is often difficult to determine if a specific schedule is close to the
optimal case or if it is worthwhile to look for other schedules.
Based on information from previous executions of the parallel program, we present a formula for an upper bound on the
minimum completion time of the program. The bound is a function of a set of parameters. Some of these parameters are obtained
from the previous executions of the program and the others describe the target multiprocessor architecture for which we want to
bound the minimum completion time. The bound is optimal when it is based on information from one previous execution. Using
these results, we are able to decide if a certain schedule is close to optimal or if it is worthwhile to look for other schedules. This is
demonstrated by evaluating the completion time of a specific schedule of a particular program. The proofs used for obtaining the
bound are based on program transformations and combinatorial mathematics.
Subject: Computer Science\Computersystems
Keywords: Parallel program scheduling, optimal performance bounds, multiprocessors with clusters, synchronizing processes, information from previous executions
Edit