计算机体系结构期末复习资料.doc

计算机体系结构期末复习资料

第一章 计算机体系结构的基本概念
1. 层次结构——计算机系统能够按语言的功能划分为多级层次结构，每一层以不同的语言为特征。
第一级---微程序机器级。第二级—机器语言。第三级—操作系统虚拟机。第四级—汇编语言虚拟机。第五级—高级语言虚拟机。第六级—应用语言虚拟机
2. 体系结构——程序员所看到的计算机的属性，即概念性结构与功能特性。
3. 透明性——在计算机技术中，对原来存在的事物或属性，从某一角度来看又仿佛不存在的概念称为透明性。
4. 系列机——在一个厂家生产的具有相同的体系结构，但具有不同的组成和实现的一系列不同型号的机器。
5. 软件兼容——同一个软件能够不加修改地运行于体系结构相同的各档机器上，而且它们所获得的结果一样，差别只在于运行的时间不同。
6. 兼容机——不同厂家生产的、具有相同体系结构的计算机。
7. 计算机组成——计算机体系结构的逻辑实现。
8. 计算机实现——计算机组成的物理实现。
9. 存储程序计算机（冯·诺依曼结构）——采用存储程序原理，将程序和数据存放在同一存储器中。指令在存储器中按其执行顺序存储，由指令计数器指明每条指令所在的单元地址。
10. 并行性——在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作。
11. 响应时间——从事件开始到结束之间的时间，也称执行时间。
12. 测试程序——用于测试计算机性能的程序，可分为四类：真实程序、核心程序、小测试程序、合成测试程序。
13. 测试程序组件——选择一个各个方面有代表性的测试程序，组成一个通用的测试程序集合。这个通用的测试程序集合称为测试程序组件。
14. 大概率事件优先——此原则是计算机体系结构中最重要和最常见的原则。对于大概率事件（最常见的事件），赋予它优先的处理权和资源使用权，以获得全局的最优结果。
15. 系统加速比——系统改进前与改进后总执行时间之比。
16. Amdahl定律——加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中的所占的重要性。
17. 程序的局部性原理——程序在执行时所访问的地址不是随机的，而是相对簇聚；这种簇聚包括指令和数据两部分。
18. CPI——指令时钟数（Cycles per Instruction）。
1.4 对于一台400MHz计算机执行标准测试程序，程序中指令类型，执行数量和平均时钟周期数如下：
指令类型
指令执行数量
平均时钟周期数
整数
45000
1
数据传送
75000
2
浮点
8000
4
分支
1500
2

求该计算机的有效CPI、MIPS和程序执行时间。

解：

程序执行时间=（）／400=575ìs

1.5 计算机系统有三个部件能够改进，这三个部件的加速比如下：
部件加速比1＝30； 部件加速比2＝20； 部件加速比3＝10；
(1) 如果部件1和部件2的可改进比例为30％，那么当部件3的可改进比例为多少时，系统的加速比才能够达到10？
(2) 如果三个部件的可改进比例为30％、30％和20％，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？
解：在多个部件可改进情况下Amdahl定理的扩展:

式中，fi为可加速部件i在未优化系统中所占的比例；Si是部件i的加速比。

CISC——复杂指令集计算机。RISC——精简指令集计算机。

