并行计算整理考试资料笔记

.并行计算（parallelcomputing）是指，在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解速度，或者求解应用问题规模的目的。.并行计算的基本条件：并行机、应用问题必须具有并行度、并行编程.并行计算的主要研究目标：加速求解问题的速度、提高求解问题的规模.并行计算的主要研究内容：并行机的高性能特征抽取、并行算法设计与分析、并行实现技术、并行应用.推动并行计算发展的主要动力：大规模科学与工程计算应用对并行计算的需求、微电子技术与大规模集成电路VLSI的发展、.并行算法分类（a按运算基本对象的不用分为：数值并行算法、非数值并行算法。 B按并行进程间相互执行顺序关系的不同分为：同步并行算法、异步并行算法、独立并行算法。 C按各进程承担的计算任务粒度的不同分为：细粒度并行算法、中粒度并行算法、大粒度并行算法。 ）.并行算法的发展阶段：基于向量运算的并行算法设计阶段、基于多向量处理机的并行算法设计阶段、 SIMD类并行机上的并行算法设计阶段、 MIMD类并行机上的并行算法设计阶段、现代并行算法设计.当前流行的并行编程环境：消息传递、共享存储和数据并行。.标准消息传递接口MPI将消息传递并行编程环境分解为两部分：构成该环境的所有消息传递函数的标准接口说明，它们是根据并行应用程序对消息传递功能的不同要求而制定的，不考虑该函数能否具体实现、各并行机厂商提供的对这些函数的具体实现。.MPI系统就是指所有这些具有标准接口说明的消息传递函数所构成的函数库。.在标准串行程序设计语言（C、Fortran、C++）的基础上，再加入实现进程间通信的 MPI消息传递库函数，就构成了MPI并行程序设计所依赖的并行编程环境。标准消息传递接口 MPI优点：具有很好的可移植性，被当前所有并行环境支持；具有很好的可扩展性，是目前高效率的大规模并行计算（数百个处理器）最可信赖的平台；比其他消息传递系统好用；有完备的异步通信功能；有精确的定义，从而为并行软件的发展提供了必要的条件。.消息传递并行机模型：P--MPI进程、M--每个进程的局部内存空间、多个“P/M”进程/内存模块通过互联网络相互连接，构成一个分布式存储的进程拓扑结构。.各个进程之间可以直接通信， 但是各个进程只能直接访问自身的局部内存空间，对其他进程的局部内存空间的访问只能调用消息传递函数， 通过进程间通信才能实现。 核心是消息传递标准函数库，而构成该函数库的所有函数就构成了用户面对的消息传递并行编程环境。.进程可表示成四元组（P,CD,S）,其中P是程序代码、C是进程的控制状态、D是进程数据、S是进程的执行状态.进程是计算机中已运行程序的实体。程序本身只是指令的集合，进程才是程序（那些指令）的真正运行。.进程特征：资源特征：进程是计算机系统分配资源的最小单位 ；执行特征：进程是程序的并发执行。.进程状态：非存在状态：进程依赖的程序还没有投入运行；就绪状态： 进程由其父进程 （例如，操作系统的内核进程或Shell进程，或其他应用程序进程）调入并准备运行；运行状态：进程占有 CPU和其他必需的计算资源，并执行指令；挂起状态：由于CPU或其他必需的计算资源被其他进程占有，或必需等待某类事件的发生，进程转入挂起状态，以后一旦条件满足，由操作系统唤醒并转入就绪状态；退出状态：进程正常结束或因异常退出而被废弃。.进程间通信是指同一台处理机或不同处理机的多个进程间传送数据或消息的一些技术或方法。.现代操作系统提供的进程间通讯的方式： 通信：进程间的数据传递称为进程间通信。 在同一台处理机中，通信可以通过读/写操作系统提供的共享数据缓存区来实现； 在不同处理机中，通信可以通过网络传输数据来实现。特别地，称两个进程之间传递的数据为消息，称这种操作为消息传递。消息传递可以在同一台处理机的多个进程之间发生，也可以在不同处理机的多个进程之间发生。同步：同步是使位于相同或不同处理机中的多个进程之间相互等待的操作，它要求进程的所有操作均必须等待到达某一控制状态之后才进行。聚集或规约：聚集将位于相同或不同处理机中的多个进程的局部结果综合起来，通过某种操作，例如求最大值、最小值、累加和，产生一个新的结果，存储在某个指定的或者所有的进程的变量中。.线程指的是进程中一个单一顺序的控制流。它是系统独立调度和分派的基本单位。线程由操作系统内核施行管理，由线程库具体实现。进程产生时， 其执行特征构成一个线程， 称之为主线程。主线程调用线程库函数，可以动态地创建新的线程， 称之为从线程。.并行机分类（a根据指令流和数据流的不同组合，计算机系统可分为：单指令流单数据SISD就是传统的单处理机（又叫串行机或顺序机卜单指令流多数据流SIMD同时用相同的指令对不同的数据进行操作、多指令流单数据流MISD、多指令流多数据流MIMDo.目前主要的并行计算机有五种：对称多处理共享存储并行机 SMP、分布共享存储并行机 DSM、机群（cluster）＞星群（constellation）、大规模并行机MPP。22.SMP的特点：对称共享存储、单一的操作系统映像、局部高速缓存cache及其数据一致性、低通信延迟、共享总线带宽、支持消息传递、共享存储并行程序设计.DSM的特征：并行机以结点为单位，每个结点包含一个或多个CPU,每个CPU拥有自己的局部cache,并共享局部存储器和 I/O设备，所有结点通过高性能互联网络相互连接、物理上分布存储、单一的内存地址空间、非一致内存访问（NUMA）模式、单一的操作系统映像、基于 cache的数据一致性、低通信延迟与高通信带宽、扩展性好、支持消息传递、共享存储并行程序设计。.MPP的特征：由数百个乃至数千个计算结点和 I/O结点组成，每个结点相对独立，并拥有一个或多个微处理器。这些结点配备有局部 cache,并通过局部总线或互联网络与局部内存模块和 I/O设备相连接。通常地，这些微处理器针对应用特征， 进行了某些定制，与商用的通用微处理器略有不同、这些结点由局部高性能网卡（NIC）通过高性能互联网络相互连接。各个结点均拥有不同的操作系统映像、各个结点间的内存模块相互独立，且不存在全局内存单元的统一硬件编址、仅支持消息传递 （MPI）并行程序设计，不支持全局共享的（OpenMP）并行程序设计模式。.访存模型根据内存访问的性质，并行机的访存模型可以分为均匀访存模型、 非均匀访存模型、分布式访存模型及混合访存四类。.并行计算机的组成要素：结点（node）、互联网络（interconnectnetwork）、内存（memory）。.结点构成并行计算机的最基本单位，包含2个或者2个以上微处理器（CPU）,并行程序执行时，程序分派的各个进程将并行地运行在结点的各个微处理器上，通过集线器（HUB）连接。集线器一般采用高速全交互交叉开关，或者高带宽总线完成。.网络的拓扑结构是引用拓扑学中研究与大小，形状无关的点，线关系的方法。把网络中的并行机结点抽象为一个点，把传输介质抽象为一条线，由点和线组成的几何图形就是网络的拓扑结构。.网络的拓扑结构反映出网中个实体的结构关系， 是理解和建立并行网络的第一步， 它对并行网络的性能，系统的可靠性与通信费用都有重大影响。.互联网络的拓扑结构可用无向图表示。其中，图中的结点唯一地代表并行机的各个结点，图中的边表示在两个端点代表的并行机结点之间，存在直接连接的物理通信通道。.并行机规模：并行机包含的结点总数，或者包含的CPU总数。.结点的度：拓扑结构图中， 以某个结点为端点的边的条数， 称为该结点的度。 结点的度表示， 存在多少个结点，与该结点有直接的物理连接通道。.结点距离：两个结点之间跨越的图的边的最少条数。.网络直径：网络中任意两个结点之间的最长距离。.点对点带宽：图中边对应的两个结点之间相互连接的物理通道的通信带宽。.点对点延迟：图中任意两个结点之间的一次零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟，所有结点之间的最大延迟称为网络的最大延迟；.折半宽度（对分带宽）：对分图成相同规模的两个子图（它们的结点数相等，或者至多相差 1）时，必须去掉的边的最少条数，或者，这些边对应的网络点对点带宽的最小总和；.总通信带宽：所有边对应的网络通信带宽之和.评价互联网络的基本准则：固定并行机包含的结点个数， 如果点对点带宽越高、 折半宽度越大、或者网络直径越小、点对点延迟越小，则互联网络质量可以说越高。.网络拓扑结构分类：静态拓扑结构、动态拓扑结构、宽带互联网。.静态拓扑结构特点：结点之间存在固定的物理连接， 且在程序的执行过程中， 结点间的连接方式不变。常见结构：阵列（array）、环（ring）、网格（mesh）、网格环（torus,也叫环面）、树（tree）、超立方体（hypercube）、蝶网（butter?y）、Benes网等。.动态拓扑结构特点：结点之间无固定的物理连接，而是在连接路径的交叉点处用电子开关、路由器或仲裁器等提供动态连接。常见结构：单一总线、多层总线、交叉开关、多级互联网络等类型。.宽带互联网络典型代表：以太网（Ethernet）、商用交换机（switch）、专用微机机群互联网络。第二章.vi编辑器的使用：vi是一种广泛存在于各种UNIX和Linux系统中的文本编辑程序，Vi的功能十分强大，但是命令繁多，不容易掌握，Vi的发明者：billjoy。vi是标准的Linux文本编辑程序。vi不是基于窗口的，所以，这个多用途编辑程序可以用于在任何类型的终端上编辑各式各样的文件。.创建一个文件：vifilenameo如果filename已经存在，vi会打开现存文件。如果是一个新文件， vi会创建它.状态行：屏幕的最后一行被称为状态行，用于显示文件名及文件中行和字符的个数 。.vi的三种模式：输入模式（输入文本）、命令模式（执行命令）、末行模式（执行特定命令）。.vi被运行时，通常处在命令模式下.键入以下命令可以使vi退出命令模式，进入输入模式： Ii,Aa,Oo。在该模式中，可以输入命令来执行许多种功能。大多数的 vi命令都是由一个或两个字母加上一个可选数字组成。以冒号开头的命令实际上是ex命令，即进入末行模式进行保存、退出等操作。.保存:w后面接回车键.保存并退出输入：wq后面接回车键.退出但不保存输入:q后面接回车键，使用q!强行退出.在文件中移动光标向左移动一个字符：按 ho向右移动一个字符：按lo向下移动一行：按jo向上移动一行：按k。移动到当前行的开头处：按人（即Shift—6）。移动到当前行的结尾处： 按$（即Shift—4）。移动到顶部：按H（大写）使光标移动到屏幕的顶部。移动到中部：按M（大写）使光标移动到屏幕的中间。移动到底部：按L（大写）使光标移动到屏幕的底部。向前翻页一屏：要向前滚动（向下移动）一整屏，需按下Ctrl-fo光标将移动到新屏的左上角。向前滚动半屏：要向前滚动半屏，需按Ctrl-d。向后翻页一屏：要向后滚动（即向上移动）一整屏，需按下Ctrl-bo向后滚动半屏：要向后滚动半屏，需按下ctrl-u54.插入文本：添加：输入a后，在光标的右边插入文本，输入A,在一行的结尾处添加文本：插入：通过在命令模式下输入i,在光标的左边插入文本，通过在命令模式下输入 I,在行首插入文本：插入新行：输入o,在当前光标位置下面打开一行，输入O,在当前光标位置上面打开一行.撤消更改：撤消前一个命令：在最后一个命令之后立即输入 u来撤消该命令：重复某个命令 .:撤消对一行的更改：输入U来撤消你对一行所做的所有更改，这个命令只有在你没将光标移动到该行以外时才生效。.删除文本：删除一个字符：为删除一个字符，需将光标放置在要删除的字符上并输入 x,为删除光标之前（其左边）的一个字符，需输入 X:删除一个词或词的部分内容：为删除一个词，需将光标放置到该词的开头并输入dw,为删除词的部分内容，需将光标放置到该词要保存部分的右边。输入dw来删除该词余下的部分：删除一行：将光标放置到该行的任意处并输入 dd：删除多行ndd：删除行的部分内容：将光标放置到该行要保存部分的右边，并输入 Do为删除光标左边的所有内容，须将光标放置到该行要删除部分的右边，并输入d0（d-零）。：删除到文件的结尾：为删除从当前行到文件结尾的所有内容，需输入dG57.复制和移动文本复制一行命令： yy：粘贴命令：p：移动文本：先将要移动的部分用删除命令删除，然后再粘贴就可以了：复制指定文件的内容 :rfilename.查找一个字符串查找一个字符串：输入/,并在/后面输入要查找的串，然后按下回车：输入“n”跳转到该串的下一个出现处：输入“N”跳转到该串的上一个出现处.替换一个字符串在一行内替换头一个字符串 01d为新的字符串new:s/o1d/new.在一行内替换所有的字符串 01d为新的字符串new:s/o1d/new/g.在两行内替换所有的字符串 01d为新的字符串new:#,#s/o1d/new/g.在文件内替换所有的字符串 01d为新的字符串new:%s/o1d/new/g.进行全文替换时询问用户确认每个替换需添加 c选项:%s/o1d/new/gc.设置vi显示行号:setnumber.取消行号显示:setnonumber.设置显示用户模式:setshowmode.设置文件只读:setreadonly.Linux下C程序的编译与运行:gcc-ohe11o_wor1dhe11o_wor1d.c或gcc-che11o_wor1d.c或gcc-ohe11o_wor1dhe11o_wor1d.o或./he11o_wor1d.程序基本结构一个MPI程序的各个进程通过调用 MPI函数进行通信，协同完成一项计算任务。 在MPI的C语言接口中，所有函数名均采用MPI_Xxxxx_xxxx的形式，如MPI_Send,MPI_Type_commit等等.MPI的C语言接口函数通常返回一个整数值表示操作成功与否， 返回彳！为MPI_SUCCESS（0表示操作成功，否则表示操作的错误码。 MPI接口中除了函数和SUBROUTINE外，还定义了一组常量及 C变量类型，它们的命名规则为：所有常量的名称全部大写，如 PI_COMM_WORLD,MPI_INT等；而C变量类型