一、 问答题


1、在讨论PRAM-CRCW时，我们说CRCW是最强的PRAM模型，还给出了四种不同的CRCW模型：公共PRAM-CRCW，任意PRAM-CRCW，优先PRAM-CRCW，求和PRAM-CRCW。可以在其他的PRAM模型上对一个PRAM-CRCW模型进行仿真，假设t是优先PRAM-CRCW上一个算法的运行时间，请给出这个算法在下面的模型上的运行时间上限：
    (1) 公共PRAM-CRCW
    (2) 任意PRAM-CRCW
    (3) PRAM-CREW
    (4) PRAM-EREW




2、考虑如下的PRAM-EREW模型：p个处理器，m个存储器。我们可以在一个p个处理器，每个处理器有m/p个存储器的消息传递结构的并行计算机上模拟这个模型。如果一个算法在这种PRAM-EREW上的运行时间是t，请给出这个算法在下面的体系结构上的运行时间上限：
    (1) p处理器的环（ring）
    (2) p处理器的二维网格（mesh）
    (3) p处理器的超立方体（hypercube）




3、假定处理器P_i（1≤i≤n ）开始时存有数据di，所谓的前序累加求和（Prefix-Sum）指用 来代替P_i中的原始数据d_i ，下面的算法给出了PRAM模型上的前序累加求和的算法：
前序累加求和算法
输入：P_i中保存有d_i ，1≤i≤n
输出：P_i中的内容为
Program Prefix_sum
Begin
    for j=0 to logn - 1 do
        for k = 2j + 1 to n par-do
              （i）   P_i = d_i - 2^j
              （ii）  d_i = d_i + d_i - 2^j
        endfor
    endfor
End.

其中，Par-do表示不同的循环变量对应的计算可以并行执行
    (1) 以n = 8为例，按照上面的算法逐步计算出累加和。
    (2) 分析算法时间复杂度。

/*用BSPLib求前序累加和*/
#include "bsp.h"
int bsp_allsums ( int x ) {
    int j, left, right;

    bsp_push_reg(&right, sizeof(int));
    bsp_push_reg(&left, sizeof(int));

    right = x;
    for( j = 1 ; j < bsp_nprocs(); j * = 2) {
        if ( bsp_pid ( ) + j < bsp_nprocs ( ) )
            bsp_put ( bsp_pid( ) + j , &right, & left ,0 ,sizeof ( int ));
        bsp_sync( );
        if( bsp_pid ( ) > = j ) right + = left;
    }
    bsp_pop_reg( &right );
    bsp_pop_reg( &left );
    return right ;
}

void main ( ) {
    bsp_begin ( bsp_nprocs( ) );
        printf(" On %d sum is %d \n", bsp_pid( ), bsp_allsums (1 + bsp_pid ( ) ) );
    bsp_end ( ) ;
}