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

会计学1深入理解计算机系统复习清华计算机系统结构等相关概念与范畴

第1页/共69页

概念——计算机系统结构编写出能够在机器上正确运行的系统程序所必须了解到的计算机系统的属性研究计算机系统软件与硬件的功能分配，确定计算机系统软件与硬件的分界面研究计算机系统的外部特性，即程序员所看到的计算机系统属性第2页/共69页程序员看到的计算机系统属性

数据表示：硬件直接认别和处理的数据类型

寻址技术：编址方式、寻址方式和定位方式

寄存器定义：寄存器定义、数量和使用规则

指令系统：指令的操作类型、格式、排序等

存储系统：要求速度高、容量大、价格便宜

中断系统：中断类型、中断级别和响应方式

输入输出系统：数据交换方式、交换过程控制

机器工作状态：定义和切换方式，如内核态、执行态、管理态和用户态等第3页/共69页概念——计算机组成计算机系统的逻辑实现

设计功能部件：处理器，主存储器等

数据通路的宽度

各种操作对功能部件的共享程度

确定功能部件的并行度

设计缓冲和排队策略

设计控制机构

采用何种可靠性技术概念——汇编语言用符号表示的机器语言，可包括宏构造第4页/共69页概念——冯诺依曼计算机第5页/共69页特点:存储程序、运算器为中心、集中控制

存储器是字长固定的、顺序线性编址的一维结构，每个地址是唯一定义的

由指令形式的低级机器语言驱动

指令顺序执行，一般按照指令在存储器中存放的顺序执行，程序分支由转移指令实现

运算器为中心，输入输出设备与存储器之间的数据传送都途经运算器

集中控制，运算器、存储器、输入输出设备的操作以及它们之间的联系都由控制器控制第6页/共69页现代处理器运算速度计算公式： P＝FzXIPCXTPC其中:Fz为处理机的工作主频IPC(InstructionPerCycle)指令级并行度TPC(ThreadingPerCycle)线程级并行度例如：主频3GHz，4核Pentium4处理器的最高运算速度为：P＝3GHzX4IPCX4TPC=48GIPS

即：每秒钟480亿次概念——处理器运算速度第7页/共69页提高处理器性能的主要途径(1)提高主频Fz：

增加流水线级数，依靠计算机系统结构

缩短门电路延迟时间，依靠电子技术(2)提高指令级并行度IPC

依靠并行算法和计算机系统结构(3)提高线程级并行度TPC

依靠并行算法、程序设计和计算机系统结构第8页/共69页近期出现的新问题：

线延迟大于门延迟

漏电流很大

功耗惊人•近期提高计算机性能的途径

只能依靠并行算法、程序设计和计算机系统结构，不能指望电子技术不仅对计算机系统结构，而且对并行算法、软件技术和计算机应用技术都将产生深远的影响第9页/共69页

