Cover image for The Art of Multiprocessor Programming, Revised Reprint

The Art of Multiprocessor Programming, Revised Reprint

Author Nir Shavit , Maurice Herlihy
Release Date: 2012/06/01
ISBN: 9780123973375
Topic:
0%
34
Chapters
0-1
Hours read
0k
Total Words
    Start Reading Now    
       Add to Wishlist       
View table of contents

Book Description

Revised and updated with improvements conceived in parallel programming courses, The Art of Multiprocessor Programming is an authoritative guide to multicore programming. It introduces a higher level set of software development skills than that needed for efficient single-core programming. This book provides comprehensive coverage of the new principles, algorithms, and tools necessary for effective multiprocessor programming. Students and professionals alike will benefit from thorough coverage of key multiprocessor programming issues.

  • This revised edition incorporates much-demanded updates throughout the book, based on feedback and corrections reported from classrooms since 2008
  • Learn the fundamentals of programming multiple threads accessing shared memory
  • Explore mainstream concurrent data structures and the key elements of their design, as well as synchronization techniques from simple locks to transactional memory systems
  • Visit the companion site and download source code, example Java programs, and materials to support and enhance the learning experience

Table of Contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright
  5. Dedication
  6. Acknowledgments
  7. Product Note
  8. Preface
  9. Suggested Ways to Teach the Art of Multiprocessor Programming
  10. 1. Introduction
    1. 1.1 Shared Objects and Synchronization
    2. 1.2 A Fable
    3. 1.3 The Producer–Consumer Problem
    4. 1.4 The Readers–Writers Problem
    5. 1.5 The Harsh Realities of Parallelization
    6. 1.6 Parallel Programming
    7. 1.7 Chapter Notes
  11. I Principles
    1. 2. Mutual Exclusion
      1. 2.1 Time
      2. 2.2 Critical Sections
      3. 2.3 2-Thread Solutions
      4. 2.4 The Filter Lock
      5. 2.5 Fairness
      6. 2.6 Lamport's Bakery Algorithm
      7. 2.7 Bounded Timestamps
      8. 2.8 Lower Bounds on the Number of Locations
      9. 2.9 Chapter Notes
    2. 3. Concurrent Objects
      1. 3.1 Concurrency and Correctness
      2. 3.2 Sequential Objects
      3. 3.3 Quiescent Consistency
      4. 3.4 Sequential Consistency
      5. 3.5 Linearizability
      6. 3.6 Formal Definitions
      7. 3.7 Progress Conditions
      8. 3.8 The Java Memory Model
      9. 3.9 Remarks
      10. 3.10 Chapter Notes
    3. 4. Foundations of Shared Memory
      1. 4.1 The Space of Registers
      2. 4.2 Register Constructions
      3. 4.3 Atomic Snapshots
      4. 4.4 Chapter Notes
    4. 5. The Relative Power of Primitive Synchronization Operations
      1. 5.1 Consensus Numbers
      2. 5.2 Atomic Registers
      3. 5.3 Consensus Protocols
      4. 5.4 FIFO Queues
      5. 5.5 Multiple Assignment Objects
      6. 5.6 Read–Modify–Write Operations
      7. 5.7 Common2 RMW Operations
      8. 5.8 The compareAndSet() Operation
      9. 5.9 Chapter Notes
    5. 6. Universality of Consensus
      1. 6.1 Introduction
      2. 6.2 Universality
      3. 6.3 A Lock-Free Universal Construction
      4. 6.4 A Wait-Free Universal Construction
      5. 6.5 Chapter Notes
  12. II Practice
    1. 7. Spin Locks and Contention
      1. 7.1 Welcome to the Real World
      2. 7.2 Test-And-Set Locks
      3. 7.3 TAS-Based Spin Locks Revisited
      4. 7.4 Exponential Backoff
      5. 7.5 Queue Locks
      6. 7.6 A Queue Lock with Timeouts
      7. 7.7 A Composite Lock
      8. 7.8 Hierarchical Locks
      9. 7.9 One Lock To Rule Them All
      10. 7.10 Chapter Notes
    2. 8. Monitors and Blocking Synchronization
      1. 8.1 Introduction
      2. 8.2 Monitor Locks and Conditions
      3. 8.3 Readers–Writers Locks
      4. 8.4 Our Own Reentrant Lock
      5. 8.5 Semaphores
      6. 8.6 Chapter Notes
    3. 9. Linked Lists
      1. 9.1 Introduction
      2. 9.2 List-Based Sets
      3. 9.3 Concurrent Reasoning
      4. 9.4 Coarse-Grained Synchronization
      5. 9.5 Fine-Grained Synchronization
      6. 9.6 Optimistic Synchronization
      7. 9.7 Lazy Synchronization
      8. 9.8 Non-Blocking Synchronization
      9. 9.9 Discussion
      10. 9.10 Chapter Notes
    4. 10. Concurrent Queues and the ABA Problem
      1. 10.1 Introduction
      2. 10.2 Queues
      3. 10.3 A Bounded Partial Queue
      4. 10.4 An Unbounded Total Queue
      5. 10.5 An Unbounded Lock-Free Queue
      6. 10.6 Memory Reclamation and the ABA Problem
      7. 10.7 Dual Data Structures
      8. 10.8 Chapter Notes
    5. 11. Concurrent Stacks and Elimination
      1. 11.1 Introduction
      2. 11.2 An Unbounded Lock-Free Stack
      3. 11.3 Elimination
      4. 11.4 The Elimination Backoff Stack
      5. 11.5 Chapter Notes
    6. 12. Counting, Sorting, and Distributed Coordination
      1. 12.1 Introduction
      2. 12.2 Shared Counting
      3. 12.3 Software Combining
      4. 12.4 Quiescently Consistent Pools and Counters
      5. 12.5 Counting Networks
      6. 12.6 Diffracting Trees
      7. 12.7 Parallel Sorting
      8. 12.8 Sorting Networks
      9. 12.9 Sample Sorting
      10. 12.10 Distributed Coordination
      11. 12.11 Chapter Notes
    7. 13. Concurrent Hashing and Natural Parallelism
      1. 13.1 Introduction
      2. 13.2 Closed-Address Hash Sets
      3. 13.3 A Lock-Free Hash Set
      4. 13.4 An Open-Addressed Hash Set
      5. 13.5 Chapter Notes
    8. 14. Skiplists and Balanced Search
      1. 14.1 Introduction
      2. 14.2 Sequential Skiplists
      3. 14.3 A Lock-Based Concurrent Skiplist
      4. 14.4 A Lock-Free Concurrent Skiplist
      5. 14.5 Concurrent Skiplists
      6. 14.6 Chapter Notes
    9. 15. Priority Queues
      1. 15.1 Introduction
      2. 15.2 An Array-Based Bounded Priority Queue
      3. 15.3 A Tree-Based Bounded Priority Queue
      4. 15.4 An Unbounded Heap-Based Priority Queue
      5. 15.5 A Skiplist-Based Unbounded Priority Queue
      6. 15.6 Chapter Notes
    10. 16. Futures, Scheduling, and Work Distribution
      1. 16.1 Introduction
      2. 16.2 Analyzing Parallelism
      3. 16.3 Realistic Multiprocessor Scheduling
      4. 16.4 Work Distribution
      5. 16.5 Work-Stealing Dequeues
      6. 16.6 Chapter Notes
    11. 17. Barriers
      1. 17.1 Introduction
      2. 17.2 Barrier Implementations
      3. 17.3 Sense-Reversing Barrier
      4. 17.4 Combining Tree Barrier
      5. 17.5 Static Tree Barrier
      6. 17.6 Termination Detecting Barriers
      7. 17.7 Chapter Notes
    12. 18. Transactional Memory
      1. 18.1 Introduction
      2. 18.2 Transactions and Atomicity
      3. 18.3 Software Transactional Memory
      4. 18.4 Hardware Transactional Memory
      5. 18.5 Chapter Notes
  13. III Appendix
    1. A. Software Basics
    2. B. Hardware Basics
  14. Index
18.222.69.152