Summary of 24th March's Lecture

Memory Consistency Policies

P1 ->    1. A=1  

             2. PRINT(B,C)

P2 ->    1. B=1  

             2. PRINT(A,C)

P3 ->    1. C=1  

             2. PRINT(A,B) )

If programs are allowed to execute instructions out of program order then there are 6! = 720 possible execution interleavings.

However, if individual program order is maintained then the total possible execution interleavings reduce to :

=> 720/(2*2*2)= 90.

From these 90 interleavings not all combinations can result. For example, the outcome 000000 isn’t possible if processors execute instructions in program order only.

Memory Consistency Issues

Behavior of a shared memory system as observed in the processor is called memory model.

In general, choosing a memory model involves making a compromise between a strong model minimally restricting software and a weak model offering efficient implementation.

Sequential Consistency Model

Lamport ( 1979)

A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

Release Consistency Model

One of the most relaxed memory models.

It requires that synchronization accesses in the program be identified and classified as either acquire or release.

Condition for release consistency :

• Before a read/write is performed all previous acquires must be performed.

• Before a release is performed all previous read/store must be performed.

Lazy Release Consistency

It has an additional condition that before any acquire is performed any previous read/store must be performed.

Dubois (1989)

The following two sufficient conditions were provided to achieve sequential consistency in shared-memory access:

(a) Before a load is allowed to perform with respect to any other processor, all previous load accesses must be globally performed and all previous store accesses must be performed with respect to all processors.

(b) Before a store is allowed to perform with respect to any other processor, all previous load accesses must be globally performed and all previous store accesses must be performed with respect to all processors.

Some others model that could be classified b/w SC and RC:

• Sindhu (1992) - Total store order.

• Goodman (1990) - Processor Consistency.

The stores and swaps issued by a processor are placed in a dedicated store buffer for the processor, which is operated as first-in-first-out. Thus the order in which memory executes

these operations for a given processor is the same as the order ill which the processor issued them (in program order).

The memory order corresponds to the order in which the switch is thrown from one processor to another.

A load by a processor first checks its store buffer to see if it contains a store to the same location. If it does, then the load returns the value of the most recent such store. Otherwise, the load goes directly to memory, Since not all loads go to memory immediately, loads in general do not appear in memory order. A processor is logically blocked from issuing further operations until the load returns a value.

BY : SAHIL AGGARWAL & SANDEEP SHOKEEN