29.1 Introduction and Objectives
In this chapter we discuss how C++ supports the creation of programs and algorithms by decomposing them into components that can potentially run in parallel. In general terms, potential or exploitable concurrency involves being able to structure code to permit a problem's subproblems to run on multiple processors. Each subproblem is implemented by a task. A task (Quinn, 2004) is a program in local memory in combination with a collection of I/O ports. Tasks send data to other tasks through their output ports and they receive data from other tasks through their input ports. It is obvious from this discussion that tasks can depend on other tasks because they need the data that is produced by other tasks. We model these dependencies by a data dependency graph or task graph. This is a directed graph where each vertex represents a task to be completed and an edge from vertex a to vertex b means that task a must complete before task b begins. The absence of an edge between two vertices means that there is no dependency between them and hence the related tasks can be run in parallel.
The goals of this chapter are to:
- Analyse a program for potential parallelism. Create a data dependency graph to identify the main tasks and their dependencies.
- Apply task and data decomposition patterns to break a program into pieces that can execute concurrently (Mattson, Sanders and Massingill, 2005).
- Choose an algorithm structure ...