BIBLIOGRAPHY
모리스 헐리히, and 니르 샤비트. 2020. 멀티프로세서 프로그래밍. https://www.yes24.com/product/goods/3461480.
History
Related-Notes
멀티프로세서 프로그래밍
(모리스 헐리히 and 니르 샤비트 2020)
- The Art of Multiprocessor Programming
- 모리스 헐리히 and 니르 샤비트
- 생각을 바꾸는 다중코어 프로그래밍 다중코어 환경에서 프로그램을 어떻게 작성해야 하고, 위와 같은 문제를 어떻게 해결해야 하는지, 자료 구조는 어떻게 디자인해야 하는지 명확하게 밝힌 책이다. 오늘날 컴퓨터 산업은 속도 경쟁을 포기했고, 단일코어에서 다중코어 경쟁…
- 2020
Preface
Introduction
1.1. Shared Objects and Synchronization 1.2. A Fable 1.2.1. Properties of Mutual Exclusion 1.2.2. The Moral 1.3. The Producer–Consumer Problem 1.4. The Readers–Writers Problem 1.5. The Harsh Realities of Parallelization 1.6. Parallel Programming 1.7. Chapter Notes 1.8. Exercises
Principles
Mutual Exclusion
2.1. Time 2.2. Critical Sections 2.3. 2-Thread Solutions 2.3.1. The LockOne Class 2.3.2. The LockTwo Class 2.3.3. The Peterson Lock 2.4. The Filter Lock 2.5. Fairness 2.6. Lamport’s Bakery Algorithm 2.7. Bounded Timestamps 2.8. Lower Bounds on the Number of Locations 2.9. Chapter Notes 2.10. Exercises
Concurrent Objects
3.1. Concurrency and Correctness 3.2. Sequential Objects 3.3. Quiescent Consistency 3.3.1. Remarks 3.4. Sequential Consistency 3.4.1. Remarks 3.5. Linearizability 3.5.1. Linearization Points 3.5.2. Remarks 3.6. Formal Definitions 3.6.1. Linearizability 3.6.2. Compositional Linearizability 3.6.3. The Nonblocking Property 3.7. Progress Conditions 3.7.1. Dependent Progress Conditions 3.8. The Java Memory Model 3.8.1. Locks and Synchronized Blocks 3.8.2. Volatile Fields 3.8.3. Final Fields 3.9. Remarks 3.10. Chapter Notes 3.11. Exercises
Foundations of Shared Memory
4.1. The Space of Registers 4.2. Register Constructions 4.2.1. MRSW Safe Registers 4.2.2. A Regular Boolean MRSW Register 4.2.3. A Regular M-Valued MRSW Register 4.2.4. An Atomic SRSW Register 4.2.5. An Atomic MRSW Register 4.2.6. An Atomic MRMW Register 4.3. Atomic Snapshots 4.3.1. An Obstruction-Free Snapshot 4.3.2. A Wait-Free Snapshot 4.3.3. Correctness Arguments 4.4. Chapter Notes 4.5. Exercises
The Relative Power of Primitive Synchronization Operations
5.1. Consensus Numbers 5.1.1. States and Valence 5.2. Atomic Registers 5.3. Consensus Protocols 5.4. FIFO Queues 5.5. Multiple Assignment Objects 5.6. Read–Modify–Write Operations 5.7. Common2 RMW Operations 5.8. The compareAndSet() Operation 5.9. Chapter Notes 5.10. Exercises
Universality of Consensus
6.1. Introduction 6.2. Universality 6.3. A Lock-Free Universal Construction 6.4. A Wait-Free Universal Construction 6.5. Chapter Notes 6.6. Exercises
II. Practice
Spin Locks and Contention
7.1. Welcome to the Real World 7.2. Test-And-Set Locks 7.3. TAS-Based Spin Locks Revisited 7.4. Exponential Backoff 7.5. Queue Locks 7.5.1. Array-Based Locks 7.5.2. The CLH Queue Lock 7.5.3. The MCS Queue Lock 7.6. A Queue Lock with Timeouts 7.7. A Composite Lock 7.7.1. A Fast-Path Composite Lock 7.8. Hierarchical Locks 7.8.1. A Hierarchical Backoff Lock 7.8.2. A Hierarchical CLH Queue Lock 7.9. One Lock To Rule Them All 7.10. Chapter Notes 7.11. Exercises
Monitors and Blocking Synchronization
8.1. Introduction 8.2. Monitor Locks and Conditions 8.2.1. Conditions 8.2.2. The Lost-Wakeup Problem 8.3. Readers–Writers Locks 8.3.1. Simple Readers–Writers Lock 8.3.2. Fair Readers–Writers Lock 8.4. Our Own Reentrant Lock 8.5. Semaphores 8.6. Chapter Notes 8.7. Exercises
Linked Lists: The Role of Locking
9.1. Introduction 9.2. List-Based Sets 9.3. Concurrent Reasoning 9.4. Coarse-Grained Synchronization 9.5. Fine-Grained Synchronization 9.6. Optimistic Synchronization 9.7. Lazy Synchronization 9.8. Non-Blocking Synchronization 9.9. Discussion 9.10. Chapter Notes 9.11. Exercises
Concurrent Queues and the ABA Problem
10.1. Introduction 10.2. Queues 10.3. A Bounded Partial Queue 10.4. An Unbounded Total Queue 10.5. An Unbounded Lock-Free Queue 10.6. Memory Reclamation and the ABA Problem 10.6.1. A Naïve Synchronous Queue 10.7. Dual Data Structures 10.8. Chapter Notes 10.9. Exercises
Concurrent Stacks and Elimination
11.1. Introduction 11.2. An Unbounded Lock-Free Stack 11.3. Elimination 11.4. The Elimination Backoff Stack 11.4.1. A Lock-Free Exchanger 11.4.2. The Elimination Array 11.5. Chapter Notes 11.6. Exercises
Counting, Sorting, and Distributed Coordination
12.1. Introduction 12.2. Shared Counting 12.3. Software Combining 12.3.1. Overview IDLE FIRST ROOT 12.3.2. An Extended Example 12.3.3. Performance and Robustness 12.4. Quiescently Consistent Pools and Counters 12.5. Counting Networks 12.5.1. Networks That Count 12.5.2. The Bitonic Counting Network A Software Bitonic Counting Network Proof of Correctness A Periodic Counting Network A Software Periodic Counting Network 12.5.3. Performance and Pipelining 12.6. Diffracting Trees 12.7. Parallel Sorting 12.8. Sorting Networks 12.8.1. Designing a Sorting Network A Bitonic Sorting Algorithm 12.9. Sample Sorting 12.10. Distributed Coordination 12.11. Chapter Notes 12.12. Exercises
Concurrent Hashing and Natural Parallelism
13.1. Introduction 13.2. Closed-Address Hash Sets 13.2.1. A Coarse-Grained Hash Set 13.2.2. A Striped Hash Set 13.2.3. A Refinable Hash Set 13.3. A Lock-Free Hash Set 13.3.1. Recursive Split-Ordering 13.3.2. The BucketList Class 13.3.3. The LockFreeHashSet<T> Class 13.4. An Open-Addressed Hash Set 13.4.1. Cuckoo Hashing 13.4.2. Concurrent Cuckoo Hashing 13.4.3. Striped Concurrent Cuckoo Hashing 13.4.4. A Refinable Concurrent Cuckoo Hash Set 13.5. Chapter Notes 13.6. Exercises
Skiplists and Balanced Search
14.1. Introduction 14.2. Sequential Skiplists 14.3. A Lock-Based Concurrent Skiplist 14.3.1. A Bird’s-Eye View 14.3.2. The Algorithm 14.4. A Lock-Free Concurrent Skiplist 14.4.1. A Bird’s-Eye View 14.4.2. The Algorithm in Detail 14.5. Concurrent Skiplists 14.6. Chapter Notes 14.7. Exercises
Priority Queues
15.1. Introduction 15.1.1. Concurrent Priority Queues 15.2. An Array-Based Bounded Priority Queue 15.3. A Tree-Based Bounded Priority Queue 15.4. An Unbounded Heap-Based Priority Queue 15.4.1. A Sequential Heap 15.4.2. A Concurrent Heap Bird’s-Eye View In Detail 15.5. A Skiplist-Based Unbounded Priority Queue 15.6. Chapter Notes 15.7. Exercises
Futures, Scheduling, and Work Distribution
16.1. Introduction 16.2. Analyzing Parallelism 16.3. Realistic Multiprocessor Scheduling 16.4. Work Distribution 16.4.1. Work Stealing 16.4.2. Yielding and Multiprogramming 16.5. Work-Stealing Dequeues 16.5.1. A Bounded Work-Stealing Dequeue 16.5.2. An Unbounded Work-Stealing DEQueue 16.5.3. Work Balancing 16.6. Chapter Notes 16.7. Exercises
Barriers
17.1. Introduction 17.2. Barrier Implementations 17.3. Sense-Reversing Barrier 17.4. Combining Tree Barrier 17.5. Static Tree Barrier 17.6. Termination Detecting Barriers 17.7. Chapter Notes 17.8. Exercises
Transactional Memory
18.1. Introduction
18.1.1. What is Wrong with Locking? 18.1.2. What is Wrong with compareAndSet()? 18.1.3. What is Wrong with Compositionality? 18.1.4. What can We Do about It?
18.2. Transactions and Atomicity
18.3. Software Transactional Memory
18.3.1. Transactions and Transactional Threads 18.3.2. Zombies and Consistency 18.3.3. Atomic Objects 18.3.4. Dependent or Independent Progress? 18.3.5. Contention Managers 18.3.6. Implementing Atomic Objects 18.3.7. An Obstruction-Free Atomic Object Bird’s-Eye View Why It Works In Detail 18.3.8. A Lock-Based Atomic Object Bird’s-Eye View Why It Works In Detail
18.4. Hardware Transactional Memory
18.4.1. Cache Coherence 18.4.2. Transactional Cache Coherence 18.4.3. Enhancements 18.5. Chapter Notes 18.6. Exercises
III. Appendix
Software Basics
A.1. Introduction
A.2. Java
A.2.1. Threads A.2.2. Monitors A.2.3. Yielding and Sleeping A.2.4. Thread-Local Objects
A.3. C#
A.3.1. Threads A.3.2. Monitors A.3.3. Thread-Local Objects
A.4. Pthreads
A.4.1. Thread-Local Storage A.5. Chapter Notes
Hardware Basics
B.1. Introduction (and a Puzzle) B.2. Processors and Threads B.3. Interconnect B.4. Memory B.5. Caches B.5.1. Coherence B.5.2. Spinning B.6. Cache-Conscious Programming, or the Puzzle Solved B.7. Multi-Core and Multi-Threaded Architectures B.7.1. Relaxed Memory Consistency B.8. Hardware Synchronization Instructions B.9. Chapter Notes B.10. Exercises