现代计算机体系结构.ppt

《现代计算机体系结构.ppt》由会员分享，可在线阅读，更多相关《现代计算机体系结构.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现代计算机体系结构1现代计算机体系结构现代计算机体系结构主讲教师：张钢主讲教师：张钢主讲教师：张钢主讲教师：张钢 教授教授教授教授天津大学计算机学院天津大学计算机学院天津大学计算机学院天津大学计算机学院通信邮箱：提交作业邮箱：2016年2The Main Contents课程主要内容Chapter 1.Fundamentals of Quantitative Design and AnalysisChapter 2.Memory Hierarchy DesignChapter 3.Instruction-Level Parallelism and Its ExploitationChapter

2、 4.Data-Level Parallelism in Vector,SIMD,and GPU ArchitecturesChapter 5.Thread-Level ParallelismChapter 6.Warehouse-Scale Computers to Exploit Request-Level and Data-Level ParallelismAppendix A.Pipelining:Basic and Intermediate Concepts3.4/3.5/3.6课堂讨论2022/12/144Advantages of Dynamic SchedulingDynami

3、c schedulingHardware rearranges the instruction execution to reduce stalls while maintaining data flow and exception behaviorWhats the meaning that maintaining data flow and exception behavior?2022/12/145Advantages of Dynamic SchedulingAdvantagesIt handles cases when dependences unknown at compile t

4、ime it allows the processor to tolerate unpredictable delays such as cache misses,by executing other code while waiting for the miss to resolveIt allows code that compiled for one pipeline to run efficiently on a different pipeline It simplifies the compiler Why?2022/12/146HW Schemes:Instruction Par

5、allelismKey idea:Allow instructions behind stall to proceedDIVD F0,F2,F4ADDD F10,F0,F8SUBD F12,F8,F14Enables out-of-order execution and allows out-of-order completion(e.g.,SUBD)In a dynamically scheduled pipeline,all instructions still pass through issue stage in order(in-order issue)What are the me

6、aning that in-order issue,out-of-order execution,out-of-order completion?2022/12/147HW Schemes:Instruction ParallelismWill distinguish when an instruction begins execution and when it completes execution;between 2 times,the instruction is in executionWhen and Where in a pipeline?Note:Dynamic executi

7、on creates WAR and WAW hazards and makes exceptions harderWhy it can create WAR and WAW?2022/12/148Dynamic Scheduling Step 1Simple pipeline had 1 stage to check both structural and data hazards:Instruction Decode(ID),also called Instruction IssueSplit the ID pipe stage of simple 5-stage pipeline int

8、o 2 stages:IssueDecode instructions,check for structural hazards Read operandsWait until no data hazards,then read operands Understand?ExISExWb2022/12/149A Dynamic Algorithm:TomasulosFor IBM 360/91(before caches!)Long memory latencyGoal:High Performance without special compilersSmall number of float

9、ing point registers(4 in 360)prevented interesting compiler scheduling of operationsThis led Tomasulo to try to figure out how to get more effective registers renaming in hardware!Why Study 1966 Computer?The descendants of this have flourished!Alpha 21264,Pentium 4,AMD Opteron,Power 5,2022/12/1410To

10、masulo AlgorithmControl&buffers distributed with Function Units(FU)FU buffers called“reservation stations”;have pending operandsRegisters in instructions replaced by values or pointers to reservation stations(RS);called register renaming;Renaming avoids WAR,WAW hazardsMore reservation stations than

11、registers,so can do optimizations compilers cant2022/12/1411Tomasulo AlgorithmResults to FU from RS,not through registers,over Common Data Bus that broadcasts results to all FUsAvoids RAW hazards by executing an instruction only when its operands are availableLoad and Stores treated as FUs with RSs

12、as wellInteger instructions can go past branches(predict taken),allowing FP ops beyond basic block in FP queue2022/12/1412Tomasulo OrganizationFP addersAdd1Add2Add3FP multipliersMult1Mult2From MemFP RegistersReservation StationsCommon Data Bus(CDB)To MemFP OpQueueLoad BuffersStore BuffersLoad1Load2L

13、oad3Load4Load5Load62022/12/1413Reservation Station ComponentsOp:Operation to perform in the unit(e.g.,+or)Vj,Vk:Value of Source operandsStore buffers has V field,result to be storedQj,Qk:Reservation stations producing source registers(value to be written)Note:Qj,Qk=0=readyStore buffers only have Qi

14、for RS producing result Busy:Indicates reservation station or FU is busyRegister result statusIndicates which functional unit will write each register,if one exists.Blank when no pending instructions that will write that register.2022/12/1414Three Stages of Tomasulo Algorithm1.Issueget instruction f

15、rom FP Op Queue If reservation station free(no structural hazard),control issues instr&sends operands(renames registers).2.Executeoperate on operands(EX)When both operands ready then execute;if not ready,watch Common Data Bus for result3.Write resultfinish execution(WB)Write on Common Data Bus to al

16、l awaiting units;mark reservation station available2022/12/1415Three Stages of Tomasulo AlgorithmNormal data bus:data+destination(“go to”bus)Common data bus:data+source (“come from”bus)64 bits of data+4 bits of Functional Unit source addressWrite if matches expected Functional Unit(produces result)D

17、oes the broadcastExample speed:3 clocks for Flopt.+,-;10 clocks for Flopt.*;40 clocks for Flopt./2022/12/1416Tomasulo ExampleClock cycle counterFU countdownInstruction stream3 Load/Buffers3 FP Adder R.S.2 FP Mult R.S.2022/12/1417Tomasulo Example Cycle 12022/12/1418Tomasulo Example Cycle 2Note:Can ha

18、ve multiple loads outstanding2022/12/1419Tomasulo Example Cycle 3Note:registers names are removed(“renamed”)in Reservation Stations;MULT issuedLoad1 completing;what is waiting for Load1?2022/12/1420Tomasulo Example Cycle 4Load2 completing;what is waiting for Load2?2022/12/1421Tomasulo Example Cycle

19、5Timer starts down for Add1,Mult12022/12/1422Tomasulo Example Cycle 6Issue ADDD here despite name dependency on F6?2022/12/1423Tomasulo Example Cycle 7Add1(SUBD)completing;what is waiting for it?2022/12/1424Tomasulo Example Cycle 82022/12/1425Tomasulo Example Cycle 92022/12/1426Tomasulo Example Cycl

20、e 10Add2(ADDD)completing;what is waiting for it?2022/12/1427Tomasulo Example Cycle 11Write result of ADDD here?All quick instructions complete in this cycle!2022/12/1428Tomasulo Example Cycle 122022/12/1429Tomasulo Example Cycle 132022/12/1430Tomasulo Example Cycle 142022/12/1431Tomasulo Example Cyc

21、le 15Mult1(MULTD)completing;what is waiting for it?2022/12/1432Tomasulo Example Cycle 16Just waiting for Mult2(DIVD)to complete2022/12/1433Faster than light computation(skip a couple of cycles)2022/12/1434Tomasulo Example Cycle 552022/12/1435Tomasulo Example Cycle 56Mult2(DIVD)is completing;what is

22、waiting for it?2022/12/1436Tomasulo Example Cycle 57Once again:In-order issue,out-of-order execution and out-of-order completion.2022/12/1437Why can Tomasulo overlap iterations of loops?Register renamingMultiple iterations use different physical destinations for registers(dynamic loop unrolling).Res

23、ervation stations Permit instruction issue to advance past integer control flow operationsAlso buffer old values of registers-totally avoiding the WAR stall Other perspective:Tomasulo building data flow dependency graph on the fly2022/12/1438Tomasulos scheme offers 2 major advantages1.Distribution o

24、f the hazard detection logicdistributed reservation stations and the CDBIf multiple instructions waiting on single result,&each instruction has other operand,then instructions can be released simultaneously by broadcast on CDB If a centralized register file were used,the units would have to read the

25、ir results from the registers when register buses are available2.Elimination of stalls for WAW and WAR hazardsHardware-Based SpeculationProblemA wide issue processor may need to execute a branch every clock cycle to maintain maximum performance.just predicting branches accurately may not be sufficie

