2016年深圳大学《并行计算》期末试卷(陆克中老师).doc

《并行计算》试卷 A卷 第 PAGE 1 页 共 NUMPAGES 2 页 学院 专业 学院 专业 姓名 学号 座号　　　 ( 密 封 线 内 不 答 题 ) ……………………………………………………密………………………………………………封………………………………………线……………………………………线……………………………………… _____________ ________ … 开/闭卷 闭卷 A/B卷 A 课程编号 课程名称 并行计算 学分 3.5 命题人(签字) 陆克中 审题人(签字) 刘刚 2016 年 5 月 1 日 题号 一 二 三 四 五 六 七 八 九 十 基本题总分 附加题 得分 评卷人 请详述均匀存储访问和非均匀存储访问的特点。（10分） 画出一个8X8的2-D环绕网络，假设最左下角节点序号为（0,0），最右上角序号为（7,7），请给出一条从（1,1）到（6,7）的最短路径。（10分） 一到多人通信又称之为单点散播，源处理器有p个信包，每一个去往一个目的地。试证明使用SF方式在超立方实行一到多人通信的通信时间为tslogp+mtw(p-1)。（10分） 设顺序执行一个程序时间为T1=N，并行处理时间为Tp=N/P+5，其中N为负载，P为处理器个数。（15分） （1）试求固定负载时的加速比并讨论其结果。 （2）试求固定时间时的加速比并讨论其结果。 给定序列（12,2,6,8,13,1,16,17,5,7,18,9,3,10,4,11,15,14）和3台处理器P1，P2，P3，运行MIMD上的PSRS排序算法，描述出处理器P1的执行过程。（15分） 画出基于batcher比较器的（6,5,8,1,2,4,7,3）的排序网络，并标出每个batcher比较器的输入和输出数据。（15分） 利用Cannon矩阵乘法计算C4X4=A4X4B4X4，描述处理器P0,1的执行过程（包括发送消息，接收消息和本地计算）。（15分） 其中矩阵A和矩阵B为。 用奇偶规约法求下列三对角方程。（10分） 4X1+X2=2 4X1+11X2-5x3=7 2X2+14X3-6X4=13 5X3+18X4=24