概念——指令执行速度第10页/共69页第11页/共69页平均速度第12页/共69页概念——Amdahl定律第13页/共69页第14页/共69页第15页/共69页数的表示第16页/共69页Bits,Bytes,andIntegersSizesofCObjects(inBytes)CDataType Typical32-bit IntelIA32 x86-64char 1 1 1short 2 2 2int 4 4 4long 4 4 8longlong 8 8 8float 4 4 4double 8 8 8longdouble 8 10/12 10/16char* 4 4 8Oranyotherpointer第17页/共69页Bit-LevelOperationsinCOperations&,|,~,^AvailableinCLogicOperationsinC&&,||,!View0as“False”Anythingnonzeroas“True”Alwaysreturn0or1EarlyterminationShiftOperationsLogicalvs.ArithmeticShiftamount<0orwordsize第18页/共69页Signedvs.UnsignedinCConstantsBydefaultareconsideredtobesignedintegersUnsignedifhave“U”assuffix0U,4294967259UCastingExplicitcastingbetweensigned&unsignedsameasU2TandT2Uinttx,ty;unsignedux,uy;tx=(int)ux;uy=(unsigned)ty;Implicitcastingalsooccursviaassignmentsandprocedurecallstx=ux;uy=ty;Unsignedisdangerous!第19页/共69页IntegerCPuzzlesRevisitedx<0 ((x*2)<0)ux>=0x&7==7 (x<<30)<0ux>-1x>y -x<-yx*x>=0x>0&&y>0 x+y>0x>=0 -x<=0x<=0 -x>=0(x|-x)>>31==-1ux>>3==ux/8x>>3==x/8x&(x-1)!=0intx=foo();inty=bar();unsignedux=x;unsigneduy=y;Initialization第20页/共69页FloatingPointRepresentationBitstorightof“binarypoint”representfractionalpowersof2Representsrationalnumber:bibi–1b2b1b0b–1b–2b–3b–j••••••.1242i–12i••••••1/21/41/82–j第21页/共69页NumericalForm–1sM2ESignbitsdetermineswhethernumberisnegativeorpositiveSignificandMnormallyafractionalvalueinrange[1.0,2.0).ExponentEweightsvaluebypoweroftwoEncodingMSBissignbitexpfieldencodesEfracfieldencodesMSizesSingleprecision:8expbits,23fracbitsDoubleprecision:11expbits,52fracbitsExtendedprecision:15expbits,63fracbitsFloatingPointRepresentationsexpfrac第22页/共69页“Normalized”NumericValuesCondition

exp

000…0andexp

111…1Exponentcodedasbiasedvalue

E=Exp–BiasExp:unsignedvaluedenotedbyexpBias:BiasvalueSingleprecision:127(Exp:1…254,E:-126…127)Doubleprecision:1023(Exp:1…2046,E:-1022…1023)ingeneral:Bias=2e-1-1,whereeisnumberofexponentbitsSignificandcodedwithimpliedleading1

M=

1.xxx…x2

xxx…x:bitsoffracMinimumwhen000…0

(M=1.0)Maximumwhen111…1

(M=2.0–)Getextraleadingbitfor“free”第23页/共69页DenormalizedValuesCondition

exp=000…0ValueExponentvalueE=–Bias+1SignificandvalueM=

0.xxx…x2xxx…x:bitsoffracCases

exp=000…0,frac=000…0Notethathavedistinctvalues+0and–0exp=000…0,frac

000…0Condition

exp=111…1Cases

exp=111…1,frac=000…0Representsvalue(infinity)OperationthatoverflowsBothpositiveandnegativeexp=111…1,frac

000…0Not-a-Number(NaN)第24页/共69页sexpfrac E

Value

00000000 -6 000000001 -6 1/8*1/64=1/51200000010 -6 2/8*1/64=2/512…00000110 -6 6/8*1/64=6/51200000111 -6 7/8*1/64=7/51200001 000 -6 8/8*1/64=8/51200001001 -6 9/8*1/64=9/512…00110110 -1 14/8*1/2=14/1600110111 -1 15/8*1/2=15/1600111000 0 8/8*1=100111001 0 9/8*1=9/800111010 0 10/8*1=10/8…01110 110 7 14/8*128=22401110111 7 15/8*128=24001111000 n/a infclosesttozerolargestdenormsmallestnormclosestto1belowclosestto1abovelargestnormDenormalizednumbersNormalizednumbers第25页/共69页Round-To-EvenBinaryFractionalNumbers“Even”whenleastsignificantbitis0Halfwaywhenbitstorightofroundingposition=100…2ExamplesRoundtonearest1/4(2bitsrightofbinarypoint)Value Binary Rounded Action RoundedValue23/32 10.000112 10.002 (<1/2—down)

223/16 10.001102 10.012 (>1/2—up)

21/427/8 10.111002 11.002 (1/2—up)

325/8 10.101002 10.102 (1/2—down)

