System disruptions
We are currently experiencing disruptions on the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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 Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems
Responsible organisation
1992 (English)Report (Other academic)
Abstract [en]

Consider a multiprocessor with $k$ identical processors, executing parallel programs consisting of $n$ processes. Let $T_s(P)$ and $T_d(P)$ denote the execution times for the program $P$ with optimal static and dynamic allocations respectively, i. e. allocations giving minimal execution time. We derive a general and explicit formula for the maximal execution time ratio $g(n,k)=\max T_s(P)/T_d(P)$, where the maximum is taken over all programs $P$ consisting of $n$ processes. Any interprocess dependency structure for the programs $P$ is allowed, only avoiding deadlock. Overhead for synchronization and reallocation is neglected. Basic properties of the function $g(n,k)$ are established, from which we obtain a global description of the function. Plots of $g(n,k)$ are included. The results are obtained by investigating a mathematical formulation. The mathematical tools involved are essentially tools of elementary combinatorics. The formula is a combinatorial function applied on certain extremal matrices corresponding to extremal programs. It is mathematically complicated but rapidly computed for reasonable $n$ and $k$, in contrast to the np-completeness of the problems of finding optimal allocations.

Place, publisher, year, edition, pages
1992.
Series
Blekinge Tekniska Högskola Forskningsrapport, ISSN 1103-1581 ; 1
Keywords [en]
multiprocessor, parallel computer, static allocation, dynamic allocation, extremal combinatorics
National Category
Mathematical Analysis Computer Sciences
Identifiers
URN: urn:nbn:se:bth-00014Local ID: oai:bth.se:forskinfo326482736585211AC12568A3002CA9A7OAI: oai:DiVA.org:bth-00014DiVA, id: diva2:838200
Note
Also published in SIAM Journal of Computing, Vol. 24, No. 4, pp. 751-764, August 1995.Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

fulltext(341 kB)385 downloads
File information
File name FULLTEXT01.pdfFile size 341 kBChecksum SHA-512
0e833b805fac6e24f7d847edb7ae44bf19f4f6292b5833b35b5770f712ed2119f84f26949d7e59631bfe3e1c4c60eb4168709f1b25e4ef45fa6122d68f8ddb2a
Type fulltextMimetype application/pdf

Other links

http://traveler.bth.se/fou/forskinfo.nsf/all/326482736585211ac12568a3002ca9a7/$file/siamrev.tex

Authority records

Lennerstad, HåkanLundberg, Lars

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
Mathematical AnalysisComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 385 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 338 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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