《并行算法考试题》由会员分享，可在线阅读，更多相关《并行算法考试题（3页珍藏版）》请在金锄头文库上搜索。
1、1、 名词解释： （1）等分宽度：把网络划分为两个相等的部分（节点数之多差 1） ，所需要去掉的网络 边的条数。 （2）网络直径：网络中两个节点之间的最远的距离 （3）并行运行时间：从第一台处理机开始执行任务开始，到最后一台处理机执行完任 务所经历的时间。 （4）并行步：能够同时执行的操作数。 （5）加速比：同一任务在串行计算下的运行时间/并行计算下的运行时间。2、 介绍超立方体网络互连方式的性能指标 解答：q 维超立方体，等分宽度为 2q-1，网络直径：q，网络接口数：q3、 按照指令流和数据流，并行计算机可以分为哪些类型？各自适合什么样的并行计算？ 排名在前 20 的计算机都是什么类型的计
2、算机？它们的区别是什么？ 解答： （1）SISD： （2）SIMD： （3）MISD： （4）MIMD： 4、 并行算法有哪些设计方法？ （1）流水线技术 （2）分而治之策略 （3）平衡二叉树方法 （4）倍增技术 （5）加速级联策略 5、 举例说明平衡树方法的原理？ 参考：使用 n/2 台计算机，可以在步完成运算。n2log6、 Logp 模型有哪些参数？BSP 模型有哪些参数？这两个模型之间的关系是什么？ （1）L：延迟 （2）o：cpu 开销 （3）g：连续发送/接收消息的时间间隙 （4）P：处理机个数 BSP 模型： （1）P：处理机数 （2）g：选路器吞吐率 （3）L：全局同步之间的时
3、间间隔 关系： （1）本质上等效，可以相互模拟 （2）用 BSP 模拟 LOGP 所进行的计算时，通常会慢常数倍。 （3）反之，慢对数倍7、 题目记不清了，只要知道两个公式就可以了，对于 logp：L+2o 对于 logGp：t+t 8、 计算加速比和效率的题，具体记不清了，只要会使用公式就可以了。9、 关于群集系统中 QR 分解的题目。将矩阵的行列都分成 5 等分，得到它的 25 个任务， 按照贪婪算法的调度思想，画出子任务执行的并行步。参考 4 等分时的并行步，如图10、设计 FFT 算法，实现 256 个输入数据的转换，有 4 台处理机。并计算通信开销 提示：信同步处理阶段，相互通通信串行处理阶段，不需要.log.loglogloglog2222 2 PPNPN N（1）串行计算时间： （2）并行运行时间：PPTTS1 PSEP PNntTelems2log)/(log221pnNtttTelemcomp)log2)(/()/(log)/()/(22PpnttppnttpPpnttppnttpTcomm
