第二个问题操作系统可以保证I/O操作的数据不在cache中。如果不能，就作废Cache中相应的数据。
6.11 假设在一个计算机系统中：
（1） 每页为32KB，Cache块大小为128字节；
（2） 对应新页的地址不在Cache中，CPU不访问新页中的任何数据； （3） Cache中95%的被替换块将再次被读取，并引起一次失效； （4） Cache使用写回方法，平均60%的块被修改过； （5） I/O系统缓冲能够存储一个完整的Cache块； （6） 访问或失效在所有Cache块中均匀分布；
（7） 在CPU和I/O之间，没有其它访问Cache的干扰； （8） 无I/O时，每100万个时钟周期内有18000次失效；
（9） 失效开销是40个时钟周期。如果被替换的块被修改过，则再加上30个周期用
于写回主存；
（10） 假设计算机平均每200万个周期处理一页。 试分析I/O对于性能的影响有多大？ 解：每个主存页有32K/128＝256块。
因为是按块传输，所以I/O传输本身并不引起Cache失效。但是它可能要替换Cache中的有效块。如果这些被替换块中有60％是被修改过的，将需要（256×60％）×30＝4608个时钟周期将这些被修改过的块写回主存。
这些被替换出去的块中，有95％的后继需要访问，从而产生95％×256＝244次失效，将再次发生替换。由于这次被替换的244块中数据是从I/O直接写入Cache的，因此所有块都为被修改块，需要写回主存（因为CPU不会直接访问从I/O来的新页中的数据，所以它们不会立即从主存中调入Cache），需要时间是244×（40＋30）＝17080个时钟周期。
没有I/O时，每一页平均使用200万个时钟周期，Cache失效36000次，其中60％被修改过，所需的处理时间为：
（36000×40％）×40＋（36000×60％）×（40＋30）＝2088000（时钟周期）
时钟I/O造成的额外性能损失比例为
（4608＋17080）÷（2000000＋2088000）＝0.53％ 即大约产生0.53％的性能损失。
第7章 互连网络
7.1 解释以下术语 线路交换：在线路交换中，源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。
分组交换：把信息分割成许多组（又称为包），将它们分别送入互连网络。这些数据包可以通过不同的路径传送，到目的结点后再拼合出原来的数据，结点之间不存在固定连接的物理通路。
静态互连网络：各结点之间有固定的连接通路、且在运行中不能改变的网络。
动态互连网络：由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。 互连网络：一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。在拓扑上，互连网络是输入结点到输出结点之间的一组互连或映象。
互连函数：用变量x表示输入，用函数f(x)表示输出。则f(x)表示：在互连函数f的作用下，
输入端x连接到输出端f(x)。它反映了网络输入端数组和输出端数组之间对应的置换关系或排列关系，所以互连函数有时也称为置换函数或排列函数。 网络直径：指互连网络中任意两个结点之间距离的最大值。 结点度：指互连网络中结点所连接的边数（通道数）。
等分带宽：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。
对称网络：从任意结点来看，网络的结构都是相同的。
7.2 试比较可用于动态互连的总线、交叉开关和多级互连网络的硬件复杂度和带宽。 答：总线互连的复杂性最低，成本也是最低。其缺点是每台处理机可用的带宽较窄。 交叉开关是最昂贵的，因为其硬件复杂性以n2上升，所以其成本最高。但是交叉开关的带宽和寻径性能最好。当网络的规模较小时，它是一种理想的选择。
多级互连网络的复杂度和带宽介于总线和交叉开关之间，是一种折中方案。其主要优点是采用模块化结构，可扩展性较好。不过，其时延随网络级数的增加而上升。另外，由于其硬件复杂度比总线高很多，其成本也不低。
7.3 设E为交换函数，S为均匀洗牌函数，B为蝶式函数，PM2I为移数函数，函数的自变量是十进制数表示的处理机编号。现有32台处理机，其编号为0，1，2，…，31。
（1）分别计算下列互连函数
E2（12） S（8） B（9） PM2I+3（28） E0（S（4）） S（E0（18））
（2）用E0和S构成均匀洗牌交换网（每步只能使用E0和S一次），网络直径是多少？从5号处理机发送数据到7号处理机，最短路径要经过几步？请列出经过的处理机编号。
（3）采用移数网络构成互连网，网络直径是多少？结点度是多少？与2号处理机距离最远的是几号处理机？
解：（1）共有32个处理机，表示处理机号的二进制地址应为5位。
E2（12）＝E2（01100）＝01000（8） S（8）＝S（01000）＝10000（16） B（9）＝B（01001）＝11000（24） PM2I+3（28）＝28＋23 mod32 ＝4 E0（S（4））＝E0（S（00100））＝01001（9） S（E0（18））＝S（E0（10010））＝S（10011）＝00111（7）
（2）2n个结点的均匀洗牌交换网的网络直径为2n-1，32个结点的均匀洗牌交换网的网络直径为9。
从5号处理机发送数据到7号处理机，最短路径要经过6步：
00101→00100→01000→01001→10010→10011→00111
（3）网络直径是3，结点度是9，与2号处理机距离最远的是13、15、21、23号处理机。
7.7 具有N=2n 个输入端的Omega网络，采用单元控制。 （1）N个输入总共应有多少种不同的排列？
（2）该Omega网络通过一次可以实现的置换总共可有多少种是不同的？ （3）若N=8，计算一次通过能实现的置换数占全部排列的百分比。
解：（1）N个输入的不同排列数为N！。
（2）N个输入端、输出端的Omega网络有n＝log2N级开关级，每级开关级有N/2个2×2的4功能开关，总共有（N/2）log2N个开关。置换连接是指网络的输入端与输出端的一对一连接，故只考虑2×2开关的2个功能状态，即直送与交叉。网络采用单元控制，因此，每个开关都根据连接要求处于2个功能状态中的一种状态，所以，由（N/2）log2N个开关
组成的Omega网络的开关状态的种树为：
（N/2）log2N2?NN/2
一种网络开关状态实现Omega网络的一种无冲突的置换连接，所以，一次使用Omega网络可以实现的无冲突的置换连接有NN/2种。
（3）若N=8，则一次通过能实现的置换数占全部排列的百分比为： NN/2844096???10.16% N!8!403207.8 用一个N=8的三级Omega网络连接8个处理机（P0~P7），8个处理机的输出端分别依序连接Omega网络的8个输入端0~7，8个处理机的输入端分别依序连接Omega网络的8个输出端0~7。如果处理机P6要把数据播送给处理机P0~P4，处理机P3要把数据播送给处理机P5~P7，那么，Omega网络能否同时为它们的播送要求实现连接？画出实现播送的Omega网络的开关状态图。
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 解：Omega网络使用的2×2开关有4种状态：直送、交叉、上播、下播。置换连接只使用直送和交叉状态，播送连接还需要使用上播和下播状态。分别画出实现处理机P6和P3的播送连接要求使用的开关状态，如果没有开关状态和开关输出端争用冲突，就可以使用播送连接。实际上，它们的播送要求没有冲突，因此，可以同时实现，同时实现的Omega网络开关状态图如下所示。
7.9试证明多级Omega网络采用不同大小构造块构造时所具有的下列特性： （1） 一个k×k开关模块的合法状态（连接）数目等于kk。
（2） 试计算用2×2开关模块构造的64个输入端的Omega网络一次通过所能实现置
换的百分比。
（3） 采用8×8开关模块构造64个输入端的Omega网络，重复（2）。
（4） 采用8×8开关模块构造512个输入端的Omega网络，重复（2）。 解：（1）一个k×k开关的合法状态或合法连接有：① 一个输入端连接一个输出端，即一对一的置换连接；② 一个输入端连接多个或全部输出端，即一对多的选播连接或一对全体的广播连接。
两个或两个以上的输入端连接一个输出端是非法连接。因此，某个输出端可被连接到任意一个输入端的连接有k种，无论这个输出端是被置换连接还是被播送连接。
k个输出端被连接到输入端的合法连接的数量为：
k×k×…×k＝kk k个 （2）用k×k开关模块构造N个输入端的Omega网络时，开关级数为n＝logkN，每级
开关模块数为N/k，网络的开关模块总数为（N/k）logkN。
一个k×k开关一对一连接的合法状态只有k种，所有开关都是一对一连接的合法状态才能实现一种一次使用网络的无冲突置换连接。因此，由（N/k）logkN个k×k开关组成的Omega网络一次使用的无冲突置换连接函数为：
kNlogkNk?(klogkNN)k?NNk
网络可以实现的置换连接数即为N个输出端的不同排序的排序数，即为N！，所以，Omega网使用一次实现的无冲突置换连接数占可以实现的置换连接数的比例为：
NNk/N!
若采用2×2开关模块构造的64个输入端的Omega网络，即有k=2，N=64，则Omega网使用一次实现置换连接的比例为：
6432?4.95?10-32 64！（3）若采用8×8开关模块构造64个输入端的Omega网络，即有k=8，N=64，则Omega
网使用一次实现置换连接的比例为：
648?3.85?10-16 64！（4）若采用8×8开关模块构造512个输入端的Omega网络，即有k=8，N=512，则
Omega网使用一次实现置换连接的比例为：
51264/512！