Algorithms and Parallel Computing

14.11 INTERPOLATOR SCHEDULING

As usual, we employ an affine timing function:

(14.29)

where the row vector s = [s₁ s₂] 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. 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, p₁ = [n 0]^t and p₂ = [nL + 1 0]^t, respectively. Applying the scheduling function in Eq. 14.3, we get

(14.30)

(14.31)

Since the difference t(p₂) − t(p₁) = L, we must have s₁ = 1. A valid scheduling vector that satisfies input data timing must be specified as

(14.32)

The value of s₂ will be determined by our choice of whether we need to pipeline or broadcast the output sample y(n). Choosing s₂ = 0 would result in the broadcast of y(n). Choosing s₂ = ±1 would result in ...