Enhancing Circuit Throughput with Pipelining in Computer Architecture
Pipelining plays a pivotal role in computer architecture, aiding in the evaluation of multiple inputs simultaneously to increase circuit throughput. This technique involves dividing combinational functions into distinct stages, managing FIFOs, addressing concurrency issues, and utilizing Elastic and Inelastic pipelines. The content delves into the intricacies of Elastic vs. Inelastic pipelines, the role of Ephemeral History Registers (EHRs), and concepts like the Maybe Type. Moreover, it discusses strategies for dealing with pipeline bubbles, modifying rules to accommodate various conditions, and explicit encoding of Valid/Invalid data for enhanced efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Constructive Computer Architecture: Pipelining combinational circuits Arvind Computer Science & Artificial Intelligence Lab. Massachusetts Institute of Technology September 19, 2016 http://csg.csail.mit.edu/6.175 L06-1
Content Elastic versus Inelastic pipelines The role of FIFOs Concurrency issues Ephemeral History Registers (EHRs) BSV Concepts The Maybe Type EHR L06-2 http://csg.csail.mit.edu/6.175 September 19, 2016
Pipelining Combinational Functions xi+1 xi xi-1 3 different datasets in the pipeline f0 f1 f2 Lot of area and long combinational delay Folded or multi-cycle version can save area and reduce the combinational delay but throughput per clock cycle gets worse Pipelining: a method to increase the circuit throughput by evaluating multiple inputs L06-3 http://csg.csail.mit.edu/6.175 September 19, 2016
Inelastic vs Elastic pipeline f0 f1 f2 x inQ sReg1 sReg2 outQ Inelastic: all pipeline stages move synchronously f0 f1 f2 x inQ fifo1 fifo2 outQ Elastic: A pipeline stage can process data if its input FIFO is not empty and output FIFO is not Full Most complex processor pipelines are a combination of the two styles http://csg.csail.mit.edu/6.175 September 19, 2016 L06-4
Inelastic pipeline f0 f1 f2 x inQ sReg1 sReg2 outQ rule sync-pipeline; if(inQ.notEmpty && outQ.notFull) begin inQ.deq; sReg1 <= f0(inQ.first); sReg2 <= f1(sReg1); outQ.enq(f2(sReg2)) end endrule L06-5 http://csg.csail.mit.edu/6.175 September 19, 2016
Pipeline bubbles Some issues f0 f1 f2 x inQ sReg1 sReg2 outQ rule sync-pipeline; if(inQ.notEmpty && outQ.notFull) begin inQ.deq; sReg1 <= f0(inQ.first); sReg2 <= f1(sReg1); outQ.enq(f2(sReg2)) end endrule Modify the rule to deal with these conditions http://csg.csail.mit.edu/6.175 September 19, 2016 - Red and Green tokens must move even if there is nothing in inQ! - Also if there is no token in sReg2 then nothing should be enqueued in the outQ Valid bits or the Maybe type L06-6
Explicit encoding of Valid/Invalid data Valid/Invalid f0 f1 f2 x inQ outQ sReg1 sReg2 typedefunion tagged {void Valid; void Invalid; } Validbit deriving (Eq, Bits); rule sync-pipeline; if(outQ.notFull || sReg2v != Valid) if (inQ.notEmpty) begin sReg1 <= f0(inQ.first); inQ.deq; sReg1v <= Valid end else sReg1v <= Invalid; sReg2 <= f1(sReg1); sReg2v <= sReg1v; if (sReg2v == Valid) outQ.enq(f2(sReg2))) endrule http://csg.csail.mit.edu/6.175 September 19, 2016 L06-7
When does the state change? rule sync-pipeline; if(outQ.notFull || sReg2v != Valid) if (inQ.notEmpty) begin sReg1 <= f0(inQ.first); inQ.deq; sReg1v <= Valid end else sReg1v <= Invalid; sReg2 <= f1(sReg1); sReg2v <= sReg1v; if (sReg2v == Valid) outQ.enq(f2(sReg2))) endrule f1 f2 f0 sReg2 inQ outQ sReg1 inQ sReg1v sReg2v outQ NE V NE V NE V NE V NE I NE I NE I NE I inQ sReg1v sReg2v outQ V V I I V V I I NF F NF F NF F NF F yes No Yes Yes Yes No Yes yes E E E E E E E E V V V V I I I I V V I I V V I I NF F NF F NF F NF F yes No Yes Yes Yes No Yes yes NE = Not Empty; NF = Not Full September 19, 2016 L06-8 http://csg.csail.mit.edu/6.175
Elastic pipeline Use FIFOs instead of pipeline registers no need for valid bits f0 f1 f2 x inQ fifo1 fifo2 outQ rule elasticPipeline; if(inQ.notEmpty && fifo1.notFull) begin fifo1.enq(f0(inQ.first); inQ.deq end; if(fifo1.notEmpty && fifo2.notFull) begin fifo2.enq(f1(fifo1.first); fifo1.deq end; if(fifo2.notEmpty && outQ.notFull) begin outQ.enq(f2(fifo2.first); fifo2.deq) end; endrule When does the state change? Can tokens be left in the pipeline? September 19, 2016 L06-9 http://csg.csail.mit.edu/6.175
State Change conditions for the rule f0 f1 f2 x inQ fifo1 fifo2 outQ act1 act2 act3 inQ fifo1 fifo2 outQ NE NE,NF NE,NF NF NE NE,NF NE,NF F NE NE,NF NE,F NE NE,NF NE,F . Yes Yes Yes Yes . Yes Yes No No Yes No Yes No NF F The execution of this rule assumes that enq and deq methods of the FIFOs can be executed concurrently What if they cannot? L06-10 http://csg.csail.mit.edu/6.175 September 19, 2016
One-Element FIFO Implementation x en module mkCFFifo (Fifo#(1, t)); Reg#(t) d <- mkRegU; Reg#(Bool) v <- mkReg(False); method Bool notFull; return !v; endmethod method Bool notEmpty; return v; endmethod method Action enq(t x); v <= True; d <= x; endmethod method Action deq; v <= False; endmethod method t first; return d; endmethod endmodule September 19, 2016 enq en deq !full !emty first module notFull Fifo notEmpty first 1. What if enq and deq were executed together? Can notEmpty and notFull be true simultaneously? double write error 2. no! L06-11 http://csg.csail.mit.edu/6.175
Two-Element FIFO db da module mkCFFifo (Fifo#(2, t)); Reg#(t) da <- mkRegU(); Reg#(Bool) va <- mkReg(False); Reg#(t) db <- mkRegU(); Reg#(Bool) vb <- mkReg(False); method Bool notFull; return !vb; endmethod method Bool notEmpty; return va; endmethod method Action enq(t x); if (va) begin db <= x; vb <= True; end else begin da <= x; va <= True; end endmethod method Action deq; if (vb) begin da <= db; vb <= False; end else begin va <= False; end endmethod method t first; return da; endmethod endmodule Assume, if there is only one element in the FIFO it resides in da notEmpty and notFull can be true simultaneously but concurrent execution of enq and deq will cause double write errors L06-12 http://csg.csail.mit.edu/6.175 September 19, 2016
Concurrent method calls f1 f2 f3 x inQ fifo1 fifo2 outQ rule stage1; if(inQ.notEmpty && fifo1.notFull) begin fifo1.enq(f1(inQ.first); inQ.deq end; if(fifo1.notEmpty && fifo2.notFull) begin fifo2.enq(f2(fifo1.first); fifo1.deq end; if(fifo2.notEmpty && outQ.notFull) begin outQ.enq(f3(fifo2.first); fifo2.deq) end; endrule This rule is illegal if concurrent operations on FIFOs are not permitted L06-13 http://csg.csail.mit.edu/6.175 September 19, 2016
Limitations of registers Limitations of a language with only the register primitive No communication between rules or between methods or between rules and methods in the same atomic action i.e. clock cycle Can t express a FIFO with concurrent enq and deq L06-14 http://csg.csail.mit.edu/6.175 September 19, 2016
EHR: Ephemeral History Register A new primitive element to design modules with concurrent methods September 19, 2016 http://csg.csail.mit.edu/6.175 L06-15
Ephemeral History Register (EHR) Dan Rosenband [MEMOCODE 04] r[0] normal 0 D Q w[0].data w[0].en 1 0 w[1].data w[1].en 1 bypass r[1] r[1] returns: the current state if w[0] is not enabled the value being written (w[0].data) if w[0] is enabled w[i+1] takes precedence over w[i] r[0] < w[0] r[1] < w[1] w[0] < w[1] < . L06-16 http://csg.csail.mit.edu/6.175 September 19, 2016
Designing FIFOs using EHRs Conflict-Free FIFO: Both enq and deq are permitted concurrently as long as the FIFO is not-full and not-empty The effect of enq is not visible to deq, and vise versa Pipeline FIFO: An enq into a full FIFO is permitted provided a deq from the FIFO is done simultaneously Bypass FIFO: A deq from an empty FIFO is permitted provided an enq into the FIFO is done simultaneously L06-17 http://csg.csail.mit.edu/6.175 September 19, 2016
One-Element Pipelined FIFO module mkPipelineFifo(Fifo#(1, t)) provisos(Bits#(t, tSz)); Reg#(t) d <- mkRegU; Ehr#(2, Bool) v <- mkEhr(False); Desired behavior deq < enq first < deq first < enq method Bool notFull = !v[1]; method Bool notEmpty = v[0]; methodAction enq(t x); d <= x; v[1] <= True; endmethod No double write error methodAction deq; v[0] <= False; endmethod In any given cycle: - If the FIFO is not empty then simultaneous enq and deq are permitted; - Otherwise, only enq is permitted http://csg.csail.mit.edu/6.175 method t first; return d; endmethod endmodule L06-18 September 19, 2016
One-Element Bypass FIFO module mkBypassFifo(Fifo#(1, t)) provisos(Bits#(t, tSz)); Ehr#(2, t) d <- mkEhr(?); Ehr#(2, Bool) v <- mkEhr(False); Desired behavior enq < deq first < deq enq < first method Bool notFull = !v[0]; method Bool notEmpty = v[1]; methodAction enq(t x); d[0] <= x; v[0] <= True; endmethod No double write error methodAction deq; v[1] <= False; endmethod In any given cycle: - If the FIFO is not full then simultaneous enq and deq are permitted; - Otherwise, only deq is permitted http://csg.csail.mit.edu/6.175 method t first; return d[1]; endmethod endmodule L06-19 September 19, 2016
Two-Element Conflict-free FIFO db da module mkCFFifo(Fifo#(2, t)) provisos(Bits#(t, tSz)); Ehr#(2, t) da <- mkEhr(?); Ehr#(2, Bool) va <- mkEhr(False); Ehr#(2, t) db <- mkEhr(?); Ehr#(2, Bool) vb <- mkEhr(False); rule canonicalize; if(vb[1] && !va[1]) (da[1] <= db[1]; va[1] <= True; vb[1] <= False) endrule Assume, if there is only one element in the FIFO it resides in da Desired behavior enq CF deq first < deq first CF enq method Bool notFull = !vb[0]; method Bool notEmpty = va[0]; methodAction enq(t x); db[0] <= x; vb[0] <= True; endmethod methodAction deq; va[0] <= False; endmethod method t first; return da[0]; endmethod endmodule September 19, 2016 In any given cycle: - Simultaneous enq and deq are permitted only if the FIFO is not full and not empty L06-20 http://csg.csail.mit.edu/6.175
