1Modular Refinement Arvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologygyMarch 2, 2011 L09-1http://csg.csail.mit.edu/6.375Successive refinement & Modular StructurefetchexecuteiMemrfCPUdecodememorypcwrite-backdMemCPUCan we derive the 5-stage pipeline by successive refinement of a 2-stage pipeline?fetch & decodeexecutepcrfCPUbuMarch 2, 2011 L09-2http://csg.csail.mit.edu/6.3752Architectural refinementsSeparating Fetch and DecodeRl i b Replace magic memory by multicycle memoryMulticycle functional units …Nirav Dave, M.C. Ng, M. Pellauer, Arvind [Memocode 2010] A design flow based on modular refinementMarch 2, 2011 L09-3http://csg.csail.mit.edu/6.375CPU as one moduleiMemdMemfetch & decodepcexecuteRFile rfSFIFO buCPURead method callAction method callMethod calls embody both data and control (i.e., protocol)March 2, 2011 L09-4http://csg.csail.mit.edu/6.3753A Modular organizationiMemRFile rfFIFO budMemCPUfetch & decodepcexecutesetPcenqItWBstallSuppose we include rf and pc in Fetch and bu in ExecuteFetch delivers decoded instructions to Execute and needs to consult Execute for the stall conditionExecute writes back data in rf and supplies the pc value in case of a branch mispredictionMarch 2, 2011 L09-5http://csg.csail.mit.edu/6.375Interface definitions:Fetch and Executeinterface Fetch;method Action setPC (Iaddress cpc);method Action writeback (RName dst, Value v); endinterfaceinterface Execute;method Action enqIt(InstTemplate it);method Bool stall(Instr instr)endinterfaceMarch 2, 2011 L09-6http://csg.csail.mit.edu/6.3754Recursive modular organizationmodule mkCPU2#(Mem iMem, Mem dMem)();Execute execute <- mkExecute(dMem, fetch);Fetch fetch <- mkFetch(iMem, execute);endmodulerecursive callsUnfortunately, the recursive module syntax is not so simpleMarch 2, 2011 L09-7http://csg.csail.mit.edu/6.375IssueA recursive call structure can be wrong in the sense of “circular calls”; fortunately the il f thi h kcompiler can perform this checkUnfortunately recursive call structure amongst modules is supported by the compiler in a limited way. The syntax is complicated Recursive modules cannot be synthesized separatelyMarch 2, 2011 L09-8http://csg.csail.mit.edu/6.3755Syntax for Recursive Modulesmodule mkFix#(Tuple2#(Fetch, Execute) fe)(Tuple2#(Fetch, Execute));match{ f e} fe;match{.f, .e} = fe;Fetch fetch <- mkFetch(e);Execute execute <- mkExecute(f);return(tuple2(fetch,execute));endmodule(* synthesize *)module mkCPU(Empty);match{.fetch, .execute} <-moduleFix(mkFix);moduleFix is like the Y combinatorF = Y Fmatch{.fetch, .execute} <moduleFix(mkFix);endmoduleMarch 2, 2011 L09-9http://csg.csail.mit.edu/6.375Passing parametersmodule mkCPU#(IMem iMem, DMem dMem)(Empty);module mkFix#(Tuple2#(Fetch, Execute) fe) (Tuple2#(Fetch, Execute));match{.f, .e} = fe;Fetch fetch <- mkFetch(iMem,e);Execute execute <- mkExecute(dMem,f);return(tuple2(fetch,execute);endmodulematch {.fetch, .execute} <-moduleFix(mkFix);endmoduleMarch 2, 2011 L09-10http://csg.csail.mit.edu/6.3756Fetch Modulemodule mkFetch#(IMem iMem, Execute execute) (Fetch);Instr instr = iMem.read(pc);IaddresspredIa=pc+1;IaddresspredIa= pc + 1;Reg#(Iaddress) pc <- mkReg(0);RegFile#(RName, Bit#(32)) rf <- mkBypassRegFile();rule fetch_and_decode (!execute.stall(instr)); execute.enqIt(newIt(instr,rf));pc <= predIa;endrulemethod Action writeback(RName rd, Value v);rf.upd(rd,v);endmethodmethod Action setPC(Iaddress newPC);pc <= newPC;endmethodendmoduleMarch 2, 2011 L09-11http://csg.csail.mit.edu/6.375Execute Modulemodule mkExecute#(DMem dMem, Fetch fetch) (Execute);SFIFO#(InstTemplate)bu<-mkSPipelineFifo(findf);SFIFO#(InstTemplate) bu<mkSPipelineFifo(findf);InstTemplate it = bu.first;rule execute …method Action enqIt(InstTemplate it);bu.enq(it);endmethodmethodBool stall(Instrinstr);return (stallFunc(instr, bu));endmethodendmoduleno changeMarch 2, 2011 L09-12http://csg.csail.mit.edu/6.3757Execute Module Rulerule execute (True);case (it) matchestaggedEAdd{dst: rd src1: va src2: vb}:begintaggedEAdd{dst:.rd,src1:.va,src2:.vb}: beginfetch.writeback(rd, va+vb); bu.deq();end tagged EBz {cond:.cv,addr:.av}:if (cv == 0) then beginfetch.setPC(av); bu.clear(); endelse bu.deq();tagged ELoad{dst:.rd,addr:.av}: beginfetch.writeback(rd,dMem.read(av)); bu.deq();endtagged EStore{value:.vv,addr:.av}: begindMem.write(av, vv); bu.deq();endendcaseendruleMarch 2, 2011 L09-13http://csg.csail.mit.edu/6.375Subtle Architecture Issuesinterface Fetch;method Action setPC (Iaddress cpc);After setPCis called the next instruction enqueued via method Actionwriteback (RName dst, Value v); endinterfaceinterface Execute;method Action enqIt(InstTemplate it);method Bool stall(Instr instr)endinterfaceAfter setPCis called the next instruction enqueued via enqIt must correspond to iMem(cpc)stall and writeback methods are closely related; writeback affects the results of subsequent stalls the effect of writeback must be reflected immediately in the decoded instructions Any modular refinement must preserve these extra-linguistic semantic propertiesMarch 2, 2011 L09-14http://csg.csail.mit.edu/6.3758Modular refinement: Separating Fetch and DecodefetchrfdecodepcMarch 2, 2011 L09-15http://csg.csail.mit.edu/6.375iMemFetch Module RefinementSeparating Fetch and Decodemodule mkFetch#(IMem iMem, Execute execute) (Fetch);FIFO#(Instr) fetch2DecodeQ <- mkPipelineFIFO();Instrinstr=iMem read(pc);Instrinstr= iMem.read(pc);Iaddress predIa = pc + 1;…rule fetch(True);pc <= predIa;fetch2DecodeQ.enq(instr);endrulerule decode(!ttll(fth2 dQfi t()))(!execute.stall(fetch2DecodeQ.first())); execute.enqIt(newIt(fetch2DecodeQ.first(),rf));fetch2DecodeQ.deq();endrulemethod Action setPC …method Action writeback …endmoduleAre any changes needed in the methods?March 2, 2011 L09-16http://csg.csail.mit.edu/6.3759Fetch Module Refinementmodule mkFetch#(IMem iMem, Execute execute) (Fetch);FIFO#(Instr) fetchDecodeQ <- mkFIFO();…rule fetch …rule decode …method Action writeback(RName rd, Value v);rf.upd(rd,v);endmethodno changemethodActionsetPC(IaddressnewPC);pc <= newPC;fetch2DecodeQ.clear();endmethodEndmoduleThe stall signal definition guarantees that any order for the execution of the decode rule and writeback method is valid. March 2, 2011 L09-17http://csg.csail.mit.edu/6.375Modular refinement: Modular refinement: Replace magic memory by multicycle memoryfetchrfdecodepcMarch 2, 2011 L09-18http://csg.csail.mit.edu/6.375fetchiMemdecode10The
View Full Document