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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2010/10/24,#,Click to edit Master text styles,Second Level,Third level,Fourth level,Click to edit Master title style,#,15-213,F08,Click to edit Master text styles,Second Level,Third level,Fourth level,Click to edit Master title style,#,15-213,F08,计算机组成原理,Zhang,Youhui,(,张悠慧,),zyh02,2010,秋季,课程回顾,Topics,计算机系统结构等相关概念与范畴,数的表示,汇编语言与,C,语言,代码优化,计算机系统结构等相关概念与范畴,概念,计算机系统结构,编写出能够在机器上正确运行的系统程序所 必须了解到的计算机系统的属性,研究计算机系统软件与硬件的功能分配，确 定计算机系统软件与硬件的分界面,研究计算机系统的外部特性，即程序员所看 到的计算机系统属性,程序员看到的计算机系统属性,数据表示：硬件直接认别和处理的数据类型,寻址技术：编址方式、寻址方式和定位方式,寄存器定义：寄存器定义、数量和使用规则,指令系统：指令的操作类型、格式、排序等,存储系统：要求速度高、容量大、价格便宜,中断系统：中断类型、中断级别和响应方式,输入输出系统：数据交换方式、交换过程控制,机器工作状态：定义和切换方式，如内核态、执行态、管理态和用户态等,概念,计算机组成,计算机系统的逻辑实现,设计功能部件：处理器，主存储器等,数据通路的宽度,各种操作对功能部件的共享程度,确定功能部件的并行度,设计缓冲和排队策略,设计控制机构,采用何种可靠性技术,概念,汇编语言,用符号表示的机器语言，可包括宏构造,概念,冯诺依曼计算机,特点,:,存储程序、运算器为中心、集中控制,存储器是字长固定的、顺序线性编址的一维结构，每个地址是唯一定义的,由指令形式的低级机器语言驱动,指令顺序执行，一般按照指令在存储器中存放的顺序执行，程序分支由转移指令实现,运算器为中心，输入输出设备与存储器之间的数据传送都途经运算器,集中控制，运算器、存储器、输入输出设备的操作以及它们之间的联系都由控制器控制,现代处理器运算速度计算公式：,P,Fz X IPC X TPC,其中,:Fz,为处理机的工作主频,IPC(Instruction Per Cycle),指令级并行度,TPC(Threading Per Cycle),线程级并行度,例如：主频,3GHz,，,4,核,Pentium4,处理器的最高运算速度为：,P,3GHz X 4IPC X 4TPC=48GIPS,即：每秒钟,480,亿次,概念,处理器运算速度,提高处理器性能的主要途径,(1),提高主频,Fz,：,增加流水线级数，依靠计算机系统结构,缩短门电路延迟时间，依靠电子技术,(2),提高指令级并行度,IPC,依靠并行算法和计算机系统结构,(3),提高线程级并行度,TPC,依靠并行算法、程序设计和计算机系统结构,近期出现的新问题：,线延迟大于门延迟,漏电流很大,功耗惊人,近期提高计算机性能的途径,只能依靠并行算法、程序设计和计算机系统结构，不能指望电子技术,不仅对计算机系统结构，而且对并行算法、软件技术和计算机应用技术都将产生深远的 影响,概念,指令执行速度,平均速度,概念,Amdahl,定律,数的表示,Bits,Bytes,and Integers,Sizes of C Objects(in Bytes),C Data TypeTypical 32-bitIntel IA32x86-64,char111,short222,int444,long448,long long888,float444,double888,long double810/1210/16,char*448,Or any other pointer,Bit-Level Operations in C,Operations&,|,Available in C,Logic Operations in C,&,|,!,View 0 as“False”,Anything nonzero as“True”,Always return 0 or 1,Early termination,Shift Operations,Logical vs.Arithmetic,Shift amount 0 or,word size,Signed vs.Unsigned in C,Constants,By default,are considered to be,signed integers,Unsigned if have“U”as suffix,0U,4294967259U,Casting,Explicit casting between signed&unsigned same as U2T and T2U,int tx,ty;,unsigned ux,uy;,tx=(int)ux;,uy=(unsigned)ty;,Implicit casting also occurs via assignments and procedure calls,tx=ux;,uy=ty;,Unsigned is dangerous!,Integer C Puzzles Revisited,x 0,(x*2)=0,x&7=7,(x30)-1,x y,-x=0,x 0&y 0,x+y 0,x=0,-x=0,x=0,(x|-x)31=-1,ux 3=ux/8,x 3=x/8,x&(x-1)!=0,int x=foo();,int y=bar();,unsigned ux=x;,unsigned uy=y;,Initialization,Floating Point,Representation,Bits to right of“binary point”represent fractional powers of 2,Represents rational number:,b,i,b,i,1,b,2,b,1,b,0,b,1,b,2,b,3,b,j,.,1,2,4,2,i,1,2,i,1/2,1/4,1/8,2,j,Numerical Form,1,s,M,2,E,Sign bit,s,determines whether number is negative or positive,Significand,M,normally a fractional value in range 1.0,2.0).,Exponent,E,weights value by power of two,Encoding,MSB is sign bit,exp,field encodes,E,frac,field encodes,M,Sizes,Single precision:8 exp bits,23 frac bits,Double precision:11,exp,bits,52,frac,bits,Extended precision:15,exp,bits,63,frac,bits,Floating Point Representation,s,exp,frac,“Normalized”Numeric Values,Condition,exp,000,0,and,exp,111,1,Exponent coded as,biased,value,E,=,Exp Bias,Exp,:unsigned value denoted by,exp,Bias,:Bias value,Single precision:127(,Exp,:1254,E,:-126127),Double precision:1023(,Exp,:12046,E,:-10221023),in general:,Bias,=2,e-1,-1,where e is number of exponent bits,Significand coded with implied leading 1,M,=,1.xxx,x,2,xxx,x,:bits of,frac,Minimum when,000,0,(,M,=1.0),Maximum when,111,1,(,M,=2.0,),Get extra leading bit for“free”,Denormalized Values,Condition,exp,=,000,0,Value,Exponent value,E,=,Bias,+1,Significand value,M,=,0.xxx,x,2,xxx,x,:bits of,frac,Cases,exp,=,000,0,frac,=,000,0,Note that have distinct values+0 and 0,exp,=,000,0,frac,000,0,Condition,exp,=,111,1,Cases,exp,=,111,1,frac,=,000,0,Represents value,(infinity),Operation that overflows,Both positive and negative,exp,=,111,1,frac,000,0,Not-a-Number(NaN),s exp frac,E,Value,0 0000 000-60,0 0000 001-61/8*1/64=1/512,0 0000 010-62/8*1/64=2/512,0 0000 110-66/8*1/64=6/512,0 0000 111-67/8*1/64=7/512,0 0001000-68/8*1/64=8/512,0 0001 001 -69/8*1/64=9/512,0 0110 110-114/8*1/2=14/16,0 0110 111-115/8*1/2=15/16,0 0111 00008/8*1 =1,0 0111 00109/8*1 =9/8,0 0111 010010/8*1 =10/8,0 1110110714/8*128=224,0 1110 111715/8*128=240,0 1111 000n/ainf,closest to zero,largest denorm,smallest norm,closest to 1 below,closest to 1 above,largest norm,Denormalized,numbers,Normalized,numbers,Round-To-Even,Binary Fractional Numbers,“Even”when least significant bit is,0,Half way when bits to right of rounding position=,100,2,Examples,Round to nearest 1/4(2 bits right of binary point),ValueBinaryRoundedActionRounded Value,2 3/32,10.00,011,2,10.00,2,(1/2up),2 1/4,2 7/8,10.11,100,2,11.00,2,(1/2up),3,2 5/8,10.10,100,2,10.10,2,(1/2down),2 1/2,Floating Point in C,C Guarantees Two Levels,float,single precision,double,double precision,Conversions,Casting between,int,float,and,double,changes numeric values,Double,or,float,to,int,Truncates fractional part,Like rounding toward zero,Not defined when out of range or NaN,Generally sets to Tmin or Tmax,int,to,double,Exact conversion,as long as int has,53 bit word size,int,to,float,Will round according to rounding mode,Floating Point Puzzles,For each of the following C expressions,either:,Argue that it is true for all argument values,Explain why not true,x=(int)(float)x,x=(int)(double)x,f=(float)(double)f,d=(float)d,f=-(-f);,2/3=2/3.0,d 0.0,(d*2)f,-f -d,d*d=0.0,(d+f)-d=f,int x=;,float f=;,double d=;,Assume neither,d,nor,f,is NaN,汇编与,C,语言,movl,Operand Combinations,Cannot do memory-memory transfer with a single instruction,movl,Imm,Reg,Mem,Reg,Mem,Reg,Mem,Reg,Source,Dest,C Analog,movl$0 x4,%eax,temp=0 x4;,movl$-147,(%eax),*p=-147;,movl%eax,%edx,temp2=temp1;,movl%eax,(%edx),*p=temp;,movl(%eax),%edx,temp=*p;,Src,Dest,Indexed Addressing Modes,Most General Form,D(Rb,Ri,S)MemRegRb+S*RegRi+D,D:Constant“displacement”,Rb:Base register:Any of 8 integer registers,Ri:Index register:Any,except for,%esp,Unlikely youd use,%ebp,either,S:Scale:1,2,4,or 8,Special Cases,(Rb,Ri)MemRegRb+RegRi,D(Rb,Ri)MemRegRb+RegRi+D,(Rb,Ri,S)MemRegRb+S*RegRi,Address Computation Instruction,leal,Src,Dest,Src,is address mode expression,Set,Dest,to address denoted by expression,Uses,Computing addresses without a memory reference,E.g.,translation of,p=,Computing arithmetic expressions of the form x+k*y,k=1,2,4,or 8.,%rax,%rdx,%rcx,%rbx,%rsi,%rdi,%rsp,%rbp,x86-64 General Purpose Registers,Extend existing registers.Add 8 new ones.,Make,%ebp,/,%rbp,general purpose,%eax,%edx,%ecx,%ebx,%esi,%edi,%esp,%ebp,%r8,%r9,%r10,%r11,%r12,%r13,%r14,%r15,%r8d,%r9d,%r10d,%r11d,%r12d,%r13d,%r14d,%r15d,Swap in 64-bit Mode,Operands passed in registers,First(,xp,)in,%rdi,second(,yp,)in,%rsi,64-bit pointers,No stack operations required,32-bit data,Data held in registers,%eax,and,%edx,mov,l,operation,void swap(int*xp,int*yp),int t0=*xp;,int t1=*yp;,*xp=t1;,*yp=t0;,swap:,movl(%rdi),%edx,movl(%rsi),%eax,movl%eax,(%rdi),movl%edx,(%rsi),retq,Reading Condition Codes,SetX Instructions,Set single byte based on combinations of condition codes,Conditional Branch Example,int absdiff(,int x,int y),int result;,if(x y),result=x-y;,else,result=y-x;,return result;,absdiff:,pushl%ebp,movl%esp,%ebp,movl 8(%ebp),%edx,movl 12(%ebp),%eax,cmpl%eax,%edx,jle .L7,subl%eax,%edx,movl%edx,%eax,.L8:,leave,ret,.L7:,subl%edx,%eax,jmp .L8,Body1,Set,Up,Finish,Body2,pushl%ebp,movl%esp,%ebp,pushl%ebx,movl8(%ebp),%ecx,movl12(%ebp),%edx,movl%ecx,%ebx,subl%edx,%ebx,movl%edx,%eax,subl%ecx,%eax,cmpl%edx,%ecx,cmovg%ebx,%eax,popl%ebx,popl%ebp,ret,int absdiff(,int x,int y),int result;,if(x y),result=x-y;,else,result=y-x;,return result;,Gcc 4.3.4,New Conditional Branch Example,Implementing Loops,IA32,All loops translated into form based on“do-while”,x86-64,Also make use of“jump to middle”,Why the Difference,IA32 compiler developed for machine where all operations costly,x86-64 compiler developed for machine where unconditional branches incur(almost)no overhead,“For”,“While”,“Do-While”,for(,Init,;,Test,;,Update,),Body,Init,;,while(,Test,),Body,Update,;,Goto Version,Init,;,if(!,Test,),goto,done,;,loop:,Body,Update,;,if(,Test,),goto,loop,;,done:,While Version,For Version,Do-While Version,Init,;,if(!,Test,),goto,done,;,do,Body,Update,;,while(,Test,),done,:,“For”,“While”(Jump-to-Middle),for(,Init,;,Test,;,Update,),Body,Init,;,while(,Test,),Body,Update,;,Init,;,goto,middle,;,loop:,Body,Update,;,middle:,if(,Test,),goto,loop,;,done:,While Version,For Version,Goto Version,Switch Statements,Implementation Options,Series of conditionals,Organize in tree structure,Logarithmic performance,Jump Table,Lookup branch target,Constant time,Possible when cases are small integer constants,GCC,Picks one based on case structure,Stack,Pointer,%esp,yoo,who,proc,Frame,Pointer,%ebp,Stack,“Top”,IA32-,Stack Frames,Contents,Local variables,Return information,Temporary space,Management,Space allocated when enter procedure,“Set-up”code,Deallocated when return,“Finish”code,Pointers,Stack pointer,%esp,indicates stack top,Frame pointer,%ebp,indicates start of current frame,amI,IA32/Linux Stack Frame,Current Stack Frame(“Top”to Bottom),Parameters for function about to call,“Argument build”,Local variables,If cant keep in registers,Saved register context,Old frame pointer,Caller Stack Frame,Return address,Pushed by,call,instruction,Arguments for this call,Stack Pointer,(,%esp,),Frame Pointer,(,%ebp,),Return Addr,Saved,Registers,+,Local,Variables,Argument,Build,Old%ebp,Arguments,Caller,Frame,IA32/Linux Register Usage,Integer Registers,Two have special uses,%ebp,%esp,Three managed as callee-save,%ebx,%esi,%edi,Old values saved on stack prior to using,Three managed as caller-save,%eax,%edx,%ecx,Do what you please,but expect any callee to do so,as well,Register,%eax,also stores returned value,%eax,%edx,%ecx,%ebx,%esi,%edi,%esp,%ebp,Caller-Save,Temporaries,Callee-Save,Temporaries,Special,%rax,%rbx,%rcx,%rdx,%rsi,%rdi,%rsp,%rbp,x86-64 Register Conventions,%r8,%r9,%r10,%r11,%r12,%r13,%r14,%r15,Return Value,Callee Saved,Argument#4,Argument#3,Argument#2,Argument#1,Stack Pointer,Callee Saved,Argument#5,Argument#6,Callee Saved,Used for linking,C:Callee Saved,Callee Saved,Callee Saved,Callee Saved,x86-64 Registers,Arguments passed to functions via registers,If more than 6 integral parameters,then pass rest on stack,These registers can be used as caller-saved as well,All References to Stack Frame via Stack Pointer,Eliminates need to update,%ebp,Other Registers,6+1 callee saved,2 or 3 have special uses,x86-64 Locals in the Red Zone,Avoiding Stack Pointer Change,Can hold all information within small window beyond stack pointer,/*Swap,using local array*/,void swap_a(long*xp,long*yp),volatile long loc2;,loc0=*xp;,loc1=*yp;,*xp=loc1;,*yp=loc0;,swap_a:,movq (%rdi),%rax,movq%rax,-24(%rsp),movq (%rsi),%rax,movq%rax,-16(%rsp),movq -16(%rsp),%rax,movq%rax,(%rdi),movq -24(%rsp),%rax,movq%rax,(%rsi),ret,rtn Ptr,unused,%rsp,8,loc1,loc0,16,24,x86-64 NonLeaf without Stack Frame,No values held while swap being invoked,No callee save registers needed,long scount=0;,/*Swap ai&ai+1*/,void swap_ele_se,(long a,int i),swap(,scount+;,swap_ele_se:,movslq%esi,%rsi#Sign extend i,leaq (%rdi,%rsi,8),%rdi#&ai,leaq 8(%rdi),%rsi#&ai+1,call swap#swap(),incq scount(%rip),#scount+;,ret,x86-64 Call using Jump,When,swap,executes,ret,it will return from,swap_ele,Possible since,swap,is a“tail call”,long scount=0;,/*Swap ai&ai+1*/,void swap_ele,(long a,int i),swap(,swap_ele:,movslq%esi,%rsi#Sign extend i,leaq (%rdi,%rsi,8),%rdi#&ai,leaq 8(%rdi),%rsi#&ai+1,jmp swap#swap(),Interesting Features of Stack Frame,Allocate Entire Frame at Once,All stack accesses can be relative to,%rsp,Do by decrementing stack pointer,Can delay allocation,since safe to temporarily use red zone,Simple Deallocation,Increment stack pointer,Basic Data Types,Integral,Stored&operated on in general registers,Signed vs.unsigned depends on instructions used,IntelGASBytesC,byte,b,1,unsigned,char,word,w,2,unsigned,short,double word,l,4,unsigned,int,quad word,q,8,unsigned,long int,(x86-64),Floating Point,Stored&operated on in floating point registers,IntelGASBytesC,Single,s,4,float,Double,l,8,double,Extended,t,10/12/16,long double,Array Allocation,Basic Principle,T,A,L,;,Array of data type,T,and length,L,Contiguously allocated region of,L,*,sizeof(,T,),bytes,Identifier A can be used as a pointer to array element 0,Type T*,Viewing as Multidimensional Array,Declaration,T,A,R,C,;,2D array of data type,T,R,rows,C,columns,Type,T,element requires,K,bytes,Array Size,R,*,C,*,K,bytes,Arrangement,Row-Major Ordering,A00,A0C-1,AR-10,AR-1C-1,int ARC;,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*C,Bytes,Nested Array Row Access,Row Vectors,Ai,is array of,C,elements,Each element of type,T,requires,K,bytes,Starting address,A+,i,*(,C,*,K,),A,i,0,A,i,C-1,Ai,A,R-1,0,A,R-1,C-1,AR-1,A,A,0,0,A,0,C-1,A0,int ARC;,A+i*C*4,A+(R-1)*C*4,Nested Array Element Access,Array Elements,Aij,is element of type,T,Address,A+,i,*(,C,*,K,),+,j,*,K,=,A+,(,i*C+j,),*K,A,i,j,A,i,j,Ai,A,R-1,0,A,R-1,C-1,AR-1,A,A,0,0,A,0,C-1,A0,int ARC;,A+i*C*4,A+(R-1)*C*4,A+(i*C+j)*4,Nested Array Element Access Code,Array Elements,pghindexdig,is,int,Address:,pgh+20*index+4*dig,IA32 Code,Computes address,pgh+4*dig+4*(index+4*index),movl,performs memory reference,int get_pgh_digit,(int index,int dig),return pghindexdig;,#%ecx=dig,#%eax=index,leal 0(,%ecx,4),%edx#4*dig,leal(%eax,%eax,4),%eax#5*index,movl pgh(%edx,%eax,4),%eax#*(pgh+4*dig+20*index),Array Element Accesses,Similar C references,Nested Array,Element at,Mempgh+20*index+4*dig,Different address computation,Multi-Level Array,Element at,MemMemuniv+4*index+4*dig,int get_pgh_digit,(int index,int dig),return pghindexdig;,int get_univ_digit,(int index,int dig),return univindexdig;,Using Nested Arrays,Strengths,C compiler handles doubly subscripted arrays,Generates very efficient code,Avoids multiply in index computation,Limitation,Only works if have fixed array size,#define N 16,typedef int fix_matrixNN;,/*Compute element i,k of,fixed matrix product*/,int fix_prod_ele,(fix_matrix a,fix_matrix b,int i,int k),int j;,int result=0;,for(j=0;j N;j+),result+=aij*bjk;,return result;,A,(i,*),B,(*,k),Column-wise,Row-wise,Dynamic Nested Arrays,Strength,Can create matrix of arbitrary size,Programming,Must do index computation explicitly,Performance,Accessing single element costly,Must do multiplication,int*new_var_matrix(int n),return(int*),calloc(sizeof(int),n*n);,int var_ele,(int*a,int i,int j,int n),return ai*n+j;,movl 12(%ebp),%eax#i,movl 8(%ebp),%edx#a,imull 20(%ebp),%eax#n*i,addl 16(%ebp),%eax#n*i+j,movl(%edx,%eax,4),%eax#Mema+4*(i*n+j),Optimizing Dynamic Array Mult.,Optimizations,Performed when set optimization level to,-O2,Code Motion,Expression,i*n,can be computed outside loop,Strength Reduction,Incrementing,j,has effect of incrementing,j*n+k,by,n,Performance,Compiler can optimize regular acce