21/2第26页/共69页FloatingPointinCCGuaranteesTwoLevelsfloat singleprecisiondouble doubleprecisionConversionsCastingbetweenint,float,anddoublechangesnumericvalues

DoubleorfloattointTruncatesfractionalpartLikeroundingtowardzeroNotdefinedwhenoutofrangeorNaNGenerallysetstoTminorTmax

inttodoubleExactconversion,aslongasinthas≤53bitwordsize

inttofloatWillroundaccordingtoroundingmode第27页/共69页FloatingPointPuzzlesForeachofthefollowingCexpressions,either:ArguethatitistrueforallargumentvaluesExplainwhynottruex==(int)(float)xx==(int)(double)xf==(float)(double)fd==(float)df==-(-f);2/3==2/3.0d<0.0 ((d*2)<0.0)d>f -f>-dd*d>=0.0(d+f)-d==fintx=…;floatf=…;doubled=…;AssumeneitherdnorfisNaN第28页/共69页汇编与C语言第29页/共69页movlOperandCombinationsCannotdomemory-memorytransferwithasingleinstructionmovlImmRegMemRegMemRegMemRegSourceDestCAnalogmovl$0x4,%eaxtemp=0x4;movl$-147,(%eax)*p=-147;movl%eax,%edxtemp2=temp1;movl%eax,(%edx)*p=temp;movl(%eax),%edxtemp=*p;Src,Dest第30页/共69页IndexedAddressingModesMostGeneralForm D(Rb,Ri,S) Mem[Reg[Rb]+S*Reg[Ri]+D]D: Constant“displacement”Rb: Baseregister:Anyof8integerregistersRi: Indexregister:Any,exceptfor%espUnlikelyyou’duse%ebp,eitherS: Scale:1,2,4,or8SpecialCases (Rb,Ri) Mem[Reg[Rb]+Reg[Ri]] D(Rb,Ri) Mem[Reg[Rb]+Reg[Ri]+D] (Rb,Ri,S) Mem[Reg[Rb]+S*Reg[Ri]]第31页/共69页AddressComputationInstructionleal

Src,DestSrcisaddressmodeexpressionSetDesttoaddressdenotedbyexpressionUsesComputingaddresseswithoutamemoryreferenceE.g.,translationofp=&x[i];Computingarithmeticexpressionsoftheformx+k*yk=1,2,4,or8.第32页/共69页%rax%rdx%rcx%rbx%rsi%rdi%rsp%rbpx86-64GeneralPurposeRegistersExtendexistingregisters.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第33页/共69页Swapin64-bitModeOperandspassedinregistersFirst(xp)in%rdi,second(yp)in%rsi64-bitpointersNostackoperationsrequired32-bitdataDataheldinregisters%eaxand%edx

movloperationvoidswap(int*xp,int*yp){intt0=*xp;intt1=*yp;*xp=t1;*yp=t0;}swap: movl (%rdi),%edx movl (%rsi),%eax movl %eax,(%rdi) movl %edx,(%rsi) retq第34页/共69页ReadingConditionCodesSetXInstructionsSetsinglebytebasedoncombinationsofconditioncodes第35页/共69页ConditionalBranchExampleintabsdiff(intx,inty){intresult;if(x>y){result=x-y;}else{result=y-x;}returnresult;}absdiff: pushl%ebp movl%esp,%ebp movl8(%ebp),%edx movl12(%ebp),%eax cmpl%eax,%edx jle.L7 subl%eax,%edx movl%edx,%eax.L8: leave ret.L7: subl%edx,%eax jmp.L8Body1SetUpFinishBody2第36页/共69页 pushl%ebp movl %esp,%ebp pushl %ebx movl 8(%ebp),%ecx movl 12(%ebp),%edx movl %ecx,%ebx subl %edx,%ebx movl %edx,%eax subl %ecx,%eax cmpl %edx,%ecx cmovg%ebx,%eax popl %ebx popl %ebp retintabsdiff(intx,inty){intresult;if(x>y){result=x-y;}else{result=y-x;}returnresult;}Gcc4.3.4NewConditionalBranchExample第37页/共69页ImplementingLoopsIA32Allloopstranslatedintoformbasedon“do-while”x86-64Alsomakeuseof“jumptomiddle”WhytheDifferenceIA32compilerdevelopedformachinewherealloperationscostlyx86-64compilerdevelopedformachinewhereunconditionalbranchesincur(almost)nooverhead第38页/共69页“For”“While”“Do-While”for(Init;Test;Update)

BodyInit;while(Test){

Body

Update;}GotoVersion

Init;if(!Test)gotodone;loop:

Body

Update;if(Test)gotoloop;done:WhileVersionForVersionDo-WhileVersion

Init;if(!Test)gotodone;do{

Body

Update;}while(Test)done:第39页/共69页“For”“While”(Jump-to-Middle)for(Init;Test;Update)

BodyInit;while(Test){

Body

Update;}

Init;gotomiddle;loop:

Body

Update;middle:if(Test)gotoloop;done:WhileVersionForVersionGotoVersion第40页/共69页SwitchStatementsImplementationOptionsSeriesofconditionalsOrganizeintreestructureLogarithmicperformanceJumpTableLookupbranchtargetConstanttimePossiblewhencasesaresmallintegerconstantsGCCPicksonebasedoncasestructure第41页/共69页StackPointer%espyoowhoprocFramePointer%ebpStack“Top”IA32-StackFramesContentsLocalvariablesReturninformationTemporaryspaceManagementSpaceallocatedwhenenterprocedure“Set-up”codeDeallocatedwhenreturn“Finish”codePointersStackpointer%espindicatesstacktopFramepointer%ebpindicatesstartofcurrentframeamI第42页/共69页IA32/LinuxStackFrameCurrentStackFrame(“Top”toBottom)Parametersforfunctionabouttocall“Argumentbuild”LocalvariablesIfcan’tkeepinregistersSavedregistercontextOldframepointerCallerStackFrameReturnaddressPushedbycallinstructionArgumentsforthiscallStackPointer(%esp)FramePointer(%ebp)ReturnAddrSavedRegisters+LocalVariablesArgumentBuildOld%ebpArgumentsCallerFrame第43页/共69页IA32/LinuxRegisterUsageIntegerRegistersTwohavespecialuses%ebp,%espThreemanagedascallee-save%ebx,%esi,%ediOldvaluessavedonstackpriortousingThreemanagedascaller-save%eax,%edx,%ecxDowhatyouplease,butexpectanycalleetodoso,aswellRegister%eaxalsostoresreturnedvalue%eax%edx%ecx%ebx%esi%edi%esp%ebpCaller-SaveTemporariesCallee-SaveTemporariesSpecial第44页/共69页%rax%rbx%rcx%rdx%rsi%rdi%rsp%rbpx86-64RegisterConventions%r8%r9%r10%r11%r12%r13%r14%r15ReturnValueCalleeSavedArgument#4Argument#3Argument#2Argument#1StackPointerCalleeSavedArgument#5Argument#6CalleeSavedUsedforlinkingC:CalleeSavedCalleeSavedCalleeSavedCalleeSaved第45页/共69页x86-64RegistersArgumentspassedtofunctionsviaregistersIfmorethan6integralparameters,thenpassrestonstackTheseregisterscanbeusedascaller-savedaswellAllReferencestoStackFrameviaStackPointerEliminatesneedtoupdate%ebpOtherRegisters6+1calleesaved2or3havespecialuses第46页/共69页x86-64LocalsintheRedZoneAvoidingStackPointerChangeCanholdallinformationwithinsmallwindowbeyondstackpointer/*Swap,usinglocalarray*/voidswap_a(long*xp,long*yp){volatilelongloc[2];loc[0]=*xp;loc[1]=*yp;*xp=loc[1];*yp=loc[0];}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)retrtnPtrunused%rsp−8loc[1]loc[0]−16−24第47页/共69页x86-64NonLeafwithoutStackFrameNovaluesheldwhileswapbeinginvokedNocalleesaveregistersneededlongscount=0;/*Swapa[i]&a[i+1]*/voidswap_ele_se(longa[],inti){swap(&a[i],&a[i+1]);scount++;}swap_ele_se:movslq%esi,%rsi#Signextendileaq(%rdi,%rsi,8),%rdi#&a[i]leaq8(%rdi),%rsi#&a[i+1]callswap#swap()

