14.4 DECIMATOR SCHEDULING
As usual, we employ an affine timing function
where the row vector s = [s1 s2] is the scheduling vector and the column vector p = [n k]t is any point in the dependence graph. The first component refers to the horizontal axis and the second component refers to the vertical axis.
Assigning time values to the nodes of the dependence graph transforms the dependence graph to a directed acyclic graph (DAG) as discussed in Chapters 10 and 11. More specifically, the DAG can be thought of as a serial–parallel algorithm (SPA) where the parallel tasks could be implemented using a thread pool or parallel processors for software or hardware implementations, respectively. The different stages of the SPA are accomplished using barriers or clocks for software or hardware implementations, respectively.
The restrictions on our timing function were discussed in Chapters 10 and 11. We assume that the input data x(n) arrive at consecutive times. Let us study the times associated with the points at the bottom of the graph, p = [n 0]t. Two input samples, x(n) and x(n + 1), arrive at the two points, p1 = [n 0]t and p2 = [n + 1 0]t, respectively. Applying the scheduling function in Eq. 14.3, we get
(14.4)
(14.5)
Since the difference t(p2) − t(p1) = 1, we must have ...
Get Algorithms and Parallel Computing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
