Algorithms and Parallel Computing

8.2 COMPARING DAG AND DCG ALGORITHMS

Figure 8.1a is an example of a DAG algorithm and Fig. 8.1b is an example of a DCG algorithm. An algorithm represented with a DAG requires a certain time to complete its tasks and the data flow is unidirectional from the inputs to the outputs. Thus, each task in the graph is completed once for each instance of the algorithm. When all tasks have been completed, the algorithm is terminated or another instance of it is started with another set of input data.

Figure 8.1 Example directed graphs for nonserial–parallel algorithms. (a) Directed acyclic graph (DAG). (b) Directed cyclic graph (DCG).

The DCG is most commonly encountered in discrete time feedback control systems such as adaptive filters and digital controllers for plant control. An example of a feedback control systems is a car automatic speed control and the airplane autopilot. The input is supplied to task T₀ for prefiltering or for input signal conditioning. Task T₁ accepts the conditioned input signal and the conditioned feedback output signal. The output of task T₁ is usually referred to as the error signal, and this signal is fed to task T₂ to produce the output signal. An algorithm represented by a DCG usually operates on a set of input data streams and produces a set of output data streams. The time between samples is called the sample time, which is equal to the maximum delay exhibited ...