并行处理复习题(Answer)全面

TheReviewofParallelProcess1．TheSieveofPrimes(8—10)（筛选质数）对于给定的一列数1,2,…,n，构造一个和这列数相对应的一个位向量，记为mark，则：（1）对于单处理机来说，算法如下：如图①CurrentPrime=2，Index=22，将该列数的位向量mark的所有元素置为0，即mark[i]=0；②IfCurrent2>nthen转向④ElseDomark[Index]=1,Index=Index+CurrentPrimeUntilIndex>n③找出向量mark中下一个值为零的元素，将其赋给CurrentPrime，转向②执行；④所有mark值为零的位置所对应的元素即为质数，输出。（2）对于共享存储器的系统来说，每个空闲的处理机都根据存储器中的CurrentPrime来求自己序列中的质数，同时更改存储器中共享的CurrentPrime的值，从而达到通信的目的，其他同上面的算法。（3）对于处理机私有存储器的系统来说，P1寻找每一个质数，并且向所有其他处理器广播，然后各个处理机再从它的子列中寻找质数，方法同上。2．TheSequential（连续的，结果的）algorithm(semigroup（半群）,prefixcomputation,routing,broadcasting,sorting)(20,21,23)（1）（2）（3）PacketRouting：一个处理机给另外一个处理机发送数据包；（4）Broadcasting：一个处理机给其他所有处理机发送数据包；（5）Sorting：处理机按照指定的顺序对数据进行重新排列。3．Maximum-finding,Computingprefixsumonlineararrays(24,25)（在线性组上计算最大值，并行前缀和）（1）Maximum-finding：每个处理机都有一个初始值，目标是每个处理机都知道最大值是多少。每个处理机将本身的值都存在own中，每个处理机都存储一个本地变量max-thus-far，记录迄今为止该处理机上所得到的最大值，其初始值是处理机本身的值。每一步中，每个处理机都向其左右邻居发送其数据，处理机接受到左右邻居的数据后，将其分别存储到left和right中，令max-thus-far=max（left，own，right）。最坏情况下，需要p-1个通讯步和p-1个值比较步即可完成。（2）Computingprefixsum：①每个处理机上只有一个值时，初始，只有最左边的处理机是活跃的，将其值向右边的邻居发送，其有邻居接受到数据后变为活跃的，计算两者的和（即为该元素以前的prefixsum）并向其又邻居发送结果、变为不活跃，直至最右边一个处理机计算出最后prefixsum。②处理机上有多个值时，每个处理机先对自身数据求前缀和，然后再对和求diminished前缀和，最后再将Localprefixes（自身及自身的和）同前面的diminished前缀和求和，即为相应元素的前缀和。4．Odd-evensortonlineararray(27)(在线性数组上的奇偶排序)当所有的关键值已经存储在各个处理机上，且一个处理机存一个数据时，可用Odd-evenSort。以升序排列为例，在奇数步骤，标号为奇数的处理器同其右侧的处理器进行比较，如果大于于其右侧处理器的数据，则进行交换，否则不做处理；在偶数步骤，标号为偶数的处理器同其右侧的处理器进行比较，如果大于于其右侧处理器的数据，则进行交换，否则不做处理。这样处理的结果就是将数据按升序排列。对这种排序，有如下性能度量指标：最坏情况下，最大值在P0上，从而一直移动到最右边。5．Findingtherankofeach1sinalistof0sand1s(29)（前缀和的应用）利用求该序列的parallelprefixcomputation来实现。每个1的并行前缀和就是他在该0-1序列中的序号。6．Packetroutingonatree(30)说明要路由的包的目的节点不在以self为根的子树上，所以应该向上路由，由其父节点来路由它。依赖于处理机节点的编号模式。以前序遍历为例：按前序遍历的顺序对二叉树的节点进行编号，因此每个节点序号均小于其所有后代节点的序号，即根节点的序号是该子树中序号最小的。假定每个节点知道自己的序号（记为self），其做子树的最大序号为maxl，右子树的最大序号为maxr。则将包（在节点self上）从节点i路由到节点dest的算法为：7．Findmaximumvalue,computingprefixsumandshearsorton2dmesh(33)（1）Findmaximumvalue：首先对每一行求最大值（参考第3题），从而每行都存储了该行的最大值；其次对每一列求最大值，从而每列都存储了该列的最大值。这样，所有的处理机都存储了这些元素的最大值。（2）computingprefixsum：假定处理机按行主序排列。①在每行中computingprefixsum；②在最右边一列computingdiminishedprefixsum；③将最右边的结果值在相应行中向左广播，并且与先前求出的该位置处的rowprefixsum求和。（3）shearsort：该算法在r行的2Dmesh上需要阶段。除了最后一个阶段的所有阶段，先是所有行都独立地进行蛇形排序，即偶数行从左到右