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 Execution Time Estimate of Static Versus Dynamic Allocation in Multiprocessor Systems
Responsible organisation
1995 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 24, no 4, 751-764 p.Article in journal (Refereed) Published
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 following maximal execution time ratio: g(n, k) $EQ 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 by 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
Philadelphia, Pa.: SIAM publications , 1995. Vol. 24, no 4, 751-764 p.
Keyword [en]
Multiprocessing systems, Optimization, Resource allocation, Estimation, Parallel processing systems, Computer systems programming, Computer system recovery, Synchronization, Functions, Numerical methods, Combinatorial mathematics, Matrix algebra, Computational complexity
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-10253ISI: A1995RP07000005Local ID: oai:bth.se:forskinfo1740CDD2344525C5C12568A3002CAB4EOAI: oai:DiVA.org:bth-10253DiVA: diva2:838335
Note
See also Research Report 1992/1 from University of Karlskrona/Ronneby 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

fulltext(220 kB)43 downloads
File information
File name FULLTEXT01.pdfFile size 220 kBChecksum SHA-512
f9d15cac45068b48f38a5aed2c4a16fed2c0e2f5754ec2f425ef3d2e3944425430622b454e66dc53a4c96ce5a227b8aeb2cf7dd61ed2ab8038e83cb2c4e36859
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
In the same journal
SIAM journal on computing (Print)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 43 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

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