Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems

Document type: Researchreports
Full text:
Author(s): Håkan Lennerstad, Lars Lundberg
Title: Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems
Series: Research Report
Year: 1993
Issue: 3
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: hakan@itm.hk-r.se, lasse@ide.hk-r.se
Language: English
Abstract: For the execution of an arbitrary parallel program P, consisting of a set of processes, we consider two alternative multiprocessors.

The first multiprocessor has q processors and allocates
parallel programs dynamically, i.e. processes may be reallocated from one processor to another. The second employs cluster allocation with k clusters and u processors in each cluster - here processes may be reallocated within a cluster only. Let 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 performance function
G(k,u,q)=\sup_ all parallel programs P

Hence, with optimal allocations, the execution of $P$ can never take more than 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 of processes. Any interprocess dependency structure is allowed for the parallel programs, except deadlock. Overhead for synchronization and reallocation is neglected only.

We further present optimal formulas which exploits a priori knowledge of the class of parallel programs intended for the multiprocessor, thus resulting in sharper optimal bounds. The function g(n,k,u,q) is the above maximum taken over all parallel programs consisting of n processes. The function s(n,v,k,u) is the same maximum, with q=n, taken over all parallel programs of $n$ processes which has a degree of parallelism characterized by a certain parallel profile vector

The functions can be used in various ways to obtain optimal performance bounds, aiding in multiprocessor architecture decisions. An immediate application is the evaluation
of heuristic allocation algorithms.

It is well known that the problems of finding the corresponding optimal allocations are NP-complete. We thus in effect present a methodology to obtain optimal control of NP-complete scheduling problems.
Subject: Computer Science\Computersystems
Computer Science\Distributed Computing
Mathematics\Discrete Mathematics
Keywords: multiprocessor, parallel computer, dynamic allocation, static allocation, cluster allocation, extremal combinatorics, optimal combinatorial formulas
Note: This article is written under the Project "Optimal Combinatorial Bounds Comparing Multiprocessor Architectures" Published in the Research Report series under the name "Optimal Performance Functions Comparing Process Allocation Strategies in Multiprocessor Systems". Revised version is accepted for publication in SIAM Journal on Computing.
URN: urn:nbn:se:bth-00012