Change search
ReferencesLink to record
Permanent link

Direct link
Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems
Responsible organisation
1993 (English)Report (Other academic)
Abstract [en]

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 T_c(P,k,u)}{T_d(P,q)}. 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 v=(v_1,...,v_n). 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.

Place, publisher, year, edition, pages
Blekinge Tekniska Högskola Forskningsrapport, ISSN 1103-1581 ; 3
Keyword [en]
multiprocessor, parallel computer, dynamic allocation, static allocation, cluster allocation, extremal combinatorics, optimal combinatorial formulas
National Category
Mathematical Analysis Computer Science
URN: urn:nbn:se:bth-00012Local ID: diva2:838238
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.Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(262 kB)16 downloads
File information
File name FULLTEXT01.pdfFile size 262 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links$file/combrev2.tex

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
Mathematical AnalysisComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 16 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link