Ä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
Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems
Ansvarig organisation
1993 (Engelska)Rapport (Övrigt vetenskapligt)
Abstract [en]

For the execution of an arbitrary parallel program P, consisting of a set of processes, 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 G(k,u,q)=\sup_ all parallel programs P T_c(P,k,u)}{T_d(P,q)}. 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. Any interprocess dependency structure is allowed for the parallel programs, except deadlock. Overhead for synchronization and reallocation is neglected only. We further present optimal formulas which exploits a priori knowledge of the class of parallel programs intended for the multiprocessor, thus resulting in sharper optimal bounds. The function g(n,k,u,q) is the above maximum taken over all parallel programs consisting of n processes. The function s(n,v,k,u) is the same maximum, with q=n, taken over all parallel programs of $n$ processes which has a degree of parallelism characterized by a certain parallel profile vector v=(v_1,...,v_n). The functions can be used in various ways to obtain optimal performance bounds, aiding in multiprocessor architecture decisions. An immediate application is the evaluation of heuristic allocation algorithms. It is well known that the problems of finding the corresponding optimal allocations are NP-complete. We thus in effect present a methodology to obtain optimal control of NP-complete scheduling problems.

Ort, förlag, år, upplaga, sidor
1993.
Serie
Blekinge Institute of Technology Research report, ISSN 1103-1581 ; 3
Nyckelord [en]
multiprocessor, parallel computer, dynamic allocation, static allocation, cluster allocation, extremal combinatorics, optimal combinatorial formulas
Nationell ämneskategori
Matematisk analys Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:bth-00012Lokalt ID: oai:bth.se:forskinfo2AF4A213FF3517C4C12568A3002CA9A6OAI: oai:DiVA.org:bth-00012DiVA, id: diva2:838238
Anmärkning
This article is written under the Project "Optimal Combinatorial Bounds Comparing Multiprocessor Architectures" Published in the Research Report series under the name "Optimal Performance Functions Comparing Process Allocation Strategies in Multiprocessor Systems". Revised version is accepted for publication in SIAM Journal on Computing.Tillgänglig från: 2012-09-18 Skapad: 2000-03-15 Senast uppdaterad: 2018-01-11Bibliografiskt granskad

Open Access i DiVA

fulltext(262 kB)165 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 262 kBChecksumma SHA-512
55811b949bfeaf2b44893032ef91b5746fd27bd222cc86ccc6bc6f0ee8c6910063230dd9bc3189d23758d81d54a3c91c27e94845d61c6b16e37bf178d428612e
Typ fulltextMimetyp application/pdf

Övriga länkar

http://traveler.bth.se/fou/forskinfo.nsf/all/2af4a213ff3517c4c12568a3002ca9a6/$file/combrev2.tex

Personposter BETA

Lennerstad, HåkanLundberg, Lars

Sök vidare i DiVA

Av författaren/redaktören
Lennerstad, HåkanLundberg, Lars
Matematisk analysDatavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 165 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: 148 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