An Optimal Execution Time Estimate of Static Versus Dynamic Allocation in Multiprocessor Systems
Håkan Lennerstad, Lars Lundberg · SIAM Journal on Computing · 1995
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 following 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 by 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.