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
An Optimal Upper Bound on the Minimal Completion Time in Distributed Supercomputing
Responsible organisation
1994 (English)Conference paper, (Refereed) 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.)

Place, publisher, year, edition, pages
Manchester: ACM; NY, USA , 1994.
Keyword [en]
computational complexity, parallel machines, parallel programming, scheduling
National Category
Mathematical Analysis Computer Science
Identifiers
URN: urn:nbn:se:bth-9923Local ID: oai:bth.se:forskinfo6DCB0DDF5D88D32DC12568A3002CAB57ISBN: 0897916654 (print)OAI: oai:DiVA.org:bth-9923DiVA: diva2:837910
Conference
Proceedings of International Conference on Supercomputing '94
Note
This article is written under the Project "Optimal Combinatorial Bounds Comparing Multiprocessor Architectures"Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Lundberg, LarsLennerstad, Håkan
Mathematical AnalysisComputer Science

Search outside of DiVA

GoogleGoogle Scholar

Total: 26 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