复习要点
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（网络拓扑结构）, diame
ter 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)bloc
k-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;thread技术
        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中关于同步，资源共享的语句，以及使用方法，能具有利用这些语句设计复杂同步机制的能力。（电梯控制，哲学家问题，消费者和生产者模型的控制语句的程序写法）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。