三、综合题(60分) 1.试画出基于 Batcher比较器的双调序列8,6,4,2,0,1,3,5)的双调归并 排序网络,并在标出每个 Batcher比较器的输入和输出数据 2.使用指针跳跃技术求出下面森林的根,给出求解过程。 10 6 3.给出环上一到多(one-to-al的CT选路算法描述,并在下图中画出选路步骤 根据单一信包的通讯时间to(CT)=1n+mn+ln,试推导环上的通讯时 间 t(CT)。 (①(2③ 4.先写出矩阵乘法A-Bmn的Fox算法形式描述,然后分析Fox算法在p个 处理器组成的超立方上、使用CT选路的运行时间(注:p-超立方上的 fone-toall (CT)=(t, +mt e )log p )o 5.离散富里叶变换b=∑a20,0≤j≤n-1。对于n=8,试完成下面的蝶式 计算图中的列1到列3的相应标记,并求出b3和b6 列0 列1 列25 三、 综合题（60 分） 1. 试画出基于 Batcher 比较器的双调序列(8，6，4，2，0，1，3，5)的双调归并 排序网络，并在标出每个 Batcher 比较器的输入和输出数据。 2. 使用指针跳跃技术求出下面森林的根，给出求解过程。 3. 给出环上一到多(one-to-all)的 CT 选路算法描述，并在下图中画出选路步骤。 根据单一信包的通讯时间 one to one s w h t CT = t + mt + lt − − ( ) ，试推导环上的通讯时 间 t (CT) one−to−all 。 4. 先写出矩阵乘法 Ann  Bnn 的 Fox 算法形式描述，然后分析 Fox 算法在 p 个 处理器组成的超立方上、使用 CT 选路的运行时间(注：p-超立方上的 t one−to−all(CT) = (t s + mtw )log p )。 5. 离散富里叶变换  − = = 1 0 n k kj bj ak ，0  j  n −1 。对于 n=8，试完成下面的蝶式 计算图中的列 1 到列 3 的相应标记，并求出 b3 和 b6。 7 6 5 4 0 1 2 3 1 2 6 3 4 5 7 8 10 11 12 13 9 a0 a1 a2 a3 a4 a5 a6 a7 列0 列 1 列2 列 3