深入理解计算机系统_复习_清华.ppt

计算机组成原理,Zhang,Youhui(张悠慧)zyh02,2010秋季,课程回顾,Topics计算机系统结构等相关概念与范畴数的表示汇编语言与C语言代码优化,计算机系统结构等相关概念与范畴,概念计算机系统结构,编写出能够在机器上正确运行的系统程序所必须了解到的计算机系统的属性研究计算机系统软件与硬件的功能分配，确定计算机系统软件与硬件的分界面研究计算机系统的外部特性，即程序员所看到的计算机系统属性,程序员看到的计算机系统属性数据表示：硬件直接认别和处理的数据类型寻址技术：编址方式、寻址方式和定位方式寄存器定义：寄存器定义、数量和使用规则指令系统：指令的操作类型、格式、排序等存储系统：要求速度高、容量大、价格便宜中断系统：中断类型、中断级别和响应方式输入输出系统：数据交换方式、交换过程控制机器工作状态：定义和切换方式，如内核态、执行态、管理态和用户态等,概念计算机组成,计算机系统的逻辑实现设计功能部件：处理器，主存储器等数据通路的宽度各种操作对功能部件的共享程度确定功能部件的并行度设计缓冲和排队策略设计控制机构采用何种可靠性技术,概念汇编语言,用符号表示的机器语言，可包括宏构造,概念冯诺依曼计算机,特点:存储程序、运算器为中心、集中控制存储器是字长固定的、顺序线性编址的一维结构，每个地址是唯一定义的由指令形式的低级机器语言驱动指令顺序执行，一般按照指令在存储器中存放的顺序执行，程序分支由转移指令实现运算器为中心，输入输出设备与存储器之间的数据传送都途经运算器集中控制，运算器、存储器、输入输出设备的操作以及它们之间的联系都由控制器控制,现代处理器运算速度计算公式：PFzXIPCXTPC其中:Fz为处理机的工作主频IPC(InstructionPerCycle)指令级并行度TPC(ThreadingPerCycle)线程级并行度例如：主频3GHz，4核Pentium4处理器的最高运算速度为：P3GHzX4IPCX4TPC=48GIPS即：每秒钟480亿次,概念处理器运算速度,提高处理器性能的主要途径(1)提高主频Fz：增加流水线级数，依靠计算机系统结构缩短门电路延迟时间，依靠电子技术(2)提高指令级并行度IPC依靠并行算法和计算机系统结构(3)提高线程级并行度TPC依靠并行算法、程序设计和计算机系统结构,近期出现的新问题：线延迟大于门延迟漏电流很大功耗惊人近期提高计算机性能的途径只能依靠并行算法、程序设计和计算机系统结构，不能指望电子技术不仅对计算机系统结构，而且对并行算法、软件技术和计算机应用技术都将产生深远的影响,概念指令执行速度,平均速度,概念Amdahl定律,数的表示,Bits,Bytes,andIntegers,SizesofCObjects(inBytes)CDataTypeTypical32-bitIntelIA32x86-64char111short222int444long448longlong888float444double888longdouble810/1210/16char*448Oranyotherpointer,Bit-LevelOperationsinCOperationsinty=bar();unsignedux=x;unsigneduy=y;,Initialization,FloatingPoint,RepresentationBitstorightof“binarypoint”representfractionalpowersof2Representsrationalnumber:,1,2,4,2i1,2i,1/2,1/4,1/8,2j,NumericalForm1sM2ESignbitsdetermineswhethernumberisnegativeorpositiveSignificandMnormallyafractionalvalueinrange1.0,2.0).ExponentEweightsvaluebypoweroftwoEncodingMSBissignbitexpfieldencodesEfracfieldencodesMSizesSingleprecision:8expbits,23fracbitsDoubleprecision:11expbits,52fracbitsExtendedprecision:15expbits,63fracbits,FloatingPointRepresentation,s,exp,frac,“Normalized”NumericValues,Conditionexp0000andexp1111ExponentcodedasbiasedvalueE=ExpBiasExp:unsignedvaluedenotedbyexpBias:BiasvalueSingleprecision:127(Exp:1254,E:-126127)Doubleprecision:1023(Exp:12046,E:-10221023)ingeneral:Bias=2e-1-1,whereeisnumberofexponentbitsSignificandcodedwithimpliedleading1M=1.xxxx2xxxx:bitsoffracMinimumwhen0000(M=1.0)Maximumwhen1111(M=2.0)Getextraleadingbitfor“free”,DenormalizedValues,Conditionexp=0000ValueExponentvalueE=Bias+1SignificandvalueM=0.xxxx2xxxx:bitsoffracCasesexp=0000,frac=0000Notethathavedistinctvalues+0and0exp=0000,frac0000,Conditionexp=1111Casesexp=1111,frac=0000Representsvalue(infinity)OperationthatoverflowsBothpositiveandnegativeexp=1111,frac0000Not-a-Number(NaN),sexpfracEValue00000000-6000000001-61/8*1/64=1/51200000010-62/8*1/64=2/51200000110-66/8*1/64=6/51200000111-67/8*1/64=7/51200001000-68/8*1/64=8/51200001001-69/8*1/64=9/51200110110-114/8*1/2=14/1600110111-115/8*1/2=15/160011100008/8*1=10011100109/8*1=9/800111010010/8*1=10/801110110714/8*128=22401110111715/8*128=24001111000n/ainf,closesttozero,largestdenorm,smallestnorm,closestto1below,closestto1above,largestnorm,Denormalizednumbers,Normalizednumbers,Round-To-Even,BinaryFractionalNumbers“Even”whenleastsignificantbitis0Halfwaywhenbitstorightofroundingposition=1002ExamplesRoundtonearest1/4(2bitsrightofbinarypoint)ValueBinaryRoundedActionRoundedValue23/3210.00011210.002(1/2up)21/427/810.11100211.002(1/2up)325/810.10100210.102(1/2down)21/2,FloatingPointinC,CGuaranteesTwoLevelsfloatsingleprecisiondoubledoubleprecisionConversionsCastingbetweenint,float,anddoublechangesnumericvaluesDoubleorfloattointTruncatesfractionalpartLikeroundingtowardzeroNotdefinedwhenoutofrangeorNaNGenerallysetstoTminorTmaxinttodoubleExactconversion,aslongasinthas53bitwordsizeinttofloatWillroundaccordingtoroundingmode,FloatingPointPuzzles,ForeachofthefollowingCexpressions,either:ArguethatitistrueforallargumentvaluesExplainwhynottrue,x=(int)(float)xx=(int)(double)xf=(float)(double)fd=(float)df=-(-f);2/3=2/3.0df-f-dd*d=0.0(d+f)-d=f,intx=;floatf=;doubled=;,AssumeneitherdnorfisNaN,汇编与C语言,movlOperandCombinations,Cannotdomemory-memorytransferwithasingleinstruction,movl,Imm,Reg,Mem,Reg,Mem,Reg,Mem,Reg,Source,Dest,CAnalog,Src,Dest,IndexedAddressingModes,MostGeneralFormD(Rb,Ri,S)MemRegRb+S*RegRi+DD:Constant“displacement”Rb:Baseregister:Anyof8integerregistersRi:Indexregister:Any,exceptfor%espUnlikelyyouduse%ebp,eitherS:Scale:1,2,4,or8SpecialCases(Rb,Ri)MemRegRb+RegRiD(Rb,Ri)MemRegRb+RegRi+D(Rb,Ri,S)MemRegRb+S*RegRi,AddressComputationInstruction,lealSrc,DestSrcisaddressmodeexpressionSetDesttoaddressdenotedbyexpressionUsesComputingaddresseswithoutamemoryreferenceE.g.,translationofp=Computingarithmeticexpressionsoftheformx+k*yk=1,2,4,or8.,%rax,%rdx,%rcx,%rbx,%rsi,%rdi,%rsp,%rbp,x86-64GeneralPurposeRegisters,Extendexistingregisters.Add8newones.Make%ebp/%rbpgeneralpurpose,%eax,%edx,%ecx,%ebx,%esi,%edi,%esp,%ebp,%r8,%r9,%r10,%r11,%r12,%r13,%r14,%r15,%r8d,%r9d,%r10d,%r11d,%r12d,%r13d,%r14d,%r15d,Swapin64-bitMode,OperandspassedinregistersFirst(xp)in%rdi,second(yp)in%rsi64-bitpointersNostackoperationsrequired32-bitdataDataheldinregisters%eaxand%edxmovloperation,voidswap(int*xp,int*yp)intt0=*xp;intt1=*yp;*xp=t1;*yp=t0;,swap:movl(%rdi),%edxmovl(%rsi),%eaxmovl%eax,(%rdi)movl%edx,(%rsi)retq,ReadingConditionCodes,SetXInstructionsSetsinglebytebasedoncombinationsofconditioncodes,ConditionalBranchExample,intabsdiff(intx,inty)intresult;if(xy)result=x-y;elseresult=y-x;returnresult;,absdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L7subl%eax,%edxmovl%edx,%eax.L8:leaveret.L7:subl%edx,%eaxjmp.L8,Body1,SetUp,Finish,Body2,pushl%ebpmovl%esp,%ebppushl%ebxmovl8(%ebp),%ecxmovl12(%ebp),%edxmovl%ecx,%ebxsubl%edx,%ebxmovl%edx,%eaxsubl%ecx,%eaxcmpl%edx,%ecxcmovg%ebx,%eaxpopl%ebxpopl%ebpret,intabsdiff(intx,inty)intresult;if(xy)result=x-y;elseresult=y-x;returnresult;,Gcc4.3.4,NewConditionalBranchExample,ImplementingLoops,IA32Allloopstranslatedintoformbasedon“do-while”x86-64Alsomakeuseof“jumptomiddle”WhytheDifferenceIA32compilerdevelopedformachinewherealloperationscostlyx86-64compilerdevelopedformachinewhereunconditionalbranchesincur(almost)nooverhead,“For”“While”“Do-While”,for(Init;Test;Update)Body,Init;while(Test)BodyUpdate;,GotoVersion,Init;if(!Test)gotodone;loop:BodyUpdate;if(Test)gotoloop;done:,WhileVersion,ForVersion,Do-WhileVersion,Init;if(!Test)gotodone;doBodyUpdate;while(Test)done:,“For”“While”(Jump-to-Middle),for(Init;Test;Update)Body,Init;while(Test)BodyUpdate;,Init;gotomiddle;loop:BodyUpdate;middle:if(Test)gotoloop;done:,WhileVersion,ForVersion,GotoVersion,SwitchStatements,ImplementationOptionsSeriesofconditionalsOrganizeintreestructureLogarithmicperformanceJumpTableLookupbranchtargetConstanttimePossiblewhencasesaresmallintegerconstantsGCCPicksonebasedoncasestructure,yoo,who,proc,Stack“Top”,IA32-StackFrames,ContentsLocalvariablesReturninformationTemporaryspaceManagementSpaceallocatedwhenenterprocedure“Set-up”codeDeallocatedwhenreturn“Finish”codePointersStackpointer%espindicatesstacktopFramepointer%ebpindicatesstartofcurrentframe,amI,IA32/LinuxStackFrame,CurrentStackFrame(“Top”toBottom)Parametersforfunctionabouttocall“Argumentbuild”LocalvariablesIfcantkeepinregistersSavedregistercontextOldframepointerCallerStackFrameReturnaddressPushedbycallinstructionArgumentsforthiscall,StackPointer(%esp),FramePointer(%ebp),ReturnAddr,SavedRegisters+LocalVariables,ArgumentBuild,Old%ebp,Arguments,CallerFrame,IA32/LinuxRegisterUsage,IntegerRegistersTwohavespecialuses%ebp,%espThreemanagedascallee-save%ebx,%esi,%ediOldvaluessavedonstackpriortousingThreemanagedascaller-save%eax,%edx,%ecxDowhatyouplease,butexpectanycalleetodoso,aswellRegister%eaxalsostoresreturnedvalue,%eax,%edx,%ecx,%ebx,%esi,%edi,%esp,%ebp,Caller-SaveTemporaries,Callee-SaveTemporaries,Special,%rax,%rbx,%rcx,%rdx,%rsi,%rdi,%rsp,%rbp,x86-64RegisterConventions,%r8,%r9,%r10,%r11,%r12,%r13,%r14,%r15,ReturnValue,CalleeSaved,Argument#4,Argument#3,Argument#2,Argument#1,StackPointer,CalleeSaved,Argument#5,Argument#6,CalleeSaved,Usedforlinking,C:CalleeSaved,CalleeSaved,CalleeSaved,CalleeSaved,x86-64Registers,ArgumentspassedtofunctionsviaregistersIfmorethan6integralparameters,thenpassrestonstackTheseregisterscanbeusedascaller-savedaswellAllReferencestoStackFrameviaStackPointerEliminatesneedtoupdate%ebpOtherRegisters6+1calleesaved2or3havespecialuses,x86-64LocalsintheRedZone,AvoidingStackPointerChangeCanholdallinformationwithinsmallwindowbeyondstackpointer,/*Swap,usinglocalarray*/voidswap_a(long*xp,long*yp)volatilelongloc2;loc0=*xp;loc1=*yp;*xp=loc1;*yp=loc0;,swap_a:movq(%rdi),%raxmovq%rax,-24(%rsp)movq(%rsi),%raxmovq%rax,-16(%rsp)movq-16(%rsp),%raxmovq%rax,(%rdi)movq-24(%rsp),%raxmovq%rax,(%rsi)ret,rtnPtr,unused,%rsp,8,loc1,loc0,16,24,x86-64NonLeafwithoutStackFrame,NovaluesheldwhileswapbeinginvokedNocalleesaveregistersneeded,longscount=0;/*Swapai,swap_ele_se:movslq%esi,%rsi#Signextendileaq(%rdi,%rsi,8),%rdi#ret,x86-64CallusingJump,Whenswapexecutesret,itwillreturnfromswap_elePossiblesinceswapisa“tailcall”,longscount=0;/*Swapai,swap_ele:movslq%esi,%rsi#Signextendileaq(%rdi,%rsi,8),%rdi#ArrayofdatatypeTandlengthLContiguouslyallocatedregionofL*sizeof(T)bytesIdentifierAcanbeusedasapointertoarrayelement0TypeT*,ViewingasMultidimensionalArray,DeclarationTARC;2DarrayofdatatypeTRrows,CcolumnsTypeTelementrequiresKbytesArraySizeR*C*KbytesArrangementRow-MajorOrdering,intARC;,4*R*CBytes,NestedArrayRowAccess,RowVectorsAiisarrayofCelementsEachelementoftypeTrequiresKbytesStartingaddressA+i*(C*K),A,intARC;,A+i*C*4,A+(R-1)*C*4,NestedArrayElementAccess,ArrayElementsAijiselementoftypeTAddressA+i*(C*K)+j*K=A+(i*C+j)*K,Aij,Aij,Ai,A,intARC;,A+i*C*4,A+(R-1)*C*4,A+(i*C+j)*4,NestedArrayElementAccessCode,ArrayElementspghindexdigisintAddress:pgh+20*index+4*digIA32CodeComputesaddresspgh+4*dig+4*(index+4*index)movlperformsmemoryreference,intget_pgh_digit(intindex,intdig)returnpghindexdig;,#%ecx=dig#%eax=indexleal0(,%ecx,4),%edx#4*digleal(%eax,%eax,4),%eax#5*indexmovlpgh(%edx,%eax,4),%eax#*(pgh+4*dig+20*index),ArrayElementAccesses,SimilarCreferencesNestedArrayElementatMempgh+20*index+4*dig,DifferentaddresscomputationMulti-LevelArrayElementatMemMemuniv+4*index+4*dig,intget_pgh_digit(intindex,intdig)returnpghindexdig;,intget_univ_digit(intindex,intdig)returnunivindexdig;,UsingNestedArrays,StrengthsCcompilerhandlesdoublysubscriptedarraysGeneratesveryefficientcodeAvoidsmultiplyinindexcomputationLimitationOnlyworksifhavefixedarraysize,#defineN16typedefintfix_matrixNN;,/*Computeelementi,koffixedmatrixproduct*/intfix_prod_ele(fix_matrixa,fix_matrixb,inti,intk)intj;intresult=0;for(j=0;jN;j+)result+=aij*bjk;returnresult;,DynamicNestedArrays,StrengthCancreatematrixofarbitrarysizeProgrammingMustdoindexcomputationexplicitlyPerformanceAccessingsingleelementcostlyMustdomultiplication,int*new_var_matrix(intn)return(int*)calloc(sizeof(int),n*n);,intvar_ele(int*a,inti,intj,intn)ret