CS 452/652 Winter 2023 - Lecture 21

Apr 4, 2023 prev

Multi-Core Programming

Parallelism

multiple independent execution streams
- unknown and non-deterministic execution
- somewhat similar to effects of asynchronous interrupt
- shared counter needs atomic operations

atomic assignment sufficient, example: Dekker's Algorithm (software locking)

shared state

  int wantIn[2] = {false, false};
  int turn = 0;

thread initialization (other thread: me = 1)
```
  int me = 0;
  int you = 1 - me;
```

critical section

  wantIn[me] = true;
  while (wantIn[you]) {
    if (turn != me) {
      wantIn[me] = false;
      while (turn != me) { // wait }
      wantIn[me] = true;
    }
  }
  ... // critical section
  turn = you;
  wantIn[me] = false;

with atomic RMW operations: ticket lock

shared state
```
  int ticket = 0;
  int serving = 0;
```

critical section

  int myticket = ticket++;
  while (myticket != serving) { // wait }
  ... // critical section
  serving++;

ticket++ must be atomic operation

Memory Ordering

each core respects sequential data dependencies
- what about sequential execution without data dependencies?
- example, assume A and B initialized to 0, then:
```
  Thread 1    Thread 2
  A=1         B=1
  print(B)    print(A)
```
- possible outcomes? 00 is counter-intuitive...
memory hierarchy & pipeling → out-of-order execution
- write buffers, caching hierarchy
- amplifies parallelism challenge
think of the effects as operations that "float" around
Dekker: need memory barriers after each wantIn[me] = true
example memory model: total-store-order (TSO)
- write can be delayed after read
- write/write not reordered
- does not avoid 00 outcome above
RISC processors (such as ARM) often implement more relaxed models (more reordering)
trade-off: programming semantics ↔ performance

Mechanisms

C 'volatile' avoids compiler reordering and register caching
atomic instructions: consistency/correctness of parallel operations
memory barrier/fence: execution ordering

Sequential Consistency

one of many consistency models
- formal description effects of parallel operations on mutable state
- formal reasoning about program correctness
- some model more restricted, some more relaxed
intuitive model: direct shared memory (no buffering)
- writes become globally visible in local per-processor order
- some global sequence of writes
- 'print' example above: sequential consistency prohibits 00 outcome
atomic operation guarantees SC for atomic variables
memory barrier guarantees SC for critical section data
- need memory barrier before and after critical section

Additional Notes

Java 'volatile' essentially means Sequential Consistency
x86 atomic instructions include barrier semantics

Student Course Perception Surveys

students were given time to complete the student course perception survey.