Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimal combinatorial functions comparing multiprocess allocation performance in multiprocessor systems
Ansvarlig organisasjon
2000 (engelsk)Inngår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, s. 1816-1838Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
PHILADELPHIA: SIAM PUBLICATIONS , 2000. s. 1816-1838
Emneord [en]
dynamic allocation, cluster allocation, static allocation, scheduling, multiprocessor, optimal performance, extremal combinatorics, combinatorial formula, 0, 1-matrices, optimal partition
HSV kategori
Identifikatorer
URN: urn:nbn:se:bth-8139ISI: 000086865300002Lokal ID: oai:bth.se:forskinfoAE06DEF9CDAFB99FC12575B000212885OAI: oai:DiVA.org:bth-8139DiVA, id: diva2:835828
Tilgjengelig fra: 2012-09-18 Laget: 2009-05-08 Sist oppdatert: 2018-01-11bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Personposter BETA

Lennerstad, HåkanLundberg, Lars

Søk i DiVA

Av forfatter/redaktør
Lennerstad, HåkanLundberg, Lars
I samme tidsskrift
SIAM journal on computing (Print)

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 103 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf