计算机系统结构ComputerArchitectu

计算机系统结构ComputerArchitecture,2,TheMainContents课程主要内容,Chapter12CPUStructureandFunctionCPU结构和功能Chapter13ReducedInstructionSetComputers精简指令集计算机Chapter14Instruction-LevelParallelism&SuperscalarProcessors指令集并行性和超标量处理器Chapter18ParallelProcessing并行处理,WilliamStallingsComputerOrganizationandArchitecture7thEdition,Chapter13ReducedInstructionSetComputers,4,Topics,MajorAdvancesinComputers计算机的主要改进InstructionExecutionCharacteristics指令执行的特点UseofLargeRegisterFile使用大的寄存器Compiler-BasedRegisterOptimization基于编译器的寄存器优化ReducedInstructionSetArchitecture精简指令集体系结构RISCPipeliningRISC流水线RISCvs.CISCControversyRISC和CISC的比较,5,MajorAdvancesinComputers(1),Thefamilyconcept系列概念IBMSystem/3601964DECPDP-8Separatesarchitecturefromimplementation将体系结构和它的实现分开Microporgrammedcontrolunit微程序控制器IdeabyWilkes1951ProducedbyIBMS/3601964CachememoryCache存储器IBMS/360model851969,6,MajorAdvancesinComputers(2),SolidStateRAM固态存储器(Seememorynotes)Microprocessors微处理器Intel40041971Pipelining流水线IntroducesparallelismintofetchexecutecycleMultipleprocessors多处理器,7,TheNextStep-RISC,RISC-ReducedInstructionSetComputerRISC精简指令集计算机KeyfeaturesLargenumberofgeneralpurposeregisters,oruseofcompilertechnologytooptimizeregisteruse大量通用寄存器，使用编译技术优化寄存器的使用Limitedandsimpleinstructionset一个有限简单的指令集Emphasisonoptimisingtheinstructionpipeline强调指令流水的优化,8,Comparisonofprocessors,9,DrivingforceforCISC（1）,CISC-ComplexInstructionSetComputerCISC复杂指令集计算机WhyCISC?Softwarecostsfarexceedhardwarecosts软件成本高于硬件成本Increasinglycomplexhighlevellanguages越来越复杂的高级语言Semanticgap:DifferencebetweenoperationsprovidedinHLLsandthoseprovidedincomputerarchitecture语义间隙问题：HLLs提供的操作和计算机体系结构提供的操作不同,10,DrivingforceforCISC（2）,toclosethegapLeadsto:Largeinstructionsets指令集非常大Moreaddressingmodes更多的寻址方式HardwareimplementationsofHLLstatementse.g.CASE(switch)onVAXHLL描述的硬件的实现,11,IntentionofCISC复杂指令集体系结构的目的,Easecompilerwriting使编译器的编写更容易Improveexecutionefficiency提高执行效率Complexoperationsinmicrocode因为复杂操作能以微代码实现SupportmorecomplexHLLs提供更复杂的HLL支持Atotallydifferentapproach:Simplerarchitecture简化体系结构,12,精简指令计算机RISC设计思路的提出,AnumberofstudieshavebeendonetodeterminethecharacteristicsandpatternsofexecutionofmachineinstructionsgeneratedfromHLLprograms已经进行的很多研究，目的是确定高级语言程序生成的机器指令执行的特征和模式Theresultsofthesestudiesinspiredsomeresearcherstolookforadifferentapproach促使设计人员寻找一种与复杂指令系统截然不同的方法Atotallydifferentapproach:Simplerarchitecture简化体系结构,13,ExecutionCharacteristics执行特征,DevelopmentsofRISCswerebasedonthestudyofinstructionexecutioncharacteristicsRISC的开发是基于指令的执行特性Operationsperformed完成的操作determinefunctionstobeperformedandinteractionwithmemory决定了CPU所要完成的功能及其与存储器的相互作用Operandsused(typesandfrequencies)使用的操作数及其类型和频率determinememoryorganizationandaddressingmodes决定了存储器如何组织存储它们和访问它们用的寻址方式Executionsequencing执行顺序determinesthecontrolandpipelineorganization决定了控制和流水线的组织结构,14,ExecutionCharacteristics执行特征,Dynamicmeasurements&Staticmeasurements动态测量和静态测量Dynamicmeasurementsaremeasuredduringtheexecutionoftheprogram.程序的执行中进行的动态测量。Staticmeasurementsmerelyperformthesecountsonthesourcetextofaprogram.静态测量只是在源程序文本上进行统计，这不能给出很有用的性能信息。,15,RelativeDynamicFrequency,DynamicMachineInstructionMemoryReferenceOccurrence(Weighted)(Weighted)PascalCPascalCPascalCAssign453813131415Loop5342323326Call151231334445If29431121713GoTo-3-Other613121,16,Operations操作,Assignmentstatementspredominate赋值语句占统治地位Movementofdataisofhighimportance数据的移动重要性PreponderanceofConditionalstatements(IF,LOOP)条件语句占优势地位Sequencecontrolisimportant指令集的顺序控制,17,Operations操作,Procedurecall-returnisverytimeconsuming程序的调用花费大量时间SomeHLLinstructionleadtomanymachinecodeoperations一些HLL指令导致执行大量机器代码,18,Operands,Mainlylocalscalarvariables主要是局部标量变量Optimisationshouldconcentrateonaccessinglocalvariables优化也应该集中在局部变量的访问PascalCAverageIntegerconstant162320Scalarvariable585355Array/structure262425,19,ProcedureCalls过程调用,Verytimeconsuming过程调用是编译后的HLL程序中最耗时的操作Toimplementefficiently,twoaspectsaresignificant:Dependsonnumberofparameterspassed依赖于传递的参数的数量Dependsonlevelofnesting依赖于嵌套深度Mostprogramsdonotdoalotofcallsfollowedbylotsofreturns程序一般不作大量的调用之后跟着大量的返回Mostvariablesarelocal大部分变量是局部的,20,Implications结论,MakinginstructionsetarchitectureclosetoHLL使指令集与HLL相近notmosteffective不是最有效的Bestsupportisgivenbyoptimisingmostusedandmosttimeconsumingfeatures通过优化最经常使用的和最花费时间的，是最好的方案。,21,Implications,Generalizingfromtheworkofanumberofresearchers,threeelementsemergethat,byandlarge,characterizeRISCarchitectures.Largenumberofregisters大量寄存器Operandreferencingoptimization+localityofreferencesmemoryreferencesreduced减少存储器访问Carefuldesignofpipelines精心设计流水线Conditionalbranchandprocedurecall条件分支和过程调用Simplified(reduced)instructionset精简指令集,22,UseofLargeRegisterFile,FromtheanalysisLargenumberofassignmentstatementsMostaccessestolocalscalars主要访问本地标量Heavyrelianceonregisterstorage依赖于寄存器存储Minimizingmemoryaccess最小化内存访问,23,Approaches,Softwaresolutiontomaximizeregisterusage软件方法Requirecompilertoallocateregisterstothosemostusedvariablesinagiventime依赖于编译器，把寄存器分配给那些一定时间内使用最多的变量Requiressophisticatedprogramanalysis需要复杂的程序分析Hardwaresolution硬件方法Havemoreregisters大量寄存器Thusmorevariableswillbeinregisters寄存器中存放大量变量,24,RegistersforLocalVariables,Storelocalscalarvariablesinregisters在寄存器中存放本地标量变量Reducesmemoryaccess减少存储器访问SomeproblemsEveryprocedure(function)callchangeslocality每一次过程调用都会改变局部性Oneverycall,localvariablesmustbesavedtomemory每次调用变量必须被存储到存储器Parametersmustbepassed必须传递参数Onreturn,resultsmustbereturnedandvariablesfromcallingprogramsmustberestored必须返回结果并且恢复调用程序的变量,25,RegisterWindows,Solution:RegisterwindowsOrganizationofregisterstorealizethegoal为了实现解决前述问题的目标，而对寄存器采用的组织结构FromtheanalysisOnlyfewparametersandlocalvariables少量参数和本地变量Limitedrangeofdepthofcall有限的调用深度Usemultiplesmallsetsofregisters使用多个小的寄存器组Callsswitchtoadifferentsetofregisters过程调用时自动地切换来使用不同的寄存器组Returnsswitchbacktoapreviouslyusedsetofregisters返回时切换回以前使用的寄存器组,26,OverlappingRegisterWindows,Threeareaswithinaregisterset窗口分为3个域：Parameterregisters参数寄存器域Localregisters局部寄存器域Temporaryregisters临时寄存器域,27,RegisterWindowscont.,Temporaryregistersfromonesetoverlapparameterregistersfromthenext临时寄存器用于当前过程与下一级过程(被当前过程调用的过程)交换参数和结果Temporaryregistersatonelevelarephysicallythesameastheparameterregistersatthenextlowerlevel.当前层的临时寄存器域和下一层的参数寄存器域物理上是同一个域。Thisallowsparameterpassingwithoutmovingdata这种重叠准许不用实际移动数据就能传递参数,28,CircularBufferdiagram,Theactualorganizationoftheregisterfileisasacircularbufferofoverlappingwindows.寄存器集的实际组织结构是一个由重叠窗口组成的环形缓冲器。,29,OperationofCircularBuffer,Whenacallismade,acurrentwindowpointer(CWP)ismovedtoshowthecurrentlyactiveregisterwindow当一个调用发生时，当前窗口指针移动到当前活动寄存器窗口Ifallwindowsareinuse,aninterruptisgeneratedandtheoldestwindow(theonefurthestbackinthecallnesting)issavedtomemory(only.inand.locneedtobesaved)当所有窗口都在使用就会产生中断，最老的窗口会保存到内存（只保存参数、局部窗口的数据）Asavedwindowpointerindicateswherethenextsavedwindowsshouldrestoreto保存窗口指针表明下一个保存窗口应该恢复的地方,30,OperationofCircularBuffer(2),Studiesshow:8windowsareenoughtohandleuptoofcall/returnwithoutsave/restore8个窗口足够处理99%的调用和返回E.g.,BerkeleyRISCuses8windowsof16registerseach,31,GlobalVariables-2Options,Allocatedbythecompilertomemory由编译器为全局变量指定存储器位置Straightforward直截了当Inefficientforfrequentlyaccessedvariables对经常访问的全局变量效率低下HaveasetofregistersforglobalvariablesCPU中有一组全局寄存器e.g.,registers0-7:global8-31:localtocurrentwindowIncreasedhardwareburden硬件负担增加Compilermustdecidewhichglobalvariablesshouldbedesignedtoregisters编译器也必须裁定什么样的全局变量应指派到寄存器。,32,RegistersvCache,LargeRegisterFileCacheAlllocalscalarsRecentlyusedlocalscalars所有局部变量最近使用的局部标量IndividualvariablesBlocksofmemory个别变量存储器块CompilerassignedglobalvariablesRecentlyusedglobalvariables编译器指派全局变量最近使用的全局变量Save/restorebasedonSave/restorebasedoncachingprocedurenestingalgorithm保存/恢复基于过程的嵌套深度保存/恢复基于cache替换算法RegisteraddressingMemoryaddressing寄存器寻址存储器寻址,33,RegistersvCache,大寄存器保留了所有的局部标量变量空间利用率低（窗口大，参数少）寄存器与存储器之间的数据传送不太频繁Cache有选择地保留局部标量变量可以有效地利用空间（动态更新）同时也存在空间利用率低的问题（成块传送，包含无用数据）寄存器与存储器之间的数据传送可能较频繁（组关联映像）,34,RegistersvCache,寄存器优于Cache表现在：为访问基于窗口寄存器集中的一个局部标量，使用一个窗口号和一个“虚拟的”寄存器号。这些通过一个相对简单的译码器来选择某一个具体的寄存器。为访问cache存储器中的一个位置，必须生成全宽度的地址。这种操作的复杂性取决于寻址方式。在一个组关联的cache中，地址的一部分用于读取等同于组长度的几个字和标记(tag)，地址的另一部分用于与标记进行比较，以选择所读的一个字。这一点应是很清楚的，尽管cache能与寄存器集一样地快，但cache的存取时间肯定要长。于是，从性能观点看，基于窗口的寄存器集对于局部标量是优选的。通过加入只由指令使用的cache，能进一步改善性能。,35,ReferencingaScalar-WindowBasedRegisterFile,“virtual”registernumber,windownumber,快,36,ReferencingaScalar-Cache,慢,37,CompilerBasedRegisterOptimization,Assumesmallnumberofregisters(16-32)假设只有少量寄存器可用优化寄存器的使用就是编译器的责任HLLprogramshavenoexplicitreferencestoregisters用高级语言写的程序没有对寄存器的显式引用Theobjectiveofthecompileristokeeptheoperandsforasmanycomputationsaspossibleinregistersratherthanmainmemory,andtominimizeload-and-storeoperations.编译器的目标就是，尽可能地在寄存器中而不是在主存中为多数计算保持操作数，并且减少与内存的装入和存储操作。,38,CompilerBasedRegisterOptimizationcont.,Eachquantityisassignedtoasymbolicorvirtualregister准备驻留在寄存器中的每个程序量先被指派到一个符号的或虚拟的寄存器中Map(unlimited)symbolicregisterstorealregisters然后编译器再将这些末限定数目的符号寄存器映射到固定数目的实寄存器上Symbolicregistersthatdonotoverlapcansharerealregisters那些使用不重叠的符号寄存器能共享同一实寄存器Ifyourunoutofrealregisters,somevariablesusememory若在程序具体运行期间，需要打交道的量多于实寄存器数目、则某些量要被指派到存储器位置上,39,Optimization,Theessenceoftheoptimizationtaskistodecidewhichquantitiesaretobeassignedtoregisters优化任务的本质:是判定程序中什么样的量应指派到寄存器中Thetechniqueisknownasgraphcoloring图着色技术UsedinRISCcompiler用在RISC编译器Borrowedfromthedisciplineoftopology这是由拓扑学借用过来的技术,40,GraphColoring,Givenagraphofnodesandedges对于一个由结点和边组成的给定图Assignacolortoeachnode为每个结点指定颜色Adjacentnodeshavedifferentcolors使相邻节点不同色Useminimumnumberofcolors要使用颜色的数目最少Nodesaresymbolicregisters结点是符号寄存器,41,GraphColoringcont.,Tworegistersthatareliveinthesameprogramfragmentarejoinedbyanedge若两个符号寄存器同时“存活”于同一程序段，则相应的两个结点用一条边连接起来以指出它们相关。Trytocolorthegraphwithncolors,wherenisthenumberofrealregisters尝试用n种颜色给图上色，n为实寄存器的数目Nodesthatcannotbecoloredareplacedinmemory这些不能上色的结点必须放入存储器中,42,GraphColoringApproach,AssumeaprogramwithsixsymbolicregisterstobecompiledintothreeactualregistersParta:符号寄存器使用的时间顺序Partb:寄存器干涉图,43,ATrade-Off,Atrade-offbetweenlargeregistersandregisteroptimization在使用大量的寄存器和寄存器优化之间有一个权衡考虑问题Withevensimpleregisteroptimization,thereislittlebenefittotheuseofmorethan64registers若只有相当简单的寄存器优化，那么使用多于64个寄存器只带来很少的好处Withreasonablysophisticatedregisteroptimizationtechniques,thereisonlymarginalperformanceimprovementwithmorethan32registers使用相当精致的寄存器优化技术，使用多于32个的寄存器仅有临界性能改善Studiesshow64registersareenoughwithsimpleregisteroptimization32registersareenoughwithsophisticatedregisteroptimization,44,ReducedInstructionSetArchitectureWhyCISC(1)?,WhyCISC？Easecompilerwriting使编译器的编写更容易Improveexecutionefficiency提高执行效率Compilersimplification?Disputed争论Complexmachineinstructionshardertoexploit难以使用，编译器必须找到严格满足限制的情况OptimizationmoredifficultE.g.Minimizecodesize,enhancepipelining减小代码、提高流水都很难实现,45,WhyCISC(2)?,Smallerprograms?Programtakesuplessmemory程序占用内存少Butmemoryisnowcheap但是内存非常便宜Fewerinstructionstobefetched,reducingpagefaults.取更少的指令，减少缺页Maynotoccupylessbitsinsymbolicmachinelanguage符号形式的机器语言，所占据的存储器位数却不见得小Moreinstructionsrequirelongerop-codesCISC指令多，需要的操作码就长RISCtendtoemphasizeregister,andregisterreferencesrequirefewerbitsRISC指令使用的寄存器访问要求较少位数,46,WhyCISC(1)?,CodeSizeRelativetoRISCI11CProgramsRISCI1.0VAX-11/7800.8M680000.9Z80021.2PDP-11/700.9CISC比RISC节省很少甚至没有节省VAX比PDP-11减少很少，但VAX指令复杂的多,更复杂CISC,CISC,47,WhyCISC(3)?,Fasterprograms?Morecomplexcontrolunit更复杂的控制单元Microprogramcontrolstorelarger微程序控制存储更大thussimpleinstructionstakelongertoexecute增加了简单指令的执行时间ItisfarfromclearthatCISCistheappropriatesolutionCISC是否是较合适的解决方法还远不是那么清楚,48,RISCCharacteristics,Oneinstructionpercycle每周期一条指令Registertoregisteroperations寄存器到寄存器操作Few,simpleaddressingmodes简单寻址方式Few,simpleinstructionformats简单指令格式,49,OneInstructionPerMachineCycle,Inamachinecycle在一个机器周期fetchtwooperandsfromregisters从寄存器取两个操作数PerformanALUoperation完成一个ALU操作Storetheresultinaregister结果存寄存器Thereislittleornotneedformicrocode很少或没有需要微代码Machineinstructionscanbehardwired机器指令可以用硬布线的方式实现Suchinstructionsshouldexecutefasterthancomparablemachineinstructionsonothermachines.,50,Register-to-RegisterOperations,Mostoperationsisregister-to-register大多数操作应是寄存器到寄存器的OnlyLOADandSTOREaccessingmemory只有简单的LOAD和STORE操作访问存储器Simplifyinstructionsetandcontrolunit简化指令集和控制器RISCincludeonly1or2ADDinstructionsVAXhas25differentADDinstructionsEncouragestheoptimizationofregisteruse更适合于寄存器的优化使用Frequentlyaccessedoperandsremaininhigh-speedstorage频繁存取的操作数保留在高速存储装置,51,SimpleAddressingModes,AlmostallRISCinstructionsusesimpleregisteraddressing几乎全部RISC指令都使用寄存器寻址方式MayincludeseveraladditionalmodesDisplacementandPC-relative可能包括几种其它寻址方式，如偏移和相对Simplifyinstructionsetandcontrolunit简化指令集和控制器,52,SimpleInstructionFormats,Onlyoneorafewformatsareused仅使用一种或少数几种格式Instructionlengthisfixedandalignedonwordboundaries指令长度固定并且在字边界上对齐Asingleinstructiondoesnotcrosspageboundaries单一指令不会跨越内存分页的边界Fieldlocations,especiallytheopcode,arefixed字段位置，特别是操作码字段位置是固定的Opcodedecodingandregisteroperandaccessingcanoccursimultaneously操作码的译码和寄存器操作数的访问能同时出现Simplifycontrolunit简化控制器,53,CISCvRISC,TypicalofaRISCAsingleinstructionsize(typically4bytes)单一指令长度（典型4个字节）Asmallnumberofdataaddressingmodes(typicallylessthanfive)较少的寻址方式（典型小于5种）Noindirectaddressing无间接寻址Nooperationsthatcombineload/storewitharithmetic装入存储操作不会与算术操作混在一起Nomorethanonememory-addressedoperandperinstruction每条指令不会有多于个的存储器操作数Doesnotsupportarbitraryalignmentofdataforload/storeoperations对装入存储操作不支持数据的任意对齐,54,CISCvRISC,RISCdesignsmaybenefitfromtheinclusionofsomeCISCfeaturesR