Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
2000 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, 1816-1838 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
PHILADELPHIA: SIAM PUBLICATIONS , 2000. 1816-1838 p.
Keyword [en]
dynamic allocation, cluster allocation, static allocation, scheduling, multiprocessor, optimal performance, extremal combinatorics, combinatorial formula, 0, 1-matrices, optimal partition
National Category
Mathematical Analysis Computer Science
Identifiers
URN: urn:nbn:se:bth-8139ISI: 000086865300002Local ID: oai:bth.se:forskinfoAE06DEF9CDAFB99FC12575B000212885OAI: oai:DiVA.org:bth-8139DiVA: diva2:835828
Available from: 2012-09-18 Created: 2009-05-08 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
In the same journal
SIAM journal on computing (Print)
Mathematical AnalysisComputer Science

Search outside of DiVA

GoogleGoogle Scholar

Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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