计算机体系结构复习资料(汇总版).doc

. .
第一章计算机系统结构的基础知识
1、计算机体系结构：计算机体系结构是程序员所看到的计算机属性，即概念性结构与功能特性。
2、透明性：对本来是存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。
在一个计算机系统中，低层机器的属性对高层机器的程序员往往是透明的，如传统机器级的概念性结构和功能特性，对高级语言程序员来说是透明的。
3、计算机系统结构、计算机组成、计算机实现之间的关系：
计算机系统结构指的是计算机系统的软、硬件的界面，即机器语言程序员所看到的传统机器级所具有的属性。
计算机组成：指的是计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。它着眼于物理机器级内各事件的排序方式与控制方式、各部件的功能以及各部件之间的关系。
计算机的实现：指的是计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。它着眼于器件技术和微组装技术，其中器件技术在实现技术中起主导作用。
4、计算机系统的分类：1）Flynn（单/多指令流单/多数据流四种）
2）冯氏分类法：最大并行速度。
5、程序的局部性：时间局部性（程序即将用到的信息很可能就是目前正在使用的信息）
空间局部性（程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或者邻近）。
6、计算机系统设计原理：由上往下设计、由下往上设计、从中间开始设计。
从中间设计的优点：“中间”指层次结构中的软硬件的交界面，目前一般是在传统机器语言机器级与操作系统机器级之间。好处：采用这种方法时，首先要进行软硬件功能分配，确定好这个界面。然后从这个界面开始，软件设计者往上设计操作系统、汇编、编译系统等，硬件设计者往下设计传统机器级、微程序机器级等。软件和硬件并行设计可以缩短设计周期，设计过程中可以交流协调，是一种交互式的、很好的设计方法。
7、存储程序计算机（冯·诺依曼结构）：采用存储程序原理，将程序和数据存放在同一存储器中。指令在存储器中按其执行顺序存储，由指令计数器指明每条指令所在的单元地址。存储程序原理的基本点是指令驱动。
主要特点：
·计算机以运算器为中心。输入/输出设备与存储器之间的数据传送都经过运算器；存储器、输入/输出设备的操作以及它们之间的联系都由控制器集中控制。
·在存储器中，指令和数据同等对待。指令和数据一样可以进行运算，即由指令组成饿程序是可以修改的。
·存储器是按地址访问、按顺序线性编址的一维结构，每个单元的位数是固定的。
·指令的执行是顺序的，即一般是按照指令在存储器中存放的顺序执行。程序的分支由转移指令实现。由程序计数器PC指明当前正在执行的指令在存储器中的地址。
·指令由操作码和地址码组成。操作码指明本指令的操作类型，地址码指明操作数地址和存放运算结果的地址。操作数的类型由操作码决定，操作数本身不能判定是何种数据类型。
·指令和数据均以二进制编码表示，采用二进制运算。
8、计算机五大部件：控制器、运算器、存储器、输入输出设备。
9、一条指令由那两部分组成：操作码、地址码。
10、软件兼容：同一个软件可以不加修改第运行于体系结构相同的各档及其，而且它们所获得的结果一样，差别只在于运行时间不同。
11、系列机的软件兼容方式：软件兼容有（向上兼容）和（向下兼容）之分，又有（向前兼容）和（向后兼容）之分。系列机软件必须保证（向后兼容），力争（向上兼容）。
兼容机：不同制造商生产的具有相同系统结构的计算机。
系列机：在一个厂家内生产的具有相同的体系结构，但具有不同组织和实现的一系列不同型号的机器。
12、并行性的概念：指计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠，就存在并行性。他是同时性和并发性两种含义。
同时性：两个或两个以上的事件在同一时刻发生。
并发性：两个或两个以上的事件在同一时间间隔内发生。
从处理数据的角度并行性从低到高分为：a、字串位串：每次只对一个字的一位进行处理。这是最基本的串行处理方式，不存在并行性 b、字串位并：同时对一个字的全部位进行处理，不同字之间是串行的。已开始出现并行性。 c、字并位串：同时对许多字的同一位进行处理，这种方式具有较高的并行性。 d、全并行：同时对许多字的全部位或部分位进行处理，这是最高一级的并行。
从执行角度来看，并行性从低到高依次分为：a、指令内部并行：单条指令中各微操作之间的并行。b、指令级并行：并行执行两条或两条以上的指令。c、线程级并行：并行执行两个或两个以上的线程，通常是以一个进程内派生的多个线程为调度单位。d、任务级或过程级并行：并行执行两个或两个以上的过程或任务，以子程序或进程为调度单元。e、作业或程序级并行：并行执行两个或两个以上的作业或程序。
13、提高并行性的技术途径：
（1）时间重叠：多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。
（2）资源重复：通过重复设置资源，尤其是硬件资源，大幅度提高计算机系统的性能。
（3）资源共享：是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备。
14、多机系统的耦合度分类：
（1）最低耦合：除通过某种中间存储介质之外，各计算机之间没有物理连接，也无共享的联机硬件资源。（2）松散耦合：通过通道或通信线路实现计算机间互连，共享某些外围设备，机间的相互作用是在文件或数据集一级进行。（3）紧密耦合：机间物理连接的频带较高，往往通过总线或高速开关实现互连，可以共享主存。
第二章指令系统的设计
1、计算题：Amdahl定律：加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比（P7页）。
向上（下）兼容：按某档机器编制的程序，不加修改就能运行于比它高（低）档的机器。
向前（后）兼容：按某个时期投入市场的某种型号机器编制的程序，不加修改地就能运行于在它之前（后）投入市场的机器。向后兼容是系列机的根本特征。
兼容机：由不同公司厂家生产的具有相同系统结构的计算机。
2、计算题：哈夫曼树
哈弗曼编码方法的计算（1）码长表示法（2）码点表示法
1）码长表示法：2—4—6(有三种长度，两位的、四位的、六位的)
2）码点表示法：3/6/4（最短的有三条，最长的有四条，中间长度对应为6条）
3）2—4最多码点数：13
解释：2可以有00、01、10、11四种，但是必须是2-4扩展至少有一个为两位，其他的可以在前面扩展两位，每个可以对应四种例如对于01可以变成：0001、0101、1001、1101，所以总共加起来最多只能是3*4+1=13种
4）以下四种编码中：不是2-4扩展的是（D）
A:1/2 B:2/8 C:3/4 D:4/8
大题：有一台模型机，有以下七种不同的指令，使用频率表示如下：
T1: 20% T2: 12% T3:11% T4: 15% T5: 8%
T6:3% T7: 2% T8:18% T9: 10% T10: 1%
（1） 上图为哈夫曼编码图：平均长度为
2*20%+3*（10%+11%+12%+15%+18%）+4*8%+5*3%+6*(1%+2%)=3.03
可以表示成：00、010、011、100、101、110、1110、11110、111110、111111
（2）若用定长操作码表示至少需要多少位？
答：至少需要4位
（3）用扩展操作码（只有两位）可以有多种方式表示，要求平均长度不能大于3.2，给出最合理的编码方式，并求出平均编码长度？
①采用扩展操作码可以用2—4扩展操作码的码点1/9表示：求得平均长度为：1*（20%）+4（80%）=3.4>3.2不符合
②3—4的6/4编码方式：平均长度为3*（10+11+12+15+18+20）%+4*(1+2+3+8)% =3.14<3.2符合条件
③4—5编码6/4方式：4*（10+11+12+15+18+20）%+5*(1+2+3+8)%>3.2
④2—5编码中的3/7方式：2*（15+18+20）%+5*（1+2+3+8+10+11+12）%=3.41>3.2不符合
3、数据表示：硬件能够直接识别、指令集可以直接调用的数据类型。

第三章 流水线技术
1、流水线技术是指：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。
2、从不同的角度和观点，把流水线分成多种不同的种类。
（1）按照流水线所完成的功能来分类
单功能流水线：只能完成一种固定功能的流水线。
多功能流水线:流水线的各段可以进行不同的连接，从而使流水线在不同的时间，或者在同一时间完成不同的功能。
（2）按照同一时间内各段之间的连接方式对多功能流水线做进一步的分类
静态流水线：在同一时间内，流水线的各段只能按同一种功能的连接方式工作。
动态流水线：在同一时间内，当某些段正在实现某种运算时，另一些段却在实现另一种运算。（3）按照流水的级别来进行分类
部件级流水线（运算操作流水线）：把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。
处理机级流水线（指令流水线）：把解释指令的过程按照流水方式处理。
处理机间流水线（宏流水线）：由两个以上的处理机串行地对同一数据流进行处理，每个处理机完成一项任务。
（4）按照流水线中是否有反馈回路来进行分类
线性流水线：各段串行连接、没有反馈回路的流水线。
非线性流水线：各段除了有串行连接外，还有反馈回路的流水线。
（5）根据任务流入和流出的顺序是否相同来进行分类
顺序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的。
乱序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成（从输出端流出）。又称为无序流水线、错序流水线、异步流水线。
3、流水线指标：吞吐率、加速比、效率
A吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。
最大吞吐率是指流水线在连续流动达到稳定状态后所得到的吞吐率。
第一种情况：各段时间相等（设为△t0）
假设流水线由 m 段组成，完成 n 个任务。
完成 n 个任务所需的时间

