Slide 1TopicsImplicit guards (conditions)Guards vs If’sExample: making guards explicitA problem ... (from the last lecture)One Element FIFORWire to rescueOne Element “Loopy” FIFOProblem solved!The Dead Cycle ProblemScheduling conflicting rulesA slightly simpler exampleRule SplitingSpliting the recirculate ruleSometimes rule splitting is not possiblePackaging a module: Turning a rule into a methodProcessor with a two-stage pipelineProcessor Pipelines and FIFOsSFIFO (glue between stages)Two-Stage PipelineInstructions & TemplatesRules for AddFetch & Decode Rule: ReexaminedFetch & Decode Rule: correctedRules for BranchThe Stall SignalParameterization: The Stall FunctionThe findf functionFetch & Decode RuleFetch & Decode Rule another styleExecute RuleFebruary 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 bubblesFebruary 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); a2 p1 has no effect on a2 ... Mixing ifs and whens(if (p) (a1 when q)) ; a2 ((if (p) a1); a2) when (p&q | !p)February 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 begin fifo.enq(tuple2(rip << 8, tok)); ram.req(p+signExtend(rip[15:8])); end fifo.deq();endruleThe fifo needs to be able to do enq and deq simultaneously for this rule to make senseFebruary 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; endmethod method Action deq() if (full); full <= False; endmethod method t first() if (full); return (data); endmethod method Action clear(); full <= False; endmethodendmodule One 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 cycleFebruary 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; endmethod method Action deq() if (full); full <= False; deqEN.wset(?); endmethod method t first() if (full); return (data); endmethod method Action clear(); full <= False; endmethodendmodule One 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 begin fifo.enq(tuple2(rip << 8, tok)); ram.req(p+signExtend(rip[15:8])); end fifo.deq();endruleLFIFO fifo <- mkLFIFO; // use a loopy fifoFebruary 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 begin fifo.enq(tuple2(rip << 8, tok)); ram.req(p+signExtend(rip[15:8])); end fifo.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 fireWhich one? source annotationsFebruary 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 begin fifo.enq(rip << 8); ram.req(p + rip[15:8]); end fifo.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;endruleFebruary 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 begin fifo.enq(tuple2(rip << 8, tok)); ram.req(p+signExtend(rip[15:8])); end fifo.deq();endruleFebruary 23,
View Full Document
Unlocking...