Memory consistency

From LinuxMIPS
Jump to: navigation, search

Consistency models

Strong ordering

This is a term which is used in the manuals of some of the older MIPS processors including the R4000 and R10000 but very rarely elsewhere. It has a quite reasonable definition in the R4000 User's Manual which also used to be available as an application notice. The catch - the manual doesn't make it explicit that the R4000 is strongly ordered. I (Ralf) believe this is because reordering may also happen at system level, so giving the promise just in the processors manual is worth much. The situation of the R10000 is similar sequentially ordered.

Sequential ordering

Sequential ordering was defined by Leslie Lamport as "...the results 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."

The system provides sequential consistency if every node of the system sees the (write) operations on the same memory part (page, virtual object, cell etc) in the same order, although the order may be different from the order as defined by real time (as observed by hypothetical external observer or global clock) of issuing the operations.

Processor consistency

This is a slightly more relaxed consistency model than sequential ordering. It only guarantees that writes on one particular processor are being seen by another processor in program order. Processor consistency is also known as PRAM (pipelined random access memory) or FIFO consistency.

Weak consistency

This model basically gives no guarantee. R->R, R->W, W->R and W->W reordering are allowed. To allow software to control reordering the SYNC instruction must be used.

The SYNC instruction

Introduced by the R4000 in 1991 this instruction is the safety net of the MIPS III and later architectures. The SYNC instruction contains a 5 bit field with vendor specific semantics. The standard SYNC instruction has these five bits zeroed; other values are reserved for implementation specific variants of SYNC.

Processor cycles
R10000 1
34K 13

The LL and SC instructions

LL, SC and their 64-bit brothers LLD and SCD are defined by the MIPS32 and MIPS64 architecture to not imply a SYNC instruction. Which doesn't forbid an implementation to do it anyway and indeed R4000 and R4400 processors (which predate MIPS32 and MIPS64 by many years) SC and SCD imply a SYNC instruction. The R10000 on the other hand doesn't.

Consistency models on MIPS systems

The consistency model of a system is influenced by both the processor and the rest of the system. For this reason the table below describes both the system and processor together. An "X" indicates that a particular ordering is relaxed. Multiprocessor kernels also run on the MIPS 34K but this really is a single, multithreaded, in-order core which is presented to the kernel and applications: to software this looks like processor consistency.

System CPU Consistency

Model

R->R R->W W->R W->W R->LL W->LL R->SC W->SC LL->R LL->W SC->L SC->W
Origin R10000 sequential
Various 34K processor
BCM1250 SB1 weak X X X  ?  ?  ?  ?  ?  ?  ?  ?
RM9000 E9000 weak X X X X  ?  ? X X  ?  ?  ?  ?

Consistency models on other architectures

R->R R->W W->R W->W Dep. Read
Alpha X X X X X
PARISC CPUs
PARISC Systems X X X X
x86 X X X
x86 OOStore X X X X
AMD64 X X
Power X X X X
IA-64 X X X X
SPARC RMO X X X X
SPARC PSO X X
SPARC TSO X
zSeries X

References