Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • 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
An Optimal Upper Bound on the Minimal Completion Time in Distributed Supercomputing
Ansvarlig organisasjon
1994 (engelsk)Konferansepaper, Publicerat paper (Fagfellevurdert) Published
Abstract [en]

We first consider an MIMD multiprocessor configuration with n processors. A parallel program, consisting of n processes, is executed on this system-one process per processor. The program terminates when all processes are completed. Due to synchronizations, processes may be blocked waiting for events in other processes. Associated with the program is a parallel profile vector nu , index i (1<or=i<or=n) in this vector indicates the percentage of the total execution time when i processes are executing. We then consider a distributed MIMD supercomputer with k clusters, containing u processors each. The same parallel program, consisting of n processes, is executed on this system. Each process can only be executed by processors in the same cluster. Finding a schedule with minimal completion time in this case is NP-hard. We are interested in the gain of using n processors compared to using k clusters containing u processors each. The gain is defined by the ratio between the minimal completion time using processor clusters and the completion time using a schedule with one process per processor. We present the optimal upper bound for this ratio in the form of an analytical expression in n, nu , k and u. We also demonstrate how this result can be used when evaluating heuristic scheduling algorithms (12 Refs.)

sted, utgiver, år, opplag, sider
Manchester: ACM; NY, USA , 1994.
Emneord [en]
computational complexity, parallel machines, parallel programming, scheduling
HSV kategori
Identifikatorer
URN: urn:nbn:se:bth-9923Lokal ID: oai:bth.se:forskinfo6DCB0DDF5D88D32DC12568A3002CAB57ISBN: 0897916654 (tryckt)OAI: oai:DiVA.org:bth-9923DiVA, id: diva2:837910
Konferanse
Proceedings of International Conference on Supercomputing '94
Merknad
This article is written under the Project "Optimal Combinatorial Bounds Comparing Multiprocessor Architectures"Tilgjengelig fra: 2012-09-18 Laget: 2000-03-15 Sist oppdatert: 2018-01-11bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Personposter BETA

Lundberg, LarsLennerstad, Håkan

Søk i DiVA

Av forfatter/redaktør
Lundberg, LarsLennerstad, Håkan

Søk utenfor DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 96 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • 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