The Art of Multiprocessor Programming, Revised Reprint

The Art of Multiprocessor Programming, Revised Reprint

1st Edition - May 22, 2012
  • Authors: Maurice Herlihy, Nir Shavit
  • eBook ISBN: 9780123977953

Purchase options

Purchase options
DRM-free (PDF, EPub, Mobi)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

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.

Key Features

  • 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

Readership

Students in multiprocessor and multicore programming courses and engineers working with multiprocessor and multicore systems.

Table of Contents

  • Dedication

    Acknowledgments

    Product Note

    Preface

    Suggested Ways to Teach the Art of Multiprocessor Programming

    1. Introduction

    1.1 Shared Objects and Synchronization

    1.2 A Fable

    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

    I Principles

    2. Mutual Exclusion

    2.1 Time

    2.2 Critical Sections

    2.3 2-Thread Solutions

    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

    3. Concurrent Objects

    3.1 Concurrency and Correctness

    3.2 Sequential Objects

    3.3 Quiescent Consistency

    3.4 Sequential Consistency

    3.5 Linearizability

    3.6 Formal Definitions

    3.7 Progress Conditions

    3.8 The Java Memory Model

    3.9 Remarks

    3.10 Chapter Notes

    4. Foundations of Shared Memory

    4.1 The Space of Registers

    4.2 Register Constructions

    4.3 Atomic Snapshots

    4.4 Chapter Notes

    5. The Relative Power of Primitive Synchronization Operations

    5.1 Consensus Numbers

    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

    6. 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

    II Practice

    7. 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.6 A Queue Lock with Timeouts

    7.7 A Composite Lock

    7.8 Hierarchical Locks

    7.9 One Lock To Rule Them All

    7.10 Chapter Notes

    8. Monitors and Blocking Synchronization

    8.1 Introduction

    8.2 Monitor Locks and Conditions

    8.3 Readers–Writers Locks

    8.4 Our Own Reentrant Lock

    8.5 Semaphores

    8.6 Chapter Notes

    9. Linked Lists

    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

    10. 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.7 Dual Data Structures

    10.8 Chapter Notes

    11. Concurrent Stacks and Elimination

    11.1 Introduction

    11.2 An Unbounded Lock-Free Stack

    11.3 Elimination

    11.4 The Elimination Backoff Stack

    11.5 Chapter Notes

    12. Counting, Sorting, and Distributed Coordination

    12.1 Introduction

    12.2 Shared Counting

    12.3 Software Combining

    12.4 Quiescently Consistent Pools and Counters

    12.5 Counting Networks

    12.6 Diffracting Trees

    12.7 Parallel Sorting

    12.8 Sorting Networks

    12.9 Sample Sorting

    12.10 Distributed Coordination

    12.11 Chapter Notes

    13. Concurrent Hashing and Natural Parallelism

    13.1 Introduction

    13.2 Closed-Address Hash Sets

    13.3 A Lock-Free Hash Set

    13.4 An Open-Addressed Hash Set

    13.5 Chapter Notes

    14. Skiplists and Balanced Search

    14.1 Introduction

    14.2 Sequential Skiplists

    14.3 A Lock-Based Concurrent Skiplist

    14.4 A Lock-Free Concurrent Skiplist

    14.5 Concurrent Skiplists

    14.6 Chapter Notes

    15. Priority Queues

    15.1 Introduction

    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.5 A Skiplist-Based Unbounded Priority Queue

    15.6 Chapter Notes

    16. Futures, Scheduling, and Work Distribution

    16.1 Introduction

    16.2 Analyzing Parallelism

    16.3 Realistic Multiprocessor Scheduling

    16.4 Work Distribution

    16.5 Work-Stealing Dequeues

    16.6 Chapter Notes

    17. 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

    18. Transactional Memory

    18.1 Introduction

    18.2 Transactions and Atomicity

    18.3 Software Transactional Memory

    18.4 Hardware Transactional Memory

    18.5 Chapter Notes

    III Appendix

    A. Software Basics

    B. Hardware Basics

    Index

Product details

  • No. of pages: 536
  • Language: English
  • Copyright: © Morgan Kaufmann 2012
  • Published: May 22, 2012
  • Imprint: Morgan Kaufmann
  • eBook ISBN: 9780123977953

About the Authors

Maurice Herlihy

Maurice Herlihy received an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University, on the staff of DEC Cambridge Research Lab, and is currently a Professor in the Computer Science Department at Brown University. Dr. Herlihy is an ACM Fellow, and is the recipient of the 2003 Dijkstra Prize in Distributed Computing. He shared the 2004 Gödel Prize with Nir Shavit, with whom he also shared the 2012 Edsger W. Dijkstra Prize In Distributed Computing.

Affiliations and Expertise

Brown University, Providence, RI, USA

Nir Shavit

Nir Shavit received a B.A. and M.Sc. from the Technion and a Ph.D. from the Hebrew University, all in Computer Science. From 1999 to 2011 he served as a member of technical staff at Sun Labs and Oracle Labs. He shared the 2004 Gödel Prize with Maurice Herlihy, with whom he also shared the 2012 Edsger W. Dijkstra Prize in Distributed Computing. He is a Professor in the Electrical Engineering and Computer Science Department at M.I.T. and the Computer Science Department at Tel-Aviv University.

Affiliations and Expertise

Professor of Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA