1IP Lookup-2: The Completion BufferArvind February 24, 2010 http://csg.csail.mit.edu/6.375Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyL07-1IP-Lookup module without the completion bufferoutQegemodule mkIPLookup(IPLookup);rule recirculate… ; rule exit …;method Action enter (IP ip);ram.req(ip[31:16]);done?RAMfifoenteretResulthttp://csg.csail.mit.edu/6.375fifo.enq(ip[15:0]);endmethodmethod ActionValue#(Msg) getResult(); outQ.deq();return outQ.first();endmethodendmoduleFebruary 24, 2010 L07-22IP Lookup rulesrule 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();endrulehttp://csg.csail.mit.edu/6.375Method enter and rule exit can be scheduled simultaneously, assuming fifo.enq and fifo.deq can be done simultaneouslyand ram.req and ram.deq can be done simultaneouslyFebruary 24, 2010 L07-3IP-Lookup module with the completion buffergeoutQcbufgetTokenThe packets Completion buffer ensures that departures take place in order even if lookups complete out-of-order Since cbufhas finite capacity it gives out tokens to control done?RAMfifoenteretResultQcbufyesnopackets may come out of orderSince cbufhas finite capacity it gives out tokens to control the entry into the circular pipelineThe fifo now must also hold the “token” while the memory access is in progress: Tuple2#(Token,Bit#(16))February 24, 2010L07-4http://csg.csail.mit.edu/6.375remainingIP3Completion buffer: InterfacegetResultgetTokeninterface CBuffer#(type t);method ActionValue#(Token) getToken(); methodActionput(Token tok, t d);cbufgetResultgetTokenput (result & token)http://csg.csail.mit.edu/6.375p(,);method ActionValue#(t) getResult();endinterfacetypedef Bit#(TLog#(n)) TokenN#(numeric type n);typedef TokenN#(16) Token;February 24, 2010 L07-5IP-Lookup module with the completion bufferegetcbufyesgetTokenmodule mkIPLookup(IPLookup);rule recirculate… ; rule exit …;method Action enter (IP ip);Token tok <- cbuf.getToken();ram req(ip[31:16]);done?RAMfifontertResultcbufynofor enter and getResult to execute simultaneously http://csg.csail.mit.edu/6.375ram.req(ip[31:16]);fifo.enq(tuple2(tok,ip[15:0]));endmethodmethod ActionValue#(Msg) getResult(); let result <- cbuf.getResult();return result;endmethodendmodulesimultaneously, cbuf.getTokenand cbuf.getResultmust execute simultaneouslyFebruary 24, 2010 L07-64IP Lookup rules with completion bufferrule recirculate (!isLeaf(ram.peek()));match{.tok,.rip} = fifo.first(); fifo.enq(tuple2(tok,(rip << 8)));ram.req(ram.peek() + rip[15:8]);fifo.deq(); ram.deq();endrulerule exit (isLeaf(ram.peek()));cbuf.put(ram.peek()); fifo.deq(); ram.deq();http://csg.csail.mit.edu/6.375endruleFor rule exit and method enter to execute simultaneously, cbuf.put and cbuf.getToken must execute simultaneouslyFebruary 24, 2010 For no dead cycles cbuf.getToken and cbuf.put and cbuf.getResult must be able to execute simultaneouslyL07-7Completion buffer: ImplementationIIViA circular buffer with two pointers iand o and a counter cntmodule mkCBuffer (CBuffer#(t)) provisos (Bits#(t,sz));RegFile#(Token, Maybe#(t)) buf <- mkRegFileFull();Reg#(Token) i <- mkReg(0); //input indexIVIcntobufand o, and a counter cntElements are of Maybe typehttp://csg.csail.mit.edu/6.375Reg#(Token) o <-mkReg(0); //output indexReg#(Int#(32)) cnt <- mkReg(0); //number of filled slots…Elements must be representable as bitsFebruary 24, 2010 L07-85Completion buffer: Concurrency Issue// state elements // buf, i, o, cnt ...methodActionValue#(t)getToken()IIVIVIcntiobufmethodActionValue#(t) getToken() if (cnt < maxToken);cnt <= cnt + 1; i <= (i==maxToken) ? 0 : i + 1;buf.upd(i, Invalid);return i; endmethodmethod Action put(Token tok, t data);buf.upd(tok, Valid data); Can these methods execute concurrently? NO!http://csg.csail.mit.edu/6.375pendmethodmethod ActionValue#(t) getResult() if (cnt > 0) &&& (buf.sub(o) matches tagged (Valid .x));o <= (o==maxToken) ? 0 : o + 1; cnt <= cnt - 1;return x; endmethodFebruary 24, 2010 L07-9Concurrency AnalysisProblem 1IIViA circular buffer with two pointers iand o and a counter cntIVIcntobufand o, and a counter cntElements are of Maybe typebuf must allow two simultaneous updates and one read Needs a register file with one read and two write portsShd l dffhttp://csg.csail.mit.edu/6.375Since the updates are always to different addresses there is no data hazard and concurrent operations should be permitted No compiler can detect that without full program analysis (i.e., understanding the use pattern)February 24, 2010 L07-106Concurrency AnalysisProblem -2// state elements // buf, i, o, cnt ... methodActionValue#(t)getToken()IIVIViobufmethodActionValue#(t) getToken() if (cnt < maxToken);cnt <= cnt + 1; i <= (i==maxToken) ? 0 : i + 1;buf.upd(i, Invalid);return i; endmethodmethod Action put(Token tok, t data);buf.upd(tok, Valid data); IcntConcurrent updates to cnthttp://csg.csail.mit.edu/6.375pendmethodmethod ActionValue#(t) getResult() if (cnt > 0) &&& (buf.sub(o) matches tagged (Valid .x));o <= (o==maxToken) ? 0 : o + 1; cnt <= cnt - 1;return x; endmethodFebruary 24, 2010 L07-11A special counter moduleWe often need to keep count of certain We often need to keep count of certain events Need to read count, decrement and increment Since decrementing and incrementing don’t change the count we can remove some bypassing linksbypassing links Implemented as Counter Library modules (implemented using Rwires)http://csg.csail.mit.edu/6.375February 24, 2010 L07-127Counter modulemodule mkCounter#(t v) (Counter#(t))provisos(Arith#(t), Literal#(t));#Reg#(t) cnt<- mkConfigReg(v);RWire#(t) up <- mkRWire();RWire#(t) dn <- mkRWire();(*fire_when_enabled*)rule update(True);cnt <= cnt + fromMaybe(0, up.wget) -fromMaybe(0, dn.wget); Caution: rule update must fire otherwise the cnt won’t be updatedendrulemethod t _read() = cnt;method Action incr(x) = up.wset(x);method Action decr(x) = dn.wset(x);endmoduleFebruary 24, 2010L07-13http://csg.csail.mit.edu/6.375Multiported Register file1R and 1W ports bypass or no bypass2R and 1W ports bypass or no bypass1R and 2W portsm ltiple ites into the same All useful and each requires a different implementationmultiple writes into the same register? error vs priority bypass or no bypassFebruary 24, 2010L07-14http://csg.csail.mit.edu/6.375Which type
View Full Document
Unlocking...