并行算法考试题.docVIP

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