incqscount(%rip)#scount++;ret第48页/共69页x86-64CallusingJumpWhenswapexecutesret,itwillreturnfromswap_elePossiblesinceswapisa“tailcall”longscount=0;/*Swapa[i]&a[i+1]*/voidswap_ele(longa[],inti){swap(&a[i],&a[i+1]);}swap_ele:movslq%esi,%rsi#Signextendileaq(%rdi,%rsi,8),%rdi#&a[i]leaq8(%rdi),%rsi#&a[i+1]jmpswap#swap()第49页/共69页InterestingFeaturesofStackFrameAllocateEntireFrameatOnceAllstackaccessescanberelativeto%rspDobydecrementingstackpointerCandelayallocation,sincesafetotemporarilyuseredzoneSimpleDeallocationIncrementstackpointer第50页/共69页BasicDataTypesIntegralStored&operatedoningeneralregistersSignedvs.unsigneddependsoninstructionsusedIntel GAS Bytes Cbyte b 1 [unsigned]charword w 2 [unsigned]shortdoubleword l 4 [unsigned]intquadword q 8 [unsigned]longint(x86-64)FloatingPointStored&operatedoninfloatingpointregistersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12/16 longdouble第51页/共69页ArrayAllocationBasicPrincipleT

A[L];ArrayofdatatypeTandlengthLContiguouslyallocatedregionofL*sizeof(T)bytesIdentifierAcanbeusedasapointertoarrayelement0TypeT*第52页/共69页ViewingasMultidimensionalArrayDeclarationT

A[R][C];2DarrayofdatatypeTRrows,CcolumnsTypeTelementrequiresKbytesArraySizeR*C*KbytesArrangementRow-MajorOrderingA[0][0]A[0][C-1]A[R-1][0]•

•

••

•

•A[R-1][C-1]••••••intA[R][C];A[0][0]A[0][C-1]•

•

•A[1][0]A[1][C-1]•

•

•A[R-1][0]A[R-1][C-1]•

•

••

•

•4*R*CBytes第53页/共69页•

•

•NestedArrayRowAccessRowVectors

A[i]isarrayofCelementsEachelementoftypeTrequiresKbytesStartingaddressA+

i*(C*K)A[i][0]A[i][C-1]•

•

•A[i]A[R-1][0]A[R-1][C-1]•

•

•A[R-1]•

•

•AA[0][0]A[0][C-1]•

•

•A[0]intA[R][C];A+i*C*4A+(R-1)*C*4第54页/共69页•

•

•NestedArrayElementAccessArrayElements

A[i][j]iselementoftypeTAddressA+i*(C*K)

+j*K=A+(i*C+j)*K•

•

•A[i][j]A[i][j]•

•

•A[i]A[R-1][0]A[R-1][C-1]•

•

•A[R-1]•

•

•AA[0][0]A[0][C-1]•

•

•A[0]intA[R][C];A+i*C*4A+(R-1)*C*4A+(i*C+j)*4第55页/共69页NestedArrayElementAccessCodeArrayElements

pgh[index][dig]isintAddress:

pgh+20*index+4*digIA32CodeComputesaddresspgh+4*dig+4*(index+4*index)

movlperformsmemoryreferenceintget_pgh_digit(intindex,intdig){returnpgh[index][dig];} #%ecx=dig #%eax=index leal0(,%ecx,4),%edx #4*dig leal(%eax,%eax,4),%eax #5*index movlpgh(%edx,%eax,4),%eax #*(pgh+4*dig+20*index)第56页/共69页ArrayElementAccessesSimilarCreferencesNestedArrayElementatMem[pgh+20*index+4*dig]DifferentaddresscomputationMulti-LevelArrayElementatMem[Mem[univ+4*index]+4*dig]intget_pgh_digit(intindex,intdig){returnpgh[index][dig];}intget_univ_digit(intindex,intdig){returnuniv[index][dig];}第57页/共69页UsingNestedArraysStrengthsCcompilerhandlesdoublysubscriptedarraysGeneratesveryefficientcodeAvoidsmultiplyinindexcomputationLimitationOnlyworksifhavefixedarraysize#defineN16typedefintfix_matrix[N][N];/*Computeelementi,koffixedmatrixproduct*/intfix_prod_ele(fix_matrixa,fix_matrixb,inti,intk){intj;intresult=0;for(j=0;j<N;j++)result+=a[i][j]*b[j][k];returnresult;}A(i,*)B(*,k)Column-wiseRow-wise第58页/共69页DynamicNestedArraysStrengthCancreatematrixofarbitrarysizeProgrammingMustdoindexcomputationexplicitlyPerformanceAccessingsingleelementcostlyMustdomultiplicationint*new_var_matrix(intn){return(int*)calloc(sizeof(int),n*n);}intvar_ele(int*a,inti,intj,intn){returna[i*n+j];} movl12(%ebp),%eax #i movl8(%ebp),%edx #a imull20(%ebp),%eax #n*i addl16(%ebp),%eax #n*i+j movl(%edx,%eax,4),%eax #Mem[a+4*(i*n+j)]第59页/共69页OptimizingDynamicArrayMult.OptimizationsPerformedwhensetoptimizationlevelto-O2CodeMotionExpressioni*ncanbecomputedoutsideloopStrengthReductionIncrementingjhaseffectofincrementingj*n+kbynPerformanceCompilercanoptimizeregularaccesspatterns{intj;intresult=0;for(j=0;j<n;j++)result+=a[i*n+j]*b[j*n+k];returnresult;}{intj;intresult=0;intiTn=i*n;intjTnPk=k;for(j=0;j<n;j++){result+=a[iTn+j]*b[jTnPk];jTnPk+=n;}returnresult;}第60页/共69页structS1{charc;inti[2];doublev;}*p;SatisfyingAlignmentwithStructuresOffsetsWithinStructureMustsatisfyelement’salignmentrequirementOverallStructurePlacementEachstructurehasalignmentrequirementKLargestalignmentofanyelementInitialaddress&structurelengthmustbemultiplesofKExample(underWindowsorx86-64):K=8,duetodoubleelementci[0]i[1]vp+0p+4p+8p+16p+24Multipleof4Multipleof8Multipleof8Multipleof8第61页/共69页SpecificCasesofAlignment(IA32)SizeofPrimitiveDataType:1byte(e.g.,char)norestrictionsonaddress2bytes(e.g.,short)lowest1bitofaddressmustbe024bytes(e.g.,int,float,char*,etc.)lowest2bitsofaddressmustbe0028bytes(e.g.,double)Windows(andmostotherOS’s&instructionsets):lowest3bitsofaddressmustbe0002Linux:lowest2bitsofaddressmustbe002i.e.,treatedthesameasa4-byteprimitivedatatype12bytes(longdouble)Windows,Linux:lowest2bitsofaddressmustbe002i.e.,treatedthesameasa4-byteprimitivedatatype第62页/共69页SpecificCasesofAlignment(x86-64)SizeofPrimitiveDataType:1byte(e.g.,char)norestrictionsonaddress2bytes