26、nt to generate the desired amount of ILPSolution speculating on the outcome of branches and executing the program as if our guesses were correctfetch,issue,and execute instructions,as if branch predictions were always correctProvide mechanisms to handle the situation where the speculation is incorre

27、ct.Hardware-Based Speculation3 key ideasdynamic branch prediction to choose which instructions to executespeculation to allow the execution of instructions before the control dependences are resolved with the ability to undo the effects of an incorrectly speculated sequencedynamic scheduling to deal

28、 with the scheduling of different combinations of basic blocks.Hardware-Based SpeculationTomasulos algorithm can be extended to support speculationseparate the bypassing of results among instructions from the actual completion of an instructionallow an instruction to execute and to bypass its result

29、s to other instructionswithout allowing the instruction to perform any updates that cannot be undoneInstructions using speculated results become speculativeWhen an instruction is no longer speculative,we allow it to update the register file or memoryinstruction commitHardware-Based SpeculationThe ke

30、y ideaallow instructions to execute out of order but to force them to commit in order prevent any irrevocable action until an instruction commits 阻止任何不可更改的活动直到指令提交such as updating state or taking an exceptionseparate the process of completing execution from instruction commit 把完成执行与指令提交分开an addition

31、al set of hardware buffers that hold the results of instructions before being committedreorder buffer(ROB)a source of operands for instructionssupplies operands in the interval between completion of instruction execution and instruction commit.Hardware-Based SpeculationROBA circular bufferEntries al

32、located and deallocated by two revolving pointersEntries allocated to each instructionStrictly in program orderKeeps track of the execution status of the instructionHardware-Based SpeculationROB fieldsinstruction typeopcodebranch(has no destination result)store(has a memory address destination)regis

33、ter operation(has register destinations).destinationthe register number or the memory addressvalueInstruction resultReadyThe value is readyAddressFor load/store operationROB replaces the store bufferROB.InstructionROB.DestROB.ValueROB.ReadytypedestvaluereadyROB.AHardware-Based SpeculationRegister fi

34、eldsBusyRegisterState.BusyReorderRegisterState.ReorderInstruction sequence number QiRegisterState.QiValueRegisterState.ValueBusy reorder Qi ValueHardware-Based Speculation4 stepsIssueExecuteWrite resultCommitHardware-Based Speculation4 stepsIssueIf there is an empty station and empty slot in the ROB

35、Mark the reservation station and ROB as busySend the operands to the reservation station if they are available in the register or ROBExecuteWrite resultWrite result on the CDB and from CDB into the ROBMark the reservation station as emptyCommitWhen an instruction reaches the head of the ROBMark the

36、ROB as emptyWhen the instruction is a branch with incorrect prediction,indicate the speculation was wrongThe ROB is flushedExecution is restarted at the correct successor of the branchHardware-Based SpeculationAdvantages of speculationPrecise interrupt 精确中断the processor with the ROB can dynamically

37、execute code while maintaining a precise interrupt model.flushing any pending instructions in ROBIsIsIsExExExWWWIsExWCCCCHardware-Based SpeculationAdvantages of speculationEarly recovery from branch misprediction 从分支错误预测中提早恢复the processor can easily undo its speculative actions when a branch is foun

38、d to be mispredicted.clearing the ROB for all entries that appear after the mispredicted branch清除出现在错误预测分支指令之后的所有记录allowing those that are before the branch in the ROB to continue允许出现在错误预测分支指令之前的指令继续执行performance is more sensitive to the branch prediction mechanismprefetchPre-executioncommitHardware

39、-Based SpeculationAdvantages of speculationLoad and store hazarda store updates memory only when it reaches the head of the ROBWAW and WAR hazards through memory are eliminated with speculationactual updating of memory occurs in orderRAW hazards through memory are maintained bynot allowing a load to initiate the second step of its executionCheck if any store has an Destination field that matches the value of the loadstore r1,100(r2)load r3,100(r2)作业63.14（英文版第五版）作业73.15（英文版第五版）