AN OPTIMAL EXECUTION TIME ESTIMATE OF STATIC VERSUS DYNAMIC ALLOCATION IN MULTIPROCESSOR SYSTEMS

Consider a multiprocessor with k identical processors, executing paral lel programs consisting of n processes. Let T-s(P) and T-d(P) denote t he execution times for the program P with optimal static and dynamic a llocations, respectively, i.e., allocations giving minimal execution t ime. We derive a general and explicit formula for the following maxima l 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 interproc ess dependency structure for the programs P is allowed only by avoidin g 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 for mulation. The mathematical tools involved are essentially tools of ele mentary combinatorics. The formula is a combinatorial function applied on certain extremal matrices corresponding to extremal programs. It i s mathematically complicated but rapidly computed for reasonable n and k, in contrast to the np-completeness of the problems of finding opti mal allocations.