计算机系统结构是由程序设计者所看到的一个计算机系统的属性，即概念性结构和功能性特性。
第1章 计算机系统结构的基本概念
概念
程序访问局部性：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇集。包括时间局部性和空间局部性。
透明性：在计算机技术中把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。
虚拟机与物理机：虚拟机是用软件实现的机器。物理机是相对于虚拟机而言的对实体计算机的称呼，物理机提供给虚拟机以硬件环境。
Amdahl定律：当对一个系统中的某个部件进行改进后，所获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。
用$f_e$（$f_e \leqslant 1$）表示系统可改进部分所占的比例，$r_e$（$r_e > 1$）表示被改进部分性能提高的倍数，则Amdahl定律可以表示为
CPI(Cycles Per Instruction)
用$i$代表第$i$类指令，$IC_i$代表第$i$类指令的数目，$CPI_i$代表执行每条$i$类指令所需的周期数，$IC$表示程序中的指令总数，上式也可以表示为
MIPS(Million Instructions Per Second)
CPU执行时间
例题
1. 某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：
| 指令类型 | 指令执行数量 | 平均时钟周期数 |
|---|---|---|
| 整数 | 45000 | 1 |
| 数据传送 | 75000 | 2 |
| 浮点 | 8000 | 4 |
| 分支 | 1500 | 2 |
求该计算机的有效CPI、MIPS和程序CPU执行时间。
解：
$CPI = (45000 \times 1 + 75000 \times 2 + 8000 \times 4 + 1500 \times 2) / (45000 + 75000 + 8000 + 1500) = 1.776$
$MIPS = (400 \times 10^6) / (CPI \times 10^6) = 225.225$
$CPU执行时间 = (45000 \times 1 + 75000 \times 2 + 8000 \times 4 + 1500 \times 2) / (400 \times 10^6) = 5.75 \times 10^{-4}s$
第2章 指令系统
概念
指令系统的指令编码方法：正交法、整体法、混合法。
CISC v.s. RISC：CISC指令系统庞大，执行速度低，编译程序复杂，指令使用频度低。
重叠寄存器窗口技术：寄存器窗口技术就是把整个寄存器组分成很多小组，每个过程分配一个寄存器小组，当发生过程调用时，自动地把CPU转换到不同的寄存器小组使用，不再需要做保存和恢复的操作，这个寄存器小组就叫寄存器窗口，相邻的寄存器窗口之间有部分是重叠的，便于调用参数传送。
DLX指令集结构：DLX指令中的操作可以分为4种类型，即Load和Store操作、ALU操作、分支和跳转操作、浮点操作。
问答
1. 标志符数据表示与描述符数据表示有何区别？描述符数据表示与向量数据表示对向量数据结构所提供的支持有什么不同？
答：
标志符数据表示与描述符数据表示的差别是，标志符与每个数据值相连，存在同一存储单元内，描述单个数据的类型特性；描述符与数据值分开存放，用于描述向量、数组等成块数据的特征。
描述符数据表示为向量、数组的实现提供了支持，有利于简化高级语言程序编译中的代码生成，可以比变址法更快地形成数据元素的地址。但描述符数据表示并不支持向量、数组数据结构的高效实现。而在有向量、数组数据表示的向量处理机上，硬件上设置有丰富的向量或阵列运算指令，配有流水或阵列方式处理的高速运算器，不仅能快速形成向量、数组的元素地址，更重要的是便于实现把向量各元素成块预取到中央处理机，用一条向量、数组指令流水同时对整个向量、数组高速处理，让硬件越界判断与元素运算并行。这些比起用与向量、阵列无关的机器语言和数据表示串行实现要高效的多。
2. 何谓指令格式的优化？简要列举包括操作码和地址码两部分的指令格式优化可采用的各种途径和思路。
答：
指令格式的优化指如何用最短位数表示指令的操作信息和地址信息，使程序中指令的平均字长最短。
操作码的优化：采用Huffman编码和扩展操作码编码。
对地址码的优化：采用多种寻址方式；采用$0$、$1$、$2$、$3$等多种地址制；在同种地址制内再采用多种地址形式，如寄存器-寄存器型、寄存器-主存型、主存-主存型等；在维持指令字在存储器内按整数边界存储的前提下，使用多种不同的指令字长度。
IEEE 754 标准
单精确度（$32$位），双精确度（$64$位），延伸单精确度（$> 43$位，少用），延伸双精确度（$> 79$位，通常为$80$位）。
$S$：符号位，$0$正$1$负；
$E$：指数位，为$2$的幂，在单精度中占$8$位，为表示指数为负的情况，再减去偏置$Bias = 2^{8 - 1} - 1 = 127$；
$M$：尾数位，$2$进制小数，小数点的右边部分，$f = (0.f_{n - 1}f_{n - 2} \dots f_1f_0)_2$，规定$M = 1 +f$。
例题
1. 经统计，某机器14条指令的使用频度分别为：0.01，0.15，0.12，0.03，0.02，0.04，0.02，0.04，0.01，0.13，0.15，0.14，0.11，0.03。分别求出用等长码、Huffman码和只有两种码长的扩展操作码这三种编码方式的操作码平均码长。
解：
$2^3 < 14 < 2^4$，所以等长码平均码长为$4$；Huffman编码的平均码长为$3.38$；只有两种码长的扩展操作码的平均码长为$3.4$。
只有两种码长的扩展操作码的平均码长：
$2^3 = 8, 2^2 = 4$；
从前$3$位的所有组合中拿出$1$个作为标识，共可产生$7 + 4 = 11$种编码；
从前$3$位的所有组合中拿出$2$个作为标识，共可产生$6 + 2 \times 4 = 14$种编码，符合题意；
只有两种码长的扩展操作码中，频度前$6$名的指令用$3$位表示，剩余指令用$3 + 2 = 5$位表示，平均码长为$0.8 \times 3 + 0.2 \times 5 = 3.4$。
2. 将下列IEEE单精度数由二进制数转换为十进制数。
(1)1 1000 0011 11 0000 0000 0000 0000 0000 0
解：
符号位$1$为负数
阶码真值$\ = 4$
尾数真值$\ = 1 + 0.75 = 1.75$
该浮点数的值$\ = -1.75 \times 2^4 = -28$
(2)0 0111 1110 10 1000 0000 0000 0000 0000 0
解：
符号位$0$为正数
阶码真值$\ = -1$
尾数真值$\ = 1 + 0.625 = 1.625$
该浮点数的值$\ = 1.625 \times 2^{-1} = 0.8125$
第3章 存储系统
什么是存储系统？对于一个由两个存储器$M_1$和$M_2$构成的存储系统，假设$M_1$的命中率为$h$，两个存储器的存储容量分别为$s_1$和$s_2$，存取时间分别为$t_1$和$t_2$，每千字节的成本分别为$c_1$和$c_2$。
两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件或软件与硬件相结合的方法连接起来成为存储系统。
(1) 在什么条件下，整个存储系统的每千字节平均成本会接近于$c_2$？
整个存储系统的每千字节平均成本为：
当$s_2 \gg s_1$时，上式的值约等于$c_2$，整个存储器系统的每千字节平均成本会接近于$c_2$。
(2) 该存储系统的等效存取时间$t_a$是多少？
(3) 假设两层存储器的速度比$r = t_2 / t_1$，并令$e = t_1 / t_a$为存储系统的访问效率，试以$r$和命中率$h$来表示访问效率$e$。
(4) 如果$r = 100$，为使访问效率$e > 0.95$，要求命中率$h$是多少？
将数值代入上式可得：$h > 99.95\%$。
(5) 对于(4)中的命中率实际上很难达到，假设实际的命中率只能达到0.96。现在采用一种缓冲技术来解决这个问题。当访问$M_1$不命中时，把包括被访问数据在内的一个数据块都从$M_2$取到$M_1$中，并假设被取到$M_1$中的每个数据平均可以被重复访问5次。请设计缓冲深度（即每次从$M_2$取到$M_1$中的数据块的大小）。
通过缓冲的方法，我们需要将命中率从$0.96$提高到$0.9995$。假设对存储器的访问次数为$5$，缓冲块的大小为$m$。那么，不命中率减小到原来的$1/5m$，列出等式有：
解这个方程得：$m = 16$，即要达到(4)中的访问效率，缓冲的深度应该至少是$16$（个数据单位）。
概念
多体交叉访问存储器：分为单体单字存储器，单体多字存储器，多体单字交叉存储器和多体多字交叉存储器。
并行访问存储器的冲突主要来自以下几个方面：取指令冲突，读操作数冲突，写数据冲突，读写冲突。
并行交叉访问存储器的结构：依据编址方式的不同，可分为高位交叉访问与低位交叉访问两种，其中低位交叉存储器能够有效地解决访问冲突问题。
cache的预取算法：通常可以分为恒预取和不命中时预取两种方法。
cache的一致性问题：全写法，也称直达法（write through, WT）即在对cache进行写操作的同时，也对主存该内容进行写入；写回法（write back, WB）指在CPU执行写操作时，只写入cache，不写入主存。
虚拟存储器的地址映像于变换：段式管理地址映像；页式管理地址映像；段页式管理地址映像。
cache与虚拟存储器的异同：出发点相同；原理相同；侧重点不同；数据通路不同；透明性不同；未命中时的损失不同。
存储器检错与纠错技术：奇偶校验，一维奇偶校验一次只采用单个校验位，奇校验保证每个字符的8位中1的总数为奇数，偶校验保证每个字符的8位中1的总数为偶数；二维奇偶校验可提高检错的性能，每一行和每一列分别产生一个奇偶校验位；海明校验，可自动纠错，$k$为信息位数，$r$为增加的冗余位位数，需满足$2r \geqslant k + r +1$；循环校验码（cycle redcndancy check, CRC）。
例题
1. 假设在一个采用组相联映象方式的Cache中，主存由B0～B7共8块组成，Cache有2组，每组2块，每块的大小为16个字节，采用LFU块替换算法。在一个程序执行过程中依次访问这个Cache的块地址流如下:
6，2，4，1，4，6，3，0，4，5，7，3
(1) 写出主存地址的格式，并标出各字段的长度。
(2) 写出Cache地址的格式，并标出各字段的长度。
(3) 画出主存与Cache之间各个块的映象对应关系。
(4) 如果Cache的各个块号为C0、C1、C2和C3，列出程序执行过程中Cache的块地址流情况。
(5) 采用LFU替换算法，计算Cache的块命中率。
解：
(1) 主存地址格式为：
| 1bit区号 | 1bit组号 | 1bit组内块号 | 4bit块内地址 |
|---|---|---|---|
(2) Cache地址的格式为：
| 1bit组号 | 1bit组内块号 | 4bit块内地址 |
|---|---|---|
(3)
主存的组到Cache的组之间是直接映象，对应组的块之间是全相联映象。即：主存块0、1、4、5只能装入Cache块0、1的任何块位置上，主存块2、3、6、7只能装入Cache块2、3的任何块位置上。
(4)
由于主存按Cache大小分区，因此去掉主存块地址中的区号就可以得出满足组相联映象关系的一种Cache块地址，所以该主存块地址流相应的一种Cache的块地址流为：
| 主 存 | B6 | B2 | B4 | B1 | B4 | B6 | B3 | B0 | B4 | B5 | B7 | B3 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 110 | 010 | 100 | 001 | 100 | 110 | 011 | 000 | 100 | 101 | 111 | 011 | |
| Cache | 10 | 10 | 00 | 01 | 00 | 10 | 11 | 00 | 00 | 01 | 11 | 11 |
| C2 | C2 | C0 | C1 | C0 | C2 | C3 | C0 | C0 | C1 | C3 | C3 |
(5) 采用LRU替换算法，Cache的块命中率为：$4 / 12 \approx 0.33$。
| 访问流 | B6 | B2 | B4 | B1 | B4 | B6 | B3 | B0 | B4 | B5 | B7 | B3 | 统计 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C0 | B4 | B4* | B4 | B4 | B4 | B4* | B4 | B4* | B4* | B4* | 命 | ||
| C1 | B1 | B1* | B1* | B1* | B0 | B0* | B5 | B5 | B5 | 中 | |||
| C2 | B6 | B6* | B6* | B6* | B6* | B6 | B6* | B6* | B6* | B6* | B7 | B7* | 4 |
| C3 | B2 | B2 | B2 | B2 | B2* | B3 | B3 | B3 | B3 | B3* | B3 | 次 | |
| 动作 | 调入 | 调入 | 调入 | 调入 | 命中 | 命中 | 调入 | 调入 | 命中 | 调入 | 调入 | 命中 |
2. 假设机器的时钟周期为10ns，Cache失效时的访存时间为20个时钟周期，Cache的访问时间为一个时钟周期。
(1) 设失效率为0.05，忽略写操作时的其它延迟，求机器的平均访存时间。
(2) 假设通过增加Cache容量一倍而使失效率降低到0.03，但使得Cache命中时的访问时间增加到了1.2时钟周期（即12ns），指出这样的改动设计是否合适？
(3) 如果时钟周期取决于Cache的访问时间(也就是用延长时钟周期的方法)，上述改动设计是否合适？
解：
(1) $T = H_cT_c + (1 - H_c)T_m = 0.95 \times 10 + 0.05 \times 20 \times 10 = 19.5ns$
(2) $T = H_cT_c + (1 - H_c)T_m = 0.97 \times 10 \times 1.2 + 0.05 \times 20 \times 10 = 17.64ns$，这种改动合适，使机器的平均访存时间降低。
(3) $T = H_cT_c + (1 - H_c)T_m = 0.97 \times 10 \times 1.2 + 0.03 \times 20 \times 10 \times 1.2 = 18.84ns$，合适。
3. 一个程序由5个虚页组成，采用LRU替换算法，在程序执行过程中依次访问的页地址流如下：
P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3
(1) 可能的最高页命中率是多少?
(2) 至少要分配给该程序多少个主存页面才能获得最高的命中率?
(3) 如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问存储单元的命中率。
解：
(1) 在分配的主存页面数目足够大的情况下，除了第一次调入不命中，以后的访问均命中，可以达到最高的页面命中率，即：实际命中的次数为7次，所以可能达到的最高页面命中率为：
(2) 由于在页面数大于等于5的情况下，肯定可以达到最高命中率，所以我们来看页面数小于5时能否达到该命中率：
若分配的主存页面数等于4时，调度过程如下：
| 访问流 | P4 | P5 | P3 | P2 | P5 | P1 | P3 | P2 | P3 | P5 | P1 | P3 | 统计 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LRU | 4 | 4 | 4 | 4* | 4* | 1 | 1 | 1 | 1 | 1* | 1 | 1 | 命 |
| 算 | 5 | 5 | 5 | 5 | 5 | 5 | 5* | 5* | 5 | 5 | 5 | 中 | |
| 法 | 3 | 3 | 3 | 3* | 3 | 3 | 3 | 3 | 3 | 3 | 7 | ||
| 2 | 2 | 2 | 2* | 2 | 2 | 2 | 2* | 2* | 次 | ||||
| 调入 | 调入 | 调入 | 调入 | 命中 | 调入 | 命中 | 命中 | 命中 | 命中 | 命中 | 命中 |
此时也可以达到最高命中率；
若分配的主存页面等于3时，调度过程如下：
| 访问流 | P4 | P5 | P3 | P2 | P5 | P1 | P3 | P2 | P3 | P5 | P1 | P3 | 统计 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LRU | 4 | 4 | 4* | 2 | 2 | 2* | 3 | 3* | 3 | 3 | 3* | 3 | 命中 |
| 算 | 5 | 5 | 5* | 5 | 5 | 5* | 2 | 2 | 2* | 1 | 1 | 3 | |
| 法 | 3 | 3 | 3* | 1 | 1 | 1 | 1* | 5 | 5 | 5 | 次 | ||
| 调入 | 调入 | 调入 | 调入 | 命中 | 调入 | 调入 | 调入 | 命中 | 调入 | 调入 | 命中 |
此时不能达到最高命中率。
所以至少应该分配4个主存页面。
(3) 我们假设程序每次只访问一个存储单元，这样，对每一个特定页面的访问过程可以描述如下：因为第一次总是不命中的，而平均起来，随后的1023次总是命中的，然后再次被调出主存，并再次重复先前的过程。所以访问存储单元的命中率为：
第4章 流水线系统
概念
指令的解释方式：一般分为顺序，重叠和流水三种。
流水线：把一个重复的时序过程分成若干个子过程，每个子过程都可以有效地在其专用功能段上和其他子过程同时执行的一种技术。
流水线按处理级别可分为三级：操作部件级，指令集和处理机级。
流水线按功能可分为：单功能流水线和多功能流水线。
流水线按工作方式可分为：静态流水线和动态流水线。
流水线按连接方式可分为：线性流水线和非线性流水线。
流水线调度方法：集中式动态调度和分布式动态调度。
例题
1. 若有一静态多功能流水线分为6段，如下图所示，其中乘法流水线由1、2、3、6段组成，加法流水线由1、4、5、6段组成。使用流水线时，要等某种功能（如加法）操作都处理完毕后才能转换成另一种功能（如乘法）。
若要计算：$A \times B = (a_1 + b_1) \times (a_2 + b_2) \times (a_3 + b_3)$
问：
(1) 在上述流水方式下，完成$A \times B$需多少时间？画出时空图并计算此流水线的使用效率和吞吐率。
(2) 与顺序运算方式相比，加速比为多少？
解：
(1)
完成$A \times B$需要的时间$= 19\tau$。
效率为：
吞吐率为：
加速比为：
2. 已知某单功能非线性流水线的预约表如下图，要求：
(1) 列出禁止表F和冲突向量C。
(2) 画出该流水线状态图，确定其最小平均延迟以及此时的调度方案？当按此流水调度方案共输入8个任务时，则其实际吞吐率为多少？
解：
(1) 禁止表$F = \{4\}$，冲突向量$C = (1000)$
(2)
各种调度方案及其相应的平均延迟：
最佳调度策略$(1, 1, 1, 5)$，吞吐率$= 8 / 17\Delta t$
3. 超级标量机和超级流水线机都能开发指令级的并行性，现假定这两种机器的流水线都为4段，每段均需1个时钟周期。若在超级标量机中，每个时钟周期可同时启动3条指令，而超级流水线机中则是每隔1/3时钟周期启动一条指令。现若要执行6条指令的代码序列，问在两种机器上各需用多少个时钟周期方可执行完毕？
解：
超级标量机需5个时钟周期，超级流水线机需5.67个时钟周期。
4. 在CRAY-1机上，V是向量寄存器，设向量长度均为32。S是标量寄存器，所用浮点功能执行部件的执行时间分别为：加法需6拍，相乘需7拍，从存储器读存数需6拍，求倒数近似值及除法需14拍，写入寄存器及启动功能部件（包括存储器）各需1拍。问下列各指令组中的哪些指令可以链接？哪些指令不可链接？哪些指令可以并行执行？试说明其原因并分别计算出各指令组全部完成所需的拍数。
（1）V0←存储器 （2）V2←V0+V1
V1←V2+V3 V3←存储器
V4←V5*V6 V4←V2*V3
（3）V0←存储器 （4）V0←存储器
V3←V1+V2 V1←1/V0
V4←V0*V3 V3←V1+V2
V6←V4+V5 V5←V3*V4
（5）V0←存储器 （6）V3←存储器
V1←V2+V3 V2←V0+V1
V4←V5*V6 S0←S2+S3
S0←S1+S2 V3←V1*V4
（7）V3←存储器 （8）V0←存储器
V2←V0+V1 V2←V0+V1
V4←V2*V3 V3←V1+V2
存储器←V4 V5←V3*V4
解：
(1) 三条指令可全并行执行，需(1 + 7 + 1) + (32 - 1) = 40拍
(2) 前两条并行，和第三条链接，需[(1 + 6 + 1) + (32 - 1)] + [(1 + 7 + 1) + (32 - 1)] = 79拍
(3) 前两条并行和第三条链接，而第四条指令与第三条指令串行（因第二条和第四条功能部件冲突），需[(1 + 6 + 1) + (1 + 7 + 1) + (32 - 1)] + [(1 + 6 + 1) + (32 - 1)] = 87拍
(4)全部链接，(1 + 6 + 1) + (1 + 14 + 1) + (1 + 6 + 1) + (1 + 7 + 1) + (32 - 1) = 72拍
(5)全并行执行，需(1 + 7 + 1) + (32 - 1) = 40拍
(6)前三条指令并行，与第四条指令串行（V1源操作数冲突），需[(1 + 6 + 1) + (32 - 1)] + [(1 + 7 + 1) + (32 - 1)] = 79拍
(7) 前两条指令并行，与第三条链接，再与第四条串行（因第一条和第四条冲突），需[(1 + 6 + 1) + (1 + 7 + 1) + (32 - 1)] + [(1 + 6 + 1) + (32 - 1)] = 87拍
(8) 前两条指令链接，与第三条串行（V1源操作数冲突），与第四条链接，需[(1 + 6 + 1) + (1 + 6 + 1) + (32 - 1)] + [(1 + 6 + 1) + (1 + 7 + 1) + (32 - 1)] = 95拍
第5章 并行处理和多处理机
概念
并行处理技术有三种形式：时间并行，空间并行，时间并行与空间并行组合。
并行处理技术发展：单机系统，多机系统，并行软件。
并行处理机结构：分布式存储器结构，集中式共享存储器组成的并行处理机结构。
多处理机结构：紧耦合多处理机系统，松耦合多处理机系统。
解决多处理机cache不一致的方法：监听cache协议法，基于cache目录的协议。
互连网络通信模式：单播模式，选播模式，广播模式，会议模式。
问答
1. 什么是多处理机的一致性？给出解决一致性的监听协议和目录协议的工作原理。
答：
(1) 对多个处理器维护一致性的协议称为Cache一致性协议。
(2) 目录协议的工作原理：采用一个集中的数据结构——目录。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。目录协议根据该项目中的信息以及当前要进行的访问操作，依次对相应的Cache发送控制消息，并完成对目录项信息的修改。此外，还要向请求处理器发送响应信息。
(3) 监听协议的工作原理：每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。
2. 机群系统有什么特点？
答：
(1) 系统开发周期短。由于机群系统大多采用商品化的PC机、工作站作为结点，并通过商用网络连接在一起，系统开发的重点在于通信子系统和并行编程环境上，这大大节省了研制时间。
(2) 可靠性高。机群中的每个结点都是独立的PC机或工作站，某个结点的失效并不会影响其它结点的正常工作，而且它的任务还可以传递给其它结点完成，从而有效地避免由于单结点失效引起的系统可靠性降低的问题。
(3) 可扩放性强。机群的计算能力随着结点数量的增加而增大。这主要是得益于机群结构的灵活性，由于结点之间以松耦合方式连接，机群的结点数量可以增加到成百上千。另外，机群系统的硬件容易扩充和替换，可以灵活配置。
(4) 性能价格比高。由于生产批量小，传统并行计算机系统的价格均比较昂贵，往往要几百万到上千万美元。而机群的结点和网络都是商品化的计算机产品，能够大批量生产，成本相对较低，因而机群系统的性能价格比更好。与相同性能的传统并行计算机系统相比，机群的价格要低1～2个数量级。
(5) 用户编程方便。机群系统中，程序的并行化只是在原有的C、C++或Fortran串行程序中插入相应的通信原语，对原有串行程序的改动有限。用户仍然使用熟悉的编程环境，无需适用新的环境。
例题
1. 设16个处理器的编号分别为0、1、…、15，用单级互连网络互连，若互连函数为：
(1) E(X)
(2) PM2+3，PM2-1
(3) Shuffle
(4) Butterfly
时，第9号处理器各与哪一个处理器相连？
解：
(1) E(1001) = 1000，所以第9号与第8号相连（最低位取反）;
(2) PM2+3(9) = 1，PM2-1(9) = 7分别与第1号，第7号相连；
(3) Shuffle(1001) = 0011，所以第9号与第3号相连（左移一位）;
(4) Butterfly(1001) = 1001，所以第9号与第9号相连（最高位和最低位互换）。
2. 在处理器N = 8的Omega网络中，若要实现处理器2与所有处理器相连，应怎样设置网络中交叉开关单元的状态？
解：
C上播，E、F下播，I、J、K、L上播。
3. 画出0 ~ 7号共8个处理器的三级混洗交换网络，在该图上实现将6号处理器数据播送给0 ~ 4号，同时将3号处理器数据播送给其余3个处理器时的各有关交换开关的控制状态。
解：
4. 试在含一个PE的SISD机和在含n个PE且连接成一线性环的SIMD机上计算下列求内积的表达式：其中$n = 2^k$。
假设完成每次ADD操作需要2个单元时间，完成每次MULTIPLY操作需要4个单位时间，沿双向环在相邻PE间移数需1个单位时间，
(1) SISD计算机上计算s需要多少时间？
(2) SIMD计算机上计算s需要多少时间？
(3) SIMD机计算s相对于SISD计算的加速比是多少？
解：
(1) 在SISD计算机中计算s需要串行计算$n$次乘法和$n - 1$次加法，共需要时间$4 \times n + 2 \times (n - 1) = 6n – 2$
(2) $s = 3 + 2k + n$
(3) $(6n - 2) / (3 + 2k +n)$
5. 设a为一个计算机系统中n台处理机可以同时执行的程序代码的百分比，其余代码必须用单处理机顺序执行。每台处理机的执行效率为xMIPS，并假设所有处理机的处理能力相同。那么当n = 16，x = 4MIPS的情况下，a为多少的时候系统的性能能够达到40MIPS?（ D ）
A. 0.84 B. 0.88 C. 0.92 D. 0.96
6. 假设一台4处理机带有共享存储器的计算机来执行一个混和程序，此多处理机有4种运行方式。与1，2，3，4四台处理机处于活动状态相对应。设$f_i$为i台处理机用于执行上述程序的时间百分数。已知：$f_1 = 0.4$，$f_2 = 0.3$，$f_3 = 0.2$，$f_4 = 0.1$；R1 = 4MIPS，R2 = 8MIPS，R3 ＝ 11MIPS，R4 = 15MIPS，试问上述混合程序的调和均值执行时间T为多少（ D ）
A. 0.25MIPS B. 0.375MIPS C. 0.5MIPS D. 以上都不对
第6章 输入输出系统
概念
中断：在程序运行时，系统外部、内部或现行程序本身若出现紧急事件，处理器必须立即强行终止现行程序的运行，改变机群的工作状态并启动相应的程序处理这些事件，然后再恢复原来程序的运行，这一过程称为中断。
MDA传送方式：外设通过DMA的一种专门接口电路——DMA控制器（DMAC），向CPU提出接管总线控制权的总线请求，CPU收到该信号后，在当前的总线周期结束后，会按DMA信号的优先级和提出DMA请求的先后顺序响应DMA信号。
I/O接口：I/O接口是主机与被控对象进行信息交换的纽带，主机通过I/O接口与外部设备进行数据交换。
字节多路通道：用于连接多台慢速外设，采用交叉传送数据的方式。一个通道可以连接多台外设，而且使其都处于工作状态。
选择通道：选择通道指每一个通道连接一台高速外设，也可以连接多台相同的高速外设，但通道只能对各台外设串行服务。
数组多路通道：数组多路通道是字节多路通道与选择通道工作方式的综合，是在数组传送的基础上，再分时为多个高速外设服务。
问答
1. 说明并比较程序查询方式、程序中断方式和DMA方式的CPU工作效率。
答：
程序查询方式仅适用于外围设备的数目不多，对I/O处理的实时要求不高，CPU的操作任务单一、不忙的情况。中断输入输出方式一般也用于连接低速外围设备，但CPU能与外围设备并行工作，并能处理例外事件。直接存储器访问方式主要用来连接高速外围设备。
例题
1. 一个字节多路通道连接$D_1$、$D_2$、$D_3$、$D_4$、$D_5$共5台设备，它们的数据传输率如下表所示：
| 设备名称 | $D_1$ | $D_2$ | $D_3$ | $D_4$ | $D_5$ |
|---|---|---|---|---|---|
| 数据传输速率（KB/s） | 100 | 33.3 | 33.3 | 20 | 10 |
| 服务优先级 | 1（最高） | 2 | 3 | 4 | 5 |
(1) 计算这个通道的实际流量。
(2) 为了使通道能够正常工作，请设计通道的最大流量和工作周期。
(3) 如果这个字节多路通道的最大流量正好等于通道实际流量，并假设数据传输率高的设备，其优先级也高。5台设备在0时刻同时向通道发出第一次传送数据的请求，并在以后的时间里按照各自的数据传输率连续工作。画出通道分时为各台设备服务的时间图，并计算处理完各设备的第一次请求的时刻。
解：
(1) 通道实际容量为：100 + 33.3 + 33.3 + 20 + 10 = 196.6KB/s
(2) 取流量上限为200KB/s，则工作周期为5μs。
(3) 通道分时工作的时间关系如下图所示。通道处理完各设备第一次数据服务请求的时刻分别为5μs、10μs、20μs、30μs、90μs。
2. 通道型I/O系统由一个字节多路通道A(其中包括两个子通道A1和A2)，两个数组多路通道B1和B2及一个选择通道C构成，各通道所接设备和设备的数据传送速率如表所示（见课本）。
(1) 分别求出各通道应具有多大设计流量才不会丢失信息。
(2) 设I/O系统流量占主存流量的1/2时才算流量平衡，则主存流量应达到多少?
解：
(1) 子通道A1的最大实际流量 = 50 + 35 + 20 + 20 + 50 + 35 + 20 + 20 = 250KB/S = 0.25MB/S，子通道A1至少应有0.25MB/S的流量才不丢失信息。
(2) 此I/O系统的流量应为各子通道流量之和，即为0.25 + 0.25 + 0.5 + 0.5 + 0.5 = 2MB/S，依题意I/O系统流量占主存流量的1/2才算流量平衡，因此主存流量应达到4MB/S。