DOC PREVIEW
MIT 6 375 - IP Lookup: Some subtle concurrency issues

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1IP Lookup: Some subtle concurrency issuesArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 22, 2011 L06-1http://csg.csail.mit.edu/6.375IP Lookup block in a routerLine Card (LC)ArbitrationLCQueueManagerPacket ProcessorExit functionsControlProcessorIP LookupSRAM(lookup table)SwitchLCLCA 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, 2011L06-2http://csg.csail.mit.edu/6.3752Sparse tree representation3A……BF……14A……7B7.14.7.3A7.14.*.*F…E5018IP address Result M RefA…C…F…A…F…F…F…F*E5.*.*.*D10.18.200.5C10.18.200.*B7.14.7.3F…FF…710255237.13.7.3 F10.18.201.5 F7.14.7.25.13.7.2 E10.18.200.7 C…C…5DF…20014February 22, 2011L06-3http://csg.csail.mit.edu/6.375“C” version of LPMintlpm (IPA ipa) /* 3 memory lookups */…0…0…28 10/ 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 */…216 -1……28 -128 -1p = RAM [ptr(p) + ipa [7:0]]; return value(p); /* must be a leaf */}Must process a packet every 1/15 s or 67 nsMust sustain 3 memory dependent lookups in 67 nsMemory latency ~30ns to 40nsFebruary 22, 2011L06-4http://csg.csail.mit.edu/6.3753Longest Prefix Match for IP lookup:3 possible implementation architecturesRigid pipelineLinear pipelineCircular pipelineRigid pipelineInefficient memory Linear pipelineEfficient memory Circular pipelineEfficient memory usage but simple designusage through memory port replicatorwith most complex controlDesigner’s Ranking:Which is “best”?February 22, 2011L06-5http://csg.csail.mit.edu/6.375Arvind, Nikhil, Rosenband & Dave [ICCAD 2004]Circular pipelineenter?d?RAMyesinQoutQThe fifo holds the request while the memory access is in progressenter?done?RAMyfifonopgThe 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.February 22, 2011L06-6http://csg.csail.mit.edu/6.3754interface FIFO#(type t);method Action enq(t x); // enqueue an itemFIFOmethod Action deq(); // remove oldest entrymethod t first(); // inspect oldest itemendinterfacen = # of bits needednot fullrdyenabnenabenqqOleto represent avalue of type tnot emptynot emptynrdyrdydeqfirstFIFOmoduFebruary 22, 2011L06-7http://csg.csail.mit.edu/6.375Readyctr(ctr > 0)ctr++Request-Response Interface for Synchronous MemoryAckeqAddrctr--deqEnableenqSynch MemLatency NDataDataReadyreqdepeekinterface Mem#(type addrT, type dataT);method Action req(addrT x);method Action deq();method dataT peek();endinterfaceMaking a synchronous component latency-insensitiveFebruary 22, 2011L06-8http://csg.csail.mit.edu/6.3755Circular Pipeline Coderule enter (True);IP ip = inQ.first(); enter?done?RAMinQfiforule recirculate (True);TableEntry p = ram.peek(); ram.deq();IP rip = fifo.first();if(isLeaf(p)) outQ.enq(p);ram.req(ip[31:16]);fifo.enq(ip[15:0]); inQ.deq();endruleWhen can enter fire?done? Is the same as isLeaf( (p)) Q q(p);else beginfifo.enq(rip << 8);ram.req(p + rip[15:8]);endfifo.deq();endruleFebruary 22, 2011L06-9http://csg.csail.mit.edu/6.375Circular Pipeline Code: discussionrule enter (True);IP ip = inQ.first(); enter?done?RAMinQfiforule recirculate (True);TableEntry p = ram.peek(); ram.deq();IP rip = fifo.first();if(isLeaf(p)) outQ.enq(p);ram.req(ip[31:16]);fifo.enq(ip[15:0]); inQ.deq();endruleWhen can recirculate fire?if(isLeaf(p)) outQ.enq(p);else beginfifo.enq(rip << 8);ram.req(p + rip[15:8]);endfifo.deq();endruleFebruary 22, 2011L06-10http://csg.csail.mit.edu/6.3756Ordinary FIFO won’t work but a pipeline FIFO wouldFebruary 22, 2011 L06-11http://csg.csail.mit.edu/6.375Problem solved!PipelineFIFO fifo <- mkPipelineFIFO; // use a Pipeline fiforule recirculate (True);TableEntry p = ram.peek(); ram.deq();IP rip = fifo.first();if (isLeaf(p)) outQ.enq(p);else beginRWire has been safely encapsulated inside the Pipeline FIFO – users of the beginfifo.enq(rip << 8);ram.req(p + rip[15:8]);endfifo.deq();endrule fifo need not be aware of RWiresFebruary 22, 2011L06-12http://csg.csail.mit.edu/6.3757Dead cyclesrule enter (True);IP ip = inQ.first(); enter?done?RAMinQfiforam.req(ip[31:16]);fifo.enq(ip[15:0]); inQ.deq();endrulerule recirculate (True);TableEntry p = ram.peek(); ram.deq();IP rip = fifo.first();if (isLeaf(p)) outQ.enq(p);Can a new request enter the system h ld assume simultaneous enq & deq is allowedelse beginfifo.enq(rip << 8);ram.req(p + rip[15:8]);endfifo.deq();endrulewhen an old one is leaving?February 22, 2011L06-13http://csg.csail.mit.edu/6.375The Effect of Dead Cyclesenterdone?RAMyesinfifonoCircular Pipeline RAM takes several cycles to respond to a request  Each IP request generates 1-3 RAM requestsFIFO entries hold base pointer for next lookup and What is the performance loss if “exit” and “enter” don’t ever happen in the same cycle?FIFO entries hold base pointer for next lookup and unprocessed part of the IP addressFebruary 22, 2011L06-14http://csg.csail.mit.edu/6.3758Scheduling conflicting rulesWhen two rules conflict on a shared th t b th t i 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 annotationsFebruary 22, 2011L06-15http://csg.csail.mit.edu/6.375So is there a dead cycle?rule enter (True);IP ip = inQ.first(); enter?done?RAMinQfiforam.req(ip[31:16]);fifo.enq(ip[15:0]); inQ.deq();endrulerule recirculate (True);TableEntry p = ram.peek(); ram.deq();IP rip = fifo.first();if (isLeaf(p)) outQ.enq(p);lbiIn general these two rules conflict but else beginfifo.enq(rip << 8);ram.req(p + rip[15:8]);endfifo.deq();endruleconflict but when isLeaf(p) is true there is no apparent conflict!February 22, 2011L06-16http://csg.csail.mit.edu/6.3759Rule Splitingrule foo (True);if (p) r1 <= 5;rule fooT (p);r1 <= 5;pelse r2 <= 7;endruleendrulerule fooF (!p);r2 <= 7;endrulerule fooT and fooF can be scheduled independently with some other ruleFebruary 22, 2011L06-17http://csg.csail.mit.edu/6.375Spliting the recirculate rulerule recirculate (!isLeaf(ram.peek()));IP rip = fifo.first(); fifo.enq(rip << 8);ram.req(ram.peek() + rip[15:8]);fifo.deq();


View Full Document

MIT 6 375 - IP Lookup: Some subtle concurrency issues

Documents in this Course
IP Lookup

IP Lookup

15 pages

Verilog 1

Verilog 1

19 pages

Verilog 2

Verilog 2

23 pages

Encoding

Encoding

21 pages

Quiz

Quiz

10 pages

IP Lookup

IP Lookup

30 pages

Load more
Download IP Lookup: Some subtle concurrency issues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view IP Lookup: Some subtle concurrency issues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view IP Lookup: Some subtle concurrency issues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?