MIPS Pipeline - Cornell University

1 Hakim WeatherspoonCS 3410, Spring 2012 Computer ScienceCornell UniversityMIPS PipelineSee P&H Chapter ProcessoraluPCimmmemorymemorydindoutaddr targetoffsetcmpcontrol=?new pcregisterfileinstextend+4+4 Review: Single cycle processor3 What determines performance of processor ?A) Critical PathB) Clock Cycle TimeC) Cycles Per Instruction (CPI)D) All of the aboveE) None of the above4 Review: Single Cycle ProcessorAdvantages Single Cycle per instruction make logic and clock simpleDisadvantages Since instructions take different time to finish, memory and functional unit are not efficiently utilized. Cycle time is the longest delay. Load instruction Best possible CPI is 1 However, lower MIPS and longer clock period (lower clock frequency).

2 Hence, lower : Multi Cycle ProcessorAdvantages Better MIPS and smaller clock period (higher clock frequency) Hence, better performance than Single Cycle processor Disadvantages Higher CPI than single cycle processorPipelining: Want better Performance want small CPI (close to 1) with high MIPS and short clock period (high clock frequency) CPU time = instruction count x CPI x clock cycle time6 Single Cycle vs Pipelined ProcessorSee: P&H Chapter KidsAliceBobThey don t always get Bicycle9 The MaterialsSawDrillGluePaint10 The InstructionsN pieces, each built following same sequence:SawDrillGluePaint11 Design 1: Sequential ScheduleAlice owns the roomBob can enter when Alice is finishedRepeat for remaining tasksNo possibility for conflicts12 Elapsed Time for Alice: 4 Elapsed Time for Bob: 4 Total elapsed time: 4*NCan we do better?

3 Sequential Performancetime12345678 ..Latency:Throughput:Concurrency: CPI =13 Design 2: Pipelined DesignPartition room into stagesof a pipelineOne person owns a stage at a time4 stages4 people working simultaneouslyEveryone moves right in lockstepAliceBobCarolDave14 Pipelined :Throughput:Concurrency: 15 LessonsPrinciple:Throughput increased by parallel executionPipelining: Identify Pipeline stages Isolate stages from each other Resolve Pipeline hazards (Thursday)16A ProcessoraluPCimmmemorymemorydindoutaddr targetoffsetcmpcontrol=?new pcregisterfileinstextend+4+4 Review: Single cycle processor17 Write BackMemoryInstructionFetchExecuteInstruc tionDecoderegisterfilecontrolA ProcessoraluimmmemorydindoutaddrinstPCme morycomputejump/branchtargetsnew pc+4extend18 Basic PipelineFive stage RISC load store fetch (IF) get instruction from memory, increment Decode (ID) translate opcode into control signals and read (EX) perform ALU operation, compute jump/branch (MEM) access memory if (WB) update register file19 Time Graphs123456789 Clock cycleLatency:Throughput:Concurrency.

4 IFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXM EMWBIFIDEXMEMWB20 Principles of Pipelined ImplementationBreak instructions across multiple clock cycles (five, in this case)Design a separate stage for the execution performed during each clock cycleAdd Pipeline registers (flip flops) to isolate signals between different stages21 Pipelined ProcessorSee: P&H Chapter BackMemoryInstructionFetchExecuteInstruc tionDecodeextendregisterfilecontrolPipel ined ProcessoralumemorydindoutaddrPCmemorynew pcinstIF/IDID/EXEX/MEMMEM/WBimmBActrlctr lctrlBDDM computejump/branchtargets+423 IFStage 1: Instruction FetchFetch a new instruction every cycle Current PC is index to instruction memory Increment the PC at end of cycle (assume no branches for now)Write values of interest to Pipeline register (IF/ID) Instruction bits (for later decoding) PC+4 (for later computing branch targets)24 IFPC instructionmemorynewpcaddrmc+425 IFPC instructionmemorynewpcinstaddrmc00 = read word1IF/IDWE1 Rest of Pipeline +4PC+4pcselpcregpcrelpcabs26 IDStage 2: Instruction DecodeOn every cycle.

5 Read IF/ID Pipeline register to get instruction bits Decode instruction, generate control signals Read from register fileWrite values of interest to Pipeline register (ID/EX) Control information, Rd index, immediates, offsets, .. Contents of Ra, Rb PC+4 (for computing branch targets later)27 IDctrlID/EXRest of pipelinePC+4instIF/IDPC+4 Stage 1: Instruction FetchregisterfileWERdRaRbDBABAimm28 IDctrlID/EXRest of pipelinePC+4instIF/IDPC+4 Stage 1: Instruction FetchregisterfileWERdRaRbDBABA extendimmdecoderesultdest29 EXStage 3: ExecuteOn every cycle: Read ID/EX Pipeline register to get values and control bits Perform ALU operation Compute targets (PC+4+offset, etc.) in case this is a branch Decide if jump/branch should be takenWrite values of interest to Pipeline register (EX/MEM) Control information, Rd index.

6 Result of ALU operation Value in casethis is a memory store instruction30 Stage 2: Instruction DecodepcrelpcabsEXctrlEX/MEMRest of pipelineBDctrlID/EXPC+4 BAaluj+||branch?immpcselpcregtarget31 MEMS tage 4: MemoryOn every cycle: Read EX/MEM Pipeline register to get values and control bits Perform memory load/store if needed address is ALU resultWrite values of interest to Pipeline register (MEM/WB) Control information, Rd index, .. Result of memory operation Pass result of ALU operation32 MEMctrlMEM/WBRest of pipelineStage 3: ExecuteMDctrlEX/MEMBD memorydindoutaddrmctarget33 MEMctrlMEM/WBRest of pipelineStage 3: ExecuteMDctrlEX/MEMBD memorydindoutaddrmctargetbranch?pcselpcr elpcabspcreg34 WBStage 5: Write backOn every cycle: Read MEM/WB Pipeline register to get values and control bits Select value and write to register file35 WBStage 4: MemoryctrlMEM/WBMD36 WBStage 4: MemoryctrlMEM/WBMD resultdest37IF/ID+4ID/EXEX/MEMMEM/WBmemd indoutaddrinstPC+4 OPBARtBDMDPC+4immOPRdOPRdPCinstmemRdRa RbDBARd38 AdministriviaHW2 due today Fill out Survey online.

7 Receive credit/points on homework for survey: Survey is anonymousProject1 (PA1) due week after prelim Continue working diligently. Use design doc momentumSave your work! Save often. Verify file is non zero. Periodically save to Dropbox, email. Beware of MacOSX (leopard) and (snow leopard)Use your resources Lab Section, , Office Hours, Homework Help Session, Class notes, book, Sections, CSUGLab39 AdministriviaPrelim1: next Tuesday, February 28thin evening We will start at 7:30pm sharp, so come early Prelim Review: This Wed / Fri, 3:30 5:30pm, in 155 Olin Closed Book Cannot use electronic device or outside material Practice prelims are online in CMS Material covered everything up to end of this week Appendix C (logic, gates, FSMs, memory, ALUs) Chapter 4 (pipelined [and non Pipeline ] MIPS processor with hazards) Chapters 2 (Numbers / Arithmetic, simple MIPS instructions) Chapter 1 (Performance) HW1, HW2, Lab0, Lab1, Lab240 AdministriviaCheck online syllabus/schedule and Reading for lecturesOffice HoursHomework and Programming AssignmentsPrelims (in evenings).

