You are previewing Parallel and Distributed Programming Using C++.
O'Reilly logo
Parallel and Distributed Programming Using C++

Book Description

Parallel and Distributed Programming Using C++ provides an up-close look at how to build software that can take advantage of multiprocessor computers. Simple approaches for programming parallel virtual machines are presented, and the basics of cluster application development are explained. Through an easy-to-understand overview of multithreaded programming, this book also shows you how to write software components that work together over a network to solve problems and do work.

Parallel and Distributed Programming Using C++ provides an architectural approach to parallel programming for computer programmers, software developers, designers, researchers, and software architects. It will also be useful for computer science students.

  • Demonstrates how agents and blackboards can be used to make parallel programming easier

  • Shows object-oriented approaches to multitasking and multithreading

  • Demonstrates how the UML is used to document designs that require parallel or distributed programming

  • Contains the new POSIX/UNIX IEEE Standard for the Pthreads library

Table of Contents

  1. Copyright
    1. Dedication
  2. Preface
    1. The Challenges
    2. The Approach
    3. Why C++?
    4. Libraries for Parallel and Distributed Programming
    5. The New Single UNIX Specification Standard
    6. Who is This Book For?
    7. Development Environments Supported
    8. Ancillaries
      1. UML Diagrams
      2. Program Profiles
      3. Sidebars
      4. Testing and Code Reliability
    9. Acknowledgments
  3. 1. The Joys of Concurrent Programming
    1. 1.1. What is Concurrency?
      1. 1.1.1. The Two Basic Approaches to Achieving Concurrency
    2. 1.2. The Benefits of Parallel Programming
      1. 1.2.1. The Simplest Parallel Model (PRAM)
      2. 1.2.2. The Simplest Parallel Classification
    3. 1.3. The Benefits of Distributed Programming
      1. 1.3.1. The Simplest Distributed Programming Models
      2. 1.3.2. The Multiagent (Peer-to-Peer) Distributed Model
    4. 1.4. The Minimal Effort Required
      1. 1.4.1. Decomposition
      2. 1.4.2. Communication
      3. 1.4.3. Synchronization
    5. 1.5. The Basic Layers of Software Concurrency
      1. 1.5.1. Concurrency at the Instruction Level
      2. 1.5.2. Concurrency at the Routine Level
      3. 1.5.3. Concurrency at the Object Level
      4. 1.5.4. Concurrency of Applications
    6. 1.6. No Keyword Support for Parallelism in C++
      1. 1.6.1. The Options for Implementing Parallelism Using C++
      2. 1.6.2. MPI Standard
      3. 1.6.3. PVM: A Standard for Cluster Programming
      4. 1.6.4. The CORBA Standard
      5. 1.6.5. Library Implementations Based on Standards
    7. 1.7. Programming Environments for Parallel and Distributed Programming
    8. Summary—Toward Concurrency
  4. 2. The Challenges of Parallel and Distributed Programming
    1. 2.1. The Big Paradigm Shift
    2. 2.2. Coordination Challenges
      1. Problem #1 Data Race
      2. Problem #2 Indefinite Postponement
      3. Problem #3 Deadlock
      4. Problem #4 Communication Difficulties
    3. 2.3. Sometimes Hardware Fails and Software Quits
    4. 2.4. Too Much Parallelization or Distribution Can Have Negative Consequences
    5. 2.5. Selecting a Good Architecture Requires Research
    6. 2.6. Different Techniques for Testing and Debugging are Required
    7. 2.7. The Parallel or Distributed Design Must Be Communicated
    8. Summary
  5. 3. Dividing C++ Programs into Multiple Tasks
    1. 3.1. Process: A Definition
      1. 3.1.1. Two Kinds of Processes
      2. 3.1.2. Process Control Block
    2. 3.2. Anatomy of a Process
    3. 3.3. Process States
    4. 3.4. Process Scheduling
      1. 3.4.1. Scheduling Policy
      2. 3.4.2. Using the ps Utility
      3. 3.4.3. Setting and Returning the Process Priority
    5. 3.5. Context Switching
    6. 3.6. Creating a Process
      1. 3.6.1. Parent–Child Process Relationship
        1. 3.6.1.1. The pstree Utility
      2. 3.6.2. Using the fork() Function Call
      3. 3.6.3. Using the exec Family of System Calls
        1. 3.6.3.1. execl() Functions
        2. 3.6.3.2. execv() Functions
        3. 3.6.3.3. Determining Restrictions on exec() Functions
        4. 3.6.3.4. Reading and Setting Environment Variables
      4. 3.6.4. Using system() to Spawn Processes
      5. 3.6.5. The POSIX Functions for Spawning Processes
      6. 3.6.6. Identifying the Parent and Child with Process Management Functions
    7. 3.7. Terminating a Process
      1. 3.7.1. The exit(), kill() and abort() Calls
    8. 3.8. Process Resources
      1. 3.8.1. Types of Resources
      2. 3.8.2. POSIX Functions to Set Resource Limits
    9. 3.9. What are Asynchronous and Synchronous Processes?
      1. 3.9.1. Synchronous and Asynchronous Processes Created with fork(), exec(), system(), and posix_spawn() Functions
      2. 3.9.2. The wait() Function Call
    10. 3.10. Dividing the Program into Tasks
      1. 3.10.1. Processes Along Function and Object Lines
    11. Summary
  6. 4. Dividing C++ Programs into Multiple Threads
    1. 4.1. Threads: A Definition
      1. 4.1.1. Thread Context Requirements
      2. 4.1.2. Threads and Processes: A Comparison
        1. 4.1.2.1. Differences between Threads and Processes
        2. 4.1.2.2. Threads Controlling Other Threads
      3. 4.1.3. Advantages of Threads
        1. 4.1.3.1. Context Switches during Low Processor Availability
        2. 4.1.3.2. Better Throughput
        3. 4.1.3.3. Simpler Communication between Concurrently Executing Parts
        4. 4.1.3.4. Simplify Program Structure
      4. 4.1.4. Disadvantages of Threads
        1. 4.1.4.1. Threads Can Corrupt Process Data Easier
        2. 4.1.4.2. One Bad Thread Can Kill the Entire Program
        3. 4.1.4.3. Threads are Not as Reusable by Other Programs
    2. 4.2. The Anatomy of a Thread
      1. 4.2.1. Thread Attributes
    3. 4.3. Thread Scheduling
      1. 4.3.1. Thread States
      2. 4.3.2. Scheduling and Thread Contention Scope
      3. 4.3.3. Scheduling Policy and Priority
        1. 4.3.3.1. Changing Thread Priority
    4. 4.4. Thread Resources
    5. 4.5. Thread Models
      1. 4.5.1. Delegation Model
      2. 4.5.2. Peer-to-Peer Model
      3. 4.5.3. Pipeline Model
      4. 4.5.4. Producer-Consumer Model
      5. 4.5.5. SPMD and MPMD for Threads
    6. 4.6. Introduction to the Pthread Library
    7. 4.7. The Anatomy of a Simple Threaded Program
      1. 4.7.1. Compiling and Linking Multithreaded Programs
    8. 4.8. Creating Threads
      1. 4.8.1. Getting the Thread Id
      2. 4.8.2. Joining Threads
      3. 4.8.3. Creating Detached Threads
      4. 4.8.4. Using the Pthread Attribute Object
        1. 4.8.4.1. Creating Detached Threads Using the Pthread Attribute Object
    9. 4.9. Managing Threads
      1. 4.9.1. Terminating Threads
        1. 4.9.1.1. Cancellation Points
        2. 4.9.1.2. Cleaning Up Before Termination
      2. 4.9.2. Managing the Thread’s Stack
      3. 4.9.3. Setting Thread Scheduling and Priorities
        1. 4.9.3.1. Setting Contention Scope of a Thread
      4. 4.9.4. Using sysconf()
      5. 4.9.5. Managing a Critical Section
    10. 4.10. Thread Safety and Libraries
    11. 4.11. Dividing Your Program into Multiple Threads
      1. 4.11.1. Using the Delegation Model
      2. 4.11.2. Using the Peer-to-Peer Model
      3. 4.11.3. Using the Pipeline Model
      4. 4.11.4. Using the Producer–Consumer Model
      5. 4.11.5. Creating Multithreaded Objects
    12. Summary
  7. 5. Synchronizing Concurrency between Tasks
    1. 5.1. Coordinating Order of Execution
      1. 5.1.1. Relationships between Synchronized Tasks
      2. 5.1.2. Start-to-Start (SS) Relationship
      3. 5.1.3. Finish-to-Start (FS) Relationship
      4. 5.1.4. Start-to-Finish Relationship
      5. 5.1.5. Finish-to-Finish Relationship
    2. 5.2. Synchronizing Access to Data
      1. 5.2.1. PRAM Model
        1. 5.2.1.1. Concurrent and Exclusive Memory Access
    3. 5.3. What are Semaphores?
      1. 5.3.1. Semaphore Operations
      2. 5.3.2. Mutex Semaphores
        1. 5.3.2.1. Using the Mutex Attribute Object
        2. 5.3.2.2. Using Mutex Semaphores to Manage Critical Sections
      3. 5.3.3. Read–Write Locks
        1. 5.3.3.1. Using Read-Write Locks to Implement Access Policy
      4. 5.3.4. Condition Variables
        1. 5.3.4.1. Using Condition Variables to Manage Synchronization Relationships
    4. 5.4. Synchronization: An Object-Oriented Approach
    5. Summary
  8. 6. Adding Parallel Programming Capabilities to C++ Through the PVM
    1. 6.1. The Classic Parallelism Models Supported by PVM
    2. 6.2. The PVM Library for C++
      1. 6.2.1. Compiling and Linking a C++/PVM Program
      2. 6.2.2. Executing a PVM Program as a Standalone
        1. 6.2.2.1. Starting PVM Programs Using the PVM Console
        2. 6.2.2.2. Start PVM Programs Using XPVM
      3. 6.2.3. A PVM Preliminary Requirements Checklist
      4. 6.2.4. Combining the C++ Runtime Library and the PVM Library
      5. 6.2.5. Approaches to Using PVM Tasks
        1. 6.2.5.1. Using the SPMD (SIMD) Model with PVM and C++
        2. 6.2.5.2. Using the MPMD (MIMD) Model with PVM and C++
    3. 6.3. The Basic Mechanics of the PVM
      1. 6.3.1. Process Management and Control Routines
      2. 6.3.2. Message Packing and Sending
    4. 6.4. Accessing Standard Input (stdin) and Standard Output (stdout) within PVM Tasks
      1. 6.4.1. Retrieving Standard Output (cout) from a Child Task
    5. Summary
  9. 7. Error Handling, Exceptions, and Software Reliability
    1. 7.1. What is Software Reliability?
    2. 7.2. Failures in Software Layers and Hardware Components
    3. 7.3. Definitions of Defects Depend on Software Specifications
    4. 7.4. Recognizing Where to Handle Defects versus Where to Handle Exceptions
    5. 7.5. Software Reliability: A Simple Plan
      1. 7.5.1. Plan A: The Resumption Model, Plan B: The Termination Model
    6. 7.6. Using Map Objects in Error Handling
    7. 7.7. Exception Handling Mechanisms in C++
      1. 7.7.1. The Exception Classes
        1. 7.7.1.1. The runtime_error Classes
        2. 7.7.1.2. The logic_error Classes
        3. 7.7.1.3. Deriving New Exception Classes
        4. 7.7.1.4. Protecting the Exception Classes from Exceptions
    8. 7.8. Event Diagrams, Logic Expressions, and Logic Diagrams
    9. Summary
  10. 8. Distributed Object-Oriented Programming in C++
    1. 8.1. Decomposition and Encapsulation of the Work
      1. 8.1.1. Communication between Distributed Objects
      2. 8.1.2. Synchronization of the Interaction between the Local and the Remote Objects
      3. 8.1.3. Error and Exception Handling in the Distributed Environment
    2. 8.2. Accessing Objects in Other Address Spaces
      1. 8.2.1. IOR Access to Remote Objects
      2. 8.2.2. ORBS (Object Request Brokers)
      3. 8.2.3. Interface Definition Language (IDL): A Closer Look at CORBA Objects
    3. 8.3. The Anatomy of a Basic CORBA Consumer
    4. 8.4. The Anatomy of a CORBA Producer
    5. 8.5. The Basic Blueprint of a CORBA Application
      1. 8.5.1. The IDL Compiler
      2. 8.5.2. Obtaining IOR for Remote Objects
    6. 8.6. The Naming Service
      1. 8.6.1. Using the Naming Service and Creating Naming Contexts
      2. 8.6.2. A Name Service Consumer/Client
    7. 8.7. A Closer Look at Object Adapters
    8. 8.8. Implementation and Interface Repositories
    9. 8.9. Simple Distributed Web Services Using CORBA
    10. 8.10. The Trading Service
    11. 8.11. The Client/Server Paradigm
    12. Summary
  11. 9. SPMD and MPMD Using Templates and the MPI
    1. 9.1. Work Breakdown Structure for the MPI
      1. 9.1.1. Differentiating Tasks by Rank
      2. 9.1.2. Grouping Tasks by Communicators
      3. 9.1.3. The Anatomy of an MPI Task
    2. 9.2. Using Template Functions to Represent MPI Tasks
      1. 9.2.1. Instantiating Templates and SPMD (Datatypes)
      2. 9.2.2. Using Polymorphism to Implement MPMD
      3. 9.2.3. Adding MPMD with Function Objects
    3. 9.3. Simplifying MPI Communications
      1. 9.3.1. Overloading the << and >> Operators for MPI Communication
    4. Summary
  12. 10. Visualizing Concurrent and Distributed System Design
    1. 10.1. Visualizing Structures
      1. 10.1.1. Classes and Objects
        1. 10.1.1.1. Displaying Specifics about Attributes and Services
        2. 10.1.1.2. Ordering the Attributes and Services
        3. 10.1.1.3. Template Classes
      2. 10.1.2. The Relationship between Classes and Objects
        1. 10.1.2.1. Interface Classes
      3. 10.1.3. The Organization of Interactive Objects
    2. 10.2. Visualizing Concurrent Behavior
      1. 10.2.1. Collaborating Objects
        1. 10.2.1.1. Processes and Threads
        2. 10.2.1.2. Showing the Multiple Flows of Control and Communication
      2. 10.2.2. Message Sequences between Objects
      3. 10.2.3. The Activities of Objects
      4. 10.2.4. State Machines
        1. 10.2.4.1. Concurrent Substates
      5. 10.2.5. Distributed Objects
    3. 10.3. Visualizing the Whole System
      1. 10.3.1. Visualizing Deployment of Systems
      2. 10.3.2. The Architecture of a System
    4. Summary
  13. 11. Designing Components That Support Concurrency
    1. 11.1. Taking Advantage of Interface Classes
    2. 11.2. A Closer Look at Object-Oriented Mutual Exclusion and Interface Classes
      1. 11.2.1. Semi-Fat Interfaces that Support Concurrency
    3. 11.3. Maintaining the Stream Metaphor
      1. 11.3.1. Overloading the <<, >> Operators for PVM Streams
    4. 11.4. User-Defined Classes Designed to Work with PVM Streams
    5. 11.5. Object-Oriented Pipes and fifos as Low-Level Building Blocks
      1. 11.5.1. Connecting Pipes to iostream Objects Using File Descriptors
      2. 11.5.2. Accessing Anonymous Pipes Using the ostream_iterator
      3. 11.5.3. fifos (Named Pipes), iostreams, and the ostream_iterator Classes
        1. 11.5.3.1. fifo Interface Classes
    6. 11.6. Framework Classes Components for Concurrency
    7. Summary
  14. 12. Implementing Agent-Oriented Architectures
    1. 12.1. What are Agents?
      1. 12.1.1. Agents: A First-Cut Definition
      2. 12.1.2. Types of Agents
      3. 12.1.3. What is the Difference between Objects and Agents?
    2. 12.2. What is Agent-Oriented Programming?
      1. 12.2.1. Why Agents Work for Distributed Programming
      2. 12.2.2. Agents and Parallel Programming
    3. 12.3. Basic Agent Components
      1. 12.3.1. Cognitive Data Structures
        1. 12.3.1.2. Inference Methods
    4. 12.4. Implementing Agents in C++
      1. 12.4.1. Proposition Datatypes and Belief Structures
      2. 12.4.2. The Agent Class
        1. 12.4.2.1. The Agent Loop
        2. 12.4.2.2. The Agent’s Inference Methods
      3. 12.4.3. Simple Autonomy
    5. 12.5. Multiagent Systems
    6. Summary
  15. 13. Blackboard Architectures Using PVM, Threads, and C++ Components
    1. 13.1. The Blackboard Model
    2. 13.2. Approaches to Structuring the Blackboard
    3. 13.3. The Anatomy of a Knowledge Source
    4. 13.4. The Control Strategies for Blackboards
    5. 13.5. Implementing the Blackboard Using CORBA Objects
      1. 13.5.1. The CORBA Blackboard: An Example
      2. 13.5.2. The Implementation of the black_board Interface Class
      3. 13.5.3. Spawning the Knowledge Sources in the Blackboard’s Constructor
        1. 13.5.3.1. Spawning Knowledge Sources Using PVM Tasks
        2. 13.5.3.2. Connecting Blackboard and the Knowledge Sources
        3. 13.5.3.3. Activating Knowledge Sources Using POSIX spawn()
    6. 13.6. Implementing the Blackboard Using Global Objects
    7. 13.7. Activating Knowledge Sources Using Pthreads
    8. Summary
  16. A. Diagrams
    1. A.1. Class and Object Diagrams
    2. A.2. Interaction Diagrams
      1. A.2.1. Collaboration Diagrams
      2. A.2.2. Sequence Diagrams
      3. A.2.3. Activity Diagrams
    3. A.3. State Diagrams
    4. A.4. Package Diagrams
  17. B. System Interfaces
  18. Bibliography