《计算机系统结构》往年考题参考答案
仅供参考！
一、简答题
1. 指令流水计算机中，采用独立的指令缓存与数据缓存对系统性能有什么好处。
【答】 ①解决访存和取指的结构冲突，加速流水线；②数据和指令的访问有所不同，设置单独的 Cache 有利于提高命中率，减少平均访存时间。
2. 什么是指令动态调度？使用寄存器重命名能够解决哪些数据冲突？
【答】指令动态调度是指在程序执行过程中，依靠专门的硬件队代码进行调度。使用寄存器重命名能够解决名相关（反相关、输出相关）。
3. 从数据和指令的角度，分别说明引起时间与空间局部性的原因。
【答】数据：对于刚被访问过的数据，很有可能再次访问它或者它附近的数据。指令：顺序执行的可能性较大。
4. 直接用虚拟地址索引缓存会存在什么问题？
【答】多个虚拟地址可能指向同一物理地址。
5. 多处理机为什么要维护缓存一致性？
【答】每个处理机都有一份自己的Cache，但是这些Cache都映射同一个物理主存，当一个处理机修改自己Cache的数据时，其他处理机中该部分的数据就不是最新的，造成不一致性。

二、填空题
1. 16个处理器组成的网络，使用洗牌函数相联，那么与10号相联的是 。
【答】10=(1010)2，循环左移一位得(0101)2=5。
2. 有16个处理器，编号为0,1,…,15，先经过PM2+3，再经过混洗变换后，11号处理器连向_号处理器。
【答】11经过PM2+3得到 ，3再经过混洗变换得6。
3. 使用混洗交换单级网络将一个PE中的数据播送到所有16个PE中，需要_次交换，需要混洗。假设每步只能进行混洗或交换中的一种变换。
【答】4次交换，3次混洗。
4. 16个处理器组成的网络，采用PM2±0，PM2±2链接，网络直径为 ，结点度为 。
【答】有结论： 个处理器组成的网络，采用PM2±0，PM2±n/2链接，实现各处理单元之间上下左右互联。网络直径为3，结点度为4。
5. 可以在向量与标量工作模式中切换的处理器，处理向量时效率是处理标量的9倍。已知运行一段程序时有1/4的时间在运行向量指令，向量指令的比例为 。
【答】设向量指令占比 ，则 ，解得 。
6. 向量处理器在串行模式执行以下指令需要 拍，使用链接技术需要 拍。
v3 <- A (load, 6拍)
v2 <- v0 + v1 (add, 6拍)
v4 <- v2 * v3 (mul, 7拍)
【答】串行模式下需要 拍；
使用链接技术需要 拍。
7. 处理器P1和P2执行A, B, C三种指令的周期如下
P1 P2
A 1 2
B 2 3
C 4 4
一段程序中A占60%，B占30%，C占10%，分别求P1和P2运行该程序时的CPI。
【答】P1运行该程序的CPI为 ，P2运行该程序的CPI为 。
8. 已知一处理器指令缓存不命中率为2%，数据缓存不命中率为4%，不命中代价为100周期。命中时，CPI为2，那么执行一段含有Load/Save指令各15%的程序时，其CPI为 。
【答】每条指令出现不命中的概率是 ，故其CPI为 。
9. 五段流水线CPU，各段延迟时间分别为2.2ns, 2.5ns, 2.2ns, 2.3ns, 2.3ns。连续执行10条指令，需要的时间为__，该CPU最高频率为____MHz。
【答】各段不等长的流水线计算公式参见教材58页（时空图如如3.8），需要的时间为
ns，最大周期为2.5ns，即频率为400MHz。
10. 采用预留算法实现的非线性流水线优化调度，其启动循环为(1,3)，则该流水线周期P为 ，调度后的禁止集 为 。
【答】周期 ， 。
11. 有一指令系统，共有7条指令。有两种类型，一种为寄存器－寄存器型，一种为寄存器－存储器型。指令字长为8位或16位，不同类型指令字长不同。要求变址范围－127到128。则该指令系统最多可以编址 个通用寄存器，这时，最多可以编址 个变址寄存器。
【答】考虑寄存器－寄存器型指令字长为8位，有3条指令，除去2位操作码，剩下各3位编址8个通用寄存器。寄存器－存储器型指令字长为16位，有4条指令，除去8位立即数，3位寄存器，4位操作码，剩下1位用来编址2个变址寄存器。（所给答案可能不是最优的，但是掌握这种指令的各个部分的长度如何计算的方法即可）
12. 在100次内存访问中，一级cache缺失10次，二级cache缺失5次。则一级cache的全局命中率为 ，二级cache的全局命中率为 。
【答】90%；95%。
13. 分别在以下条件时计算块地址0110的索引(index)，缓存有8块，主存有16块：
a) 二路组相联 ；
b) 直接映射 。
【答】二路组相联共8/2=4组，索引为2位。直接映射索引为3位。答案分别是10、110。
14. 缓存共有4块，每块1 byte，采用LRU策略。访问字序列0, 1, 4, 1, 0, 4在下列情况下的命中率分别是：
a) 直接映射 ；
b) 二路组相联 。
【答】直接映射
0 1 4 1 0 4
0 缺失(0) 缺失(4) 缺失(0) 缺失(4)
1 缺失(1) 命中
2
3
命中率为1/6。
二路组相联
0 1 4 1 0 4
0A 缺失(0) 命中
0B 缺失(4) 命中
1A 缺失(1) 命中
1B
命中率为1/2。

