Change search
ReferencesLink to record
Permanent link

Direct link
Using Recorded Values for Bounding the Minimum Completion Time in Multiprocessors
Responsible organisation
1998 (English)In: IEEE Transactions on Parallel and Distributed Systems, ISSN 1045-9219, E-ISSN 1558-2183, Vol. 9, no 4Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
New York, N.Y.: IEEE , 1998. Vol. 9, no 4
Keyword [en]
Parallel program scheduling, optimal performance bounds, multiprocessors with clusters, synchronizing processes, information from previous executions
National Category
Computer Science
URN: urn:nbn:se:bth-9681ISI: 000073300300003Local ID: diva2:837591
Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Lundberg, LarsLennerstad, Håkan
In the same journal
IEEE Transactions on Parallel and Distributed Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 17 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: 22 hits
ReferencesLink to record
Permanent link

Direct link