Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


538 users

0 votes
In the exam of 2020, there is an exercise on a thread containing if-statements rather than just read-and-write instructions.

Are such statements relevant for our exam or only the read-write thread we have seen in examples?

Also, do we have to know the Steinke-Nutt classification? We haven't really discussed it in depth compared to the other MSMs.
in * TF "Emb. Sys. and Rob." by (140 points)

1 Answer

+1 vote

Testing whether a thread execution is possible under a certain weak memory consistency model expects usually an abstraction of a thread's execution to just read and write instructions. Hence, you may be surprised to see such an exercise where if-statements occur. However, you can easily translate the if-statement to a read operation. For instance, if(y=2) z := 1 executes z := 1 only if y=2 holds, and to that end, we have to perform a read(y,2) before the write(z,1) in that thread. You can see that also in the example solution. If another value than 2 would be read for y, the other thread is empty, and then the result is trivial.

Apart from that simple translation of statements to read/write sequences, statements are not relevant for testing whether thread executions are consistent for a weak memory consistency model.

About the Steinke-Nutt classification: Yes, you should know it, but that can be reduced to the following basics which are essentially:

  • It is a systematic approach to define many possible weak memory consistency models. The four basic models GPO, GDO, GWO, GAO can be combined to define 2^4 = 16 weak memory consistency models that may or may not have these basic models integrated. The 16 weak memory consistency models form a lattice concerning their strength.
  • GPO is just another name for PRAM consistency; its definition is exactly the same.
  • GDO is equivalent to cache consistency; its definition is however processor-oriented instead of variable-oriented as the definition of cache consistency. So, it makes this way all definitions processor-oriented.
  • You do not need to consider the proof that GDO is equivalent to cache consistency, but you should know it.
  • GPO+GDO is almost equivalent to processor consistency; and it is believed to be the real intention of the latter.
  • slide 115 of the chapter summarizes the main results of Steinke-Nutt

by (166k points)
Imprint | Privacy Policy