并行体系结构第二次作业.docVIP

第三章 作业 修改讲义中的基本路由器模型，使其只使用输入缓冲并且没有虚通道。针对该路由器模型，重写虫孔交换和报文交换的基本延迟表达式。 答： 假设物理微片与微片大小相等，等于物理通道宽度W; 路由头假设为一个微片，消息大小为L+W位; 路由延迟为tr秒; 两个路由器间物理通道的操作频率为Bhz，则路由器间物理通道的带宽为BW位/秒; 假设连线足够短，一个时钟周期能够完成一次传输 路由器间传输延迟为tw，路由器内部延迟为ts 则： 虫孔交换的基本延迟表达式为： 报文交换的基本延迟表达式为： 考虑一个虫孔交换网络，虚电路在被控制信号或特殊消息显示拆除之前一直存在。画出长度为三个微片的消息在长度为三段链路的通路上、在源节点向通路注入控制微片并取消通路之前的传输时空图。 答：传输时空图如下图所示： 报文交换相对于消息交换的一个主要优点是，允许几个报文同时沿着从源到目的路径传输。假设所有报文沿同一路径传输，不需要为每个报文添加序列号。画出一个包括4个报文的消息在一个三段链路长的路径上传输的时空图。 答：传输时空图如下图所示： 写出二维网格中最小负向优先算法。 答：最小负向优先算法为： Xoffset = Xdest - Xcurrent Yoffset = Ydest - Ycurrent If Xoffset 0 and Yoffset 0 Channel = select (X-,Y-) Endif If Xoffset 0 and Yoffset = 0 Channel = X- Endif If Xoffset = 0 and Yoffset 0 Channel = Y- Endif If Xoffset 0 and Yoffset 0 Channel = select(X+,Y+) Endif If Xoffset 0 and Yoffset = 0 Channel = X+ Endif If Xoffset = 0 and Yoffset 0 Channel = Y+ Endif If Xoffset = 0 and Yoffset = 0 Channel = internal Endif 采用转弯模型，针对三维网格给出最短路径部分自适应路由算法，使这些算法具有尽可能少的路由限制。 答： 输入：当前节点坐标（Xcurrent,Ycurrent,Zcurrent）和目标节点坐标（Xdest,Ydest,Zdest） 输出：选择的输出通道Channel 其实现过程如下： Xoffset := Xdest – Xcurrent； Yoffset := Ydest – Ycurrent； Zoffset := Zdest – Zcurrent； if (Xoffset Yoffset Zoffset) { 随机选取第S维 While(S.offset0) {Channel = +s;} While(S.offset0) {Channel = -s;} 在剩下的二维平面中做西向优先路由； } 必有第S维offset = 0，在剩下的二维平面中做西向优先路由； Return； 给出蝶式MIN中可以建立无冲突路径的充要条件。 答：蝶式MIN 中的地址映射： 考虑从Sn-1 Sn-2…S1 S0 到 dn-1dn-2…d1d0 建立一条电路 经过第0级链路： Sn-1Sn-2…S1S0 -- -〉Sn-1Sn-2…S1S0 S0Sn-2…S1Sn-1作为第 0 级开关输入地址,经过第0 级开关后： Sn-1Sn-2…S1S0 ---〉 Sn-1Sn-2 …S1S0 ’ 经过第 1 级 链路 ： Sn-1Sn-2…S1S0’---〉S n-1Sn- 2 … S0’S1 S0Sn-1’… S1Sn-2 作为第1 级开关输入地址，经过第1 级开关后： Sn-1Sn -2 … S0’S1 ---〉Sn-1 Sn-2 … S0’S1’ 类似的有第i 级开关的输出为：Sn-1 …Si+1 … Si -1’ …S1’S 0’S I’ 从而第n -1级开关的输出为 ：Sn-2’Sn -3’…S 1’S 0’Sn -1’ 最后一级连接为恒等排列,所以 Sn-2’Sn -3’… S1’S0’Sn -1’ =dn -1 dn -2 …d1d0 从而有 ： Si’ =di+1 (0≤ i≤n -2 ), S n -1’= d 0 所以第 i 级开关的输出为 ： Sn-1 …Si+1 … di… d2 d1di+1 对于任意两个输入/输出对（S , D )和（ R, T) ,可以建立无冲突的两条路径的充要条件是 ： 对于任意的i都有: 如果要对于任意两个输入/输