计算机体系结构-东北大学乔百友chap-7.pptVIP

有限目录 有限目录的每个目录项只用一定数量的指针，而不管系统的大小如何。这减少了Cache目录对存储空间的要求，因而当存储器数据块共享比较少时更加经济。但如果有大量的处理机Cache共享相同的数据，那么它有可能降低Cache/主存的更新速度。 有限目录协议的状态与全映射目录协议十分相似，但目录项中的指针(处理机位)实际上是处理机的地址编码，若共有N台处理机，则目录项中指针部分为log2N位，每个目录项中指针的个数远远小于处理机的台数N。正因为如此，当多于允许数目的Cache同时要求某一个数据块的拷贝的时候，就必须进行指针的替换。这种指针替换过程称为驱逐(eviction)。由于多处理机系统中的处理机具有局部性（即在任何给定的时间间隔内，只有一小部分的处理机访问某个给定的存储器数据），所以有限目录足以应付这个小的处理机组了。 如图7.19所示，假设多处理机系统中共有3台处理机，目录项中只有2个指针，存储单元x所在的数据块对应的目录项中2个指针分别指向处理机P1和P2，即在P1和P2的Cache中都有单元x所在的数据块的拷贝。当P3请求访问单元x时，需将单元x在共享存储器中的数据块调入Cache3，同时采用某种替换算法修改目录项中的指针部分。在图7.19中假设替换的是指向处理机P2的指针。在这里，任一时刻最多只能有2台处理机的Cache共享一个数据块。 由于和存储器中数据块有关的目录项大小同log2N成正比，所以目录所花费的存储器容量就同存储器大小O(N)和目录项大小O(log2N)的乘积O(Nlog2N)成正比。 (3)多级立方体网络? 多级立方体网络由n级相同的网络组成，每一级都包含一个Cubei拓扑和随后一列2n-1个二功能交换单元。8个处理单元的多级立方体互连网络的拓扑结构如图5.28所示。 常见的多级立方体网络有STARAN网络和间接二进制n方体网络。两者的相同点是当第i级（0≤i≤n-1）交换单元处于交换状态时，实现的是Cubei互连函数，且都采用二功能交换单元；不同之处在于各级交换开关采用的控制方式，STARAN采用级控制（称交换网络）或部分级控制（称移数网络）；而间接二进制n方体网络采用单元控制。 当STARAN网络用作交换网络时，采用级控制，每级的所有2n-1个二功能交换开关用同一个控制信号控制。当第i级的级控制信号为0时，这一级的所有二功能交换开关都完成直连功能，当第i级的级控制信号为1时，这一级的所有二功能交换开关都完成Cubei交换函数的功能。当处理单元个数N=8时，STARAN交换网络共设计为3级(log2N=3)，共需要3个级控制信号，级控制信号的组合及所实现的功能如表5.2所示。 从表5.2可以看出，当级控制信号为K2K1K0=001时，由于第0级的级控制信号K0=1，其它级控制信号都为0，所以所有处理单元执行的交换函数的功能是Cube0 。同样的道理，当级控制信号为K2K1K0=011时，所有处理单元执行的交换函数的功能是Cube0 + Cube1 。 当级控制信号K2K1K0=011时的各级交换开关状态如图5.29所示。由图5.29中各处理单元的连接同样可以看出，当级控制信号为K2K1K0=011时，所有处理单元执行的交换函数的功能是Cube0 + Cube1 ，即二进制编码为P2P1P0的处理单元连往二进制编码为P2P1P0的处理单元。在图5.29中给出了当级控制信号为K2K1K0=011时，0号处理单元到3号处理单元的路由选择过程。 在表5.2中，当级控制信号为K2K1K0=101时，所有处理单元执行的交换函数的功能是4组2元+2组4元+1组8元，意思是对于入端的8个处理单元与出端的8个处理单元的连接在排列上表现为先将8个处理单元的排列分成4组，每组2元交换，然后再将当前的排列分成2组，每组4元交换，最后再将当前新的排列分成1组，每组8元交换，如下所示： 入端排列： 0 1 2 3 4 5 6 7 分成4组： | 0 1 | 2 3 | 4 5 | 6 7 | 每组2元交换：| 1 0 | 3 2 | 5 4 | 7 6 | 分成2组： | 1 0 3 2 | 5 4 7 6 | 每组4元交换：| 2 3 0 1 | 6 7 4 5 | 分成1组： | 2 3 0 1 6 7 4 5 | 每组8元交换： 5 4