并行计算 期末考试复习背诵要点.docx
版权申诉
11 浏览量
2022-06-22
17:00:38
上传
评论
收藏 74KB DOCX 举报
复习要点
1、Parallel computing 并行计算，sequential computing 串行计算，instruction 指令，multiple 多数据，communication 通信，exclusive 互斥，concurrent
并发，recursive 递归，data 数据，exploratory 探索，speculative 投机，block cyclic 循环块，randomized block 随机块，distribution 分配，graph partitioning
图划分，speedup 加速比，efficiency 效率，cost 费用，Amdahl’s law，architecture 构架，fundimental functions 基本函数，synchronization 同步，matrix
mulitiplication 矩阵乘，matrix transposition 矩阵转置，bitonci sorting 双调排序，odd-even sorting 奇偶排序，
Shortest path，minimum spanning tree，connected components，maximal independent set，
2、SMP（对称多处理机连接）MPP (Massive Parallel Processors 大规模并行）Cluster of Workstation（工作站机群）
Parallelism（并行化）, pipelining（流水线技术）, Network topology（网络拓扑结构）, diameter of a network（网络直径）, bisection width（对分宽度）,
data decomposition（数据分解）, task dependency graphs（任务依赖图）, granularity（粒度）, concurrency（并发）, process（进程）, processor（处理器）,
linear array（线性阵列）, mesh（格网）, hypercube（超立方体）, reduction（规约）, prefix-sum（前缀和）, gather（收集）, scatter（散发）, threads（线
程）, mutual exclusion（互斥）, shared address space（共享地址空间）, synchronization（同步）, the degree of concurrency（并发度）, Dual of a communication
operation（通信操作的对偶操作）
3、并行计算与串行计算在算法设计主要不同点：(1)具有强大的处理器互连关系(2)并行计算依赖并行计算模型上的，如共享内存，共享地址空间或消
息传递。(3) 问题不容易划分成子问题。(4)并行编程使用任务通信功能。
4、SIMD, SPMD 和 MIMD 含义。
SIMD 指单指令多数据流模型 single instruction stream, multiple data stream；由单一指令部件同时控制多个重复设置的处理单元，执行同一指令下不同 数
据的操作。MIMD 指多指令多数据流模型multiple instruction stream, multiple data stream；多个独立或相对独立的处理机分别执行各自的程序、作业或
进程。SPMD 指单程序多数据流模型Single program multiple data。
5、并行平台的两个典型的通信模式
Massage Passing 信息传递模式和 Shared address space models 共享地址空间模式两种通讯模型。基于消息传递：消息传递平台有p 个处理节点构成，每
个节点有自己独立地址空间，运行在不同节点上的进程之间的交互必须用消息来完成，这种消息交换用来传递数据、操作以及使多个进程间的行为同
步。基于共享地址空间：并行平台支持一个公共数据空间，所有处理器都可以访问这些空间，处理器通过修改存储在共享地址空间的数据来实现交互。
6、PRAM 并行随机内存访问。
EREW：exclusive-read, exclusive-write互斥读互斥写。CREW：concurrent-read, exclusive-write并发读互斥写。CRCW：concurrent-read, concurrent-write
并发读并发写。
7、4 类问题分解技术，Recursive decomposition 递归分解，Data decomposition 数据分解，Exploratory decomposition 探索分解和 Speculative decomposition
投机分解。把问题分解技术：递归分解(快速排序)，数据分解(矩阵相乘)，探测分解(迷宫问题)，投机分解(并行离散时间模拟) (1)递归分解， 如快速
排序，分割成一个独立的子问题和子问题分区组成多个较小的子问题的问题。使用分而治之策略。在这种技术中，解决问题首先它划分为一个独立的
子集。这些子集中的每一个解决通过递归应用到较小的子集结合其结果类似的分裂。(2)数据分解，矩阵乘法，矩阵与向量的乘法，按行或格网的数据
划分。基于数据独立性分解,根据对输出数据的划分来划分任务。例如：矩阵乘法，矩阵与向量的乘法，按行或格网的数据划分。数据分解步骤1 步任
务分解的基础数据;2 步到进程的映射任务。(3)探索分解，人工智能中的状态空间的问题求解、如 16 数码问题。对应于人工智能中基于解空间探索方
法的问题求解，例如迷宫游戏、16 数码问题。探索分解探索分解是2、用来分解的基础计算对应了一个解决方案的空间搜索问题。在探索分解，我们
的搜索空间分割成较小的部分，直到找到所需的解决方案。(4)投机分解， 利用处理器大多数时间处于空闲的特点，把后面可以先计算的任务，提前
计算出，在许多情况下会加速程序的运行。如对 case, if 语句的句子同时计算出来。
8、对稀疏矩阵或在同一数据集合上，操作密度不同的计算，达到调度平衡的问题, 具体方法：循环块分配 Block-cyclic, 随机块分配 randomized block,
图划分 graph partitioning (1)block-cyclic distribution （采用在一个矩阵上循环安排任务计算完成的方法） (2) Randomized block distributions对矩阵的下
标采用随机映射的方法 (3) graph partitioning 图划分的方法
9、基本通信业务，以及对他们的典型模式实现，超立方体，线性阵列和网状:
(1)one to all broadcast; all to one reduction一对多广播以及多对一规约; 环第 1 次传 1 半，第 2 次再减半。Mesh hypercube 降维后仿线性阵列。
(2)all to all broadcast; all to all reduction多对多广播以及多对多规约; 环 1 步 1 步循环 p-1 轮。Mesh hypercube 降维，每次都 1 个方向（同行或列间传）
(3)all reduce, prefix sum 全归约与前缀和;
(4)scatter, gather,散发与收集;
Mesh hypercube 降维，块—面—线，每次信息减半。
(5)all to all personalized communication多对多私自通信; 1 步 1 步循环 p-1 轮，是自己留，不是自己继续传
(6)Circular shift 循环移位。 先所有行 右移 1，第 1 列 上移 1，所有列 上移 1。
10、并行算法的分析测度，以及相应的测度计算公式公式。
答: 加速比 S = Ts/Tp （Ts 串行运行时间，Tp 并行运行时间.Tp 和 Ts 表示并行算法和串行算法的时间复杂性。）
效率 E= S/p= Ts/（Tp*p）（p：处理器的个数） 费用 Cost = Tp*p, E = Ts/cost.
因为 W = Wp+Ws Ts = W Tp=Ws+Wp/p 又因为 S= Ts/Tp则 S= W/(Ws+Wp/p)= (W/Ws)/(1+Wp/pWs)因为 p->无穷大, 则 S-> W/Ws
11、MPI 概念、框架？ 答：Message Passing Interface，典型的基于通讯模型的并行函数库，MPI 对并行进程的管理和 I/O 是通过操作系统
#include <mpi.h>
Main(int argc, char *argv[])
{ int npes, myrank;
MPI_init(&argc, &argv);
MPI_Comm_szie(MPI_COMM_WORLD, &npes);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
并行程序代码部分 通讯结束部分
MPI_Finilize()
}
12、MPI 的基本函数
MPI_Init 初始化；MPI_Finalize 终止；MPI_Comm_size 确定进程个数；MPI_Comm_rank 确定被叫进程的标号；MPI_send 发送 ；MPI_Recv 接收
13、 在 MPI 中的 blocking Message Passing Operation 和 Non-blocking Message Passing Operation 的含义和具体如何实现的。在MPI 中对应的语句？
答：现在的消息传递系统多使用三种通信模式: 同步的消息传递 (Synchronous Message Passing) 阻塞的消息传递 (Blocking Message Passing) 非阻塞的
消息传递 (Nonblocking Message Passing)
int MPI_Send(void *buf,int count,MPI_datatype datatype,int dest,int tag,MPI_Comm comm)
int MPI_Recv(void *buf,int count,MPI_datatype datatype,int source,int tag,MPI_Comm comm,MPI_Status *status)
int MPI_Isend(void *buf,int count,MPI_datatype datatype,int dest,int tag,MPI_Comm comm,MPI_Request *request)
int MPI_Irecv(void *buf,int count,MPI_datatype datatype,int source,int tag,MPI_Comm comm, MPI_Request *request)
14、给出在 Pthread 中线程的定义。一般利用Pthread 编程的程序基本结构（包含那几个语句）。
答：IEEE 指定的一个标准的线程 API，POSIX API。POSIX 也称为 Pthread 。线程的创建、终止 pthread_create pthread_exit ，等待所有线程运行完毕
以便完成结果的合并 pthread_join
#include<pthread.h>
int pthread_create( pthread_t *thread_handle, const pthread_attr_t * attribute , void * (*thread_function) (void*), void *arg ）；
int pthread_join ( pthread_t thread, void **ptr)
int pthread_exit()
15、请归纳出 Pthead 中关于同步，资源共享的语句，以及使用方法，能具有利用这些语句设计复杂同步机制的能力。（电梯控制，哲学家问题，消费
者和生产者模型的控制语句的程序写法）
答：Synchronization primitives in pthread 在共享地址空间的并行程序设计中，要解决的主要问题是对共享地址空间的使用和同步操作。使用
mutex-lock(互斥锁) 使得各个线程互斥的访问关键区域。要访问关键区域，线程必须首先获得互斥锁并锁定pthread_mutex_lock()，离开关键区域后,要
进行解锁 pthread_mutex_unlock()，一个线程被 mutex-lock 锁定后，不允许其他的线程进入关键区域。
int pthread_mutex_init(pthread_mutex_t *mutex_lock, const pthread_mutexatrr_t *lock_attr)
这个函数初始化的互斥锁 mutex_lock 锁定状态。
int Pthread_mutex_lock( pthread_mutex_t *mutex_lock);
调用此功能，锁定互斥锁 mutex_lock。如果互斥锁已经锁定，调用线程块;否则，互斥锁被锁定，调用线程返回。
int Pthread_mutex_unlock( pthread_mutex_t *mutex_lock);
16、知道 thread 和 OpenMP 是共享存储器模型的语言（并行计算环境），能说明 pthread 和 OpenMP 各自的优缺点。
答：共享地址空间可以使多个任务通过共享地址空间使程序设计变得更加方便，通讯、同步。 Thread 线程：程序流中的一个单控制流。OpenMP 是
一种可以用 C 以及 C++在共享地址空间计算机上进行编程的指令性的API。OpenMP 命令提供对并发，同步以及数据处理的支持，但不需要显式设置
互斥锁、条件变量、数据范围以及初始化。
Pthread 数据交换清晰，减轻数据移动、脏共享、竞争代价。提供丰富API，实现复杂同步操作。相关编程工具更多
OpenMP 优缺点：对线程做了一定封装，减轻一些线程相关工作，可移植性好。提供可用编程标准；可移植性，简单，可扩展性；灵活支持多线程，
负载平衡能力；程序具有模块化。只适用于硬件共享存储型机器；动态可变线程数支持困难。
17、用 Open MP 写出矩阵乘：
#pragma omp parallel default(private) shared (a, b, c, dim) num_threads(4)
#pragma omp for schedule(static)
资源评论