三、判断题：以下对MIPS架构CPU的各改进方案，哪些修改了系统结构（Architecture），哪些只修改了实现（Implementation）？填写A或者I。
(1) 将32位指令改为64位指令
(2) 加入指令Cache
(3) 增加流水线的段数
(4) 减去某些定向（forwarding）相关逻辑的实现
(5) 取消气泡
(6) 增加16个额外的通用寄存器
(7) 增加对某指令集的支持
【解】(1) A
(2) I
(3) I
(4) I
(5) I
(6) A
(7) A

四、解答题。
1. 设计了一种优化方案。
•优化后的时钟周期比未优化的快15%；
•未优化的取/存指令占总数的30%；
•优化后的取/存指令比未优化的少1/3，其它无变化；
•未优化的所有指令均用1个时钟周期；优化的取/存指令用2个时钟周期，其它指令用1个时钟周期。
（1）求优化方案的平均CPI；
（2）通过计算加速比，判断哪个方案速度更快？
【解】(1) 不妨设优化前共10条指令，取/存指令有3条。优化后的取/存指令减少了1条，即还有2条取/存指令，其他7条不变，则总指令数变为9条。
优化方案的平均CPI为 。
(2) 假设我们考虑这10条指令运行的总时间。以未优化的1个时钟周期作为单位1，优化前的运行时间为10，优化后的总时间为 ，说明优化后的更快。但是如果考虑平均每条指令的运行时间，那么优化前的更快（因为优化后平均每条指令的运行时间大于1）。

1. 在有32个处理机的并行机上运行一段程序，获得加速比26，已知该程序只有两种运行方式：在所有32个处理机上同时运行，或者只能由一个处理机执行。请问程序中只能由一个处理机执行的部分占多大比例？
   【解】设程序中只能由一个处理机执行的部分占 ，根据加速比定义有

2. 某指令系统，有三地址指令4条，单地址指令255条，零地址指令16条。其指令字长12位，地址码3位。请问扩展编码是否可行？如果单地址指令是254条呢？
   【解】（作业题）三地址指令共需要9位地址码，所以剩下3位编码操作码，用4个码点编码三地址指令，剩余4个用于扩展。单地址指令操作码有9位，可提供 个码点，用其中255个编码单地址指令，剩下1个用于扩展。这时零地址指令只有8个码点可用，所以扩展编码不可行。
   如果单地址指令是254条，那么还剩下2个用于扩展零地址指令，零地址指令自身的最低3位各可以编码8条指令，共计16条。因此可以实现扩展编码。

3. 指令字长16位，有双地址指令、单地址指令、零地址指令。地址都是6位。双地址指令15条。单地址与零地址条数相同。
   (1) 单地址与零地址指令最多能有多少条？
   (2) 给这三种指令分配操作码。
   【解】(1) 双地址指令地址码占12位，故操作码有4位，共16个码点，剩下1个码点作扩展。单地址指令的操作码最长10位，零地址指令最长16位。对于单地址指令来说，最多有 条，零地址指令也必须是63条。
   (2) 双地址指令：0000~1110；
   单地址指令：1111 000000~1111 111110；
   零地址指令：1111 111111 000000~1111 111111 111110。

4. 全相联Cache采用写直达策略。初始Cache为空。分别对按写分配和不按写分配两种策略，计算以下操作执行后的命中率。
   Write Mem[100]
   Write Mem[100]
   Read Mem[200]
   Write Mem[200]
   Write Mem[100]
   【解】（PPT上的题）按写分配：结果分别是缺失、命中、缺失、命中、命中，命中率为60%。
   不按写分配：结果分别是缺失、缺失、缺失、命中、缺失，命中率为20%。

5. Cache采用组相连映像及变换。主存1MB，Cache 32KB，块大小64B，Cache分为8组。
   (1) 写出主存地址和缓存地址的格式(写出各域及位数)；
   (2) 若Cache的访问周期为20ns，命中率0.95，要使加速比大于10，主存的访问周期应大于多少？
   【解】(1) Cache共有32KB/64B=512块，分为8路，共有512/8=64组。
   主存地址：标识8位，索引6位，块内地址6位。
   缓存地址：？。
   (2) 设主存访问周期为 ，则加速比 ns。

6. Cache有4块，每块4字，采用直接映像法。初始时Cache为空。访问的字地址序列为：0,7,12,9,16,8,17,0,12,2。求cache命中率。
   【解】访问过程如下：
   0 7 12 9 16 8 17 0 12 2
   0 Miss
   0~3 Miss
   16~19 Hit Miss
   0~3 Hit
   1 Miss
   4~7 Hit
   2 Miss
   8~11
   3 Miss
   12~15 Hit
   命中率为40%。

7. 一段程序有1000条指令，每条指令平均访问存储器1.5次，一级Cache访问需要1ns，二级Cache访问需要10ns，主存访问需要100ns。这段程序运行完后共访问二级Cache 90次，访问主存27次。
   (1) 求一级Cache和二级Cache命中率；
   (2) 求存储器等效访问时间；
   (3) 求每条指令因为访问存储器造成的平均延迟。
   【解】(1) 程序一共访存 次，一级Cache缺失了90次，故
   一级Cache（全局和局部）命中率为 ；
   二级Cache的局部命中率为 ；
   二级Cache的全局命中率为 。
   (2) 平均访存时间 ns。
   (3) 每条指令因为访问存储器造成的平均延迟为 ns。

8. 某系统Cache为4路组相联，Cache大小为16K字节，块大小为64字节。按写分配。对于如下代码：
   int M[4096], i, j;
   for (i = 0; i < 10; i++) {
   for (j = 0; j < 4096; j++) {
   M[j] = i + j;
   }
   }
   (1) 当i=0时，发生的Cache缺失是属于什么类型的缺失？发生了多少次？（4分）
   (2) 运行完这段代码，求整体缺失率。（4分）
   【解】(1) 4096长度的整型数组为16K字节，每个块为64字节，对应16个整数。当i=0时，对M各元素均是首次访问，属于必然缺失。发生 次。
   (2) 当i>0时，不再发生缺失。总访存次数为40960次，故整体缺失率为 。

9. 一个缓存，采用m路组相联，顺序访问一个元素大小和缓存块大小相等的数组，求数组长度N
   a) >m
   b)