4.2.2 Properties of retiming /96 The weight of the retimed route p=Vo>V1>...Vk is given by w(p)=w(p)+r(Vk)- r(Vo) Retiming does not change the number of delays in a cycle. ■ Retiming does not alter the iteration bound in a DFG. As the number of delays in a cycle does not change. -W-(p)=w(p)+r(Vo)-r(Vo)=w(p) Adding the constant value j to the retiming value of each node does not change the mapping from G to G.. 2021年2月 6
2021年2月 6 4.2.2 Properties of retiming The weight of the retimed route p=V0V1…Vk is given by wr (p)=w(p)+r(Vk )- r(V0 ) Retiming does not change the number of delays in a cycle. Retiming does not alter the iteration bound in a DFG. As the number of delays in a cycle does not change. wr (p)=w(p)+r(V0 )-r(V0 )=w(p) Adding the constant value j to the retiming value of each node does not change the mapping from G to Gr
4.3 Solving systems inequalities Given a set of M inequalities,where each inequality has the form r-rsk for integer values of k. Draw a constrain graph. Draw the node i for N variables ri,i=1,..N; ■Draw the node N+l; For each inequality ri-r<k,draw edge j->i with length k; ■For each node i,.draw edge N+l→i with length0. ■ Solve using a shortest path algorithm. Bellman-Ford algorithm(single-point shortest path algorithm) Floyd-Warshall algorithm(all-point shortest path algorithm) ■ If a solution exists(if no negative cycle in constraint graph), the retiming value r is obtained (r is the minimum-length from node N+1 to node i). 2021年2月 7
2021年2月 7 4.3 Solving systems inequalities Given a set of M inequalities, where each inequality has the form ri -rj≤k for integer values of k. Draw a constrain graph. Draw the node i for N variables ri , i=1,..N; Draw the node N+1; For each inequality ri -rj≤k, draw edge ji with length k; For each node i, draw edge N+1i with length 0. Solve using a shortest path algorithm. Bellman-Ford algorithm (single-point shortest path algorithm) Floyd-Warshall algorithm (all-point shortest path algorithm) If a solution exists (if no negative cycle in constraint graph), the retiming value r is obtained (ri is the minimum-length from node N+1 to node i). J i w
966 Example 4.3.1 r1-r2≤0 0 0 5 r3-r15 ● 0 r4r1≤4 5 0 r4r3≤-1 4 r3-r2≤2 ■ Shortest path r(4)=(0,0,0,-1) ■Thus,retiming value r1=0、r2=0、r3=0、r4=-1. 2021年2月 8
2021年2月 8 Example 4.3.1 r1 -r2≤0 r3 -r1≤5 r4 -r1≤4 r4 -r3≤-1 r3 -r2≤2 Shortest path r(4)=(0,0,0,-1) Thus, retiming value r1=0、 r2=0、 r3=0、 r4=-1. 2 1 4 3 0 5 4 -1 5 0 2 0 0 0
4.4 Retiming techniques 96 Two special cases of retiming Cutset retiming ·pipelining ■Two algorithms To minimize the clock period To minimize the number of registers 2021年2月 9
2021年2月 9 4.4 Retiming techniques Two special cases of retiming Cutset retiming pipelining Two algorithms To minimize the clock period To minimize the number of registers
4.4.1 Cutset retiming and pipelining Cutset retiming only affects the weights of the edges in the cutset. If the two disconnected subgraphs are labeled G1 and G2,then cutset retiming consists of adding k delays to each edge from Gi to G2, then removing k delays from each edge from G2 to G1. 2021年2月 10
2021年2月 10 4.4.1 Cutset retiming and pipelining Cutset retiming only affects the weights of the edges in the cutset. If the two disconnected subgraphs are labeled G1 and G2 , then cutset retiming consists of adding k delays to each edge from G1 to G2 , then removing k delays from each edge from G2 to G1