Algorithms and Parallel Computing

8.3 PARALLELIZING NSPA ALGORITHMS REPRESENTED BY A DAG

This chapter discusses techniques for extracting parallelism from DAG. Each task accepts input data and produces output results. We say a task, T_i, is dependent on task T_j if the output of T_j is used as its input to T_i. When the number of algorithm tasks is small, the algorithm can be described by a directed graph, which shows no regular patterns of interconnections among the tasks. Figure 8.1a shows an example of representing an NSPA by a DAG. The graph is characterized by two types of constructs: the nodes, which describe the tasks comprising the algorithm, and the directed edges, which describe the direction of data flow among the tasks. The edges exiting a node represent an output, and when they enter a node, they represent an input. Chapter 1 defined the types of nodes and edges in a DG: input node/edge, output node/edge, and intermediate node/edge.

Figure 8.1 shows the algorithm as drawn or sketched by the programmer or some graphing tool. Nodes 0, 1, and 2 are the only input nodes, and nodes 7 and 9 are the only output nodes. The algorithm has three primary inputs: in₀, in₁, and in₂, and three primary outputs: out₀, out₁, and out₂.

Example 8.1

A very popular series in computer science is the Fibonacci sequence:

An algorithm to calculate the nth Fibonacci number is given by

where N₀ = 0 and N₁ = 1. Draw a DAG to ...