Critical reference

[sbsin]

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?

[LaurieAG]

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.