Optimal combinatorial functions comparing multiprocess allocation performance in multiprocessor systems

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Author(s): Håkan Lennerstad, Lars Lundberg
Title: Optimal combinatorial functions comparing multiprocess allocation performance in multiprocessor systems
Journal: SIAM JOURNAL ON COMPUTING
Year: 2000
Pagination: 1816-1838
ISSN: 0097-5397
Publisher: SIAM PUBLICATIONS
City: PHILADELPHIA
ISI number: 000086865300002
Organization: Blekinge Institute of Technology
Department: Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)
Dept. of Telecommunications and Mathematics S-37179 Karlskrona
+46 455 38 50 00
Language: English
Abstract: For the execution of an arbitrary parallel program P, consisting of a set of processes with any executable interprocess dependency structure, 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 [GRAPHICS] 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. Overhead for synchronization and reallocation is neglected only. We further present a tight bound which exploits a priori knowledge of the class 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 over all parallel programs consisting of n processes. The functions G and g can be used in various ways to obtain tight performance bounds, aiding in multiprocessor architecture decisions.
Subject: Computer Science\Computersystems
Computer Science\Distributed Computing
Mathematics\Discrete Mathematics
Keywords: dynamic allocation, cluster allocation, static allocation, scheduling, multiprocessor, optimal performance, extremal combinatorics, combinatorial formula, 0, 1-matrices, optimal partition
Edit