An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems
|Author(s):||Håkan Lennerstad, Lars Lundberg|
|Title:||An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems|
|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:||firstname.lastname@example.org, email@example.com|
|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.
Computer Science\Distributed Computing
|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.|