电子州越女学 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