Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An Optimal Upper Bound on the Minimal Completion Time in Distributed Supercomputing
Ansvarig organisation
1994 (Engelska)Konferensbidrag, Publicerat paper (Refereegranskat) 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.)

Ort, förlag, år, upplaga, sidor
Manchester: ACM; NY, USA , 1994.
Nyckelord [en]
computational complexity, parallel machines, parallel programming, scheduling
Nationell ämneskategori
Matematisk analys Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:bth-9923Lokalt ID: oai:bth.se:forskinfo6DCB0DDF5D88D32DC12568A3002CAB57ISBN: 0897916654 (tryckt)OAI: oai:DiVA.org:bth-9923DiVA, id: diva2:837910
Konferens
Proceedings of International Conference on Supercomputing '94
Anmärkning
This article is written under the Project "Optimal Combinatorial Bounds Comparing Multiprocessor Architectures"Tillgänglig från: 2012-09-18 Skapad: 2000-03-15 Senast uppdaterad: 2018-01-11Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Lundberg, LarsLennerstad, Håkan

Sök vidare i DiVA

Av författaren/redaktören
Lundberg, LarsLennerstad, Håkan
Matematisk analysDatavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 96 träffar
RefereraExporteraLänk till posten
Permanent länk

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