Algorithms and Parallel Computing

18.6 DESIGN 1: DESIGN SPACE EXPLORATION WHEN s₁ = [1 −1]

Figure 18.2 shows the DAG for the polynomial division algorithm based on our timing function choice s₁. The equitemporal planes are the diagonal lines shown as gray lines on the right of the diagram. The associated time index values are shown at the right of the diagram. We note from the figure that the signals corresponding to the coefficients of B and the estimated q output are all pipelined, as indicated by the arrows connecting the nodes. However, the estimated partial results for Q and R are broadcast, as indicated by the diagonal lines without arrows. There are three simple projection vectors such that all of them satisfy Eq. 18.21 for the scheduling function in Eq. 18.17. The three projection vectors will produce three designs:

(18.22)

(18.23)

(18.24)

Figure 18.2 Directed acyclic graph (DAG) for polynomial division algorithm when s₁ = [1 −1], n = 9, and m = 5.

The corresponding projection matrices are

(18.25)

(18.26)

(18.27)

Our design space now allows for three configurations for each projection ...