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

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • 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
A Method for Bounding the Minimal Completion Time in Multiprocessors
Ansvarig organisation
2002 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

The cluster systems used today usually prohibit that a running process on one node is reallocated to another node. A parallel program developer thus has to decide how processes should be allocated to the nodes in the cluster. Finding an allocation that results in minimal completion time is NP-hard and (non-optimal) heuristic algorithms have to be used. One major drawback with heuristics is that we do not know if the result is close to optimal or not. In this paper we present a method for finding a guaranteed minimal completion time for a given program. The method can be used as a bound that helps the user to determine when it is worth-while to continue the heuristic search. Based on some parameters derived from the program, as well as some parameters describing the hardware platform, the method produces the minimal completion time bound. The method includes an aggressive branch-and-bound algorithm that has been shown to reduce the search space to 0.0004%. A practical demonstration of the method is presented using a tool that automatically derives the necessary program parameters and produces the bound without the need for a multiprocessor. This makes the method accessible for practitioners.

Ort, förlag, år, upplaga, sidor
2002.
Serie
Blekinge Institute of Technology Research report, ISSN 1103-1581 ; 3
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:bth-00202Lokalt ID: oai:bth.se:forskinfoAC131D74EA74944DC1256B6100540F3FOAI: oai:DiVA.org:bth-00202DiVA, id: diva2:837588
Tillgänglig från: 2012-09-18 Skapad: 2002-02-15 Senast uppdaterad: 2018-01-11Bibliografiskt granskad

Open Access i DiVA

fulltext(256 kB)128 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 256 kBChecksumma SHA-512
e4362a8009dc3d0fdf0c159b8c5cbb67e6af4c35816308281795afb47042dc7c463924f8137ee3c3bf7a6c1302617779cda67cedf2da5fab0eb0b209e2a03255
Typ fulltextMimetyp application/pdf

Personposter BETA

Lundberg, Lars

Sök vidare i DiVA

Av författaren/redaktören
Lundberg, Lars
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 128 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • 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