Bounding the gain of changing the number of memory modules in shared memory multiprocessors

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Author(s): Lars Lundberg, Håkan Lennerstad
Title: Bounding the gain of changing the number of memory modules in shared memory multiprocessors
Journal: Nordic Journal of Computing
Year: 1997
Volume: 4
Issue: 3
Pagination: 233-58
ISSN: 1236-6064
Publisher: Publishing Assoc. Nordic Journal of Comput
City: Finland
Organization: Blekinge Institute of Technology
Department: Dept. of Computer Science and Business Administration (Institutionen för datavetenskap och ekonomi)
*** Error ***
+46 455 780 00
*** Error ***
Authors e-mail:
Language: English
Abstract: 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.
Subject: Computer Science\Computersystems
Computer Science\Distributed Computing
Mathematics\Discrete Mathematics
Keywords: computational complexity, shared memory systems, synchronisation