第三章 流水线技术
1. 流水线——将一个重复的时序过程，分解为若干个子过程，而每一个子过程都可有效地在其专用功能段上与其它子过程同时执行。
2. 单功能流水线——只能完成一种固定功能的流水线。
3. 多功能流水线——流水线的各段能够进行不同的连接，从而使流水线在不同的时间，或者在同一时间完成不同的功能。
4. 静态流水线——同一时间内，流水线的各段只能按同一种功能的连接方式工作。
5. 动态流水线——同一时间内，当某些段正在实现某种运算时，另一些段却在实现另一种运算。
6. 部件级流水线——（运算操作流水线）把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。
7. 处理机级流水线——（指令流水线）把解释指令的过程按照流水方式处理。
8. 处理机间流水线——（宏流水线）由两个以上的处理机串行地对同一数据流进行处理，每一个处理机完成一项任务。
9. 线性流水线——指流水线的各段串行连接，没有反馈回路。
10. 非线性流水线——指流水线中除有串行连接的通路外，还有反馈回路。
11. 标量流水处理机——处理机不具有向量数据表示，仅对标量数据进行流水处理。
12. 向量流水处理机——处理机具有向量数据表示，并经过向量指令对向量的各元素进行处理。
13. 结构相关——某些指令组合在流水线中重叠执行时，发生资源冲突，则称该流水线有结构相关。
14. 数据相关——当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作的顺序，使得读/写操作顺序不同于它们非流水实现时的顺序，将导致数据相关。
15. 定向——将计算结果从其产生的地方直接送到其它指令需要它的地方，或所有需要它的功能单元，避免暂停。
16. RAW——两条指令i，j，i在j前进入流水线，j执行要用到i的结果，但当其在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行读操作，得到错误值。
17. WAW——两条指令i，j，i在j前进入流水线，j、i的操作数一样，在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行写操作，导致写错误。
18. WAR——两条指令i，j，i在j前进入流水线，j可能在i读某个寄存器之前对该寄存器进行写操作，导致i读出数据错误。
3.9 有一条流水线如下所示。

（1） 求连续输入10条指令，该流水线的实际吞吐率和效率；
（2） 该流水线的瓶颈在哪一段？请采取三种不同的措施消除此“瓶颈”。对于你所给出的新流水线，计算连续输入10条指令时，其实际吞吐率和效率。
解：（1）

（2）瓶颈在3、4段。
l 变成八级流水线（细分）

l 变成两级流水线（合并）

l 重复设置部件
1
2
3-1
3-2
4-1
4-2
4-3
4-4

★如果流水线有m段，各段的处理时间分别是ti（i=1，2，…，m），现在有n个任务需要完成，且每个任务均需流水线各段实现，请计算：
（1） 流水线完成这n个任务所需要的时间；
（2） 和非流水线实现相比，这n个任务流水实现的加速比是多少？加速比的峰值是多少？
解：（1）
（2）

