Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
1993.
Series
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
Identifiers
URN: urn:nbn:se:bth-00012Local ID: oai:bth.se:forskinfo2AF4A213FF3517C4C12568A3002CA9A6OAI: oai:DiVA.org:bth-00012DiVA: diva2:838238
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.Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

Other links

http://traveler.bth.se/fou/forskinfo.nsf/all/2af4a213ff3517c4c12568a3002ca9a6/$file/combrev2.tex

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 120 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

urn-nbn

Altmetric score

urn-nbn
Total: 87 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf