I've started reading a book about concurrent programming and found the part about critical reference quite difficult to understand.

 

- Definition 1: An occurrence of a variable v is defined to be a critical reference if

• a) it is assigned to in one process and has an occurrence in another process
• b) if it has an occurrence in an expression in one process and is assigned to in another

 

- Definition 2: A program satisfies limited-critical-reference (LCR) if each statement has at most 1 critical reference.

 

"Concurrent programs that satisfy the LCR restriction yield the same set of behaviors whether the statements are considered atomic or are compiled to a machine architecture with atomic load and store."

 

Do they mean that if LCR <= 1 for all statements the arbitrary interleaving of machine code instructions is such that there is no overlapping between the individual statements of the processes, that is they are executed atomically?

For LCR=1 statement B is added to the end of statement A and both are pushed through the same pipeline concurrently with other similar pairings that are not dependent on A or B.

 

In the case where statement D was dependent on statement C which was dependent on statement B which was dependent on statement A and LCR=1 then the program would compile (A+B+C+D) to run on only one pipeline/thread.

 

LCR<=1 is the minimum requirement for a program structure that will compile on a concurrent compiler.