Massively Parallel Systems Synchronization

• The topic is synchronization in massively parallel systems, covering synchronization problems, solutions, and primitives.

Synchronization

• When multiple agents access a shared hardware resource, only one agent can use the resource at a time to avoid conflicts.
• Synchronization is a computing problem dating back to multitasking operating systems.
• Reliable synchronization between threads or processes transcends memory coherence.
• Shared variables indicate if a resource is busy.
• Updating shared variables is a fundamental problem in computer architecture and operating systems.

Synchronization Problem on Uniprocessors

• Threads accessing a shared writable variable must do so under mutual exclusion, where only one process can access the variable at any one time.
• A race condition occurs when the outcome depends on the order of access.

Synchronization Problem on Multiprocessors

• Threads may run concurrently, requiring program statements to appear atomic or use mutual exclusion to prevent overlapping in time.

Critical Section

• Mutual exclusion is solved by critical sections
• Critical sections of code access shared resources and cannot be accessed concurrently by more than one thread.

Effects of Race Conditions

• Failures with the Therac-25 radiation therapy machine.
• The 2003 North American Blackout which affected millions.

Disabling Interrupts

• Disabling interrupts can solve critical sections on time-shared uniprocessor systems with a single context.
• Disabling interrupts is ineffective in multicore systems or hardware multithreaded cores, as threads execute in parallel.

Locks

• Locks are synchronization primitives that protect critical sections.
• A value of 0 indicates lock is free.
• A value of 1 (or any non-zero value) indicates lock is set.
• To acquire a lock, a thread sets it to 1.
• To release a lock, a thread sets it to 0.
• While a lock is set, threads must wait until it is released.
• Direct implementation of locks via loads and stores to shared memory can lead to deadlock.

Simple Software Lock

• Simple software locks are described using assembly-like instructions.
• Simple software lock is not atomic, multiple threads can acquire the lock at the same time.

Read-Modify-Write (RMW) Instructions

• RMW instructions read a value from memory, modify it, and write it back atomically.
• RMW instructions can return success or failure.
• Modern ISAs have atomic RMW instructions.

Test-And-Set (T&S)

• Assembly-like operation for test and set is shown.
• Sets a lock to 1 atomically, returning the old value.
• If locks are cacheable, executing T&S in a loop generates bus traffic.

Optimizing T&S

• Frequency of Ts&S can be reduced with back-off pauses.
• Exponential back-off delay is k x c at ith trial.
• Test with ordinary loads - when value is 0, try to obtain lock with T&S.
• The Test and test&set method works well with cache reduces bus traffic

Atomic Swap

• Instructions exchange a value in a register for a value in memory.

Compare-And-Swap

• Instructions swap a value in register with a value in memory if a condition is met.
• They are useful for implementing atomic queue insertions/removals.

Fetch-And-Increment

• Fetches and returns a value in memory, then atomically increments it.
• If the value returned is 0 synchronization variable is free, otherwise synchronization variable is locked

Load-Locked and Store-Conditional (LL/SC)

• LL/SC do not fit well in RISC pipeline or OoO processor because require atomic execution of two memory accesses
• LL Rx, lv reads memory [lv] into register Rx.
• SC Ry, lv tries to store Ry in memory [lv], succeeds if no other thread has written to lv since LL.
• LL reads a value from memory and marks that location as "linked.”
• SC attempts to write a new value to the memory location only if the "link" is still valid.
• Sequence LL-SC was atomic.
• Fancier atomic operations can be implemented by adding code between LL and SC.

Advantages of LL and SC

• Easier to implement in pipeline.
• Flexible and versatile RMW primitives can be implemented by changing code between LL and SC.

Implementation of LL/SC

• Bus interface supports LL-bit and lock address register
• LL-bit also cleared when lock variable ejected from cache and on context switches
• Having multiple LL-bits and lock address registers solves several locks!

LL/SC vs. Traditional RMW

• RMW instructions combine read and write into one atomic operation.
• LL/SC are two separate instructions, giving more flexibility.
• LL/SC is more like a flexible "building block" for atomic operations.

Barrier Synchronization

• A barrier is a synchronization protocol amongst multiple threads.
• All threads must reach barrier before any thread is allowed to continue

Semaphores

• Semaphores (Dijkstra) are higher-level synchronization primitives built on top of RMW instructions.
• Semaphores are integer variables with two operations, P (acquire) and V (release).
• P decrements if sem >0, else waits; V increments to release.
• Can be implemented via busy or blocking waiting.

Blocking vs. Busy Waiting

• Blocking: calling thread scheduled out, high overhead, processor works on something else.
• Busy waiting: Waiting thread repeatedly tests a location until its value changes.
• Busy waiting is better when scheduling overhead is larger than the expected wait time and there is no other thread to run.