计算机体系结构第三章练习题参考解答

第三章3.26设16个处理器编号分别为0，1，…，15，要用单级互连网络，当互连函数分别为：（1）Cube3（Cube1）（5）Butterfly（Butterfly）（8）1（9）(1)（13）(2)时，第13号处理器分别与哪一个处理器相连?解：（1）因为Cube3（Cube1(X3X2X1X0)）=Cube3(X3X2X1X0)=X3X2X1X0所以13→Cube3（Cube1(1101)）=0100→4（5）因为Butterfly（Butterfly(X3X2X1X0)）=Butterfly（X0X2X1X3）=X3X2X1X0所以13→Butterfly（Butterfly(1101)）=1101→13（8）因为1(X3X2X1X0)=X0X3X2X1所以13→1(1101)=1110→14（9）因为(1)(X3X2X1X0)=X3X2X0X1所以13→(1)(1101)=1110→14（13）因为(1)(X3X2X1X0)=X1X2X3X0所以13→(2)(1101)=0111→73.30在有16个处理器的均匀洗牌网络中，若要使第0号处理器与第15号处理器相连，需要经过多少次均匀洗牌和交换置换。解：0（0000B）号处理器与15（1111B）号处理器相连要对四位取反。交换置换一次只能对一位取反，所以要四次交换置换。交换置换每次取反只对最低位，要有三次移位，所以要四次均匀洗牌置换。即变换为0000(E)→0001(σ)→0010(E)→0011(σ)→0110(E)→0111(σ)→1110(E)→1111。3.34在编号分别为0，1，2，……，9的16个处理器之间，要求按下列配对通信：(B、1)，(8、2)，(7、D)，(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。试选择所用互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级的交换开关状态图。解：16个处理机通过N=16的互连网络互联，通信配对连接的二进制编号为：(0、A)：0000---1010(8、2)：1000---0010(1、B)：0001---1011(9、3)：1001---0011(2、8)：0010---1000(A、0)：1010---0000(3、9)：0011---1001(B、1)：1011---0001(4、E)：0100---1110(C、6)：1100---0110(5、F)：0101---1111(D、7)：1101---0111(6、C)：0110---1100(E、4)：1110---0100(7、D)：0111---1101(F、5)：1111---0101显然要求互连网络实现的互联函数为f（X3X2X1X0）=X3X2X1X0，为多重方体置换。N=16的STARAN网络在级控方式下实现的是方体置换，且当级控信号为F=f3f2f1f0=1010时，实现的互联函数是Cube3（Cube1（X3X2X1X0））=X3X2X1X0。所以采用N=16的STARAN网络在级控方式且级控信号F=1010时，可实现要求配对通信。3.41写出N=8的蝶式置换的互连函数，如采用Omega网络，则需几次通过才能完成此变换？画出Omega网络实现此变换的控制状态图。解：（1）N=8的蝶式置换的互连函数为：β（X2X1X0）=X0X1X2（2）根据Omega网络采用单元控制终端标记法寻径方法，蝶式交换的连接关系及用N=8的Omega网络实现该连接的开关要求如下表所示。SDd2d1d0K2级开关K1级开关K0级开关00000与K21上输出端连接与K11上输出端连接与K01上输出端连接14100与K22下输出端连接与K14上输出端连接与K03上输出端连接22010与K23上输出端连接与K11下输出端连接与K02上输出端连接36110与K24下输出端连接与K14下输出端连接与K04上输出端连接41001与K21上输出端连接与K11上输出端连接与K01下输出端连接55101与K22下输出端连接与K14上输出端连接与K03下输出端连接63011与K23上输出端连接与K11下输出端连接与K02下输出端连接77111与K24下输出端连接与K14下输出端连接与K04下输出端连接由表可见，当实现八个结点对连接时，对K2级开关的要求将发生下列争用开关输出端的冲突：0→0和4→1争用开关K21上输出端1→4和5→5争用开关K22下输出端2→2和6→3争用开关K23上输出端3→6和7→7争用开关K24下输出端因此，为避免K2级开关输出端的冲突，八个结点对连接分两次实现。第一次实现：0→0、1→4、2→2、3→6；第二次实现：4→1、5→5、6→3、7→7。分两次实现连接也避免K1级开关K11和K14输出端的冲突，K0级四个开关没有输出端的冲突。0123456789ABCDEF0123456789ABCDEF（3）Omega网络分2次连接的开关状态如下图。第一次第二次3.55对于4方体网络见图3-65，从结点0000到结点1111，有多少条最短路径？为什么？用E—立方维序寻径算法找出其中一条最短路径。解：（1）当源节点与目的节点的海明距离为h，则有h!条最短路径。结点0000到结点1111的海明距离为4，所以有1×2×3×4=24条最短路径。（2）方向位向量R=S⊕D=0000⊕1111=1111，V=S=0000（源节点）r1=1，V=V⊕2i-1=0000⊕0001=0001；r2=1，V=V⊕2i-1=0001⊕0010=0011；r3=1，V=V⊕2i-1=0011⊕0100=0111；r4=1，V=V⊕2i-1=0111⊕1000=1111（目的结点）。所以，0000与1111有一条最短路径为：S=0000→0001→0011→0111→1111=D。01234567012345670123456701234567