第二种情况：各段时间不等

B加速比是指流水线的速度与等功能非流水线的速度之比。S＝T非流水／T流水
若流水线为 m 段，且各段时间相等，均为△t0 ，则： T非流水＝n m△t0
T流水＝m△t0＋(n－1)△t0 (公式自己代入)
C (1)若各段时间相等，则各段的效率ei相等，即e1＝e2 ＝e3＝、、、＝em＝n△t0／T流水
整个流水线的效率为:E=n△t0/T流水=n/（n+m-1）
(2)从时－空图上看，效率实际上就是 n 个任务所占的时空区与 m 个段总的时空区之比，即：
n 个任务占用的时空区
E ＝━━━━━━━━━━━━━
m 个段总的时空区
实例分析:性能分析（分析法, 时空图法）.
例1. 四段流水线, △t1=△t3=△t4=△t, △t2=3△t,4个任务、10个任务时TP，η、SP 。
（1）分析法: 各段时间不等

(2) 时空图法:

比较说明:N>>M流水性能才发挥得更好
4、非线性流水线调度：
5、流水线中的相关是指相邻或相近的两条指令因存在某种关联
流水线相关有3种类型：a数据相关、b名相关，包括反相关和输出相关（输出相关用换名技术来消除）、c控制相关（结构相关、数据相关、控制相关）
流水线冲突有3种类型及对策：
a结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。
b数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。
包括写后读冲突、写后写冲突和读后写冲突，对策有定向技术、停顿（气泡法）和编译器解决
c控制冲突：流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。最简单方法冻结或排空。
第四章 向量处理机
1、向量处理机：为了充分发挥流水线的效率，实现高性能计算，有的流水线处理机设置了向量数据表示和相应的向量指令。这种处理机称为向量处理机。
向量处理机的四个性能指标：a.向量指令的处理时间；b.最大性能和半性能向量长度；c.向量长度临界值。

