荿系统结构笔记
袈第一章绪论
膆1、背景介绍，市场变化及原因及趋势
蚃2、计算机体系结构基本概念
肀计算机体系结构的定义
衿ComputerArchitecture = Instruction Set Architecture +
芄MachineOrganization +Hardware
膂指令级结构(InstructionSet Architecture)
螀研究软、硬件功能分配以及机器级界面的确定，既由机器语言程序设计者或编译程序
设计者所看到的机器物理系统的抽象或定义。但它不包括机器内部的数据流和控制流、
逻辑设计和器件设计等。
蚆计算机组织(ComputerOrganization)
蚇ISA的逻辑实现，包括机器级内的数据流和控制流的组成以及逻辑设计等。它着眼于
机器内各事件的排序方式与控制机构、各部件的功能以及各部件间的联系。
薁计算机实现（ComputerImplementation）
薀是指计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和
速度，器件、模块、插件、底板的划分与连接，专用器件的设计，微组装技术，信号传
输，电源、冷却及整机装配技术等。它着眼于器件技术和微组装技术，其中，器件技术
在实现技术中起着主导作用。
螈计算机体系结构＝ISA+ Organization + Hardware
螅3、定量分析技术基础
羁1、计算机系统评价
芁当客户拿到一组机器时，他们肯定想知道哪个性能最好，哪个价格最低，哪个性价比最高？
而我们设计者则需要最大限度的提高性能，使性价比达到最高，因此我们必须要就基本的
评价标准和方法。
肃常用性能评价指标：执行时间（CPUTime）、峰值速度（PeakPerformance）、负载
（load）
膈开销（overhead）、利用率（utilizationratio）、饱和性能（saturateperformance）、
羈带宽（bandwidth）、延迟（latency）、吞吐率（throughout）、加速比（speedup）、
芅Amdahi定律（amdahilaw）、效率（efficiency）、基准测试（benchmark）、
袀响应时间（responsetime）等等
蒀2、性能度量
莈性能定义为每秒完成的任务数-biggeris better
肆如果我们更关心响应时间（responsetime）
羂 | performanc e ( x ) | | 1 | _ | time ( x ) | |||
蚈 | | execution | ||||||
螇 | X 性能是Y 的n 倍是指 | x | ) | |||||
| n | Performanc e | ( | |||||
| 薂 | | Performanc e | ( | y | ) | ||
羃3、性能设计与评测的基本原则
羁并行性
芆大概率事件优先原则
节所有指令都需要取指令操作，只有部分指令访问数据
螁优化指令访问操作比优化数据访问操作优先
聿程序局部性原理：时间局部性、空间局部性
蚆4、Amdahl’s定律
羃Speedup(withE) = 1/((1-F)+F/S)) F 指fraction（小部分）S指小部分的加速比
袂CPUtime = CPI * IC * T
芇CPUtime = Seconds = Instructions x Cycles x Seconds
肅 Program Program Instruction Cycle
螃执行时间是计算机系统度量的最实际，最可靠的方式
袃第二章指令集结构设计
薀对于一种指令集结构，我们必须要知道指令格式或编码方式，操作数和操作结果存放的位
置，数据类型和大小，寻址方式，支持哪些操作，下一条指令的地址（jumps，conditions，
branches）
蒅1、指令集结构分类
蒃累加器型、堆栈型、通用寄存器型、存储器-存储器型
蚁通用寄存器型占主导地位，因为寄存器比存储器快，对编译器而言，寄存器更容易使
用
蚈通用寄存器的分类：
膈 | 芄优点 | 螂缺点 |
肁Register-Register | 蚇指令格式简单，并且长度固定，是一种简单的代码生成模型，各种指令的执行时钟周期数相近。 | 羄指令条数相对较多，目标代码大。 |
蕿Register-Memory | 腿直接对存储器操作数进行访问，容易对指令进行编码，且其目标代码较小。 | 肇指令中的操作数类型不同。指令的操作数可以存储在不同类型的存储器单元，所以每条指令的执行时钟周期数也不尽相同。 |
螅Memory-Memory | 薁编码方式紧密，不用为保存临时变量而浪费寄存器空间。 | 芇指令字长多种多样。每条指令的执行时钟周期数也大不一样，对存储器的频繁访问将导致存储器访问瓶颈问题。 |
蒆2、寻址方式
蒅如何解释存储器地址？如何说明寻址方式？
蚂目前几乎所有的机器的存储器都是按字节编址的，当读取一个32位字时，如果每次
一个字节，四次完成，每次一个字，一次就可以了，问题来了：
蚀如何将字节地址映射到字地址（尾端问题）
袅一个字是否可以存放在任何字节边界上（对齐问题）
芅对齐问题：对一个s字节的对象访问，地址为A，如果Amod s =0 那么它就是边界对齐的。
蒀边界对齐的原因是存储器本身读写的要求，存储器本身读写通常就是边界对齐的，对
于不是边界对齐的对象的访问可能要导致存储器的两次访问，然后再拼接出所需要的数。
（或发生异常）
螈重要的寻址方式:
莅偏移寻址方式,立即数寻址方式,寄存器间址方式
羆SPEC测试表明，使用频度达到75%--99%
薁还有其他很多寻址方式，这里就不解释了
3、操作数的类型、表示和大小
膀操作数类型是面向应用，面向软件系统所处理的各种数据结构
肈整型、浮点型、字符、字符串、向量类型等
蒂类型由操作码确定或数据附加硬件解释的标记，一般采用由操作码确定
薂操作数的表示：硬件结构能够识别，指令系统可以直接调用的结构
艿整型：原码、反码、补码
蒈浮点：IEEE754 标准
膂十进制：BCD码，二进制十进制表示
莀单字、双字的数据访问具有较高的频率
莇4、指令集功能设计
袇需考虑的因素：速度、价格和灵活性。基本要求：指令系统的完整性、规整性、高效率和
兼容性
羃完整性设计：具备基本指令种类
蒁兼容性：系列机
螀高效率：指令执行速度快、使用频度高
芆规整性：让所有运算部件都能对称、均匀的在所有数据存储单元之间进行操作。对所有数
据存储单元都能同等对待，无论是操作数或运算结果都可以无约束地存放到任意数据存
储单元中
蚃正交性：数据类型独立于寻址方式，寻址方式独立于所要完成的操作
1、
2、蒂CISC计算机指令集结构的功能设计
袈目标：增强指令功能，减少指令的指令条数，以提高系统性能
螆面向目标程序的优化，面向高级语言和编译器的优化
莄对大量的目标程序机器执行情况进行统计分析，找出使用频度高，执行时间长的指令
或指令串
芀对于那些使用频度高的指令，用硬件加快其执行，对于那些使用频度高的指令串，用
一条新的指令来代替它
3、
4、芀RISC计算机指令结构的功能设计
膅通过简化指令系统，用最高效的方法实现最常用的指令
膄充分发挥流水线的效率，减少CPI
莁硬件方面：硬布线控制逻辑，减少指令和寻址方式的种类，使用固定格式，采用
Load/Store，指令执行过程中设置多级流水线。
荿软件方面：十分强调优化编译的作用
袈5、指令格式
袄指令格式选择策略
莃如果代码长度最重要，那么使用变长指令格式
蒇如果性能至关重要，使用固定长度指令
芈 有些嵌入式CPU附加可选模式，由每一应用自己选择性能还是代码量
蚅 有些机器使用边执行边解压的方式
膀如果每条指令存在多个存储器操作数，或有多种寻址方式,每一操作数都要说明其寻址
方式
衿6、编译技术与计算机体系结构
蚇编译优化-4个层次
莅高层优化：一般在源码上进行，同时把输出传递给以后的优化扫描步骤
芁局部优化：仅在一系列代码片断之内（基本块）将代码优化
羈全局优化：将局部优化扩展为跨越分支，并且引入一组针对优化循环的转换
膇与机器相关的优化：充分利用特定的系统结构
膆第三章流水线技术
莃1、流水线技术
莀流水线技术要点
薆流水线技术并不能提高单个任务的执行效率，它可以提高整个系统的吞吐率
袆流水线中的瓶颈——最慢的那一段
膀多个任务同时执行，但使用不同的资源
葿其潜在的加速比＝流水线的级数
羅流水段所需时间不均衡将降低加速比
莂流水线存在装入时间和排空时间，使得加速比降低
膁由于存在相关问题，会导致流水线停顿
薇流水线正常工作的基本条件
蒅增加寄存器文件保存当前段传送到下一段的数据和控制信息
肃存储器带宽是非流水的5倍
芃指令流水线通过指令重叠减小CPI
罿充分利用数据通路
肈当前指令执行时，启动下一条指令
袃其性能受限于花费时间最长的段:解决办法：
肀串联：将最慢段进一步划分
肈并联：增加部件
薇检测和消除相关
薃如何有利于流水线技术的应用
肂所有的指令都等长
蒀只有很少的指令格式
羇只用Load/Store来进行存储器访问
| TP max | | 1 | i | } | | | |||||||||||||||||||||||
| max{t | | | |||||||||||||||||||||||||||
TP | | m i1 | t i |
| | n | | 1 ) | t | j | ||||||||||||||||||||
| ( | n | | | ||||||||||||||||||||||||||
S | | m i1 | n | | m i1 | t | i | t | j | |||||||||||||||||||||
| t | i | | ( | n | | 1 ) | | | |||||||||||||||||||||
E | | m | | [ | m i1 | n | | m i1 | t | j | 1 ) | t | ||||||||||||||||||
| t | i | | ( | n | | j | ] | ||||||||||||||||||||||
E | | TP | | m i1 | t | i | ||||||||||||||||||||||||
莄 | m | | | |||||||||||||||||||||||||||
膃TP:吞吐率 S加速比 E效率-设备利用效率
薈2、流水线的相关
莆采用流水线技术必然会带来流水线相关问题，虽然我们使用等待策略总是可以解决相关,
但是，流水线控制必须能检测相关，否则由软件设计来避免
肄结构相关同一时间两种方式使用同一资源 （停顿等待）
羀数据相关在数据未准备好之前，就需要使用数据当前指令的执行需要上一条指令的结果
（RAW,WAW,WAR硬件方法：采用定向技术，软件方法：指改变指令顺序，插入缓冲槽，指
令集调度）
羁RAW（写后读）由于实际的数据交换需求而引起的
袆WAR（读后写）由于重复使用寄存器名“r1”引起的
螅DLX5 段基本流水线不会有此类相关因为，所有的指令都是5段,并且读操作总是在
第2段，而写操作在第5段。
羂 WAW（写后写）也是由于重复使用寄存器“r1”引起的
聿在DLX5 段基本流水线中，也不会发生。因为所有指令都是5段，并且写操作都在第
5段，在后面的复杂的流水线中我们将会看到WAR和WAW相关。
芅控制相关由于控制类指令引起的，试图在条件未评估之前，就做决定
薅分支需要解决两个问题：分支目标地址（转移成功意谓着PC值不是PC+4），转移条件
是否有效，这两点在DLX中都在流水线的靠后段中确定
肃译码在ID段后，转移地址必须在ID段后才知道，此时取进来的指令可能是错误的指
令
膈解决控制相关的静态方法：
羈1、Stall：直到分支方向确定
芅2、预测分支失败：直接执行后继指令，如果分支实际情况为分支成功，则撤销流水线
中的指令对流水线状态的更新
袀DLX分支指令平均47%为分支失败
蒀由于PC+4已经计算出来，因此可以用它来取下一条指令
莈3、预测分支成功：平均53%DLX 分支为分支成功，但分支目标地址在ID段才能计算
出目标地址
肆4、延迟转移：选择指令来填充延迟槽
羂3、异常精确中断非精确中断
蚈异常发生在指令中，并且要求恢复执行，要求==>流水线必须安全地shutdown
螇PC必须保存，如果重新开始的是一条分支指令，它需要重新执行
薂引起异常的指令前面的指令都已执行完，故障后的指令可以重新从故障点后执行
羃理想情况，引起故障的指令没有改变机器的状态
羁要正确的处理这类异常请求，必须保证故障指令不产生副作用
芆精确中断对整数流水线而言，不是太难实现
节第四章指令级并行
螁本章研究的是减少停顿(stalls)数的方法和技术
聿流水线提高的是指令带宽（吞吐率），而不是单条指令的执行速度
蚆相关限制了流水线性能的发挥
羃结构相关：需要更多的硬件资源
袂数据相关：需要定向，编译器调度
芇控制相关：尽早检测条件，计算目标地址，延迟转移，预测
肅增加流水线的级数会增加相关产生的可能性
螃异常，浮点运算使得流水线控制更加复杂
袃编译器可降低数据相关和控制相关的开销
薀Load延迟槽
蒅Branch延迟槽
蒃Branch预测
蚁1、指令级并行的概念
蚈计算机系统的并行性，从执行程序的角度，分为：
膈指令内部并行：指令内部的微操作
芄指令级并行：并行执行两条或多条指令
螂任务级或过程级并行：并行执行两个或多个过程或任务
肁作业或程序级并行：在多个作业或程序间并行
蚇从处理数据的角度，并行性等级分为：
羄字串位串
蕿字串位并
腿字并位串
肇全并行
螅提高并行的三种途径
薁时间重叠
芇资源重复
蒆资源共享
蒅ILP:无关的指令重叠执行
蚂流水线的平均CPI
蚀Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR
Stalls+ WAW Stalls + Control Stalls
袅2、硬件方案:指令级并行
芅为什么要使用硬件调度方案?
蒀在编译时无法确定的相关，可以通过硬件调度来优化
螈编译器简单
莅代码在不同组织结构的机器上，同样可以有效的运行
羆基本思想:允许stall后的指令继续向前流动
薁DIVD F0,F2,F4
膀ADDD F10,F0,F8
肈SUBD F12,F8,F14
蒂允许乱序执行（out-of-orderexecution）=>out-of-order completion
薂硬件方案之一:记分牌
艿记分牌控制的四阶段
1、Issue—指令译码，检测结构相关
蒈 如果当前指令所使用的功能部件空闲，并且没有其他活动的指令使用相同的目的寄存器
（WAW),记分牌发射该指令到功能部件，并更新记分牌内部数据，如果有结构相关或WAW相
关，则该指令的发射暂停，并且也不发射后继指令，直到相关解除.
膂2、Readoperands—没有数据相关时，读操作数
莀如果先前已发射的正在运行的指令不对当前指令的源操作数寄存器进行写操作，或者
一个正在工作的功能部件已经完成了对该寄存器的写操作，则该操作数有效.操作数有效
时，记分牌控制功能部件读操作数，准备执行。
莇记分牌在这一步动态地解决了RAW相关，指令可能会乱序执行。
袇3、Execution—取到操作数后执行(EX)
羃 接收到操作数后，功能部件开始执行.当计算出结果后，它通知记分牌，可以结束该条
指令的执行.
蒁4、Writeresult—finish execution (WB)
螀 一旦记分牌得到功能部件执行完毕的信息后，记分牌检测WAR相关，如果没有WAR相关，
就写结果，如果有WAR相关，则暂停该条指令。
芆 | Example: | F0,F2,F4 |
蚃 | DIVD | |
蒂 | ||
ADDD | F10,F0,F8 |
袈 | SUBD | F8,F8,F14 |
螆CDC6600 scoreboard 将暂停SUBD直到ADDD读取操作数后，才进入WR段处理。
莄记分牌的主要思想是：允许stall后的指令继续进行处理
芀可以out-of-orderexecution => out-of-order completion
芀ID段检测结构相关和WAW相关
膅6600scoreboard 的缺陷:
膄没有定向数据通路
莁指令窗口较小，仅局限于基本块内的调度
荿功能部件数较少，容易产生结构相关，特别是其Loadstore 操作也是用IU部件完成
的
袈结构冲突时不能发射
袄WAR相关是通过等待解决的
莃WAW相关时，不会进入IS阶段
蒇动态调度方案之二：TomasuloAlgorithm
芈Tomasulo算法的三阶段：性能受限于CommonData Bus
蚅1、Issue—从FP操作队列中取指令
膀如果RS空闲(nostructural hazard), 则控制发射指令和操作数(renames
registers).消除WAR，WAW相关
衿2、Execution—operateon operands (EX)
蚇 当两操作数就绪后，就可以执行
如果没有准备好，则监测CommonData Bus 以获取结果。通过推迟指令执行避免RAW相关
莅3、Writeresult—finish execution (WB)
芁 将结果通过CommonData Bus 传给所有等待该结果的部件;
表示RS可用
|
|
羈Tomasulo | 膇Scoreboard |
膆流水化的功能部件 | 莃多个功能部件 |
莀(6 load, 3 store, 3 +, 2 x/÷) | 薆(1 load/store, 1 + , 2 x, 1 ÷) |
袆指令窗口大小: ~ 14 instructions | 膀~ 5 instructions |
葿有结构冲突时不发射 | 羅相同 |
莂WAR: 用寄存器重命名避免 | 膁stall 来避免 |
薇WAW:用寄存器重命名避免 | 蒅停止发射 |
肃从FU 广播结果 | 芃写寄存器方式 |
罿Control: RS | 肈集中式scoreboard |
袃关于异常处理?
肀乱序完成加大了实现精确中断的难度
肈在前面指令还没有完成时，寄存器文件中可能会有后面指令的运行结果.如果这些前面的
指令执行时有中断产生，怎么办？
薇例如：
薃DIVDF10, F0, F2
肂SUBDF4, F6, F8
蒀ADDDF12, F14, F16
羇需要“rollback”寄存器文件到原来的状态:
莄精确中断含义是其返回地址为：该地址之前的所有指令都已完成，其后的指令还都没有完
成
膃实现精确中断的技术：顺序完成（或提交）
薈即提交指令完成的顺序必须与指令发射的顺序相同
莆ReorderBuffer:
肄提供了撤销指令运行的机制
羀指令以发射序存放在ROB中
羁指令顺序提交
袆有效的支持精确中断，推测执行
螅分支预测对提高性能是非常重要的
羂推断执行是利用了ROB撤销指令执行的机制
聿控制相关的动态解决技术
芅控制相关：由条件转移或程序中断引起的相关，也称全局相关。控制相关对流水线的吞吐
率和效率影响相对于数据相关要大得多
薅条件指令在一般程序中所占的比例相当大
肃中断虽然在程序中所占的比例不大，但中断发生在程序中的哪一条指令，发生在一条指令
执行过程中的哪一个功能段都是不确定的
膈处理好条件转移和中断引起的控制相关是很重要的。
羈当分支方向预测错误时，不仅流水线中有多个功能段要浪费，更严重的是可能造成程序执
行结果发生错误，因此当程序沿着错误方向运行后，作废这些程序时，一定不能破坏通用寄
存器和主存储器的内容。
芅动态分支预测方法
袀基于BPB(BranchPrediction Buffer)
1、
2、蒀一位预测1-bitBHT
莈问题:在一个循环中,1-bit BHT 将导致2次分支预测错误
肆最后一次循环,前面都是预测成功，而这次需要退出循环
羂第一次循环，由于前面预测为失败，而这次实际上为成功
3、
4、蚈两位预测2-bitBHT
螇解决办法:2 位记录分支历史
5、
6、薂两级预测
羃记录转移历史信息
羁根据所记录的转移历史信息，预测转移的方向
芆3、多指令流出技术
节如何使CPI< 1 两种基本方法
螁Superscalar:
聿每个时钟周期所发射的指令数不定（1－8条）
蚆由编译器或硬件完成调度
羃IBMPowerPC, Sun UltraSparc, DEC Alpha, HP 8000
袂该方法对目前通用计算是最成功的方法
芇(Very)Long Instruction Words (V)LIW:
肅每个时钟周期流出的指令数（操作）固定(4-16)
螃由编译器调度，实际上由多个单操作指令构成一个超长指令
袃目前比较成功的应用于DSP，多媒体应用
薀1999/2000HP 和Intel达成协议共同研究VLIW
蒅第五章存储系统
蒃计算机（CPU+存储系统+I/O）冯诺依曼结构是五个部分（控制器，运算器，主存，输入，
输出）
蚁Cpu_time=IC*CPI*I
蚈前面第四章主要讲cpu方面的,通过指令级并行来减少平均的指令执行时间,以及各种相
关及其解决方案（减少stall）,和超标量（多发射），来减少CPI
膈存储系统主要讲cache(提高访存速度)和虚存技术（提高主存容量），主要讲下面四个部
分：映射功能，查找策略，替换策略，写策略.
芄一、存储层次结构
1、
2、螂存储系统的设计目标
肁通过优化存储系统的组织来使得针对典型的应用平均访存时间最短
蚇基本解决方法：多级层次结构CPU-M1-M2-----Mn
羄存储系统速度接近速度最快M1，容量和价格接近最大最便宜的Mn。
3、
4、蕿存储层次的工作原理和基本概念
腿TemporalLocality（时间局部性）：保持最近访问的数据项最接近微处理器
肇SpatialLocality（控件局部性）：把地址连续的若干个字构成的块从底层复制到上
一层
螅Block：（块，不同层次的block大小可能不同）
薁镜像和一致性问题：高层存储器是低层存储器的一个镜像，高层存储器内容修改必须
反映到低层存储器中去，保持数据的一致性。
芇寻址：访问数据的方式。
蒆若一组程序对存储器的访问，其中N1次在M1中找到所需数据，N2次在M2中找到数据
则
蒅HitRate（命中率）:存储器访问在较高层命中的比例H=N2/(N1+N2)
蚂HitTime（命中时间）:访问较高层的时间，TA1
蚀失效率：访问的块不在存储系统较高层次上的概率
肃MissRate (失效率)=1- (Hit Rate) = 1 – H ＝N2/(N1+N2)
蒃当在M1中没有命中时，一般必须从M2中将所访问的数据所在块搬到M1中，然后CPU
才能在M1中访问
蚇设传送一个块的时间为TB,即不命中时的访问时间为：TA2+TB+TA1= TA1+TM
羆TM通常称为失效开销
薃平均访存时间TA= HTA1+(1-H)(TA1+TM)= TA1+(1-H)TM
5、
6、膄常见的存储层次的组织
蝿Registers<-> Memory 由编译器完成调度
莈cache<-> memory 由硬件完成调度
芆memory<-> disks 由硬件和操作系统（虚拟管理），由程序员完成调度
蚀二、Cache基本知识
螀Cache是CPU和主存之间的一个高速，小容量的存储器
蒇1、映象规则
蚅当要把一个块从主存调入Cache时，如何放置问题
莀三种方式
薈全相联方式： 即所调入的块可以放在cache中的任何位置
薅直接映象方式：主存中每一块只能存放在cache中的唯一位置一般，主存块地址i
与cache中块地址j的关系为：j＝imod （M)，M为cache中的块数
肅组相联映象：主存中每一块可以被放置在Cache中唯一的一个组中的任意一个位置，
组由若干块构成，若一组由n块构成，我们称N路组相联
膁组间直接映象
虿组内全相联
羇若cache中有G组，则主存中的第i块的组号K
蒄K= i mod (G),
袁2、查找方法
蚀显然相联度N越大，实现查找的机制就越复杂，代价就越高
肆无论直接映象还是组相联，查找时，只需比较tag，index无需参加比较
羃
薁主存地址格式
蒈Cache结构中主存地址格式：CacheTag 放在高位段，CacheIndex 放中间，字节选择
位放在低位段
蒈Cache Tag | 莃Cache Index | 莂Block offset |
蕿Cache标记 块地址 块内地址
薆Cache地址格式
肆块地址 | 肂Block offset |
薀
蚅3、替换算法
蒆主存中块数一般比cache中的块多，可能出现该块所对应的一组或一个Cache块已全
部被占用的情况，这时需强制腾出其中的某一块，以接纳新调入的块，替换哪一块，这
是替换算法要解决的问题：
袃直接映象，因为只有一块，别无选择
莈组相联和全相联有多种选择
肇替换方法
袅随机法（Random)，随机选择一块替换
薃优点：简单，易于实现
葿缺点：没有考虑Cache块的使用历史，反映程序的局部性较差，失效率较高
膆FIFO－选择最早调入的块
莄优点：简单
莃虽然利用了同一组中各块进入Cache的顺序，但还是反映程序局部性不够，因为最先
进入的块，很可能是经常使用的块
薁最近最少使用法（LRU)(Least Recently Used)
薈优点：较好地利用了程序的局部性，失效率较低
螄缺点：比较复杂，硬件实现较困难
肄观察结果（失效率）
莈相联度高，失效率较低。
蚆Cache容量较大，失效率较低。
膃LRU在Cache容量较小时，失效率较低
薀随着Cache容量的加大，Random的失效率在降低
荿4、写策略
螅程序对存储器读操作占26％，写操作占9％
蚂写所占的存储器访问比例 9/(100+26+9)大约为7％
芀占访问数据Cache的比例：9/(26+9)大约为25%
蒁大概率事件优先原则－优化Cache的读操作
膇Amdahl定律：不可忽视“写”的速度
芆“写”的问题
肁读出标识，确认命中后，对Cache写 （串行操作）
芈Cache与主存内容的一致性问题
芅写策略就是要解决:何时更新主存问题
螅两种写策略
螁写直达法（Writethrough)
艿优点：易于实现，容易保持不同层次间的一致性
蚈缺点：速度较慢
膅写回法（Writeback)
薂优点：速度快，减少访存次数
莁缺点：一致性问题
螆当发生写失效时的两种策略
薄按写分配法(Writeallocate)：写失效时，先把所写单元所在块调入Cache，然后再进
行写入，也称写时取（Fetchon Write)方法
节不按写分配法（no-writeallocate):写失效时，直接写入下一级存储器，而不将相应
块调入Cache，也称绕写法（Writearound)
膈原则上以上两种方法都可以应用于写直达法和写回法，一般情况下
腿WriteBack 用Writeallocate
肃Writethrough 用no-writeallocate
肂三、改进Cache性能的方法
膀CPU time = (CPU execution clock cycles + clock cycle time
Memorystall clock cycles) x
芇Memory stall clock cycles = (Reads x Read miss rate x Read miss penalty + Writes
x Write miss rate x Write miss penalty)
蒃Memory stall clock cycles = Memory accesses x Miss rate x Miss penalty
螃Different measure: AMAT（平均访存时间）
Average Memory Access time (AMAT) = Hit Time + (Miss Rate x Miss Penalty)
芁Note: memory hit time is included in execution cycles
莅平均访存时间＝命中时间＋失效率×失效开销
膆从上式可知，基本途径
蒃降低失效率
肈减少失效开销
螈降低命中时间
薅1、降低Cache失效率的方法
芃引起Cache失效的原因可分为三类 3C
膀强制性失效(Compulsory)
袆第一次访问某一块，只能从下一级Load，也称为冷启动或首次访问失效
羅容量失效（Capacity)
螀如果程序执行时，所需块由于容量不足，不能全部调入Cache，则当某些块被替换后，
若又重新被访问，就会发生失效。
膁可能会发生“抖动”现象
腿冲突失效（Conflict(collision))
蚈组相联和直接相联的副作用
螄若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的
组或块有空闲位置)，然后又被重新访问的情况，这就属于冲突失效
节从统计规律可知
薁相联度越高，冲突失效就越小
膈强制性失效和容量失效不受相联度的影响
蒅强制性失效不受Cache容量的影响
芄容量失效随着容量的增加而减少
虿符合2:1Cache经验规则
薇即大小为N的直接映象Cache的失效率约等于大小为N/2的两路组相联的Cache失效
率。
芅降低失效率的基本方法
莅增大块大小：减缓强制性失效（控件局部性原理）,
肂可能会增加冲突失效（因为在容量不变的情况下，块的数目减少了）
羆失效开销增大（上下层间移动，数据传输时间变大）
羅设计块大小的原则，不能仅看失效率
膃原因：平均访存时间＝ 命中时间＋失效率×失效开销
膀增大Cache容量：对冲突和容量失效的减少有利
蚀提高相联度：8路组相联在降低失效率方面的作用已经和全相联一样有效
蚆会增加命中时间
芄伪相联技术：也称为ColumnAssociate(列相联）。该方法能获得多路组相联Cache的
低失效率，又能保持直接映象的Cache命中速度。先以直接映象方式查找块
薂如果失效，查找另一块
聿另一块入口地址，即将索引字段最高位取反
蒆如果还是失效，只好再访问下一级存储器
羁问题
蚁具有一快一慢的命中时间，对应于正常命中和伪命中
蕿如果直接映象Cache里的许多快速命中在伪相联中变成慢速命中，那
么这种优化措施反而会降低整体性能
膇解决问题的简单方法：交换两块的内容
肃编译优化技术：无需对硬件做任何改动，通过软件优化降低失效率。
蝿减少指令失效，重新组织程序（指令调度）而不影响程序的
羈 正确性
羇减少数据失效，主要通过优化来改善数据的空间局部性和时间局部
性，基本方法为：
膄数据合并（page212数组合并）
膂内外循环交换循环融合
莇分块
蚇通过预取可帮助减少强制性失效,必须小心不要把你需要的东西换出去,需要预测比较
准确（对数据较困难，对指令相对容易）
羁2、减少Cache失效开销
芀减少CPU与存储器间性能差异的重要手段
螇平均访存时间＝命中时间＋失效率×失效开销
蒈基本手段：
羃多级Cache技术(MultilevelCaches)：采用两级Cache
蚂 与CPU无关，重点是Cache与Memory之间的接口
蒀问题：为了使Memory-CPU性能匹配，到底应该把Cache做的更快，还
是应该把Cache做的更大
袄答案：两者兼顾。二级Cache–降低失效开销（减少访问存储器的次数。
带来的复杂性：性能分析问题
肄性能参数
螁平均访存时间＝命中时间L1+失效率L1×失效开销L1
罿失效开销L1= 命中时间L2+失效率L2×失效开销L2
蚄 | AMAT | = | HitTimeL1+MissrateL1×(HitTimeL2+Miss | rateL2×Miss |
penaltyL2)
袂对第二级Cache，系统所采用的术语
衿局部失效率：该级Cache的失效次数/到达该级Cache的访存次数
荿全局失效率：该级Cache的失效次数/CPU 发出的访存总次数
莅子块放置技术(Sub-blockPlacement)：
袃在减少Tag数量的同时，减少Cache与Memory之间的数据传送量
芁增加块大小是减少Tag数量的有效手段，但增加了Cache和Memory之间
的数据传送量，从而加大了失效开销
螈解决方法：将大块分成若干小块，其中每一小块共享Tag域，并增加Va表示该子
块是否有效。
膅Cache和Memory之间的最小数据传送单位为子块，从而降低了Cache
和Memory间的数据传送量，以减少失效开销
羄请求字处理技术(CriticalWord First and Early Restart)：
莀尽早重启动：只要所请求的字到达，立即发送给CPU，让等待的CPU尽早重启
动继续执行，让其余字的传送与CPU的执行并行。
膈请求字优先：调块时，首先向存储器请求CPU所需要的字，请求字一到达就发
给CPU，让CPU继续执行，同时从存储器中调入其他字。
袅让读优先于写(GivingPriority to Read Misses over Writes)：
螂WriteBuffer (写缓冲)，特别对写直达法更有效
螂CPU不必等待写操作完成，即将要写的数据和地址送到WriteBuffer 后，CPU
继续作其他操作。
蚇写缓冲导致对存储器访问的复杂化
蚆原因：在读失效时，写缓冲中可能保存有所读单元的最新值，还没有写回。
袃解决问题的简单方法1：推迟对读失效的处理，直到写缓冲器清空，导致新的
问题——读失效开销增大。
袁另一办法2：在读失效时，检查写缓冲的内容，如果没有冲突，而且存储器可
访问，就可以继续处理读失效
莀由于读操作为大概率事件，需要读失效优先，以提高性能
莆合并写(MergingWrite Buffer)
袄非阻塞Cache技术
罿预取技术
螀3、通过并行操作减少失效开销或失效率
肇非阻塞Cache技术(NonblockingCaches to Reduce stalls on Cache Misses)
蚂对有些允许乱序执行的机器（采用动态调度方法）,CPU无需在Cache失效时等待。
即在等待数据Cache失效时，可以继续取指令。
莁采用非阻塞Cache或非锁定Cache技术，在某一Cache失效时，仍然允许CPU进行
其他的命中访问，可以有效地提高CPU性能。
腿硬件预取技术(HardwarePrefetching of Instructions and Data)
袇VictimCache, Pseudo Associative Cache 可以在不影响处理器时钟的频率下，降低
失效率，预取技术也能实现这一点
螃CPU在执行这块代码时，硬件预取下一块代码，因为CPU可能马上就要执行这块代
码，这样可以降低或消除Cache的访问失效
蒀当块中有控制指令时，预取失效
薈预取的指令可以放在Icache中，也可以放在其他地方（存取速度比Memory块的地
方）
薇注意：预取是利用存储器的空闲带宽，而不是与正常的存储器操作竞争。
螅编译器控制的预取技术(Compiler-ControlledPrefetching)
螂在ISA中增加预取指令，让编译器控制预取
肈预取的种类
莈寄存器预取:把数据取到R中
薂Cache预取：只将数据取到Cache中，不放入寄存器
羀故障问题
蒇两种类型的预取可以是故障性预取，也可以是非故障性预取
袄所谓故障性预取指在预取时若出现虚地址故障，或违反保护权限，就会有异常发生
蚃非故障性预取，如导致异常就转化为空操作。
聿只有在预取时，CPU可以继续执行的情况下，预取才有意义
袇Cache在等待预取数据返回的同时，可以正常提供指令和数据，称为非阻塞Cache
或非锁定Cache
薄循环是预取优化的主要目标
蚅失效开销较小时，Compiler简单的展开一两次，调度好预取与执行的重叠
莁失效开销较大时，编译器将循环体展开多次，以便为较远的循环预取数据
薀由于发出预取指令需要花费一条指令的开销，因此要避免不必要的预取
芅4、减少命中时间
蒂容量小，结构简单的Cache
薀容量小，一般命中时间短，有可能做在片内
罿另一方案，保持Tag在片内，块数据在片外，如DECAlpha
肅第一级Cache应选择容量小且结构简单的设计方案
薃虚拟Cache
袂物理地址Cache。VA通过TLB产生物理地址，然后存取Cache
葿缺点：需要中间的转换过程，导致命中时间拉长
螆基本思路：对于支持VM的CPU，采用虚拟Cache
蚅即直接能以VA来判定是否命中
羀流水线化Cache访问
袈将地址转换和访问Cache分开，分别安排在流水线的不同段中
薆四、主存
莂存储器的访问源：取指令、取操作数、写操作数和I/O
莃种类：DRAM和SRAM
芇存储器性能指标
芆容量、速度和每位价格
蒄访问时间（AccessTime)
蒁存储周期（CycleTime)
蚇解决存储器频带问题的三种途径：多个存储器并行工作，设置各种缓冲器，Cache存储系
统
肇提高主存性能的方法
薅增大存储器的宽度（并行访问存储器）:最简单直接的方法
蕿优点：简单、直接，可有效增加带宽
莀缺点：增加了CPU与存储器之间的连接通路的宽度，实现代价提高主存容量扩充时，
增量应该是存储器的宽度，写操作问题（部分写操作）
螇冲突问题
莂取指令冲突，遇到程序转移时，一个存储周期中读出的n条指令中，后面的指令将无
用
羂读操作数冲突。一次同时读出的几个操作数，不一定都有用
袀写操作冲突。这种并行访问，必须凑齐n个字之后一起写入。如果只写一个字，必须
先把属于同一个存储字的数据读到数据寄存器中，然后在地址码的控制下修改其中一个
字，最后一起写。
蒈读写冲突。当要读写的字在同一个存储字内时，无法并行操作。
莄冲突的原因
肀从存储器本身看，主要是地址寄存器和控制逻辑只有一套。如果有n个独立的地址寄存器
和n套读写控制逻辑，那么第3，4种冲突自然解决，第1、2种冲突也会有所缓解。
艿采用简单的多体交叉存储器
羄一套地址寄存器和控制逻辑
蒅存储器芯片组织为多个体（Bank）
蒃存储体的宽度，通常为一个字，不需要改变总线的宽度
蚈目的：在总线宽度不变的情况下，完成多个字的并行读写
螄缺陷：不能对单个体单独访问，对解决冲突没有帮助，逻辑上是一种宽存储器，对各个存
储体的访问被安排在不同的时间段
节独立存储体
薁目的：可对单个存储体独立操作
膈多处理机系统，I/O，CPU（hitunder n misses, 非阻塞Cache)
蒅思路：有多个存储控制器，每个体有独立的地址线，可能有独立的数据线
芄多体交叉方式中访存操作和数据传送重叠；独立存储体完全重叠
虿独立存储体方式与多体交叉方式的结合
薇主存系统由若干独立存储体构成
芅独立存储体内，按多体交叉方式组织
莅避免存储体冲突：两个访问请求访问同一个体
肂五虚拟存储器
羆允许应用程序的大小，超过主存容量。目的是提高存储系统的容量
羅帮助OS进行多进程管理
膃每个进程可以有自己的地址空间
膀提供多个进程空间的保护
蚀可以将多个逻辑块映射到共享的物理存储器上
蚆静态重定位和动态重定位
芄应用程序运行在虚地址空间
薂虚实地址转换对用户是透明的
聿虚拟存储管理的是主存－辅助存储器这个层面上
蒆失效：页失效或地址失效
羁块：页或段
蚁Cache与VM的区别
蕿目的不同：Cache是为了提高访存速度，VM是为了提高存储容量
膇替换的控制者不同：Cache失效由硬件处理，VM的页失效通常由OS处理
肃一般页失效开销很大，因此替换算法非常重要
蝿地址空间：VM空间由CPU的地址尺寸确定，Cache的大小与CPU地址尺寸无关
羈下一级存储器
羇Cache下一级是主存
膄VM下一级是磁盘，大多数磁盘含有文件系统，文件系统寻址与主存不同，它通常在I/O空间中，VM的下一级通常称为SWAP空间
膂页式管理和段式管理
VM可分为两类：页式和段式
页式：每页大小固定
段式：每段大小不等
映象规则
选择策略：低失效率和复杂的映象算法，还是简单的映射方法，高失效率
由于失效开销很大，一般选择低失效率方法，即全相联映射
查找算法－用附加数据结构
固定页大小－用页表：VPN－>PPN，Tag标识该页是否在主存
可变长段－段表：段表中存放所有可能的段信息，段号－>段基址再加段内偏移量，可能由许多小尺寸段
页表
页表中所含项数：一般为虚页的数量
功能:VPN－>PPN，方便页重新分配，有一位标识该页是否在内存
替换规则
LRU是最好的，但真正的LRU方法，硬件代价较大
用硬件简化，通过OS来完成
为了帮助OS寻找LRU页，每个页面设置一个usebit
当访问主存中一个页面时，其usebit置位
OS定期复位所有使用位，这样每次复位之前，使用位的值就反映了从上次复位到现在 的这段时间中，哪些页曾被访问过。
当有失效冲突时，由OS来决定哪些页将被换出去。
写策略：总是用写回法，因为访问硬盘速度很慢。
页面大小的选择
页面选择较大的优点，减少了页表的大小，如果局部性较好，可以提高命中率
页面选择较大的缺点，内存中的碎片较多，内存利用率低，进程启动时间长，失效开销加大TLB（Translationlook-asideBuffer)
页表一般很大，存放在主存中。，导致每次访存可能要两次访问主存，一次读取页表项，一次读写数据
解决办法：采用TLB
存放近期经常使用的页表项，是整个页表的部分内容的副本。
速度至关重要
TLB过小，意义不大
TLB过大，代价较高
相联度较高（容量小）
以下无正文
仅供个人用于学习、研究；不得用于商业用途。
Forpersonal use only in study and research; not for commercial use.
仅供个人用于学习、研究；不得用于商业用途。
Nurfür den persönlichen für Studien, Forschung, zu kommerziellenZwecken verwendet werden.
Pourl 'étude et la recherche uniquement à des fins personnelles; pas àdes fins commerciales.
仅供个人用于学习、研究；不得用于商业用途。то л ь к о для людей, которые используются дляобучения, исследований и не должны
использоватьсяв коммерческих целях.