1February 23, 2007 http://csg.csail.mit.edu/6.375/ L08-1Blusepc-5: Dead cycles, bubbles and Forwarding in PipelinesArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 23, 2007L08-2http://csg.csail.mit.edu/6.375/TopicsSimultaneous enq & deq in a FIFOThe RWire solutionDead cycle elimination in the IP circular pipeline codeTwo-stage processor pipelineValue forwarding to reduce bubbles2February 23, 2007L08-3http://csg.csail.mit.edu/6.375/Implicit guards (conditions)Rulerule <name> (<guard>); <action>; endrulewhere<action> ::= r <= <exp>| m.g(<exp>)| if (<exp>) <actions> endifFebruary 23, 2007L08-4http://csg.csail.mit.edu/6.375/Guards vs If’sA guard on one action of a parallel group of actions affects every action within the group(a1 when p1); (a2 when p2) ==> (a1; a2) when (p1 && p2)A condition of a Conditional action only affects the actions within the scope of the conditional action(if (p1) a1); a2p1 has no effect on a2 ... Mixing ifs and whens(if (p) (a1 when q)) ; a2≡ ((if (p) a1); a2) when (p&q | !p)3February 23, 2007L08-5http://csg.csail.mit.edu/6.375/Example: making guards explicitrule recirculate (True);if (p) fifo.enq(8);r <= 7;endrulerule recirculate ((p && fifo.engG) || !p);if (p) fifo.enqB(8);r <= 7;endruleFebruary 23, 2007L08-6http://csg.csail.mit.edu/6.375/A problem ... (from the last lecture)rule recirculate (True);TableEntry p <- ram.resp();match {.rip, .tok} = fifo.first();if (isLeaf(p)) cbuf.put(tok, p);else beginfifo.enq(tuple2(rip << 8, tok));ram.req(p+signExtend(rip[15:8]));endfifo.deq();endruleThe fifo needs to be able to do enq and deqsimultaneously for this rule to make sense4February 23, 2007L08-7http://csg.csail.mit.edu/6.375/module mkFIFO1 (FIFO#(t));Reg#(t) data <- mkRegU(); Reg#(Bool) full <- mkReg(False);method Action enq(t x) if (!full);full <= True; data <= x;endmethodmethod Action deq() if (full);full <= False;endmethodmethod t first() if (full);return (data);endmethodmethod Action clear();full <= False;endmethodendmoduleOne Element FIFOenq and deq cannot even be enabled together much less fire concurrently!nnot emptynot fullrdyenabrdyenabenqdeqFIFOmoduleFebruary 23, 2007L08-8http://csg.csail.mit.edu/6.375/RWire to rescue interface RWire#(type t);method Action wset(t x);method Maybe#(t) wget();endinterfaceLike a register in that you can read and write it but unlike a register- read happens after write- data disappears in the next cycle5February 23, 2007L08-9http://csg.csail.mit.edu/6.375/module mkLFIFO1 (FIFO#(t));Reg#(t) data <- mkRegU(); Reg#(Bool) full <- mkReg(False);RWire#(void) deqEN <- mkRWire();method Action enq(t x) if (!full || isValid (deqEN.wget()));full <= True; data <= x;endmethodmethod Action deq() if (full);full <= False; deqEN.wset(?);endmethodmethod t first() if (full);return (data);endmethodmethod Action clear();full <= False;endmethodendmoduleOne Element “Loopy” FIFOnot emptynot fullrdyenabrdyenabenqdeqFIFOmoduleor!fullFebruary 23, 2007L08-10http://csg.csail.mit.edu/6.375/Problem solved!rule recirculate (True);TableEntry p <- ram.resp();match {.rip, .tok} = fifo.first();if (isLeaf(p)) cbuf.put(tok, p);else beginfifo.enq(tuple2(rip << 8, tok));ram.req(p+signExtend(rip[15:8]));endfifo.deq();endruleLFIFO fifo <- mkLFIFO; // use a loopy fifo6February 23, 2007L08-11http://csg.csail.mit.edu/6.375/The Dead Cycle Problemrule enter (True);Token tok <- cbuf.getToken();IP ip = inQ.first(); ram.req(ext(ip[31:16]));fifo.enq(tuple2(ip[15:0], tok)); inQ.deq();endruleenter?enter?done?done?RAMcbufinQfiforule recirculate (True);TableEntry p <- ram.resp();match {.rip, .tok} = fifo.first();if (isLeaf(p)) cbuf.put(tok, p);else beginfifo.enq(tuple2(rip << 8, tok));ram.req(p+signExtend(rip[15:8]));endfifo.deq();endruleCan a new request enter the system simultaneously with an old one leaving?February 23, 2007L08-12http://csg.csail.mit.edu/6.375/Scheduling conflicting rulesWhen two rules conflict on a shared resource, they cannot both execute in the same clockThe compiler produces logic that ensures that, when both rules are applicable, only one will fire Which one?source annotations7February 23, 2007L08-13http://csg.csail.mit.edu/6.375/A slightly simpler examplerule enter (True);IP ip = inQ.first(); ram.req(ip[31:16]);fifo.enq(ip[15:0]); inQ.deq();endruleenter?enter?done?done?RAMinQfiforule recirculate (True);TableEntry p = ram.peek(); ram.deq();IP rip = fifo.first();if (isLeaf(p)) outQ.enq(p);else beginfifo.enq(rip << 8);ram.req(p + rip[15:8]);endfifo.deq();endruleFebruary 23, 2007L08-14http://csg.csail.mit.edu/6.375/Rule Splitingrule foo (True);if (p) r1 <= 5;else r2 <= 7;endrulerule fooT (p);r1 <= 5;endrulerule fooF (!p);r2 <= 7;endrule≡8February 23, 2007L08-15http://csg.csail.mit.edu/6.375/Spliting the recirculate rulerule recirculate (!isLeaf(ram.peek()));IP rip = fifo.first(); fifo.enq(rip << 8);ram.req(ram.peek() + rip[15:8]);fifo.deq(); ram.deq();endrulerule exit (isLeaf(ram.peek()));outQ.enq(ram.peek()); fifo.deq(); ram.deq();endrulerule enter (True);IP ip = inQ.first(); ram.req(ip[31:16]);fifo.enq(ip[15:0]); inQ.deq();endruleFebruary 23, 2007L08-16http://csg.csail.mit.edu/6.375/Sometimes rule splitting is not possiblerule recirculate (True);TableEntry p <- ram.resp();match {.rip, .tok} = fifo.first();if (isLeaf(p)) cbuf.put(tok, p);else beginfifo.enq(tuple2(rip << 8, tok));ram.req(p+signExtend(rip[15:8]));endfifo.deq();endrule9February 23, 2007L08-17http://csg.csail.mit.edu/6.375/Packaging a module:Turning a rule into a methodinQenter?enter?done?done?RAMcbuffiforule enter (True);Token t <- cbuf.getToken();IP ip = inQ.first(); ram.req(ip[31:16]);fifo.enq(tuple2(ip[15:0], t)); inQ.deq();endruleFebruary 23, 2007 http://csg.csail.mit.edu/6.375/ L08-18Processor with a two-stage pipeline5-minute break to stretch you legs10February 23, 2007L08-19http://csg.csail.mit.edu/6.375/Processor Pipelines and FIFOsfetchexecuteiMemrfCPUdecodememorypcwrite-backdMemFebruary 23, 2007L08-20http://csg.csail.mit.edu/6.375/interface SFIFO#(type t, type tr);method Action enq(t); // enqueue an itemmethod Action deq(); // remove oldest entrymethod t first(); // inspect oldest itemmethod Action clear(); // make FIFO emptymethod Bool find(tr); // search FIFOendinterfaceSFIFO (glue between stages)n = # of bits neededto represent thevalues of type “t“m = # of bits neededto represent thevalues of type “tr"not fullnot emptynot
View Full Document
Unlocking...