中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第七章 并行算法的一般设计过程

▪ 3.1 并行程序开发方法 ▪ 3.1.1 并行层次与代码粒度 ▪ 3.1.2 并行程序开发策略 ▪ 3.1.3 并行编程模式 ▪ 3.1.4 并行应用编程过程 ▪ 3.2 并行程序设计模型 ▪ 3.2.1 计算π样本程序 ▪ 3.2.2 数据并行模型 ▪ 3.2.3 消息传递模型 ▪ 3.2.4 共享变量模型 ▪ 3.3 并行编程语言和环境概述 ▪ 3.3.1 早期并行编程语言 ▪ 3.3.2 近代并行编程语言与环境 ▪ 3.3.3 并行说明性语言环境 ▪ 3.4 循环程序并行化的一般方法 ▪ 3.4.1 数据相关分析 ▪ 3.4.2 .数据划分与处理器指派 ▪ 3.4.3 循环重构

中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第六章 并行算法的基本设计技术

中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第四章 并行算法的设计基础

1.①试证明:当n≥p时,算法6.1的时间复杂度为logn p ②令表示P中第j段中的元素数,试证明算法61在执行过程中,处理器中所积累 的元素数目不会超过2n/p,即∑<

1.画出书中图78二叉树的通信图.并分析其计算和通信次数。 2.画出书中图7.9蝶式固的通信图,并分析其计算和通信次数

图论在计算机科学、信息科学、人工智能网络理论、系统工程、控制论、运筹学和 经济管理等领域有着广泛的应用。但很多图论问题虽易表达,却难以求解,其中有相当多 的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MP 编程实现,包括传递闭包、连通分量、最短路径和最小生成树等

计算几何是计算机科学中的一个分支,是专门研究有关几何对象问题的。它在图像分 析、模式识别、计算机图形学等中应用甚广。本章主要介绍几个基本计算几何问题的简单 并行算法和它们的MPI编程实现,包括包含问题、相交问题和凸壳问题等

一、填空题 1.常用的并行算法设计的基本技术有等。 2.常见的并行计算模型有等。 3.PAM设计过程分为和四步

1、令n是待排序的元素数,p=2是d维超立方中处理器的数目。假定开始随机选定主元 x,并将其播送给所有其他处理器,每个处理器按索接收到的x,对其np个元素按照≤x 和>x进行划分,然后按维进行交换。这样在超立方上实现的快排序算法如下: