考试试题一

一、名词解释（20分，每小题四分）
　　MIMD
　　CC-NUMA
　　存储转发
　　交叉开关
　　递归分解

二、（16分）设矩阵为方阵。A 在存储器中存放的顺序为a₀₀ ，a₀₁ ，…，a₀₃ ，a₁₀ ，…，a₁₃ ，a₂₀ ，…，a₂₃ ，a₃₀ ，…，a₃₃ 。若想用单级静态互连网络实现的转置，应采用什么网络？

三、试分析以下用BSPLib并行求4个整数1，2，3，4的前序累加和的过程（参见图）。

程序为： /*用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 ( ) ;
}

四、（16分）在并行计算中，如果问题规模为W固定，问题的串行部分为Ws，请证明不管用多少处理器，并行系统的加速比上限为W/Ws。

五、（16分）给出下图给出行块带状划分时矩阵转置的算法分析和性能评价。

六、（16分）给出快速排序算法的一种并行设计，并分析开销。