AbstractWe 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.
Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); C.4 [Performance of Systems]; G.2.1 [Discrete Mathematics]: Combinatorics
Additional Key Words and Phrases: performance bound, memory modules, multiprocessor, crossbar network, combinatorics
Selected references
- Cynthia Dwork, Maurice Herlihy, and Orli Waarts. Contention in shared memory algorithms. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 174-183, San Diego, California, 16-18 May 1993.