An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems

Document type: Researchreports
Full text:
Author(s): Håkan Lennerstad, Lars Lundberg
Title: An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems
Series: Research Report
Year: 1992
Issue: 1
ISSN: 1103-1581
Organization: Blekinge Institute of Technology
Department: Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)
Dept. of Telecommunications and Mathematics S-371 79 Karlskrona
+46 455 780 00
Authors e-mail:,
Language: English
Abstract: Consider a multiprocessor with $k$ identical processors,
executing parallel programs consisting of $n$ processes.

Let $T_s(P)$ and $T_d(P)$ denote the execution times for the program $P$
with optimal static and dynamic allocations respectively, i. e. allocations giving minimal execution time.

We derive a general and explicit formula for the maximal execution time ratio $g(n,k)=\max T_s(P)/T_d(P)$,
where the maximum is taken over all programs $P$ consisting of $n$ processes.
Any interprocess dependency structure for the programs $P$ is allowed, only avoiding deadlock.
Overhead for synchronization and reallocation is neglected.

Basic properties of the function $g(n,k)$ are established, from which we obtain a global description of the function. Plots of $g(n,k)$ are included.

The results are obtained by investigating a mathematical formulation. The mathematical tools involved are essentially tools of
elementary combinatorics. The formula is a combinatorial function applied on certain extremal matrices corresponding to
extremal programs. It is mathematically complicated but rapidly computed for reasonable $n$ and $k$, in contrast to
the np-completeness of the problems of finding optimal allocations.
Subject: Computer Science\Computersystems
Computer Science\Distributed Computing
Mathematics\Discrete Mathematics
Keywords: multiprocessor, parallel computer, static allocation, dynamic allocation, extremal combinatorics
Note: Also published in SIAM Journal of Computing, Vol. 24, No. 4, pp. 751-764, August 1995.
URN: urn:nbn:se:bth-00014