Introduction to Multiprocessors - Fundamentals of Computer Organization and Architecture - page 248

If a new request arrives while the memory is busy servicing a previous request, the
memory module sends a wait signal through the memory controller to the processor
making the new request. In response, the requesting processor may hold its request
on the line until the memory becomes free or it may repeat its request some time
later. If the arbitration unit receives two requests, it selects one of them and passes
it to the memory controller. Again, the denied request can be either held to be
served next or it may be repeated some time later.
The arbitration unit may not be adequate to organize the use of the memory
module by the two processors. The main problem will be in the sequencing of inter-
actions between memory accesses from the two processors. Consider the following
two scenarios for accessing the same memory location M(1000) by the two pro-
cessors P a and P b (Fig. 11.9). Let us also assume that the initial value stored in
memory location M(1000) is 150. Note that in both cases, the sequence of instruc-
tions performed by each processor is the same. The only difference between the two
scenarios is the relative time at which the two processors update the value in
M(1000). A careful examination of the two scenarios will show that the value
stored in location M(1000) after the first scenario will be 151 while the stored
value following the second scenario will be 152.
The above illustrative example presents the case of a nonfunctional behavior of
this simple shared memory system. Such an example should demonstrate the basic
requirements for the success of such systems. These requirements are:

1. A mechanism for conflict resolution among rival processors
2. A technique for specifying the sequencing constraints
3. A mechanism for enforcing the sequencing specifications

Approaches for satisfying these basic requirements are covered in Chapter 4 of our
topic on Advanced Computer Architecture and Parallel Processing (see reference list).
The use of different interconnection networks in a shared memory multiprocessor
system leads to systems with one of the following characteristics:

1. Shared memory architecture with a uniform memory access (UMA)
2. Cache-only memory architecture (COMA)
3. Distributed shared memory architecture with nonuniform memory access
(NUMA)

Cycle Processor P a Processor P b Cycle Processor P a Processor P b

1
2
3
4
5
6

a ← M(1000); 1

2
3
4
5
6

a ← M(1000);

b ← M(1000); a ← a + 1;

a ← a + 1; M(1000) ← a;

b ← b + 1; b ← M(1000)

M(1000) ← a;

b ← b + 1;

M(1000) ← b; M(1000) ← b;

Scenario 1 Scenario 2

Figure 11.9 Potential shared memory problem