电子科技大学：《DSP算法实现技术与架构 VLSI Digital Signal Processing Systems Design and Implementation》课程教学资源（课件讲稿）Chapter 03 流水与并行 Pipelining and Parallel Processing

电子州越女学 University of Electrenie Sciance and Tochnology of China Chapter 3 Pipelining and Parallel Processing Dr.Ling National Key Lab of Science and Technology on Communication

Chapter 3 Pipelining and Parallel Processing Dr. Ling National Key Lab of Science and Technology on Communication

U 3.1 Introduction 966 a(n) b(n) ◆ process time no less than 2Tadder x(n) + y(n) How to increase process time a(n) b(n-1) pipelining D y(n-1) a(2k) b(2k) x(2k) y(2k) Parallel a(2k+1) b(2k+1) x(2k+1) y(2k+1) 2021年2月 2

2021年2月 2 3.1 Introduction  process time no less than 2Tadder  How to increase process time ? + + a(2k) b(2k) x(2k) y(2k) + + a(2k+1) b(2k+1) x(2k+1) y(2k+1) + + a(n) b(n) x(n) y(n) + + a(n) b(n-1)  pipelining D y(n-1)  Parallel

986 Pipelining transformation leads to reduction in the critical path,which can be exploited to either increase the clock speed or sample speed or to reduce power consumption at same speed. In parallel processing,multiple outputs are computed in parallel in a clock period. Therefore,the effective sampling speed is increased by the level of parallelism.Similar to the pipelining,parallel processing can also be used for reduction of power consumption. 2021年2月 3

2021年2月 3  Pipelining transformation leads to reduction in the critical path, which can be exploited to either increase the clock speed or sample speed or to reduce power consumption at same speed.  In parallel processing, multiple outputs are computed in parallel in a clock period. Therefore, the effective sampling speed is increased by the level of parallelism. Similar to the pipelining, parallel processing can also be used for reduction of power consumption

3.2 Pipelining 966 3 tap FIR filter y(n)=box(n)+bx(n-1)+bx(n-2) x(n) D b0 bl b2 critical path=TM+2TA y(n) The speed of an architecture is limited by the longest path ASIC between any 2 registers or la path 1 海D or between an input and a re path3 Path 4 CLK or between a register/latch al path 2 or between the input and the 2021年2月 4

2021年2月 4 3.2 Pipelining  The speed of an architecture is limited by the longest path  between any 2 registers or latches  or between an input and a register/latch  or between a register/latch and an output  or between the input and the output. D D X X X + + x(n) y(n) b0 b1 b2 3 tap FIR filter ( ) ( ) ( 1) ( 2) y n  b0 x n  b1 x n   b2 x n  critical path=TM+2TA

/966 This longest path or the critical path can be reduced by suitable placing the pipelining registers/latches in the architecture; The pipelining registers/latches can only be placed across any feed-forward cutset of the graph. x(n) D critical path-TM+TA 3 y(n) 1 Clock Input Point 1 Point 2 Point 3 Output 0 X0) ax(0)+bx(-1) 1 X(1) ax(1)+bx(0) ax(0)+bx(-1) 2 X(2) ax(2)+bx(1) ax(1)+bx(0) 3 X3) ax(3)+bx(2) ax(2)+bx(1) cx(0) ax(2)+bx(1)+cx(0)=y2) 2021年2月 5

2021年2月 5  This longest path or the critical path can be reduced by suitable placing the pipelining registers/latches in the architecture;  The pipelining registers/latches can only be placed across any feed-forward cutset of the graph. D D X X X + + x(n) y(n) a b c D D critical path=TM+TA Clock Input Point 1 Point 2 Point 3 Output 0 X(0) ax(0)+bx(-1) 1 X(1) ax(1)+bx(0) ax(0)+bx(-1) 2 X(2) ax(2)+bx(1) ax(1)+bx(0) 3 X(3) ax(3)+bx(2) ax(2)+bx(1) cx(0) ax(2)+bx(1)+cx(0)=y(2) 1 2 3

/966 Drawbacks: Increase the number of registers/latches; Increase the system latency. 2021年2月 6

2021年2月 6  Drawbacks:  Increase the number of registers/latches;  Increase the system latency

Definition /96 Cutset:A cutset is a set of edges of a graph such that if these edges are removed from the graph,the graph becomes disjoint; Feed-forward Cutset:A cutset is called a feed forward cutset if the data move in the forward direction on all the edges of the cutset. 2021年2月 7

2021年2月 7 Definition  Cutset: A cutset is a set of edges of a graph such that if these edges are removed from the graph, the graph becomes disjoint;  Feed-forward Cutset: A cutset is called a feed forward cutset if the data move in the forward direction on all the edges of the cutset

U Feed-forward cutset /966 example A2 D A4 A6 A3 A5 A2 D A4 D D A6 D D A3 A5 2021年2月 8

2021年2月 8 Feed-forward cutset  example A1 A2 A4 A3 A5 A6 D D A2 A4 A3 A5 A6 D D D D A1 D D

3.2.1 Data-broadcast structure /96 How to reduce the critical path without introducing latches in FIR filter Transposition theorem:Reversing the direction of all the edges and interchanging the input and output port,the functionality of the system preserved. Source node Z critical path-TM+2TA b0 bl b2 Sink node 2021年2月 9

2021年2月 9 3.2.1 Data-broadcast structure  How to reduce the critical path without introducing latches in FIR filter ?  Transposition theorem: Reversing the direction of all the edges and interchanging the input and output port, the functionality of the system preserved. Z-1 Z-1 b0 b1 Sink node Source node b2 critical path=TM+2TA

/966 ■ Signal-flow graph reversal or transposition form Z y(n) b0 bl b2 x(n) x(n) b2 bl b0 X X critical path-TM+TA y(n) 2021年2月 10

2021年2月 10  Signal-flow graph reversal or transposition form Z-1 Z-1 b0 b1 b2 y(n) x(n) D D X X X + + x(n) y(n) b2 b1 b0 critical path=TM+TA