6章作业解析.ppt

1、第4、6章作业解析,第6章作业 6.3 8*8矩阵每个元素可表示为aij，其中i、j为行列下标，分别用3位二进制数表示。 aij存放位置的计算：i*8+j即为数组内偏移量，即i作为高3位，j作为低3位拼接在一起形成的二进制数，简单记作（ij）。 矩阵转置对应的操作： aij的初始存放位置位于（ij），需要把它转移到内存位置（ji）。 二进制地址的变换：6位地址循环左移3位。,分析：对于已存在的互连网络中，可以实现地址移位的是均匀洗牌网络，该网络把源地址循环左移1位得到目的地址。 结论：使用单级的均匀洗牌网络可以实现矩阵的转置变换，但是需要3次数据传送过程，因为对8*8矩阵进行转置需要将原始地址

2、循环左移3位。 限制条件：需要并行存储结构或者交叉编址的存储结构，64个内存单元分别位于不同的存储体中，即便不是全部都在不同的存储体，也至少需要保证数据传输时不会出现错误，能够并行的进行读写。,6.4 对于题目中给出的互连关系，观察其规律： （B，1）=（1011，0001） 1101的第3和第1位取反，得到0001 （8，2）=（1000，0010） 1000的第3和第1位取反，得到0010 观察题目所给的所有互连关系，可以得到统一的地址变换规则：源地址的第1、3位取反得到目的地址。,分析：源地址中某一位取反得到目的地址，这是方体置换的规则，可以考虑使用方体置换来实现题目中给出的互连关系。

3、由于是第1、3位都需要取反，所以必须经过2次方体置换，即Cube1和Cube3置换的重叠置换。 在以存在的互连网络结构中，可以实现多个方体置换重叠的是STARAN网络，而且它的各级开关必须工作在级控制方式下。 目前需要实现的是16*16的STARAN网络，如果仍然使用2*2开关，则开关级数为log216=4，需要4个级控制信号，表示为： f3 f2 f1 f0。,基于STARAN网络级控制方式下，级控制信号与方体置换的对应关系：P197的式（6-21）和P198的第一段文字，可得如下规律： 第i级开关的控制信号fi=1时，实现Cubei置换，如果有多级控制信号同时为1，则实现多个方体置换的重叠

4、置换。 由此可得本题中16*16 STARAN网络的级控制信号：1010，f3和f1为1，实现Cube3和Cube1的重叠置换。,6.5 网络中的开关是按单元控制的，根据网络的控制特征，任意一个数据传输所使用的开关控制信号依次为终端编号（目标地址）二进制表示形式由高到低的数据位。 在本题中，控制信号为1100，则无论源地址为什么，最终数据都会被导向目标地址1100，即第12号结点。 结论：第8号结点是与第12号结点相连的。,6.6 网络规模分析：本题没有给出网络规模，只能通过网络的构建规则反推。 设网络规模为N，开关级数为n，使用k*k的开关，则在网络中有如下关系： n=logkN 本题中规定

5、开关级数为2，使用4*4开关，即n=2，k=4，则可反推网络规模： N=42=16，即一个16*16的网络。,每级开关个数分析： 网络的网络规模为N，如果使用k*k开关，则每级开关个数为： N / K 在本题中为16 / 4 = 4，每级共有4个开关。,固定置换分析：如果有n级开关，则从网络的输入端到输出端共有n+1级固定置换，其中最后一级固定为恒等置换。 本题中有2级开关，除去输出端那一级恒等置换外，前面还有2级4位的均匀洗牌置换。,对于采用2*2开关的网络，固定的均匀洗牌置换满足的条件：如果把开关全部设为“直通”状态，则网络实现恒等置换。 在使用4*4开关的网络中，该条件是不能满足的，因为

6、对于一个4位的二进制地址，经过2次均匀洗牌（循环左移2位）是不能实现地址还原的。 如果要实现恒等置换，则需要两次通过该网络才能实现。,6.7 这里以8*8的网络为例进行分析。 蝶式置换的原理：源地址的最高位与最低位交换。 源地址与目标地址的对应关系如下： 000000 001100 010010 011110 100001 101101 110011 111111,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,结论分析：在网络中采用终端标记法可以实现蝶式置换，但是在一次通过中会产生资源冲突，需要组织为二次通过。

7、黄线对应的传输过程组织为一个通信编队，红线对应的传输过程组织为另一个通信编队，两个编队可以顺序执行，也可以组织为流水线的方式通过网络。 开关状态：开关状态需要分为两次列出，每一次数据传输开关状态是不同的。,6.8 （1）按照教材中对网络的定义，S表示二进制的源地址，D表示二进制的目标地址。 在每个开关有两个控制信号时，使用D的每个数据位作为一个输入信号的“上传”或“下传”控制。 如果规定2*2开关只能使用“直通”和“交叉”两种工作模式，则每个开关仅需要一个控制信号，该信号为“0”时代表直通，为“1”时代表交叉。,考虑任意一个源接点的编号S： 如果其最高位为0，则经过一次均匀洗牌后，该位变为最低

8、位，与某一个开关的上端输入连接。 如果其最高位为1，则经过一次均匀洗牌后，该位变为最低位，与某一个开关的下端输入连接。,现在考虑该源结点对应的目标结点地址D： 如果D的最高位为0，表示S对应的第一级开关应该将S的输入上传。 如果D的最高位为1，表示S对应的第一级开关应该将S的输入下传。 下面综合分析S和D最高位的对应情况：,1）S最高位为0，D最高位为0： S的输入连接在第一级某个开关的上输入端，D要求该开关对S的输入上传。 则采用“直通”方式可以完成。 2） S最高位为0，D最高位为1： S的输入连接在第一级某个开关的上输入端，D要求该开关对S的输入下传。 则采用“交叉”方式可以完成。,3）

9、 S最高位为1，D最高位为0： 同理可知，采用“交叉”方式。 4） S最高位为1，D最高位为1： 同理可知，采用“直通”方式。 上面证明了针对S和D的最高位，使用异或运算可以得到正确的控制信号。,考虑某第i级的任意一个开关针对当前输入所作的操作对当前编号Si的影响： 当前编号Si的含义：不再等于S，是经过了n-i级均匀洗牌和n-i-1级开关处理后的编号。 第i级当前开关“直通”：不改变当前编号。 第i级当前开关“交叉”：将当前编号的最低位取反。,当前编号Si的最低位是如何得来的？ 是第n-i次均匀洗牌前的最高位，它已经参加了对第n-i级当前开关控制信号的演算，以后不会再使用它。 对第n-i-1

10、级开关而言，S的当前输入应该连接在某个开关的上端还是下端，由S的第i+1位来决定，为0则连接上端，为1则连接下端。 与第n-1级类似，第n-i-1级开关应该直通还是交叉，由S和D第i+1位的异或结果决定。 由此，可以使用递推方法证明，SD ，异或结果为每一级开关对应的控制信号。,（2）广播连接算法 设源结点为S，它需要和每一个目标结点进行广播通信，则产生开关控制信号的算法思想如下： BroadCast(int S, int i) ;S为当前源结点编号 ;i为级数 if( i != 0) int S0 = S; BroadCast(S0, i-1); 对编号S0对应的开关产生上播或下播控制信号；

11、 int S1 = S最低位取反的结果; BroadCast(S1,i-1); 对编号S1对应的开关产生上播或下播控制信号； else 对编号S对应的开关产生上播或下播控制信号； ,补充题目分析： 网络 （1）画出由2*2开关构成的16个输入输出端的Omega网络。 （2）结点1011传送消息给结点0101，同时结点0111传送消息给结点1001，画出完成这一寻径的开关设置。这种情况会阻塞吗？,分析： 网络规模N=16，采用2*2开关，则k=2，开关级数为： n=logkN=log216=4 每级开关个数为 N / k =16 / 2 = 8 前面4级固定连接采用均匀洗牌置换，最后一级为恒等置

12、换。,1011,0101,0111,1001,第4章作业 4.8和4.12答案有误。 LRU算法与LFU算法的本质和区别。 本质：LRU算法与LFU算法都是属于替换算法，特别注意替换算法所针对的对象。 例如，LRU算法用于Cache-主存结构时，针对的对象是Cache块；用于主存-磁盘结构时，针对的对象是内存块。,区别： 假设用于Cache-主存结构。 LRU：least recently used，淘汰最近最少使用的Cache块，把它写回主存，并把主存中新的页面替换进来。 LFU：least frequently used，相对于当前时刻而言，淘汰最早使用过的Cache块。 （注意，替换时要受地址转换机制的限制）,对于LFU算法而言，“最近”或“近期”的含义是清楚的，如果一共有n个Cache块，则“近期”就是指最近的n次Cache访问，最早使用的那个Cache块被优先考虑淘汰。 对于LRU算法而言，“近期”的含义是模糊的，可以是任意一个设定的时间片段或Cache访问次数。 例如，假设一共有8个Cache块，LRU算法设定的近期为1分钟，在这1分钟内块A被使