Optimal combinatorial functions comparing multiprocess allocation performance in multiprocessor systems

For the execution of an arbitrary parallel program P, consisting of a set o f processes with any executable interprocess dependency structure, we consi der two alternative multiprocessors. The first multiprocessor has q processors and allocates parallel programs d ynamically; i.e., processes may be reallocated from one processor to anothe r. The second employs cluster allocation with k clusters and u processors i n each cluster: here processes may be reallocated within a cluster only. Le t T-d(P, q) and T-c(P, k, u) be execution times for the parallel program P with optimal allocations. We derive a formula for the program independent p erformance function [GRAPHICS] Hence, with optimal allocations, the execution of P can never take more tha n a factor G(k, u, q) longer time with the second multiprocessor than with the first, and there exist programs showing that the bound is sharp. The supremum is taken over all parallel programs consisting of any number o f processes. Overhead for synchronization and reallocation is neglected onl y. We further present a tight bound which exploits a priori knowledge of the c lass of parallel programs intended for the multiprocessors, thus resulting in a sharper bound. The function g(n, k, u, q) is the above maximum taken o ver all parallel programs consisting of n processes. The functions G and g can be used in various ways to obtain tight performan ce bounds, aiding in multiprocessor architecture decisions.