第五章 指令级并行及其开发—硬件开发
1、指令调度：通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟，将相关指令转化为无关指令。指令调度是循环展开的技术基础。
静态调度：它不是在程序执行的过程中，而是在编译期间进行代码调度和优化的。
动态调度：是在程序的执行过程中，依靠专门硬件对代码进行调度。
2、记分牌动态调度方法：该机器用一个称为记分牌的硬件实现了对指令的动态调度。
3、多指令流出技术（CPI值小于，就必须采用多流出技术），处理器有3种基本结构：
超长指令字：每个时钟周期流出的指令数是固定的，它们构成一条长指令，或说是一个混合指令包，这种处理器目前只能通过编译静态调度。
超标量：每个时钟周期流出的指令数不定，它既可以通过编译器静态调度，也可以通过记分牌或 Tomasulo算法动态调度。
超流水：将每个功能部件进一步流水化，特别是取 指令或指令流出被分解为多个段，使得一个功能部件在一拍中可以处理多条指令。
流水线实现的五步：取指令、指令编译或寄存器读取、执行或有效地址计算、存储器访问或分支完成、写回
4、多指令处理机有几种（超流水线处理机）
K段流水线基准标量处理机、m度超标量处理机、n度超流水线处理机、(m,n)度超标量超流水线处理机。
指令多流出处理器受哪些因素的限制呢？主要受以下三个方面的影响：a程序所固有的指令级并行性。b硬件实现上的困难。c超标量和超长指令字处理器固有的技术限制。
第六章指令级并行及其开发—软件开发
1、循环展开和指令调度要注意哪些问题？
1 保证正确性：在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制，操作数偏移量的修改；
2 注意有效性：只有能够找到不同循环体之间的无关性，才能有效地使用循环展开；
3 使用不同的寄存器，否则可能导致新的冲突；
4 删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正；
5 注意对存储器数据的相关性分析；6 注意新的相关性。由于原循环不同次的迭代在展开后都到了同一次循环体中，因此可能带来新的相关性。
第七章存储系统
1、程序的局部性原理：程序在执行时所访问的地址不是随机的，而是相对簇聚；这种簇聚包括指令和数据两部分。包含时间局部性（程序马上将要用到的信息很可能就是现在正在使用的信息）和空间局部性（程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的）。
2、计算机三级存储系统：高速缓冲存储器、主存储器、辅助存储器。
3、三种映像规则：全相联映像、直接相联映像、组相联映像。
全相联：是指主存中的任一块可以被放置到Cache中的任意一个位置。
直接映像：是指主存中的每一块只能放置到Cache中唯一的一个位置。
组相联映像：Cache被等分为若干组，每组有若干个块构成。主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。
4、三种类型的不命中：强制性不命中、容量不命中、冲突不命中。
命中率与Cache和相联度关系：（1）相联度越高，冲突不命中就越少。（2）强制性不命中和容量不命中不受相联度影响。（3）强制性不命中不受Cache容量的影响，但容量不命中却随着容量的增加而减少。
牺牲Cache：在Cache和其下一级存储器的数据通路上增设一个全相联的小Cache，称为牺牲Cache。牺牲Cache中存放因冲突而被替换出去的那些块。每当失效发生时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需块。
5、Cache优化技术三种优化措施考一种：
优化技术
不命中率
不命中开销
命中时间
硬件复杂度
说明
增加块大小
+
—

0
实现容易；Pentium 4的第二级Cache采用了128B的块
增加Cache容量
+

1
被广泛采用，特别是第二级Cache
提高相联度
+

—
1
被广泛采用
“牺牲”Cache
+

2
AMD Athlon采用了8个项的“牺牲”Cache
伪相联Cache
+

2
MIPS R10000的第二级Cache采用
硬件预取指令和数据
+

2~3
许多机器预取指令，UltraSPARC Ⅲ预取数据
编译器控制的预取
+

3
需同时采用非阻塞Cache；有几种微处理器提供了对这种预取的支持
用编译技术减少Cache不命中次数
+

0
向软件提出了新要求；有些机器提供了编译器选项

使读不命中优于写

+

1
在单处理机上实现容易，被广泛采用
写缓冲合并

+

1
与写直达合用，广泛应用，例如21164，UltraSPARC Ⅲ
尽早重启动和关键字优先

+

2
被广泛采用
非阻塞Cache

+

3
所有乱序执行的CPU中都采用
两级Cache

+

2
硬件代价大；两级Cache的块大小不同时实现困难；被广泛采用
小而简单的Cache
—

+
0
实现容易，被广泛采用
对Cache进行索引时不必进行地址转换

+
2
对于小容量Cache来说实现容易，已被Alpa21164和UltraSPARC Ⅲ采用
流水化Cache访问

+
1
被广泛采用
Trace Cache

