Parallel Programming at TU München

• Multiple concurrent executions aka. single program multiple data
• master/worker
• pipelining
• arbitrary task dependencies

Drawback 1: possible imbalance caused by workload

Drawback 2: possible imbalance caused by machine

Memory/Cache Coherency: reasoning about updates to one memory location

Memory Consistency: reasoning about updates to several memory locations

• Program order for loads/stores are preserved
• All stores eventually become visible
• All processors see the same order of writes

A multiprocessor system is sequentially consistent if the result of any
execution is the same as if the operations of all processors were executed in
some sequential order, and the operations of each individual processor appear
in this sequence in the order specified by the program”

Why is the program order requirement hard?
• Network can reorder
• Use of write-buffers
• Compiler optimizations
Why is the atomicity requirement hard?
• A write has to take place instantly with respect to all processors
• Can lead to a system-wide serialization of writes
We need to relax consistency requirements
• Necessary to achieve well performing systems
• Increase the level of concurrency
• Compensate with synchronization primitives
• Need them anyway for proper synchronization of contents
• Can implicitly execute consistency operations
Create the “illusion” of sequentially consistency

nowait
threads do not synchronize after the parallel loop