第五章 存储层次
1． 存储层次——采用不同的技术实现的存储器，处在离CPU不同距离的层次上，目标是达到离CPU最近的存储器的速度，最远的存储器的容量。
2． 全相联映象——主存中的任一块能够被放置到Cache中任意一个地方。
3． 直接映象——主存中的每一块只能被放置到Cache中唯一的一个地方。
4． 组相联映象——主存中的每一块能够放置到Cache中唯一的一组中任何一个地方（Cache分成若干组，每组由若干块构成）。
5． 替换算法——由于主存中的块比Cache中的块多，因此当要从主存中调一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全部被占用的情况。这时，需要被迫腾出其中的某一块，以接纳新调入的块。
6． LRU——选择最近最少被访问的块作为被替换的块。实际实现都是选择最久没有被访问的块作为被替换的块。
7． 写直达法——在执行写操作时，不但把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。
8． 写回法——只把信息写入Cache中相应块，该块只有被替换时，才被写回主存。
9． 按写分配法——写失效时，先把所写单元所在的块调入Cache，然后再进行写入。
10． 不按写分配法——写失效时，直接写入下一级存储器中，而不把相应的块调入Cache。
11． 命中时间——访问Cache命中时所用的时间。
12． 失效率——CPU访存时，在一级存储器中找不到所需信息的概率。
13． 失效开销——CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。
14． 强制性失效——当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。
15． 容量失效——如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。
16． 冲突失效——在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。
17． 2：1Cache经验规则——大小为N的直接映象Cache的失效率约等于大小为N /2的两路组相联Cache的实效率。
18． 相联度——在组相联中，每组Cache中的块数。
19． Victim Cache——位于Cache和存储器之间的又一级Cache，容量小，采用全相联策略。用于存放由于失效而被丢弃（替换）的那些块。每当失效发生时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需块。
20． 伪相联Cache——一种既能获得多路组相联Cache的低失效率，又能获得直接映象Cache的命中速度的相联办法。
★ 降低Cache失效率有哪几种方法？简述其基本思想。
常见的降低Cache失效率的方法有下面几种：
（1） 增加Cache块大小。增加块大小利用了程序的空间局部性。
（2） 提高相联度，降低冲突失效。
（3） Victim Cache，降低冲突失效。
（4） 伪相联Cache，降低冲突失效。
（5） 硬件预取技术，指令和数据都能够在处理器提出访问请求前进行预取。
（6） 由编译器控制的预取，硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。
（7） 编译器优化，经过对软件的优化来降低失效率。
★给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？
（1） 理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次；
（2） 两者Cache容量均为64KB，块大小都是32字节；
（3） 组相联Cache中的多路选择器使CPU的时钟周期增加了10％；
（4） 这两种Cache的失效开销都是80ns；
（5） 命中时间为1个时钟周期；
（6） 64KB直接映象Cache的失效率为1.4％，64KB两路组相联Cache的失效率为1.0％。
解： 平均访问时间＝命中时间＋失效率×失效开销
平均访问时间1-路=2.0+1.4% *80=3.12ns
平均访问时间2-路=2.0*(1+10%)+1.0% *80=3.0ns
两路组相联的平均访问时间比较低
CPUtime=（CPU执行+存储等待周期）*时钟周期
CPU time=IC（CPI执行+总失效次数/指令总数*失效开销） *时钟周期
=IC（（CPI执行*时钟周期）+（每条指令的访存次数*失效率*失效开销*时钟周期））
CPU time 1-way=IC(2.0*2+1.2*0.014*80)＝5.344IC
CPU time 2-way=IC(2.2*2+1.2*0.01*80)＝5.36IC
相对性能比：5.36/5.344=1.003
直接映象cache的访问速度比两路组相联cache要快1.04倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。因此这里选择两路组相联。
★ 伪相联中，假设在直接映象位置没有发现匹配，而在另一个位置才找到数据（伪命中）时，需要1个额外的周期，而且不交换两个Cache中的数据，失效开销为50个时钟周期。试求：
（1） 推导出平均访存的时间公式。
（2） 利用（1）中得到的公式，对于2KBCache和128KBCache，重新计算伪相联的平均访存时间。请问哪一种伪相联更快？
假设 2KB直接映象Cache的总失效率为0.098，2路相联的总失效率为0.076；
128KB直接映象Cache的总失效率为0.010，2路相联的总失效率为0.007。
解：
不论作了何种改进，失效开销相同。不论是否交换内容，在同一“伪相联”组中的两块都是用同一个索引得到的，因此失效率相同，即：失效率伪相联＝失效率2路。
伪相联cache的命中时间等于直接映象cache的命中时间加上伪相联查找过程中的命中时间*该命中所需的额外开销。
命中时间伪相联＝命中时间1路＋伪命中率伪相联×1
交换或不交换内容，伪相联的命中率都是由于在第一次失效时，将地址取反，再在第二次查找带来的。
因此 伪命中率伪相联＝命中率2路－命中率1路＝（1－失效率2路）－（1－失效率1路）
＝失效率1路－失效率2路。交换内容需要增加伪相联的额外开销。
平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×1
＋失效率2路×失效开销1路
将题设中的数据带入计算，得到：
平均访存时间2Kb=1+(0.098-0.076)*1+(0.076 *50 ) =4.822
平均访存时间128Kb=1+(0.010-0.007)*1+(0.007 *50 ) =1.353
显然是128KB的伪相联Cache要快一些。