ACM Comm 2011 03 Data Structures in the Multi-Core Age (Notes)
Data Structures in the Multicore Age |
Contents
Data Structures in the Multicore Age
People
Ideas
- Concurrent Data Structures have a trade-off between correctness and performance.
- Concurrent World Correctness - Safety, Nothing Bad Happens. Liveness, Something Good will Eventually Happen.
- Consistency Conditions - Serializability, Linearizability, Sequential consistency, and Quiescent Consistency.
- Contention Manager - Stalled threads keep the same resource while the winning thread holds it. Thus increasing traffic. A Contention Manager reduces that.
- Different Threads require a shared resource. This moves away from a Turing Machine.
- Future software engineers will need to learn how to program using these novel structures, understanding their performance benefits and their fairness limitations. - author's comment
- Progress Conditions - Deadlockfreedom, Starvation-freedom, Lockfreedom, and Wait-Freedom.
- Stalls - Threads access a shared resource one at a time.
- The data structures of our childhood—stacks, queues, and heaps—will soon disappear, replaced by looser “unordered” concurrent constructs based on distribution and randomization. - author's comment
- Threads need exclusive access to a resource. How do we get around this? Read-Only objects are trivial. Read-Write objects get exciting.
- Threads-and-Objects Model - parallel programming model where threads communicate using shared objects.
- We are experiencing a fundamental shift in the properties required of concurrent data structures and of the algorithms at the core of their implementation. - author's comment
References
- Amdahl's Law[1] Describes the theoretical speedup for a fixed system after a given bottle-neck is cleared. Consequence - the bottle-neck always moves.
Internal Links
Parent Article: Reading Notes