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
Bounding the gain of changing the number of memory modules in shared memory multiprocessors
Responsible organisation
1997 (English)In: Nordic Journal of Computing, ISSN 1236-6064, Vol. 4, no 3, 233-58 p.Article in journal (Refereed) Published
Abstract [en]

We consider a multiprocessor, with p processors and m memory modules. If more than one processor want to access a memory module simultaneously, these accesses will be serialized due to memory contention. The completion time of a program executing on this system is thus affected by the way addresses are mapped onto memory modules, and finding a mapping which results in minimal completion time is NP-hard. If we change the number of memory modules from m to m’, while keeping the number processors constant, we will generally change the minimal completion time. The gain of changing the number of memory modules from m to m’ for a certain program is defined as the ratio between the minimal completion times, using m and m’ modules respectively. Here, we present an optimal upper bound on the maximum gain of changing the number of memory modules, as a function of m, m’ and p, including the case when m’ is infinitely large. The bound is obtained by investigating a mathematical formulation. The mathematical tools involved are essentially elementary combinatorics. The formula for calculating the bound is mathematically complicated but can be rapidly computed for reasonable m, m’ and p. This bound makes it possible to do price-performance trade-offs and to compare any mapping of addresses to memory modules with the optimal case. The results are applicable to different multiprocessor architectures, e.g. systems with crossbar networks and systems with multiple buses. The results also make it possible to calculate optimal performance bounds for multiprocessors containing cache memories: as well as for multiprocessors with no cache memories. Moreover, we discuss how the results can be used for calculating bounds for programs with as well as without synchronizations.

Place, publisher, year, edition, pages
Finland: Publishing Assoc. Nordic Journal of Comput , 1997. Vol. 4, no 3, 233-58 p.
Keyword [en]
computational complexity, shared memory systems, synchronisation
National Category
Mathematical Analysis Computer Science
Identifiers
URN: urn:nbn:se:bth-9667Local ID: oai:bth.se:forskinfoAF56222AE7AC710DC12568A3002CAB71OAI: oai:DiVA.org:bth-9667DiVA: diva2:837573
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
In the same journal
Nordic Journal of Computing
Mathematical AnalysisComputer Science

Search outside of DiVA

GoogleGoogle Scholar

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