Algorithms and Parallel Computing

10.8 SOFTWARE AND HARDWARE IMPLEMENTATIONS OF THE DAG TECHNIQUE

By using different scheduling functions and projection directions, the DAG is converted to a set of tasks that can be executed concurrently in software threads or in hardware systolic arrays. The technique maps the DAG of the algorithm to simultaneous multithreaded (SMT) tasks or single instruction multiple data stream (SIMD)/systolic hardware. In the following section, we shall refer to the computations at each node as tasks, knowing that tasks translate to threads in software or PEs in hardware. In all cases discussed in this section we choose the scheduling function s = [1 –1].

10.8.1 Design 1: Projection Direction d₁ = [1 0]^t

Since the chosen projection direction is along the extremal ray direction, the number of concurrent tasks will be finite. A point p = [i j]^t ∈ DAG maps to the point . The pipeline is shown in Fig. 10.5. Task T(i) stores the filter coefficient a(i). The filter output is obtained from the rightmost PE. Notice that both inputs x and y are pipelined between the PEs. Some explanation of notation in the is in order. An arrow connecting tasks T(i) to task T(j) indicates that the output data of T(i) is stored in memory and is made available to T(j) at the next time step. An arrow exiting a task indicates ...