Bài giảng Xử lý tin hiệu số với FPGA: Chương 4 - Hoàng Trang

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

4
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Xử lý tin hiệu số với FPGA" Chương 4: Tái định thì, cung cấp cho người học những kiến thức như: giới thiệu về việc nghỉ việc; mô tả định lượng; thuộc tính của việc nghỉ hưu; giải hệ bất đẳng thức; cắt thời gian lại;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Xử lý tin hiệu số với FPGA: Chương 4 - Hoàng Trang

4/2/2013 Đ I H C QU C GIA TP.H CHÍ MINH TRƯ NG Đ I H C BÁCH KHOA KHOA ĐI N-ĐI N T B MÔN K THU T ĐI N T X LÝ TÍN Hi U S V I FPGA Chaper 4: Retiming (Tái đ nh thì) om GV: Hoàng Trang Email: hoangtrang@hcmut.edu.vn mr.hoangtrang@gmail.com .c Thank to: th y H Trung M ng Slide: from text book of Parhi co TP.H Chí Minh 01/2013 1 an th ng Thu t ng o du English Vietnamses Pipelining t o đư ng ng u Cutset t pc t cu Transposed SFG SFG chuy n v Data broadcast truy n d li u kh p nơi, phát tán d li u Parallel processing x lý song song block processing x lý kh i communication bound gi i h n truy n thông th i gian tr truy n thông 2 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Outline • Retiming Introduction • Preliminaries – Quantitative Description – Properties of Retiming – Solving systems of inequalities om • Special Cases – Cutset Retiming .c – Pipelining • Uses of Retiming ng – Retiming for Clock Period Minimization – Retiming for Register Minimization co BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng 4.1 INTRODUCTION o • Retiming is a transformation technique used to du change the locations of delay elements in a circuit u without affecting the input/output characteristics of cu the circuit. • For example, consider the IIR filters in Fig. 4.1(a) & (b). Although the filters in Fig. 4.1(a) and Fig. 4.1(b) have delays at different locations, these filters have the same input/output characteristics. These 2 filters can be derived from one another using retiming. BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 4 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Example: om .c The filter in Fig. 4.1(a) is described by The filter in Fig. 4.1(b) is described by ng co 5 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng Applications of Retiming o du • Retiming has many applications in synchronous circuit design. These applications include u – reducing the clock period of the circuit, cu – reducing the number of registers in the circuit, – reducing the power consumption of the circuit, and – logic synthesis 6 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Applications of Retiming (cont’d) • Retiming can be used to increase the clock rate of a circuit by reducing the computation time of the critical path. • For example: – The critical path of the filter in Fig. 4.1(a) = TM +TA = 3 u.t. => this filter cannot be clocked with a clock period of less than 3 u.t. – The retimed filter in Fig. 4.1(b) = TA+TA = 2 u.t. => this filter can be clocked with a clock period of 2 u.t. om – By retiming the filter in Fig. 4.1(a) to obtain the filter in Fig. 4.1(b), the clock period has been reduced from 3 u.t. to 2 u.t., or by 33%. • Retiming can be used to decrease the number of registers in a .c circuit. The filter in Fig. 4.1 (a) uses 4 registers while the filter in Fig. 4.1 (b) uses 5 registers. ng • Since retiming can affect the clock period and the number of registers, it is sometimes desirable to take both of these co parameters into account. 7 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th o ng du u cu 8 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Example: om .c ng co 9 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng Retiming o • Generalization of Pipelining du • Pipelining is Equivalent to Introducing Many delays at the Input followed by Retiming u cu 10 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 4.2 DEFINITIONS AND PROPERTIES 4.2.1 Quantitative Description of Retiming • Retiming maps circuit G to a retimed circuit Gr • Retiming solution characterized by a value r(V) for each node V in graph – Let w(e) denote weight of edge e of graph G, and om wr(e) denote weight of edge e of graph Gr – Weight of edge rom U e V in the retimed graph is computed from weight of edge in original graph using .c wr(e) = w(e) + r(V) - r(U) • Retiming solution is feasible if wr(e) >= 0 for all edges ng co BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 11 an th ng Node Retiming o • Retiming equation: du • Transfer delay through a node in DFG: u e v u 3D D 2D subject to wr(e) ≥ 0. cu r(v) = 2 v v wr (e) = w(e) + r (v) − r (u ) 2D D 3D • Let p be a path from v0 to vk e0 e1 ek v0 v1 vk • r(v) = # of delays transferred from k −1 p out-going edges to incoming edges of then wr ( p ) = ∑ wr (ei ) node v i =0 k −1 • w(e) = # of delays on edge e = ∑ ( w(ei ) + r (vi +1 ) − r (vi ) ) • wr(e) = # of delays on edge e after i =0 retiming = w( p ) + r (vk ) − r (v0 ) 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Invariant Properties 1. Retiming does NOT change the total number of delays for each cycle. 2. Retiming does not change loop bound or iteration bound of the DFG om 3. If the retiming values of every node v in a DFG G are added to a constant integer j, the .c retimed graph Gr will not be affected. That is, ng the weights (# of delays) of the retimed graph will remain the same. co BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th Example: o ng du u cu 14 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 DFG Illustration of the Example om .c T∞ = max. {(1+2+1)/2, (1+2+1)/3} = 2 ng T∞ = max. {(1+2+1)/2, (1+2+1)/3} = 2 co Cr. Path Delay = max{2,2,1+1} = 2 t.u Cr. Path delay = 2+1 = 3 t.u an th ng 4.2.2 Properties of Retiming o k −1 • Weight of a path from node 0 to node k is w( p ) = ∑ w(ei ) du number of delays between those nodes i =0 • Computation time of a path between node 0 u to node k is the sum of computation times k t ( p ) = ∑ t (Vi ) cu (adders, etc.) of each of the nodes i =0 • Properties: – Retiming does not change number of delays in a cycle – Retiming does not alter iteration bound of DFG – Adding a constant value j to the retiming value of each node does not change the mapping from G to Gr BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 om .c ng co 17 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng 4.3 Solving Systems of Inequalities • Shortest path algorithms (Appendix A of Parhi book) o – Bellman-Ford du – Floyd-Warshall • Given a set of M inequalities and N variables, where each inequality has the form ri – rj
4/2/2013 om .c ng co 19 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng Bellman-Ford Algorithm o Find shortest path from an arbitrarily du chosen origin node U to each node in a directed graphif no negative cycle −3 exists. 1 2 Given a direct graph 1 u 1 1 w(m,n): weight on edge from node m cu 2 to node n, = ∞ if there is no edge from 4 3 m to n r(i,j): the shortest path from node U to  0 −3 ∞ ∞  ∞ 2 22 node i within j-1 steps. ∞ 0 1 1    r = 0 0 −1 −1 r(i,1) = w(U,i), W =  r(i,j+1) = min {r(k,j) + w(k,i)}, ∞ ∞ 0 2  1 1 1 0     j = 1, 2, …, N-1  1 ∞ ∞ 0 1 1 1 0 if max(r(:,n-1)-r(:,n))>0, then there is a negative cycle. Else, r(i,n-1) gives shortest cycle length from i to U. Note that 1 > 0, hence there is at least one negative cycle. 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Floyd-Warshall Algorithm Find shortest path between all −3 possible pairs of nodes in the 1 2 1 graph provided no negative cycle 1 2 exists. 2 4 3 Algorithm: Initialization: R(1) =W;  0 −3 ∞ ∞  0 −3 −2 −1 om For k=1 to N ∞ 0 1 2   1 2 W =  R (2) = 3 0  R(k+1)(u,v) = min{R(k)(u,:) + R(k)(:,v)} ∞ ∞ 0 2  3 ∞ 0 2 If R(k)(u,u)< 0 for any k, u, then a     1 ∞ ∞ 0 1 −2 ∞ 0 .c  negative cycle exist. Else, 0 −3 −2 −1 R(N+1)(u,v) is SP from u to v 3 0 1 2  R (3) = R (4) = R (5) =   ng 3 0 0 2    1 −2 −1 0  co an th ng Retiming Example – Bellman-Ford Algorithm o du • For retiming example: • Bellman-Ford Algorithm for – r(2) – r(1) ≤ 1 Shortest Path u – r(1) – r(3) ≤ 0 cu – r(1) – r(4) ≤ 1 0 1 ∞ ∞ ∞ – r(3) – r(2) ≤ –1  ∞ 0 −1 −1  ∞  – r(4) – r(2) ≤ –1 W = 0 ∞ 0 ∞ ∞   1 ∞ ∞ 0 ∞ 0 0 0 0  0  −1 0 0 −1 −1 0 1 2 0 0 0 0  3 1   1 −1 R = 0 −1 −1 −1 4   0 0 0 −1 −1 −1 0 0 0  0 0 0   5 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Retiming Example – Floyd-Warshall algorithm • Floyd-Warshall algorithm 0 1 ∞ ∞ ∞ 0 1 0 0 ∞  ∞ 0 −1 −1 ∞  −1 0 −1 −1 ∞      W = R (1) = 0 ∞ 0 ∞ ∞ R (3) = R (4) = R (5) = R (6) =0 1 0 0 ∞ om     1 ∞ ∞ 0 ∞ 1 2 1 0 ∞ 0 0 0 0  0   −1  0 −1 −1 0   0 1 0 0 ∞ .c  −1 0 −1 −1 ∞    R (2) =0 1 0 ∞ ∞   ng 1 2 ∞ 0 ∞ 0  0 −1 −1 0   co an th ng 4.4 RETIMING TECHNIQUES o du • This section considers some techniques used for retiming: u – First, two special cases of retiming, namely, cutset cu retiming and pipelining, are considered. – Two algorithms are then considered for etiming to minimize the clock period and retiming to minimize the number of registers that are required to implement the circuit. 24 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 4.4.1 Cutset Retiming and Pipelining Cutset Retiming om .c ng co 25 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng Single Node Subgraph Cutset Retiming o du u cu BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 26 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 om .c ng co 27 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th o ng du u cu 28 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 om .c ng co 29 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th o ng du u cu 30 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 om .c ng co 31 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th o ng du u cu 32 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 om .c ng co 33 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th ng Pipelining o du u cu (a) (b) (c) Fig. 4.6 (a) The unretimed DFG with a cutset shown as a dashed line. (b) The 2 graphs G1 and G2 formed by removing the edges in the cutset. (c) The graph obtained by cutset retiming with k = 2. 34 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Lattice Filter om .c ng co 35 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th N‐Slow Down ng • Cutset retiming is often used in combination with slow-down. • The procedure is to first replace each delay in the DFG with N delays to o create an N -slow version of the DFG and then to perform cutset retiming on the du N –slow DFG u cu 36 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 Time Scaling (Slow Down) • Transform each delay element x(3) x(2) x(1) y(3) y(2) y(1) (register) D to ND and reduce + the sample frequency by N fold D will slow down the computation N times. × om • During slow down, the -- x(3) -- x(2) -- x(1) y(3) -- y(2) -- y(1) processor clock cycle time + .c remains unchanged. Only the 2D sampling cycle time increased. × ng • Provides opportunity for retiming, and interleaving. co an th o ng du u cu 38 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
4/2/2013 om .c ng co 39 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 an th o ng du u cu 40 BM Đi n T -DSP-FPGA-chapter4 Hoàng Trang 01/2013 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt