北京大学计算机科学技术系北京大学微处理器研究开发中心课件

2011年2月28日,程 旭,复 习,高等计算机系统结构,复习 性能、成本,完成任务的时间 (执行时间) 执行时间(execution time), 响应时间(response time), 延迟(latency) 单位时间(每天、小时、星期、秒、纳秒等等)内完成的任务数量(性能) 吞吐率(throughput), 带宽(bandwidth),什么是性能（Performance）？,“X 比 Y 快 n 倍” (“ X is n times faster than Y” ) 是指,性能的定义,Performance is in units of things per sec Bigger is better If we are primarily concerned with responds time,影响CPU性能的几个方面,指令总数 CPI 时钟频率 程序 编译器 指令系统体系结构 组成 工艺技术,X,X,X,X,X,X,X,X,选择基准程序集（Benchmark Sets）,Toy benchmarks Kernels Synthetic benchmarks e.g. Whetstones and Dhrystones Simplified programs Real programs,SPEC: System Performance Evaluation Cooperative,第一版 1989 10个程序(6Fp+4Int)产生单一数值(SPECmarks) 第二版 1992 SPECInt92 (6Int) 和 SPECfp92 (14Fp) 不限制编译器的开关. DEC 4000 Model 610在93年3月: spice: unix.c:/def=(sysv,has_bcopy,攂copy(a,b,c)=memcpy(b,a,c) wave5: /ali=(all,dcom=nat)/ag=a/ur=4/ur=200 nasa7: /norecu/ag=a/ur=4/ur2=200/lc=blas 第三版 1995 一组新的程序: SPECint95 (8Int) 和 SPECfp95 (10Fp) 揵有效期 三年 ? 对所有程序使用同一开关设置: SPECint_base95, SPECfp_base95,1989年，第一版; 10 个程序, 用单一数值来总结性能 (6Fp+4Int), 相对于VAX 11/780 其中有一个程序: 99%的时间耗费在该程序的单一一行代码上 新型前端编译器可以非常显著地改进它的性能,第一版SPEC,SPEC95,如何总结性能,算术平均值 (或者加权算术平均值) 追踪 执行时间: SUM(Ti)/n 或者 SUM(Wi*Ti) 比率（例如MFLOPS） 的 调和平均值 (或者加权调和平均值) 追踪 执行时间: n/SUM(1/Ri) 或者 n/SUM(Wi/Ri) 为了按比例伸缩性能，规格化执行时间 是 非常便捷的！ 例如， 参照机器的时间 被评测机器的时间 注意，不可使用规格化的执行时间的算术平均值，而应该使用几何平均值！ 几何平均值平等对待所有的改进情况: A 程序 的执行 从 2 秒 减少到 1 秒 与 B 程序 的执行 从 2000 秒 减少到 1000 秒 同等重要！,为什么对规格化数值要进行几何平均？,性能评测,or better or worse, benchmarks shape a field Good products created when have: Good benchmarks Good ways to summarize performance Given sales is a function in part of performance relative to competition, investment in improving product as reported by performance summary If benchmarks/summary inadequate, then choose between improving product for real programs vs. improving product to get more sales; Sales almost always wins! Execution time is the measure of computer performance!,功耗问题能耗有效性,功耗问题,性能成本比 Cost/Performance What is Relationship of Cost to Price?,Component Costs Direct Costs (add 25% to 40%) recurring costs: labor, purchasing, scrap, warranty Gross Margin (add 82% to 186%) nonrecurring costs: R&D, marketing, sales, equipment maintenance, rental, financing cost, pretax profits, taxes Average Discount to get List Price (add 33% to 66%): volume discounts and/or retailer markup,人是如何思考(Thinking)的？,简单的模型？,现代计算机的理论基础,1936 Alan Turing 阿伦图灵 On Computable Numbers Turing Machine ACE - EDSAC 1945 John von Neumann 冯诺依曼 First Draft of a Report on the EDVAC,数字逻辑基础回顾,同步时序电路 有穷状态自动机FSM 数据通路+控制 = 数字系统,控制,数据通路,状态信息 输入信号,控制 信号输出,状态,有穷状态自动机,显式描述出系统的状态 状态间的迁移用“有向边+输入”描述 输出可以表示为状态的一部分也可以表现为输出边的一部分,“Mod 3 Machine”,Input (MSB first),1,1,1,0,有穷状态自动机的实现：组合逻辑+锁存器,冯诺依曼结构-存储程序的概念,存储程序的概念,计算机由运算器、控制器、存储器和输入设备、输出设备五大部件组成 指令和数据以同等的地位存放于存储器中，并按地址访存 指令和数据都用二进制数表示 指令由操作码和地址码组成，操作码用来表示操作的性质，地址码用来表示操作数存在存储器中的位置 指令是顺序存放、顺序执行的，并可根据运算结果或设定的条件改变执行顺序,计算机的简单模型IAS,程序计数器：Program Counter (PC) 累加器ACC和路 存储地址寄存器MAR 存储数据寄存器MDR/MBR 指令寄存器IR,微程序控制器,State machine in which part of state is a “micro-pc”. Explicit circuitry for incrementing or changing PC Includes a ROM with “microinstructions”. Controlled logic implements at least branches and jumps,复习 指令系统、流水线、Cache,典型 RISC,32位固定格式指令(3种格式) 32个32位GPR (R0恒为0, 双精成对使用) 3地址、reg-reg算术指令 load/store使用单一寻址方式: base + displacement 无间接寻址 简单的转移条件(基于寄存器数值) 延迟转移,参见: SPARC, MIPS, HP PA-Risc, DEC Alpha, IBM PowerPC, CDC 6600, CDC 7600, Cray-1, Cray-2, Cray-3,例如: MIPS,Op,31,26,0,15,16,20,21,25,Rs1,Rd,immediate,Op,31,26,0,25,Op,31,26,0,15,16,20,21,25,Rs1,Rs2,target,Rd,Opx,Register-Register,5,6,10,11,Register-Immediate,Op,31,26,0,15,16,20,21,25,Rs1,Rs2/Opx,immediate,Branch,Jump / Call,串行洗衣店,串行洗衣店需要8个小时完成4个工作量 如果他们了解流水技术，那么需要多长时间完成上述工作呢？,30,任 务 次 序,工作时间,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,6 PM,7,8,9,10,11,12,1,2 AM,流水技术性质,流水技术无助于减少单个任务的 处理延迟(latency) ，但有助于提高整体工作负载 的吞吐率 多个不同任务同时操作, 使用不同资源 潜在加速比 = 流水线级数 流水线的速率受限于最慢的流水段 流水段的执行时间如果不均衡,那么加速比就会降低 开始填充流水线的时间 和 最后排放流水线的时间 降低加速比 相关将导致流水线暂停,6 PM,7,8,9,时间,任 务 顺 序,指 令 执 行 次 序,时间 (时钟周期),Inst 0,Inst 1,Inst 2,Inst 4,Inst 3,Figure 3.3, Page 133,CC1,CC2,CC3,CC4,CC5,CC6,CC7,CC8,CC9,流水线可以看为随时间偏移的一系列数据通路,程序流,时间,常规流水化执行的表示,计算机设计的法则,Make the Common Case Fast Amdahl定律 The CPU Performance Equation CPI CPU time = (IC CPI) / f Principle of Locality Cache Memory Hierarchy Take Advantage of Parallelism Piplelining Instruction-Level Parallelism,流水线冒险(Pipeline Hazards) 结构冒险(structural hazards): 试图同时以两种不同的方式使用同一资源； 原因：硬件无法支持同时重叠执行的所有可能的指令组合 数据冒险(data hazards): 在产生数据之前,就试图使用它们 原因：流水线中的重叠执行的指令依赖于前面指令的结果 控制冒险(control hazards):在判定转移条件之前，就试图决策转移方向 原因：可能改变PC的指令的流水,流水技术的主要障碍,Figure 3.6, Page 142,指 令 次 序,时间 (时钟周期),Load,Instr 1,Instr 2,Instr 3,Instr 4,此例中，检测非常容易!,Mem,写,读,Mem,Mem,单口存储器是一种结构冒险,Figure 3.7, Page 143,指 令 次 序,时间 (时钟周期),Load,Instr 1,Instr 2,（stall),Instr 3,写,读,Mem,Mem,增加空泡（暂停）解决单存储器结构冒险,Ignoring cycle time overhead of pipelining and assuming stages are perfectly balanced,All instructions take the same number of cycles,流水线加速比计算公式,流水线加速比计算公式(续),Machine A: Dual ported memory Machine B: Single ported memory, but its pipelined implementation has a 1.05 times faster clock rate Ideal CPI = 1 for both Loads are 40% of instructions executed SpeedUpA = Pipeline Depth/(1 + 0) x (clockunpipe/clockpipe) = Pipeline Depth SpeedUpB = Pipeline Depth/(1 + 0.4 x 1) x (clockunpipe/(clockunpipe / 1.05) = (Pipeline Depth/1.4) x 1.05 = 0.75 x Pipeline Depth SpeedUpA / SpeedUpB = Pipeline Depth/(0.75 x Pipeline Depth) = 1.33 Machine A is 1.33 times faster,示例: 双口 与 单口 存储器,Figure 3.9, page 147,add r1,r2,r3,sub r4,r1,r3,and r6,r1,r7,or r8,r1,r9,xor r10,r1,r11,关于r1的数据冒险,InstrI followed by InstrJ Read After Write (RAW，先写后读相关、写后读相关) InstrJ tries to read operand before InstrI writes it Caused by a “Dependence” (in compiler nomenclature). This hazard results from an actual need for communication.,三种普通的数据相关,I: add r1,r2,r3 J: sub r4,r1,r3,InstrI followed by InstrJ Write After Read (WAR，先读后写相关、读后写相关) InstrJ tries to write operand before InstrI reads i Gets wrong operand Called an “anti-dependence” by compiler writers. This results from reuse of the name “r1”. Cant happen in DLX 5 stage pipeline because: All instructions take 5 stages, and Reads are always in stage 2, and Writes are always in stage 5,三种普通的数据相关（续一）,InstrI followed by InstrJ Write After Write (WAW,写后写相关) InstrJ tries to write operand before InstrI writes it Leaves wrong result ( InstrI not InstrJ ) Called an “output dependence” by compiler writers This also results from the reuse of name “r1”. Cant happen in DLX 5 stage pipeline because: All instructions take 5 stages, and Writes are always in stage 5 Will see WAR and WAW in later more complicated pipes,三种普通的数据相关（续二）,从某流水段向其他流水段前递(forward)结果,（Fig3.10 Page149）,add r1,r2,r3,sub r4,r1,r3,and r6,r1,r7,or r8,r1,r9,xor r10,r1,r11,IF,ID/RF,EX,MEM,WB,指 令 次 序,时间 (时钟周期),如果适当定义读/写次序，就可能正常工作,数据冒险解决策略,Figure 3.12 Page 153,IF,ID/RF,EX,MEM,WB,指 令 次 序,时间 (时钟周期),lw r1,0(r2),sub r4,r1,r3,Dm,不能通过前递技术解决 需要增加流水线互锁（pipeline interlock）硬件，进行检测 必须延迟/暂停与装入指令相关的指令,装入指令:不能通过前递解决的数据相关,A=B+C,a=b+c； d=e-f;,通过编译调度解决的数据相关,assuming a, b, c, d ,e, and f in memory. Slow code: LW Rb,b LW Rc,c ADD Ra,Rb,Rc SW a,Ra LW Re,e LW Rf,f SUB Rd,Re,Rf SW d,Rd,Fast code: LW Rb,b LW Rc,c LW Re,e ADD Ra,Rb,Rc LW Rf,f SW a,Ra SUB Rd,Re,Rf SW d,Rd,Figure 3.20, Page 161,ZERO？,Data Memory,支持数据前递的硬件改变,控制冒险,Reg File,Ra,Rw,busW,Rb,busA,busB,PC,Data Memory,Read Data,Address,Wr Data,+4,ALU,IF/ID,ID/EX,EX/MEM,MEM/WB,Figure 3.22, Page 163,ADD,3级暂停转移的控制冒险,转移暂停的影响,If CPI = 1, 30% branch, Stall 3 cycles = new CPI = 1.9! Two part solution: Determine branch taken or not sooner, AND Compute taken branch address earlier DLX branch tests if register = 0 or 0 DLX Solution: Move Zero test to ID/RF stage Adder to calculate new PC in ID/RF stage 1 clock cycle penalty for branch versus 3,控制冒险,Reg File,Ra,Rw,busW,Rb,busA,busB,PC,Data Memory,Read Data,Address,Wr Data,+4,ALU,IF/ID,ID/EX,EX/MEM,MEM/WB,Figure 3.22, Page 163,ADD,Figure 3.24, Page 165,可改变PC的指令的出现频率,Figure 3.25, Page 166,前跳和后转的转移占总转移的67%,1) Simplest scheme: Freeze the pipeline,2) Prediction-not-taken,3) Prediction-taken,4) Delayed Branch,减小流水线中转移的损失,ADD R1,R2,R3,IF R2=0 THEN,Delay slot,IF R2=0 THEN,ADD R1,R2,R3,SUB R4,R5,R6,ADD R1,R2,R3,IF R1=0 THEN,Delay slot,ADD R1,R2,R3,IF R1=0 THEN,SUB R4,R5,R6,ADD R1,R2,R3,IF R1=0 THEN,Delay slot,SUB R4,R5,R6,ADD R1,R2,R3,IF R1=0 THEN,SUB R4,R5,R6,(a) From before,(b) From target,(c) From fall through,对转移延迟槽的调度,延迟和删除的转移的性能(Fig.3.32 P172),延迟转移,Where to get instructions to fill branch delay slot? Before branch instruction From the target address: only valuable when branch taken From fall through: only valuable when branch not taken Cancelling branches allow more slots to be filled Compiler effectiveness for single branch delay slot: Fills about 60% of branch delay slots About 80% of instructions executed in branch delay slots useful in computation About 50% (60% x 80%) of slots usefully filled Delayed Branch downside: 7-8 stage pipelines, multiple instructions issued per clock (superscalar),评测不同的转移处理策略,Scheduling Branch CPI speedup v. speedup v. scheme penalty unpipelined stall Stall pipeline 3 1.42 3.5 1.0 Predict taken 1 1.14 4.4 1.26 Predict not taken 1 1.09 4.5 1.29 Delayed branch 0.5 1.07 4.6 1.31,小结 1:,设计中必须考虑技术的发展 Capacity Speed Logic 2x in 3 years 2x in 3 years DRAM 4x in 3 years 2x in 10 years Disk 4x in 3 years 2x in 10 years 执行任务所需时间 Execution time, response time, latency 每天、每小时、每周、每秒完成的任务 Throughput, bandwidth X比Y快 n 倍 是指： ExTime(Y) Performance(X) - = - ExTime(X) Performance(Y),小结 2:,Amdahl定律: CPI: 执行时间 是 计算机系统的 真正 测度! 创造成功产品需要:好基准程序、正确总结方法 晶模成本约为晶模面积的四次方,小结3：控制 与 流水,Just overlap tasks; easy if tasks are independent Speed Up Pipeline Depth; if ideal CPI is 1, then: Hazards limit performance on computers: Structural: need more HW resources Data (RAW,WAR,WAW): need forwarding, compiler scheduling Control: delayed branch, prediction,存储层次,微处理器-DRAM 的延迟差距,1,10,100,1000,1980,1981,1983,1984,1985,1986,1987,1988,1989,1990,1991,1992,1993,1994,1995,1996,1997,1998,1999,2000,1982,Performance,Time,存储层次的级别,CPU寄存器 100s Bytes 10s ns,Cache K Bytes 10100 ns 10.1cent/bit,主存 M Bytes 200ns-500ns 0.0001.00001 cent/bit,磁盘 G Bytes 10毫秒 10-510-6 cent/bit,容量 访问时间 成本,磁带 无限 秒分 10-8,寄存器堆,Cache,存储器,磁盘,磁带,指令操作数,块（Blocks）,页（Pages）,文件（Files）,分段传输单位,程序/编译器 1-8 字节,Cache控制 8-128字节,操作系统 512-4K字节,用户/操作员 Mbytes,较高级别,较低级别,较快,较大,局部性原理,局部性原理: 程序在一定的时间段内通常只会访问地址空间较小的部分。 例如：10%的代码将耗费90%的程序执行时间。 两种不同类型的局部性: 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期她很可能还会被再次访问。 空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。 在过去的十五年，计算机硬件主要依赖局部性来改进性能,地址空间,0,2,访问的可能性,存储层次：术语,命中（Hit）： 数据在较高层的某一块中出现（例如X块） 命中率（Hit Rate）：在较高层发现存储访问的比率 命中时间（Hit Time）：访问在较高层命中数据的时间 RAM访问时间 + 确定命中/失效的时间 失效（Miss）：需要从较低层中的块中找回数据（Y块） 失效率（Miss Rate） = 1 - (命中率) 失效损失（Miss Penalty）：替换较高层存储的一个数据块的时间 + 将该块交付给处理器的时间 命中时间 失效损失(Alpha 21264中约需500条指令处理时间!),Cache度量,Hit rate: fraction found in that level So high that usually talk about Miss rate Miss rate fallacy: as MIPS to CPU performance, miss rate to average memory access time in memory Average memory-access time = Hit time + Miss rate x Miss penalty (ns or clocks) Miss penalty: time to replace a block from lower level, including time to replace in CPU access time: time to lower level = f(latency to lower level) transfer time: time to transfer block =f(BW between upper & lower levels),位置 0 可以被来自以下位置的数据占用： 主存位置0、4、8, . 等等 一般情况：任何地址最低两位为0的主存位置 地址 cache索引 我们应该将哪一个放置在cache中? 我们如何知道到底哪一个在cache中呢?,最简单的Cache: 直接映射Cache,主存,4 字节直接映射Cache,主存地址,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,Cache索引（Index）,0,1,2,3,示例: 32B数据块的1KB直接映射Cache,对于 2 N 字节cache: 最高的 (32 - N)位总是Cache标签 最低的 M位是字节选择 (块大小 = 2M),0,1,2,3,Cache 数据,Byte 0,0,4,31,0x50,作为Cache状态的一部分存储,有效位,31,Byte 1,Byte 31,:,Byte 32,Byte 33,Byte 63,:,Byte 992,Byte 1023,:,Cache 标签,9,:,Cache 索引,Cache标签,示例: 0x50,示例: 0x01,字节选择,示例: 0x00,两路组相联Cache,N路组相联: 对每个Cache索引有N个数据块(entries) N个直接映射cache并行工作 示例：两路组相联cache Cache索引来选择cache中的某一组 该组种的两个标签进行并行比较 根据标签比较的结果来选择数据,组相联Cache缺点,N路组相联Cache 与 直接映射Cache: N个比较器 与 1个比较器 在输出数据时，增加了额外的多路选择延迟 在判断命中/失效时候，才可以得到数据 在直接映射Cache中, Cache块在命中/失效之前就可以得到： 可以先假设命中并继续执行，如果以后发现失效再恢复。,另一个极端的示例: 全相联,全相联Cache - 将组相联的思想推广到极限! 完全不要Cache索引 并行地比较所有的 Cache标签 示例：块大小 = 32 字节, 需要N个 27位的比较器 根据定义： 对于全相联cache，冲突失效 = 0,:,Cache 数据,字节 0,0,4,31,:,Cache标签 (27位长),有效位,:,字节 1,字节 31,:,字节 32,字节 33,字节 63,:,Cache 标签,字节选择,示例: 0x01,X,X,X,X,X,Cache的设计空间,一些相互影响的维 Cache大小 块大小 相联度 替换策略 写穿透 与 写返回 写分配 最佳选择是进行折衷 根据访问特性 工作负载 使用 (I-cache, D-cache, TLB) 依赖于技术工艺/成本 “简洁”常胜,Associativity,Cache Size,Block Size,Bad,Good,Less,More,Factor A,Factor B,存储层次设计的四个问题,Q1: 信息块可以放在高层的哪里？ (Block placement) 全相联、组相联、直接映射 Q2: 如果信息块在高层，那么如何找到它？ (Block identification) 标记/信息块 Q3: 在失效时，应该替换掉哪个信息块？(Block replacement) 随机、 LRU Q4: 在写操作时，会发生什么情况 (Write strategy) 回写（Write Back）或 直写（Write Through） (使用写缓冲器),Q1:信息块可以放在高层的哪里？,第12块 放到 8块的cache: 全相联、直接映射、2路组相联 S.A. Mapping = Block Number Modulo Number Sets,Cache,Memory,全相联,直接映射 (12 mod 8) = 4,2路组相联 (12 mod 4) = 0,Q2:如果信息块在高层，那么如何找到它？,Tag on each block No need to check index or block offset Increasing associativity shrinks index, expands tag,Q3: 在失效时，应该替换掉哪个信息块？,直接映射 很简单！ 组相联 或 全相联 随机 LRU (Least Recently Used) Assoc: 2-way 4-way 8-way Size LRU Ran LRU Ran LRU Ran 16 KB 5.2% 5.7% 4.7% 5.3% 4.4% 5.0% 64 KB 1.9% 2.0% 1.5% 1.7% 1.4% 1.5% 256 KB 1.15% 1.17% 1.13% 1.13% 1.12% 1.12%,Q4: 在写操作时，会发生什么情况？,直写（Write through） 信息不仅被写入CACHE,而且还要写到底层的存储中 写返回（Write back） 信息仅被写入到CACHE中。被修改的cache块只有在被替换时才会回写到主存 块 干净 还是 脏? 各自利弊? WT: read misses cannot result in writes WB: no repeated writes to same location WT 总是与 “写缓冲器（write buffers）”结合，从而无需等待低级存储,写穿透的写缓冲器,在Cache和存储器之间需要一个写缓冲器 处理器：将数据写入cache和写缓冲器 存储器控制器：将缓冲器中的内容写入存储器 写缓冲器就像一个先进先出栈（FIFO）： 典型数据项的数目：4 可以很好地工作，如果： 存储操作的频率 (写时间) 1 / DRAM写周期 存储器设计人员最害怕的事情： 存储频率(写时间) 1 / DRAM写操作 写缓冲器饱和,现代计算机的存储层次体系,通过利用程序局部性原理的优点: 向用户提供最廉价工艺所可能提供的最多的存储空间 向用户提供最快速工艺所可能提供的最快访问速度,虚拟存储系统设计的基本问题,从二级存贮器向主存传输信息块的大小 如果某信息块需要引入主存M，但是M已经装满，那么M中的一些区域就必须释放，以为新的信息块腾出空间 替换策略（replacement policy） M中的哪个区域将安放新的信息块 放置策略（placement policy ） 失效的信息项只有在出现页面失效(fault)时，才从第二级存储器中取出 读取/装入策略（fetch/load policy）,分页组织 虚拟 和 物理 地址被划分为同等大小的信息块,页帧（page frames）,页（pages）,pages,reg,cache,mem,disk,frame,地址映射,V = 0, 1, . . . , n - 1 虚拟地址空间 M = 0, 1, . . . , m - 1 物理地址空间 映射: V M U 0 地址映射函数,n m,MAP(a) = a 如果在虚拟地址 a 的数据出现在物理地址 a ，并且 a 在 M中 = 0 如果在虚拟地址 a 的数据不出现在M中,处理器,名字空间 V,地址变换 机制,缺页处理,主存,二级存储,a,a,a,0,失效信息项故障,物理地址,OS 完成这