并行计算简介Blaise Barney, 劳伦斯利弗莫尔国家实验室译者：卢洋，同济大学原文地址：https:///tutorials/parallel_comp/目录1 摘要2 概述2.1 什么是并行计算2.2 为什么使用并行计算3 概念和术语3.1 冯诺依曼体系结构3.2 Flynn经典分类法3.3 一些通用的并行术语4 并行计算机存储结构4.1 共享内存4.2 分布式内存4.3 混合型分布式共享内存5 并行编程模型5.1 概览5.2 共享内存模型5.3 线程模型5.4 消息传递模型5.5 数据并行模型5.6 其他模型6 设计并行程序6.1 自动化vs. 手工并行化6.2 问题的理解和程序6.3 问题分解6.4 通信6.5 同步6.6 数据依赖6.7 负载平衡6.8 粒度6.9 I/O6.10 并行程序设计的限制和消耗6.11 性能分析与调整7 并行示例7.1 数组程序7.2 PI 的计算7.3 简单的加热等式7.4 一维的波等式8 参考和更多信息1 摘要为了让新手更加容易熟悉此话题，本教程覆盖了并行计算中比较基础的部分。

首先在概述中介绍的是与并行计算相关的术语和概念。

然后探索并行存储模型和编程模型这两个话题。

之后讨论一些并行程序设计相关的问题。

本教程还包含了几个将简单串行化程序并行化的例子。

无基础亦可阅读。

2 概述2.1 什么是并行计算传统上，一般的软件设计都是串行式计算：-软件在一台只有一个CPU的电脑上运行；-问题被分解成离散的指令序列；-指令被一条接一条的执行；-在任何时间CPU上最多只有一条指令在运行图在最简单的情形下，并行计算是使用多个计算资源去解决可计算问题。

-用多核CPU来运行；-问题被分解成离散的部分可以被同时解决；-每一部分被细分成一系列指令；-每一部分的指令可以在不同的CPU上同时的执行；-图计算资源可以包括：-多核CPU；-任意数量的CPU用网络连接起来；-或者以上两者结合；可计算问题通常展示出如下的特性：-能分解成可以同时解决的离散的工作块；-同一时刻可以执行多条程序指令；-通常用多个计算资源解决问题所花的时间要比单个计算资源要短；●宇宙是并行的并行计算是由串行计算发展而来，试图去模仿真实世界中事物的处理过程：许多复杂的互相关联的事件同时发生，例如：银河系的变换；行星的运动；天气和海洋的变化；交通堵塞；大陆板块迁移；炊烟升起；自动的流水线；建造空间飞行器；开车买汉堡；●并行计算的用途：在历史上，并行计算被认为是高端计算，并用于为复杂的科学计算和基于真实世界的工程问题建模。

下面是一些例子：-大气层、地球、环境-物理学应用、核能、原子能、凝聚态、高压、溶解、光电子；-生物科学、生物工程、基因学-化学、分子科学-地理和地震学-机械工程、从弥补术到空间飞行器-电气工程、电路设计、微电子学-计算机科学、数学今天，商务应用是推动快速计算机发展的更大的推动力。

这些应用需要用复杂的方法处理大量数据。

例如：-数据库、数据挖掘-石油勘探-网络搜索引擎、基于网络的商务服务-医学成像和诊断-制药设计-国有企业或跨国企业的管理-金融经济建模-高级制图和虚拟现实、特别实在娱乐事业上-网络视频和多媒体技术-协同工作环境2.2 为什么使用并行计算●主要的原因有：节省时间和成本：理论上，使用更多的资源会使一个任务提前完成，而且会节约潜在的成本。

况且可以使用便宜的、甚至市面将要淘汰的CPU来构建并行聚簇。

●解决更大规模的问题：很多问题是相当庞大而复杂的，尤其是当计算机的内存受到限制的时候，用单个计算机来解决是不切实际或者根本不可能的。

例如：-"Grand Challenge" (/wiki/Grand_Challenge) 问题需要Peta级浮点运算能力和存储空间的计算资源。

-网络搜索引擎和网络数据库每秒钟要执行上百万次的处理。

支持并行：单一的计算资源在同一时刻只能做一件事情。

多个计算资源能够同时做很多事情。

例如：Access Grid (/)提供一个全球的合作网络，在这里来自世界上不同国家的人们可以开会并―现场‖指导工作。

使用非本地资源：当缺少本地计算资源的时候可以使用广泛的网络或Internet计算资源。

例如：-SETI@home () 使用超过330000个计算机来执行每秒超过528T次浮点运算；(August 04, 2008)-Folding@home ()使用超过340,000 计算机来执行每秒4.2P次浮点运算(November 4, 2008)串行计算的限制：在理论上和实际上，想要轻易地制造更快的串行计算机存在着巨大的限制。

-传输速度——线性计算机的执行速度直接取决于数据在硬件中传输的速度。

光速的绝对限制是每纳秒30cm，铜导线是每纳秒9cm。

不断提升的执行速度更加靠近极限。

-微型化的极限——处理器技术使芯片集成了更多的晶体管。

但是，即使使用分子或者原子级别的组件也会很快达到芯片集成晶体管的极限。

-经济上的限制——让单个芯片变得更快需要增加昂贵的投入。

用多个一般的芯片来取代单个高性能的芯片或许性能会更好而且更便宜。

