[转帖]并行计算知识概要

翔羽

<p>&nbsp;</p><p>1并行计算的目的<br/>计算机处理问题的规模包括：<br/>&nbsp;输入输出规模<br/>&nbsp;计算规模<br/>&nbsp;内存需求规模<br/>&nbsp;通信规模<br/>分别表示问题求解所需要的：<br/>&nbsp;I/O量<br/>&nbsp;计算量<br/>&nbsp;内存大小<br/>&nbsp;通信量（包括通信次数与通信数据量）<br/>根据消耗资源程度，可分为：<br/>&nbsp;CPU密集应用<br/>&nbsp;disk密集应用<br/>&nbsp;memory密集应用<br/>&nbsp;网络密集应用<br/>不同类型的问题，性能瓶颈也往往不同。并行计算就是要有针对性的消除相应的瓶颈，从而达到缩短计算时间的目的。<br/>2 并行计算机介绍<br/>2.1 分类<br/>根据指令流和数据流的不同，通常把计算机系统分为：<br/>&nbsp;单指令流单数据流（SISD，Single-Instruction Single-Data）<br/>&nbsp;单指令流多数据流（SIMD，Single-Instruction Multiple-Data）<br/>&nbsp;多指令流单数据流（MISD）<br/>&nbsp;多指令流多数据流（MIMD）<br/>并行计算机系统绝大部分为MIMD系统，包括<br/>&nbsp;并行向量机（PVP，Parallel Vector Processor）；<br/>&nbsp;对称多处理机（SMP,Symmetric Multiprocessor）；<br/>&nbsp;大规模并行处理机（MPP，Massively Parallel Processor）；<br/>&nbsp;机群（Cluster）；<br/>&nbsp;分布式共享存储多处理机（DSM，Distributied Shared Memory）<br/>2.2 机群（Cluster）<br/>cluster的每个系统节点都是一个完整的工作站，一个节点可以是一台PC,各个节点一般由商品化的网络互连，节点上的网络接口是松散耦合到I/O总线上的每个节点一般有本地磁盘，一个完整的操作系统驻留在每个节点上。<br/>我国的曙光1000A、曙光2000、曙光3000以及前不久推出的曙光4000L等都是机群架构的并行计算机。<br/>2.3曙光百万亿数据处理超级服务器<br/>40个机柜组成<br/>644个CPU，峰值速度：每秒3万亿次浮点计算<br/>644GB内存<br/>百万亿字节（100TB）存储<br/>最大可“在线”扩展到80个机柜<br/>1300个CPU，峰值速度：每秒6.75万亿次<br/>4000G内存<br/>600T存储<br/>1200A最大电流，160千瓦最大功耗的海量处理系统<br/>3 进程与消息传递：<br/>3.1进程<br/>进程是一个程序，是操作系统中独立存在的可执行的基本程序单位。<br/>3.2 多个进程<br/>&nbsp;多个进程可以同时存在于单机内同一操作系统：由操作系统负责调度分&nbsp;&nbsp; 时共享处理机资源（CPU、内存、存储、外设等）；<br/>&nbsp;进程间相互独立（内存空间不相交）：在操作系统调度下各自独立地运行，例如多个串行应用程序在同一台计算机中运行； <br/>&nbsp;进程间可以相互交换信息：例如数据交换、同步等待<br/>&nbsp;消息是这些交换信息的基本单位，消息传递是指这些信息在进程间的相互交换，是实现进程间通信的唯一方式；<br/>&nbsp;<br/>&nbsp;最基本的消息传递操作：发送消息（send），接受消息（receive），进程同步（barrier），规约（reduction）；<br/>&nbsp;消息传递的实现：共享内存或信号量，用户不必关心；<br/>3.3 消息传递库函数<br/>&nbsp;应用程序接口（API，Apply Program Interface）：提供给应用程序（FORTRAN、C、C++语言）的可直接调用的完成进程间消息传递的某项特定功能的函数；<br/>&nbsp;消息传递库：所有定义的消息传递函数编译形成的软件库，调用其内部函数的应用程序，通过与之联接，即可成为可并行执行的程序；<br/>&nbsp;目前流行的消息传递函数库：PVM、MPICH、LAMMPI等；<br/>4并行算法基本介绍<br/>4.1并行算法的定义与分类<br/>4.1.1算法定义<br/>算法是解题的精确描述，是一组规则，它规定了解决某一特定类型问题的一系列运算。<br/>并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解。<br/>4.1.2算法分类<br/>并行算法就是对并行计算过程的精确描述，并行算法可以从不同的角度分类为：<br/>&nbsp;数值计算并行算法和非数值计算并行算法<br/>&nbsp;同步并行算法和异步并行算法<br/>&nbsp;共享存储并行算法和分布存储并行算法<br/>4.2数值计算与非数值计算<br/>4.1.1数值计算<br/>求解数值计算问题的算法称为数值算法（Numerical Algorithm），数值计算是指基于代数关系运算的计算问题，如矩阵运算、多项式求值、线性代数方程组求解等。科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。<br/>4.1.2非数值计算<br/>非数值计算是指基于比较关系运算，诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算法（Non-numerical Algorithm）。非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题、海量数据挖掘等，近年来广泛关注的生物信息学主要也是非数值计算。<br/>4.3并行设计：<br/>4.3.1不可并行处理<br/>&nbsp;数据相关<br/>1： A＝B+C<br/>2： D＝A×B<br/>其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。<br/>显然，P1和P2不能并行执行。<br/>&nbsp;数据反相关<br/>1： A＝B×C<br/>2： C＝E+D<br/>&nbsp; P1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。也不可并行。<br/>4.3.1并行化处理<br/>并行程序设计需要将问题的并行求解算法转化为特定的适合并行计算模型的并行算法：<br/>&nbsp;&nbsp;&nbsp;&nbsp; P1： A＝B+C<br/>&nbsp;&nbsp;&nbsp;&nbsp; P2： E＝A×D<br/>改为并行算法：<br/>E= B×D +C×D<br/>那么就可以并行为：<br/>11：B×D<br/>&nbsp;&nbsp;&nbsp; P12：C×D<br/>&nbsp;&nbsp;&nbsp; P2：E＝P11+P12<br/>5 MPI（标准消息传递界面：Message Passing Interface）<br/>MPI(Message Passing Interface )是目前最重要的并行编程工具,它具有移植性好功能强大效率高等多种优点,而且有多种不同的免费、高效、实用的版本,几乎所有的并行计算机厂商都提供对它的支持。<br/>MPI其实就是一个库，共有上百个函数调用接口，在FORTRAN和C语言中可以直接对这些函数进行调用，MPI提供的调用虽然很多但最常使用的只有6个，只要会使用FORTRAN或者是C就可以比较容易地掌握MPI的基本功能，只需通过使用这6个函数就可以完成几乎所有的通信功能。<br/>&nbsp;MPI标准：根据应用程序对消息传递功能的需求，全球工业、应用和研究部门联合推出标准的消息传递界面函数，不考虑其具体实现，以保证并行应用程序的可移植性；<br/>&nbsp;MPI的具体实现：消息传递库函数，目前有影响的为MPICH和LAMMPI，我们注重MPICH系列。<br/></p>