中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第一章 并行计算机系统及其结构模型

第一章并行计算机系统及其结构模型 习题例题: 1.查阅资料,找出一个并行计算的典型应用,详细描述该应用在并行化方面成功和失败之 处以及遇到的困难:(从下列方面考虑:该应用是针对什么科学或者工程上的具体问题 设计的:对于要解决的问题,该应用实际效果怎样,模拟结果和物理结果进行比较的结 果如何:该应用的运行在什么并行计算平台上;(比如分布式或共享内存,向量机)这 个应用使用那种开发工具开发的:该应用的实际工作性能怎样,和运行平台最佳性能相 比较;该应用的可扩展性如何?如果不好,你认为它的扩展性的瓶颈在何处? 2.一个N=2个节点的洗牌交换网络如图所示。试问:此节点度=?网络直径=?和网络 对剖宽度=? N=8的洗牌交换网络 3.一个N=(k+1)2个节点的蝶形网络如图所示。试问:此网节点度=?网络直径=?和 网络对剖宽度=? k=3的蝶型网络 4.参照图,试解释为什么:①当I/O处理器将一个新的数据X写回主存而绕过采用WT 策略的高速缓存时会造成高速缓存和主存间的不一致:②当直接从主存输出数据而绕过 高速缓存采用WB策略时也会造成不一致

第一章 并行计算机系统及其结构模型 习题例题： 1. 查阅资料，找出一个并行计算的典型应用，详细描述该应用在并行化方面成功和失败之 处以及遇到的困难：（从下列方面考虑：该应用是针对什么科学或者工程上的具体问题 设计的；对于要解决的问题，该应用实际效果怎样，模拟结果和物理结果进行比较的结 果如何；该应用的运行在什么并行计算平台上；（比如分布式或共享内存，向量机）这 个应用使用那种开发工具开发的；该应用的实际工作性能怎样，和运行平台最佳性能相 比较；该应用的可扩展性如何？如果不好，你认为它的扩展性的瓶颈在何处？） 2. 一个 n N = 2 个节点的洗牌交换网络如图所示。试问：此节点度=？网络直径=？和网络 对剖宽度=？ 0 1 2 3 4 5 6 7 N=8 的洗牌交换网络 3. 一个 k N = (k +1)2 个节点的蝶形网络如图所示。试问：此网节点度=？网络直径=？和 网络对剖宽度=？ 行 0 行 1 行 2 行 3 k=3 的蝶型网络 4. 参照图，试解释为什么：①当 I／O 处理器将一个新的数据 X’写回主存而绕过采用 WT 策略的高速缓存时会造成高速缓存和主存间的不一致；②当直接从主存输出数据而绕过 高速缓存采用 WB 策略时也会造成不一致

处理器 PPI 高速缓冲 存储器 /O处理器 存储器1O存储器(输入)存储器(输出) (写通过) 写回) 将一种互连网络中的结点映射到另一种网络的过程叫做嵌入( Embedding)。研究嵌入 是很重要的,因为设计在某一特定网络连接的并行机上的算法,如果实际运行在另一种 与之不同的互连网络的并行机上时,我们要重新分析其通信(即选路)时间。试问 ①如何将一个环形网络嵌入到带环绕的二维网孔中去? ②被嵌入到带环绕的二维网孔上的原设计的算法其选路时间有何变化?

5. 将一种互连网络中的结点映射到另一种网络的过程叫做嵌入（Embedding）。研究嵌入 是很重要的，因为设计在某一特定网络连接的并行机上的算法，如果实际运行在另一种 与之不同的互连网络的并行机上时，我们要重新分析其通信（即选路）时间。试问： ①如何将一个环形网络嵌入到带环绕的二维网孔中去？ ②被嵌入到带环绕的二维网孔上的原设计的算法其选路时间有何变化？