并行计算的基本原理

并行计算的基本原理并行计算（ParallelComputing）是指同时使用多种计算资源解决计算问题的过程。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本―使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。第1页，共15页。第2页，共15页。第3页，共15页。并行计算的特点为利用并行计算，通常计算问题表现为以下特征：

（1）将工作分离成离散部分，有助于同时解决；

（2）随时并及时地执行多个程序指令；

（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。

并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。

第4页，共15页。并行计算机的分类并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。SISDSIMDMIMD第5页，共15页。并行计算的术语（1）Task：可计算工作在逻辑上不连续的分区。一个任务通常是一个程序或者类似程序一样的可以被处理器执行的指令集。ParallelTask：一个任务可以被多个处理器安全的并行的执行，产生正确的结果。SerialExecution：程序相继的执行，每次一个状态。在最简单的情况下，单核处理器就是这样运行的。可是，实际上所有并行的任务有一些并行程序的区域一定要串行的执行。ParallelExecution：一个或多个任务同时执行的程序，每个任务同时能够执行相同的或不同的代码语句。Pipelining：不同的处理器单元把一个任务根据输入流来分解成一系列步骤来执行，相当于一条流水线；并行计算的一种。第6页，共15页。并行计算的术语（2)SharedMemory（共享内存）：完全从硬件的视角来描述计算机体系结构，所有的处理器直接存取通用的物理内存（基于总线结构）。在编程的角度上来看，他指出从并行任务看内存是同样的视图，并且能够直接定位存取相同的逻辑内存位置上的内容，不管物理内存是否真的存在。SymmetricMulti-Processor（对称多处理器）：这种硬件体系结构是多处理器共享一个地址空间访问所有资源的模型；共享内存计算。DistributedMemory（分布式存储）：从硬件的角度来看，基于网络存储的物理内存访问是不常见的。在程序模型中，任务只能看到本地机器的内存，当任务执行时一定要用通信才能访问其他机器上的内存空间。Communication：并行任务都需要交换数据。有几种方法可以完成，例如：共享内存总线、网络传输，然而不管用什么方法，真实的数据交换事件通常与通信相关。Synchronization：实时并行任务的调度通常与通信相关。总是通过建立一个程序内的同步点来完成，一个任务在这个程序点上等待，直到另一个任务到达相同的逻辑设备点是才能继续执行。同步至少要等待一个任务，致使并行程序的执行时间增加。第7页，共15页。并行计算的术语(3)ObservedSpeedup：测量代码并行化之后的加速比。这是最简单也最广泛使用的测量并行程序性能的方法。ParallelOverhead（并行开销）：对并行任务调度花费的时间没有做有用的工作。并行开销可以包含如下因素：任务启动时间、同步、数据通信、并行编译器、库、工具、操作系统等花费的软件开销，任务终止的时间等。Scalability：指的是并行系统通过增加更多的处理器的个数按比例提高并行性能的能力。促进可扩展性的因素有：硬件——特别是内存、CPU带宽和网络通信，应用程序算法，相关的并行开销、特定的应用和编码方式的特征。Multi-coreProcessors：一个CPU上有多个处理器。ClusterComputing：用一般的处理器单元（处理器、网络、SMP）来构建并行系统。Supercomputing/HighPerformanceComputing（高性能计算）：使用世界上最快最大的机器来解决大规模的问题。第8页，共15页。并行计算机的存储结构共享内存、分布式内存、混合型分布式共享内寸

第9页，共15页。接点间的连接按连接方式分类：

Completely-connected,Star,Tree,LinearArrayandRing,Hypercube集群计算机：通过高速网络LAN将PC机或工作站连结而成。第10页，共15页。并行编程1.线程模型（OpenMP,POSIX)2.消息传递模型（MPI，PVM）3.数据并行模型（HPF）第11页，共15页。问题分解1.作用域分解：与问题相关的数据将会被分解。每个并行的任务只能使用部分数据。2.功能分解：关注要被完成的计算而不是操作数据的计算。问题是根据当前一定要完成的任务划分的。每个任务完成全部工作的一部分。第12页，共15页。关注的问题1、通信2、同步3、数据依赖4、负载平衡5、I/O第13页，共15页。并行计算的性能分析1、加速比（speedup)2、并行效率第14页，共15页。内容梗概并行计算的基本原理。并行计算的主要目的是快速解决大型且复杂的计算问题。（3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。并行计算科学中主要研究的是空间上的并行问题。一个任务通常是一个程序或者类似程序一样的可以被处理器执行的指令集。ParallelTask：一个任务可以被多个处理器安全的并行的执行，产生正确的结果。在最简单的情况下，单核处理器就是这样运行的。可是，实际上所有并行的任务有一些并行程序的区域一定要串行的执行。ParallelExecution：一个或多个任务同时执行的程序，每个任务同时能够执行相同的或不同的代码语句。DistributedMemory（分布式存储）：从硬件的角度来看，基于网络存储的物理内存访问是不常见的。有几种方法可以完成，例如：共享内存总线、网络传输，然而不管用什么方法，真实的数据交