1、试分析下列循环嵌套中各语句间的相关关系:

1、假定有n个进程P(),P(1),…,P(n-1),数组元素a[i开始时被分配给进程P()试写 出求归约和a[0]+a[+…+a[n-1]的代码段,并以n=8示例之

1.试计算下属序列的DFT(a)(13,17,19,23)(b)(2,1,3,7,5,4,0,6) 2.试计算下述序列的逆DFT(a)(16,-0.76+8.66i,-6+6i,-9.25+2.66i0,-9.25-

1.试证明:在奇偶归约算法中,如果对于所有i,满足g+(即对角占优),则 消去奇下标变量后的方程组仍具有对角占优的性质

1、根据9.3.2节所讨论的矩阵向量乘法,试证明:在p个处理器的超立方上, 用SF选路方法进行矩阵-向量乘法,其并行运行时间约为 n2lp+ log+(3/2)tn(n/p)log

1、对于一个2×4的网孔(处理器按行主方式依次编号为0,1,2,3,4,5,6,7),如 何将其嵌入3维超立方中? [提示:将2×4的网孔使用Gray码按行主对其进行编号

1.画出书中图78二叉树的通信图.并分析其计算和通信次数。 2.画出书中图7.9蝶式固的通信图,并分析其计算和通信次数

1.①试证明:当n≥p时,算法6.1的时间复杂度为logn p ②令表示P中第j段中的元素数,试证明算法61在执行过程中,处理器中所积累 的元素数目不会超过2n/p,即∑<

1、令n是待排序的元素数,p=2是d维超立方中处理器的数目。假定开始随机选定主元 x,并将其播送给所有其他处理器,每个处理器按索接收到的x,对其np个元素按照≤x 和>x进行划分,然后按维进行交换。这样在超立方上实现的快排序算法如下:

1.试证明 Brent定理:令W(n)是某并行算法A在运行时间T(n)内所执行的运算数量, 则A使用p台处理器可在t(n)=((n)p+(n)时间内执行完毕