7. Partitioning and Synchronization Design
Keywords: perfbook_html

#
7. Partitioning and Synchronization Design

This chapter describes how to design software to take advantage of the multiple CPUs that are increasingly appearing in commodity systems. It does this by presenting a number of idioms, or ``design patterns'' that can help you balance performance, scalability, and response time. As noted in earlier chapters, the most important decision you will make when creating parallel software is how to carry out the partitioning. Correctly partitioned problems lead to simple, scalable, and high-performance solutions, while poorly partitioned problems result in slow and complex solutions.

@@@ roadmap @@@

Subsections

- 7.1 Partitioning Exercises
  - 7.1.1 Dining Philosophers Problem
  - 7.1.2 Double-Ended Queue
    - 7.1.2.1 Right- and Left-Hand Locks
    - 7.1.2.2 Compound Double-Ended Queue
    - 7.1.2.3 Hashed Double-Ended Queue
    - 7.1.2.4 Compound Double-Ended Queue Revisited
    - 7.1.2.5 Double-Ended Queue Discussion
  - 7.1.3 Partitioning Example Discussion
- 7.2 Design Criteria
- 7.3 Synchronization Granularity
  - 7.3.1 Sequential Program
  - 7.3.2 Code Locking
  - 7.3.3 Data Locking
  - 7.3.4 Data Ownership
  - 7.3.5 Locking Granularity and Performance
- 7.4 Parallel Fastpath
  - 7.4.1 Reader/Writer Locking
  - 7.4.2 Hierarchical Locking
  - 7.4.3 Resource Allocator Caches
    - 7.4.3.1 Parallel Resource Allocation Problem
    - 7.4.3.2 Parallel Fastpath for Resource Allocation
    - 7.4.3.3 Data Structures
    - 7.4.3.4 Allocation Function
    - 7.4.3.5 Free Function
    - 7.4.3.6 Performance
    - 7.4.3.7 Real-World Design
- 7.5 Performance Summary