Slide 1but first a correction from the last lecture …One-Element Pipeline FIFOOne-Element Pipeline FIFO AnalysisSolution- Config registers Lie a littleOne-Element Pipeline FIFO A correct solutionAn aside Unsafe modulesback to today’s lecture …IP Lookup block in a routerSparse tree representation“C” version of LPMLongest Prefix Match for IP lookup: 3 possible implementation architecturesCircular pipelineFIFORequest-Response Interface for Synchronous MemoryCircular Pipeline CodeCircular Pipeline Code: discussionOrdinary FIFO won’t work but a pipeline FIFO wouldProblem solved!Dead cyclesThe Effect of Dead CyclesScheduling conflicting rulesSo is there a dead cycle?Rule SplitingSpliting the recirculate rulePackaging a module: Turning a rule into a methodIP Lookup: Some subtle concurrency issuesArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 22, 2010 L06-1http://csg.csail.mit.edu/6.375but first a correction from the last lecture …February 22, 2010 L06-2http://csg.csail.mit.edu/6.375module mkPipelineFIFO1 (FIFO#(t)); Reg#(t) data <- mkRegU(); Reg#(Bool) full <- mkReg(False); RWire#(void) deqEN <- mkRWire(); Bool deqp = isValid (deqEN.wget())); method Action enq(t x) if (!full || deqp); 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; endmethod endmodule One-Element Pipeline FIFO!empty!fullrdyenabrdyenabenqdeqFIFOmoduleor!fullThis works correctly in both cases (fifo full and fifo empty).first < enqdeq < enqenq < cleardeq < clearThis actually won’t work!February 22, 2010L06-3http://csg.csail.mit.edu/6.375module mkPipelineFIFO1 (FIFO#(t)); Reg#(t) data <- mkRegU(); Reg#(Bool) full <- mkReg(False); RWire#(void) deqEN <- mkRWire(); Bool deqp = isValid (deqEN.wget())); method Action enq(t x) if (!full || deqp); full <= True; data <= x; endmethod method Action deq() if (full); full <= False; deqEN.wset(?); endmethod...One-Element Pipeline FIFOAnalysis!empty!fullrdyenabrdyenabenqdeqFIFOmoduleor!fullRwire allows us to create a combinational path between enq and deq but does not affect the conflict analysisConflict analysis:February 22, 2010L06-4http://csg.csail.mit.edu/6.375Solution- Config registers Lie a littleConfigReg is a Register (Reg#(a))Reg#(t) full <- mkConfigRegU;Same HW as Register, but the definition says read and write can happen in either orderHowever, just like a HW register, a read after a write gets the old valuePrimarily used to fool the compiler analysis to do the right thingFebruary 22, 2010L06-5http://csg.csail.mit.edu/6.375module mkLFIFO1 (FIFO#(t)); Reg#(t) data <- mkRegU(); Reg#(Bool) full <- mkConfigReg(False); RWire#(void) deqEN <- mkRWire(); Bool deqp = isValid (deqEN.wget())); method Action enq(t x) if (!full || deqp); 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; endmethod endmodule One-Element Pipeline FIFOA correct solution!empty!fullrdyenabrdyenabenqdeqFIFOmoduleor!fullNo conflicts around full: when both enq and deq happen; if we want deq < enq then full must be set to True in case enq occurs.Scheduling constraint on deqEn forces deq < enqFebruary 22, 2010L06-6http://csg.csail.mit.edu/6.375first < enqdeq < enqenq < cleardeq < clearAn asideUnsafe modulesBluespec allows you to import Verilog modules by identifying wires that correspond to methodsSuch modules can be made safe either by asserting the correct scheduling properties of the methods or by wrapping the unsafe modules in appropriate Bluespec codeConfig Reg is an example of an unsafe moduleFebruary 22, 2010L06-7http://csg.csail.mit.edu/6.375back to today’s lecture …February 22, 2010 L06-8http://csg.csail.mit.edu/6.375IP Lookup block in a routerQueueManagerPacket ProcessorExit functionsControlProcessorLine Card (LC)IP LookupSRAM(lookup table)ArbitrationSwitchLCLCLCA packet is routed based on the “Longest Prefix Match” (LPM) of it’s IP address with entries in a routing tableLine rate and the order of arrival must be maintainedline rate 15Mpps for 10GEFebruary 22, 2010L06-9http://csg.csail.mit.edu/6.3751823IP address Result M Ref7.13.7.3 F10.18.201.5 F7.14.7.25.13.7.2 E10.18.200.7 CSparse tree representation3A…A…BC…C…5DF…F…14A…A…7F…F…200F…F…F*E5.*.*.*D10.18.200.5C10.18.200.*B7.14.7.3A7.14.*.*F…F…FF…E5710255014In this lecture:Level 1: 16 bits Level 2: 8 bits Level 3: 8 bits 1 to 3 memory accesses February 22, 2010L06-10http://csg.csail.mit.edu/6.375“C” version of LPMintlpm (IPA ipa) /* 3 memory lookups */{ int p;/* Level 1: 16 bits */ p = RAM [ipa[31:16]]; if (isLeaf(p)) return value(p);/* Level 2: 8 bits */ p = RAM [ptr(p) + ipa [15:8]]; if (isLeaf(p)) return value(p);/* Level 3: 8 bits */ p = RAM [ptr(p) + ipa [7:0]]; return value(p); /* must be a leaf */}Not obvious from the C code how to deal with - memory latency - pipelining…216 -10……28 -10…28 -10Must process a packet every 1/15 s or 67 nsMust sustain 3 memory dependent lookups in 67 nsMemory latency ~30ns to 40nsFebruary 22, 2010L06-11http://csg.csail.mit.edu/6.375Longest Prefix Match for IP lookup:3 possible implementation architecturesRigid pipelineInefficient memory usage but simple designLinear pipelineEfficient memory usage through memory port replicatorCircular pipelineEfficient memory with most complex controlDesigner’s Ranking:1 2 3Which is “best”?Arvind, Nikhil, Rosenband & Dave ICCAD 2004February 22, 2010L06-12http://csg.csail.mit.edu/6.375Circular pipelineThe fifo holds the request while the memory access is in progressThe architecture has been simplified for the sake of the lecture. Otherwise, a “completion buffer” has to be added at the exit to make sure that packets leave in order.enter?enter?done?done?RAMyesinQfifonooutQNext lectureFebruary 22, 2010L06-13http://csg.csail.mit.edu/6.375interface FIFO#(type t); method Action enq(t x); // enqueue an item method Action deq(); // remove oldest entry method t first(); // inspect oldest itemendinterfaceFIFO n = # of bits needed to represent a value of type tnot fullnot emptynot
View Full Document
Unlocking...