+
3
Pentium 4 采用
第八章 输入输出系统
1、I/O系统的可靠性、可用性和可信性
a.系统从初始状态开始一直提供服务的能力，用平均无故障时间衡量
b.系统正常工作时间在连续两次正常服务间隔时间中所占的比例，用平均失效间隔时间衡量
c.多大程度上可以合理地认为服务是可靠的，不可度量。
2、同步方式、异步方式的优缺点
同步总线的控制线中包含一个时钟，总线上所有设备的所有通讯操作都以该时钟为基准。这种总线不仅速度快，而且成本低。但同步总线有两个缺点：①由于时钟过长距离传输后会扭曲，因而同步总线不能用于长距离的连接。特别是对于高速同步总线来说，更是如此。②总线上的所有设备都必须以同样的时钟频率工作。虽然有的同步总线上可以连接不同速度的设备，但其工作频率必须以最慢的设备为基准。CPU-储存器总线通常是采用同步总线。
异步总线上没有统一的参考时钟，每个设备都有各自的定时方法。总线上的发送设备和接收设备采用握手协议。异步总线能够比较容易地连接各种不同的设备，而且由于不是用统一的时钟来定时，因而也就不存在时钟扭曲和同步的问题，所以其传输距离可以比较长。很多I/O总线都采用异步总线。
同步总线通常比异步总线快，因为它避免了传输时握手协议的额外开销。选择同步总线还是异步总线，不仅要考虑数据宽带，而且要考虑传输距离以及可以连接的设备数量。一般来说，如果设备的类型较少且距离较近，则宜采用同步总线；否则，就宜采用异步总线。
3、三种通道类型，三种类型通道与CPU、设备控制器和外设的连接关系，三种类型的通道的流量
（1）字节多路通道a为多台低速或中速的外设服务。b以字节交叉的方式分时轮流地为它们服务。c字节多路通道可以包含多个子通道，每个子通道连接一台设备控制器。
（2）选择通道a为多台高速外围设备服务。b在一段时间内只为一台高速外设独占使用。c选择通道的硬件包括5个寄存器、格式变换部件及通道控制部件
（3）数组多路通道a适用于高速设备。b每次选择一个高速设备后传送一个数据块，轮流为多台外围设备服务。c数组多路通道之所以能够并行地为多台高速设备服务，是因为虽然其所连设备的传输速率很高，但寻址等辅助操作时间很长。
通道流量：一个通道在数据传送期间，单位时间内能够传送的最大数据量，一般用字 节个数来表示。又称为通道吞吐率，通道数据传输率等。 通道最大流量，一个通道在满负荷工作状态下的流量。
TS：设备选择时间。
TD：传送一个字节所用的时间。
p： 在一个通道上连接的设备台数，且这些设备同时都在工作。
n: 每台设备传送的字节数，这里假设每台设备传送的字节数都相同。
k： 数组多路通道传输的一个数据块中的包含的字节数。在一般情况下，k<n。对于磁盘、 磁带等磁表面存储器，通常k=512。
T： 通道完成全部数据传送工作所需时间。
字节多路通道：

选择通道：

数组多路通道：
第九章 互连网络
1、互连网络：一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。这些结点可以是处理器、存储模块或其他设备。
2、基本互联函数：恒等函数、交换函数、均匀洗牌函数
交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接

主要用于构造立方体互连网络和各种超立方体互连网络。它共有n＝log2N种互连函数。（N为结点个数）当N＝8时，n＝3，可得到常用的立方体互连函数：

N=8 的立方体交换函数

均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。
函数关系

即把输入端的二进制编号循环左移一位。
N=8 的均匀洗牌和逆均匀洗牌函数
逆均匀洗牌函数：将输入端的二进制编号循环右移
一位而得到所连接的输出端编号。
互连函数

逆均匀洗牌是均匀洗牌的逆函数
3、互连网络的主要特性参数有：（时延和带宽是评估互连网络性能的两个基本指标）
（1）网络规模：网络中结点的个数。表示该网络所能连接的部件的数量。
（2）结点度：与结点相连接的边数（通道数），包括入度和出度。进入结点的边数称为入度。
从结点出来的边数称为出度。
（3）距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。
（4）网络直径：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。
（5）结点之间的线长：两个结点之间连线的长度，用米、千米等表示。
（6）等分宽度：当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。线等分宽度：B＝b×w 其中：w为通道宽度（用位表示）。该参数主要反映了网络最大流量。
（7）对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。 课本P257弄清楚线性阵列和环和带弦环。
1、cache降低失效率的几种方法增加Cache块大小、提高相联度、victim cache、伪相联 cache、硬件预存、编译器控制的预存、编译器优化
4、减少失效开销技术
让读失效优先于写‚子块放置技术ƒ请求字处理技术„非阻塞Cache技术…采用两级Cache
5、请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU
. .jz.