现在的计算机体系结构越来越依赖于硬件层次的并行来提高性能：-多个执行单元-管道指令-多核谁？什么？ 给出了并行计算用户的数据统计——下面的图标只是一个样例。

下面几点需要注意：-扇形可能重叠——例如，研究的部分可能在经典研究中。

作者不得不二选一。

-目前为止未分类的最大应用可能是多种应用集合。

未来在过去的20年里，更快速网络、分布式系统、多核处理器体系结构（甚至是在桌面应用级别）的发展趋势已经很清楚的指出并行化是未来科学计算的发展方向。

3 概念和术语3.1 冯诺依曼体系结构以匈牙利数学家约翰. 冯诺依曼命名，他是第一个在1945年的论文中提出通用电子计算机必要条件的创始人。

从那时开始，实际上所有的计算机都遵从这个基本的设计，区别于早期的硬布线编程的计算机设计。

主要有五个主要的部件构成：-内存-控制单元-逻辑计算单元-输入输出读/写随机存储内存用于储存程序指令和数据：-程序指令是告诉计算机做什么事的代码数据-数据是程序用到的简单数据控制单元从内存中取回指令/数据，解码指令然后连续协调操作来完成编码工作。

计算单元完成基本的计算操作。

输入输出是用户操作的界面。

3.2 Flynn经典分类法有很多方法给并行计算机分类，其中，Flynn分类法从1966年开始使用被大家广为接受。

Flynn分类是利用两个独立的标准指令和数据对多核计算机体系结构进行划分的。

每一个标准有两种可能的值：单个或者多个。

下面的矩阵定义了4中可能的Flynn分类：-S I S D：单指令单数据-S I M D：单指令多数据-M I S D：多指令单数据-M I M D：多指令多数据-单指令单数据（SISD）串行计算机单个指令：在一个系统时钟周期只有一条指令可以被执行。

单数据：在一个系统时钟周期只有一个数据流可以被用来输入。

确定性执行。

这是迄今为止最老的，但大多数通用计算机都是这个类型。

例如：老一代的大型机、微机和工作站，还有现在大多数的PC机。

UNIVAC1IBM 360CRAY1CDC 7600PDP1Dell LaptopØ单指令多数据：并行计算机的一种单指令：所有的处理单元在给定的时钟周期只能执行相同的指令。

多数据：每一个处理器单元可以同时处理不同的数据元素。

最适合处理高度规则的问题，如图形图像处理。

同步，确定性执行。

两类：处理器数组和向量流水线。

例如：处理器矩阵：Connection Machine CM-2,MasPar MP-1 & MP-2, ILLIAC IV；向量流水线：IBM 9000, Cray X-MP, Y-MP & C90, Fujitsu VP, NEC SX-2, Hitachi S820, ETA10。

最先进的计算机，特别是带有图形处理器单元的计算机都使用SIMD指令集和执行单元。

ILLIAC IVMasParCray X-MPCray Y-MPThinking Machines CM-2Cell Processor (GPU)Ø 多指令单数据（MISD）：单数据流进入多处理器单元。

每一个处理器单元通过独立的指令流在独立的操作数据。

这种计算机几乎在市面上找不到。

有一个实验机Carnegie-Mellon C.mmp可能用于单信号流上多频率过滤、用多密码学算法破解单码信息。

Ø 多指令多数据（MIMD）现在，大多数通用并行计算机都是这种。

多指令：每个处理器可以执行不同的指令流多数据：每个处理器可以用不同的数据流。

同步或异步、确定性或非确定性执行。

例如：大多数的超级计算机、网格计算机、多核SMP计算机，多核PC机。

注意：很多MIMD体系结构也包含SIMD执行子构件。

3.3 一些通用的并行术语像其他的东西一样，并行计算机有他自己的术语。

下面列出了一些与并行计算相关的通用的术语。

其中大多数都会在后面再进行详细的讨论。

Task：可计算工作在逻辑上不连续的分区。

一个任务通常是一个程序或者类似程序一样的可以被处理器执行的指令集。

Parallel Task：一个任务可以被多个处理器安全的并行的执行，产生正确的结果。

Serial Execution：程序相继的执行，每次一个状态。

在最简单的情况下，单核处理器就是这样运行的。

可是，实际上所有并行的任务有一些并行程序的区域一定要串行的执行。

Parallel Execution：一个或多个任务同时执行的程序，每个任务同时能够执行相同的或不同的代码语句。

Pipelining：不同的处理器单元把一个任务根据输入流来分解成一系列步骤来执行，相当于一条流水线；并行计算的一种。

Shared Memory（共享内存）：完全从硬件的视角来描述计算机体系结构，所有的处理器直接存取通用的物理内存（基于总线结构）。

在编程的角度上来看，他指出从并行任务看内存是同样的视图，并且能够直接定位存取相同的逻辑内存位置上的内容，不管物理内存是否真的存在。

Symmetric Multi-Processor（对称多处理器）：这种硬件体系结构是多处理器共享一个地址空间访问所有资源的模型；共享内存计算。

Distributed Memory（分布式存储）：从硬件的角度来看，基于网络存储的物理内存访问是不常见的。

在程序模型中，任务只能看到本地机器的内存，当任务执行时一定要用通信才能访问其他机器上的内存空间。

Communication：并行任务都需要交换数据。

有几种方法可以完成，例如：共享内存总线、网络传输，然而不管用什么方法，真实的数据交换事件通常与通信相关。

Synchronization：实时并行任务的调度通常与通信相关。