8 Tuesday, February 28th Thursday, March 29th Thursday, April 26thSchedule is subject to change41 Collaboration, Late, Re grading Policies Black Board Collaboration Policy Can discuss approach together on a black board Leave and write up solution independently Do not copy solutionsLate Policy Each person has a total of four slip days Max of twoslip days for any individual assignment Slip days deducted first for anylate assignment, cannot selectively apply slip days For projects, slip days are deducted from all partners 20% deducted per day late after slip days are exhaustedRegrade policy Submit written request to lead TA, and lead TA will pick a different grader Submit another written request, lead TA will regrade directly Submit yet another written request for professor to : Sample Code (Simple)Assume eight register machineRun the following code on a pipelined datapathaddr3 r1 r2 ; reg 3 = reg 1 + reg 2nand r6 r4 r5 ; reg 6 = ~(reg 4 & reg 5)lwr4 20 (r2) ; reg 4 = Mem[reg2+20]addr5 r2 r5 ; reg 5 = reg 2 + reg 5swr7 12(r3) ; Mem[reg3+12] = reg 7 Slides thanks to Sally McKee43 Example: : Sample Code (Simple)add r3, r1, r2; nand r6, r4, r5; lw r4, 20(r2); add r5, r2, r5; sw r7, 12(r3).

9 44 MIPS instruction formatsAll MIPS instructions are 32 bits long, has 3 formatsR typeI typeJ type op rs rt rd shamt func6 bits 5 bits 5 bits 5 bits 5 bits 6 bitsop rs rt immediate6 bits 5 bits 5 bits16 bitsop immediate (target address)6 bits26 bits45 MIPS Instruction TypesArithmetic/Logical R type: result and two source registers, shift amount I type: 16 bit immediate with sign/zero extensionMemory Access load/store between registers and memory word, half word and byte operationsControl flow conditional branches: pc relative addresses jumps: fixed offsets, register absolute46 Time Graphs123456789addnandlwaddswClock cycleLatency:Throughput:Concurrency:IFID EXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWB IFIDEXMEMWB47 PCInstmemRegister fileMUXALUMUX4 Datamem+MUXBits 11 15 Bits 16 20opRtimmvalBvalAPC+4PC+4targetALUresult opdestvalBopdestALUresultmdatainstructio n0R2R3R4R5R1R6R0R7regAregBBits 26 31datadestIF/IDID/EXEX/MEM MEM/WBextendMUXRd48datadestIF/IDID/EXEX/ MEM MEM/WBextend0 MUX049 PCInstmemRegister fileMUXALUMUX4 Datamem+MUXBits 11 15 Bits 16 20nop0000400nop00nop0000add 3 1 29121873641022R2R3R4R5R1R6R0R7 Bits 26 31datadestFetch:add 3 1 2add 3 1 2 Time.

10 1IF/IDID/EXEX/MEM MEM/WBextend0 MUX050 PCInstmemRegister fileMUXALUMUX4 Datamem+MUXBits 11 15 Bits 16 20add39364800nop00nop0000nand 6 4 59121873641022R2R3R4R5R1R6R0R712 Bits 26 31datadestFetch:nand 6 4 5nand 6 4 5 add 3 1 2 Time: 2IF/IDID/EXEX/MEM MEM/WBextend2 MUX351 PCInstmemRegister fileMUXALUMUX4 Datamem+MUXBits 11 15 Bits 16 20nand6718812445add39nop0000lw 4 20(2)9121873641022R2R3R4R5R1R6R0R745 Bits 26 31datadestFetch:lw 4 20(2)lw 4 20(2) nand 6 4 5 add 3 1 2 Time: 33693IF/IDID/EXEX/MEM MEM/WBextend5 MUX63252 PCInstmemRegister fileMUXALUMUX4 Datamem+MUXBits 11 15 Bits 16 20lw2018912168 3nand67add34500add 5 2 5 9121873641022R2R3R4R5R1R6R0R724 Bits 26 31datadestFetch:add 5 2 5add 5 2 5 lw 4 20(2) nand 6 4 5 add 3 1 2 Time: 41876453IF/IDID/EXEX/MEM MEM/WBextend4 MUX06553 PCInstmemRegister fileMUXALUMUX4 Datamem+MUXBits 11 15 Bits 16 20add57916201229lw418nand6 300sw 7 12(3)9451873641022R2R3R4R5R1R6R0R725 Bits 26 31datadestFetch:sw 7 12(3)sw 7 12(3) add 5 2 5 lw 4 20 (2) nand 6 4 5 add 3 1 2 Time: 59204 364