Figure Q$3\mathrm{.}1$ ASAP schedule of the digital filter algorithm

Figure Q$3\mathrm{.}2$ ALAP schedule of the digital filter algorithm a$)$ In the context of digital high$-$level synthesis, briefly describe the

principle of the resource$-$constrained list scheduling algorithm.

b$)$ Figure Q$3\mathrm{.}1$ and Figure Q$3\mathrm{.}2($shown overleaf$)$ show the as$-$soon$-$as

possible $($ASAP$)$ and as late$-$as$-$possible $($ALAP$)$ schedules respectively

of a recursive digital filter algorithm, where $x1,t1,t2,$ are the input

variables, $y1,t1,t2$ are the output variables, $a11$ and $a21$ are the filter

coefficients. The filter algorithm operations are denoted by $O1$ to $O9$ and

it has been assumed that each arithmetic operation takes one control step

for execution.

Using the force$-$directed scheduling algorithm, calculate the operation

probabilities and hence produce the distribution graph of the two

arithmetic operations $(**,+)$ of the filter algorithm.

c$)$ In the force$-$directed scheduling, the self$-$force, Foi$($j$),$ for assignment

operation oi from time frame $t1,t2$ into $c-$step $j$ is given by:

$F_{o_i}(j)=DG(j)-{\displaystyle \underset{k=t_l}{\overset{t_2}{}}}\frac{DG(k)}{t_2-t_l+1}$

The predecessor and successor force associated with the reduction of the

schedule time frame from $t1,t2$ to $t3,t4$ is given by:

$F_{o_i}([t_3,t_4])={\displaystyle \underset{k=t_3}{\overset{t_4}{}}}\frac{DG(k)}{t_4-t_3+1}-{\displaystyle \underset{k=t_1}{\overset{t_2}{}}}\frac{DG(k)}{t_2-t_1+1}$

where $DG(j)$ is the distribution graph value in c$-$step $j.$

Compute the self$-$force, predecessor, successor and total forces

associated with assigning operation O$6$ of the distribution graph

obtained in Q$3($b$)$ into all possible control steps of the filter schedule.

Hence identify the control$-$step for the operation so that hardware

resources are minimised.

$8$

$12$help