理解矩阵乘法 - 阮一峰的网络日志
理解矩阵乘法
大多数人在高中，或者大学低年级，都上过一门课《线性代数》。这门课其实是教矩阵。
刚学的时候，还蛮简单的，矩阵加法就是相同位置的数字加一下。
矩阵减法也类似。
矩阵乘以一个常数，就是所有位置都乘以这个数。
但是，等到矩阵乘以矩阵的时候，一切就不一样了。
这个结果是怎么算出来的？
教科书告诉你，计算规则是，第一个矩阵第一行的每个数字（2和1），各自乘以第二个矩阵第一列对应位置的数字（1和1），然后将乘积相加（ 2 x 1 + 1 x 1），得到结果矩阵左上角的那个值3。
也就是说，结果矩阵第m行与第n列交叉位置的那个值，等于第一个矩阵第m行与第二个矩阵第n列，对应位置的每个值的乘积之和。
怎么会有这么奇怪的规则？
我一直没理解这个规则的含义，导致《线性代数》这门课就没学懂。研究生时发现，线性代数是向量计算的基础，很多重要的数学模型都要用到向量计算，所以我做不了复杂模型。这一直让我有点伤心。
前些日子，受到的启发，我终于想通了，矩阵乘法到底是什么东西。关键就是一句话，矩阵的本质就是线性方程式，两者是一一对应关系。如果从线性方程式的角度，理解矩阵乘法就毫无难度。
下面是一组线性方程式。
矩阵的最初目的，只是为线性方程组提供一个简写形式。
老实说，从上面这种写法，已经能看出矩阵乘法的规则了：系数矩阵第一行的2和1，各自与 x 和 y 的乘积之和，等于3。不过，这不算严格的证明，只是线性方程式转为矩阵的书写规则。
下面才是严格的证明。有三组未知数 x、y 和 t，其中 x 和 y 的关系如下。
x 和 t 的关系如下。
有了这两组方程式，就可以求 y 和 t 的关系。从矩阵来看，很显然，只要把第二个矩阵代入第一个矩阵即可。
从方程式来看，也可以把第二个方程组代入第一个方程组。
上面的方程组可以整理成下面的形式。
最后那个矩阵等式，与前面的矩阵等式一对照，就会得到下面的关系。
矩阵乘法的计算规则，从而得到证明。
=========================================
以下为广告部分。欢迎大家在我的网络日志。
[赞助商广告]
如果你想换工作，花五分钟，浏览一下 ，也许人生从此就会不同。
的目标是，只要你有2年以上的互联网工作经验（一线互联网公司更好），它就极有可能帮你拿到年薪 20W--80W 的 Offer。
它最近对514位用户的一份，有两点发现。
（1）所有离职的工程师之中，BAT员工最受欢迎，新工作的薪酬通常可以翻番。
（2）只有40%的程序员跳槽去了C轮、D轮和上市公司，其余60%都去了天使轮、A轮和B轮的公司，其中不乏资深的高级程序员。原因是这些创业公司刚刚起步、产品模式初步得到认可，上升空间大、技术人才需求量大、愿意给出较多的期权。
结合上面两点，年青程序员可以这样设计自己的职业生涯：
1、至少有一次大公司的成功工作经历。
所谓"成功"，是指参与过知名的产品开发或主力项目经验。这一般代表你已经具备：良好的代码规范、团队协作能力、与大牛一起工作的开阔眼界成熟的技术体系。
2、然后，加入一家高速发展的创业公司。
帮助你实现这条职业道路。
统计学里面，正态分布（normal distribution）最常见。男女身高、寿命、血压、考试成绩、测量误差等等，都属于正态分布。
眼下最热门的技术，绝对是人工智能。
图像识别（image recognition）是现在的热门技术。
本文通过五个例子，介绍蒙特卡罗方法（Monte Carlo Method）。线性代数公式大全_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
线性代数公式大全
&&包括行列式、矩阵、矩阵的初等变换与线性方程组、向量组的线性相关性、相似矩阵和二次型的概念、定理、推论公式。
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢2003高性能计算培训_甜梦文库
2003高性能计算培训
2003 年高性能计算培训班材料?迟学斌 张林波 莫则尧 中国科学院计算机网络信息中心 中国科学院数学与系统科学研究院 北京应用物理与计算数学研究所 2003 年 8 月 28 日?本文档及程序示例可从 http://lssc./training2003 下载目 录第一部分第一章 第二章并行计算基础13 23 37 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 37 38 38 38 38 39 39 39 40 41 42 43 43 43 44 45 47 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 47 48 48 49 49 50 51 52 53 55 55 56并行计算基础知识 并行计算机体系结构第三章 Linux 机群 §3.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . §3.2 构建 Linux 机群的要素 . . . . . . . . . . . . . . §3.3 几种典型的 Linux 机群结构 . . . . . . . . . . . §3.3.1 单台微机 . . . . . . . . . . . . . . . . . . §3.3.2 由几台日常使用的微机构成的机群 . . . §3.3.3 专用并行机群 . . . . . . . . . . . . . . . §3.4 在单机上安装、 配置 MPI 并行环境 . . . . . . §3.4.1 Linux 的安装 . . . . . . . . . . . . . . . §3.4.2 MPICH 的安装 . . . . . . . . . . . . . . §3.5 在联网的多台机器上安装、配置 MPI 并行环境 §3.5.1 设置 NFS . . . . . . . . . . . . . . . . . §3.5.2 设置 NIS . . . . . . . . . . . . . . . . . . §3.5.3 设置 rsh . . . . . . . . . . . . . . . . . . §3.5.4 MPICH 的安装 . . . . . . . . . . . . . . §3.5.5 MPICH 程序的编译、运行 . . . . . . . . §3.6 专用并行机群系统 . . . . . . . . . . . . . . . . §3.7 组建大型机群系统需要考虑的一些问题 . . . . 第四章 矩阵并行计算 §4.1 矩阵相乘的若干并行算法 . . . . . . . . . . . . §4.1.1 行列划分算法 . . . . . . . . . . . . . . . §4.1.2 行行划分算法 . . . . . . . . . . . . . . . §4.1.3 列列划分算法 . . . . . . . . . . . . . . . §4.1.4 列行划分算法 . . . . . . . . . . . . . . . §4.1.5 Cannon 算法 . . . . . . . . . . . . . . . . §4.2 线性方程组的解法 . . . . . . . . . . . . . . . . §4.2.1 分布式系统的并行 LU 分解算法 . . . . §4.2.2 具有共享存储系统的并行 LU 分解算法 §4.2.3 三角方程组的并行解法 . . . . . . . . . . §4.3 对称正定线性方程组的并行解法 . . . . . . . . §4.3.1 Cholesky 分解列格式的并行计算 . . . . §4.3.2 双曲变换 Cholesky 分解 . . . . . . . . .iii目§4.3.3 修正的双曲变换 Cholesky 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . §4.4 三对角方程组的并行解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . §4.4.1 递推法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . §4.4.2 分裂法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . §4.5 异步并行迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . §4.5.1 异步并行迭代法基础 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . §4.5.2 线性迭代的一般收敛性结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .录58 59 59 61 61 62 62第二部分第五章 §5.1 §5.2 §5.3 §5.4 §5.5 §5.6 §5.7 §5.8 §5.9 §5.10 §5.11 §5.12 §5.13 §5.14 §5.15 §5.16 §5.17 §5.18MPI 并行程序设计6567 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 68 68 71 73 73 78 82 84 85 85 90 93 93 93 97消息传递并行程序设计平台 MPI MPI 并行环境管理函数 . . . . . . 进程控制函数 . . . . . . . . . . . . MPI 进程组操作函数 . . . . . . . . MPI 通信子操作 . . . . . . . . . . 点到点通信函数 . . . . . . . . . . . 阻塞式通信函数 . . . . . . . . . . . 非阻塞式通信函数 . . . . . . . . . 特殊的点到点通信函数 . . . . . . . MPI 的通信模式 . . . . . . . . . . 用户定义的数据类型与打包 . . . 用户定义的数据类型 . . . . . . . MPI 的数据打包与拆包 . . . . . . 聚合通信 . . . . . . . . . . . . . . 障碍同步 . . . . . . . . . . . . . . 单点与多点通信函数 . . . . . . . 多点与多点通信函数 . . . . . . . 全局归约操作 . . . . . . . . . . . 进程拓扑结构 . . . . . . . . . . . §5.18.1 迪卡尔拓扑结构 . . . . . . §5.18.2 一般拓扑结构 . . . . . . . §5.18.3 底层支持函数 . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 113第六章 文件输入输出 (MPICIO) §6.1 基本术语 . . . . . . . . . . §6.2 基本文件操作 . . . . . . . §6.2.1 打开 MPI 文件 . . §6.2.2 关闭 MPI 文件 . . §6.2.3 删除文件 . . . . . . §6.2.4 设定文件长度 . . . §6.2.5 为文件预留空间 . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115目录iii §6.2.6 查询文件长度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116§6.3 查询文件参数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 §6.3.1 查询打开文件的进程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 §6.3.2 查询文件访问模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 §6.4 设定文件视窗 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 §6.4.1 文件中的数据表示格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 §6.4.2 可移植数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 §6.4.3 查询数据类型相应于文件数据表示格式的域 . . . . . . . . . . . . . . . . . . . . 118 §6.5 文件读写操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 §6.5.1 使用显式位移的阻塞型文件读写 . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 §6.5.2 使用独立文件指针的阻塞型文件读写 . . . . . . . . . . . . . . . . . . . . . . . . . 119 §6.5.3 使用共享文件指针的阻塞型文件读写 . . . . . . . . . . . . . . . . . . . . . . . . . 120 §6.5.4 非阻塞型文件读写函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 §6.5.5 分裂型文件读写函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 §6.6 文件指针操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 §6.6.1 独立文件指针操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 §6.6.2 共享文件指针操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 §6.6.3 文件位移在文件中的绝对地址 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 §6.7 不同进程对同一文件读写操作的相容性 . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 §6.7.1 设定文件访问的原子性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 §6.7.2 查询 atomicity 的当前值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 §6.7.3 文件读写与存储设备间的同步 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 §6.8 子数组数据类型创建函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124第七章 MPI 程序示例 §7.1 矩阵乘积 . . . . . . . . . . . §7.1.1 算法描述 . . . . . . . §7.1.2 MPI 并行程序 . . . . §7.1.3 MPI 并行程序的改进 §7.2 Poisson 方程求解 . . . . . . §7.2.1 并行算法设计 . . . . §7.2.2 MPI 并行程序设计 . §7.2.3 MPI 并行程序的改进 参考文献 附127 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 143 145 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146录 §A.1 Linpack 性能测试 . . . . . . . . . . . §A.1.1 相关链接 . . . . . . . . . . . . §A.1.2 HPL 简介 . . . . . . . . . . . . §A.1.3 适用于 Linux 的 BLAS 库 . . . §A.1.4 HPL 的编译、运行与性能优化第一部分 并行计算基础第一章 并行计算基础知识1. 并行计算机的发展1.1 计算机系统发展简史计算机的起源可以追溯到欧洲文艺复兴时期。16-17 世纪的思想解放和社会大变革，大 大促进了自然科学技术的发展， 其中制造一台能帮助人进行计算的机器， 就是最耀眼的思想 火花之一。 1614 年，苏格兰人 John Napier 发表了关于可以计算四则运算和方根运算的精巧装置的 论文。1642 年，法国数学家 Pascal 发明能进行八位计算的计算尺。1848 年，英国数学家 George Boole 创立二进制代数学。1880 年美国普查人工用了 7 年的时间进行统计，而 1890 年，Herman Hollerith 用穿孔卡片存储数据，并设计了机器，仅仅用了 6 个周就得出了准确 的数据（ 人） 。1896 年，Herman Hollerith 创办了 IBM 公司的前身。 这些“计算机” ，都是基于机械运行方式，还没有计算机的灵魂：逻辑运算。而在这之 后，随着电子技术的飞速发展，计算机开始了质的转变。 1943 年到 1959 年时期的计算机通常被称作第一代计算机。使用真空电子管，所有的程 序都是用机器码编写，使用穿孔卡片。1946 年，John W. Mauchly 和 J. Presper Eckert 负责研 制的 ENIAC (Electronic Numerical Integrator and Computer)是第一台真正意义上的数字电子 计算机。重 30 吨，18000 个电子管，功率 25 千瓦。主要用于弹道计算和氢弹研制。 1949 年，科学杂志大胆预测“未来的计算机不会超过 1.5 吨。 ” 真空管时代的计算机尽管已经步入了现代计算机的范畴，但其体积之大、能耗之高、故 障之多、 价格之贵大大制约了它的普及应用。 直到 1947 年， Bell 实验室的 William B. Shockley、 John Bardeen 和 Walter H. Brattain.发明了晶体管，电子计算机才找到了腾飞的起点，开辟了 电子时代新纪元。 1959 年到 1964 年间设计的计算机一般被称为第二代计算机。 大量采用了晶体管和印刷 电路。计算机体积不断缩小，功能不断增强，可以运行 FORTRAN 和 COBOL ，接收英文 字符命令。出现大量应用软件。 尽管晶体管的采用大大缩小了计算机的体积、降低了其价格，减少了故障。但离人们的 要求仍差很远，而且各行业对计算机也产生了较大的需求，生产更强、更轻便、更便宜的机3器成了当务之急，而集成电路的发明，不仅仅使体积得以减小，更使速度加快，故障减少。 1958 年，在 Robert Noyce（INTEL 公司的创始人）的领导下，继发明了集成电路后， 又推出了微处理器。 1964 年到 1972 年的计算机一般被称为第三代计算机。大量使用集成电路，典型的机型 是 IBM360 系列。1972 年以后的计算机习惯上被称为第四代计算机。基于大规模集成电路， 及后来的超大规模集成电路。计算机功能更强，体积更小。 在这之前， 计算机技术主要集中在大型机和小型机领域发展， 但随着超大规模集成电路 和微处理器技术的进步，计算机进入寻常百姓家的技术障碍已突破。特别是从 INTEL 发布 其面向个人机的微处理器 8080 的同时，互联网技术、多媒体技术也得到了空前的发展，计 算机真正开始改变人们的生活。 1976 年，Cray-1，第一台商用超级计算机。集成了 20 万个晶体管，每秒进行 1.5 亿次 浮点运算。今天，INTEL 已经推出主频达到 3.06Ghz 的处理器，并已经推出了 4.7G 主频的 Pentium4 样品。 与整个人类的发展历程相比、与传统科学技术相比，计算机的历史才刚刚开始书写，我 们正置身其中，感受其日新月异的变化，被计算机大潮裹挟着丝毫不得停歇。1.2 并行计算机发展简述40 年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并 行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操 作系统） 、应用软件，最后随着问题求解环境的发展而达到顶峰。创建和使用并行计算机的 主要原因是因为并行计算机是解决单处理器速度瓶颈的最好方法之一。 并行计算机是由一组处理单元组成的， 这组处理单元通过相互之间的通信与协作， 以更 快的速度共同完成一项大规模的计算任务。 因此， 并行计算机的两个最主要的组成部分是计 算节点和节点间的通信与协作机制。 并行计算机体系结构的发展也主要体现在计算节点性能 的提高以及节点间通信技术的改进两方面。 60 年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也 更加小巧和廉价。 这些技术发展的结果导致了并行计算机的出现， 这一时期的并行计算机多 是规模不大的共享存储多处理器系统，即所谓大型主机（Mainframe） 。IBM 360 是这一时期 的典型代表。 到了 60 年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出4现了。 与单纯提高时钟频率相比， 这些并行特性在处理器内部的应用大大提高了并行计算机 系统的性能。伊利诺依大学和 Burroughs 公司此时开始实施 Illiac IV 计划，研制一台 64 个 CPU 的 SIMD 主机系统，它涉及到硬件技术、体系结构、I/O 设备、操作系统、程序设计语 言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小了的 16 CPU 系统终于在 1975 年面世时，整个计算机界已经发生了巨大变化。 首先是存储系统概念的革新，提出虚拟存储和缓存的思想。IBM 360/85 系统与 360/91 是属于同一系列的两个机型，360/91 的主频高于 360/85，所选用的内存速度也较快，并且 采用了动态调度的指令流水线；但是，360/85 的整体性能却高于 360/91，唯一的原因就是 前者采用了缓存技术，而后者则没有。 其次是半导体存储器开始代替磁芯存储器。 最初， 半导体存储器只是在某些机器被用作 缓存，而 CDC 7600 则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储 器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到了计算 机中。元器件技术的这两大革命性突破，使得 Illiac IV 的设计者们在底层硬件以及并行体系 结构方面提出的种种改进都大为逊色。 1976 年 CRAY-1 问世以后， 向量计算机从此牢牢地控制着整个高性能计算机市场 15 年。 CRAY-1 对所使用的逻辑电路进行了精心的设计， 采用了我们如今称为 RISC 的精简指令集， 还引入了向量寄存器，以完成向量运算。这一系列全新技术手段的使用，使 CRAY-1 的主频 达到了 80 MHz。 微处理器随着机器的字长从 4 位、8 位、16 位一直增加到 32 位，其性能也随之显著提 高。正是因为看到了微处理器的这种潜力，卡内基-梅隆大学开始在当时流行的 DEC PDP 11 小型计算机的基础上研制成功一台由 16 个 PDP 11/40 处理机通过交叉开关与 16 个共享存储 器模块相连接而成的共享存储多处理器系统 C.mmp。 从 80 年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于 SMP 方式 的总线协议， 而伯克利加州大学则对总线协议进行了扩展， 提出了 Cache 一致性问题的处理 方案。从此，C.mmp 开创出的共享存储多处理器之路越走越宽；现在，这种体系结构已经 基本上统治了服务器和桌面工作站市场。 同一时期，基于消息传递机制的并行计算机也开始不断涌现。80 年代中期，加州理工 成功地将 64 个 i 处理器通过超立方体互连结构连结起来。 此后， 便先后出现了 Intel iPSC 系列、INMOS Transputer 系列，Intel Paragon 以及 IBM SP 的前身 Vulcan 等基于消息 传递机制的并行计算机。 80 年代末到 90 年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM5将大量早期 RISC 微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享 存储器缓存一致的同时，使系统具有一定的可扩展性（Scalability） 。90 年代初期，斯坦福大 学提出了 DASH 计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布 式共享存储器的缓存一致性。后来，IEEE 在此基础上提出了缓存一致性协议的标准。 90 年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的 CM-5 除大量 采用商品化的微处理器以外， 也允许用户层的程序传递一些简单的消息； CRAY T3D 是一台 NUMA 结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并 采取了一些减少消息传递延迟的技术。 随着商品化微处理器、网络设备的发展，以及 MPI/PVM 等并行编程标准的发布，机群 架构的并行计算机出现。IBM SP2 系列机群系统就是其中的典型代表。在这些系统中，各个 节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。 今天，越来越多的并行计算机系统采用商品化的微处理器加上商品化的互连网络构造， 这种分布存储的并行计算机系统称为机群。 国内几乎所有的高性能计算机厂商都生产这种具 有极高性能价格比的高性能计算机， 并行计算机就进入了一个新的时代， 并行计算的应用达 到了前所未有的广度和深度。1.3 可扩展的并行计算机体系结构根据指令流和数据流的不同，通常把计算机系统分为：单指令流单数据流（SISD） 、单 指令流多数据流（SIMD） 、多指令流单数据流（MISD） 、多指令流多数据流（MIMD）四类。 并行计算机系统除少量专用的 SIMD 系统外，绝大部分为 MIMD 系统，包括并行向量机 （PVP，Parallel Vector Processor） ；对称多处理机（SMP,Symmetric Multiprocessor） ；大规模 并行处理机（MPP，Massively Parallel Processor） ；机群（Cluster） ；分布式共享存储多处理 机（DSM，Distributied Shared Memory） 。这 5 种并行计算机的结构模型参见图 1。6VPVPVPP/CP/CP/C交 叉 开 关总 线 或 交 叉 开 关SMSM （ A）SMSMSM（B）MBSMMB P/CMB P/CMB P/C LMP/C LM DIR NICLMLM DIRNICNIC NIC（C）定 制 网 络 MB P/C M B LD NIC IOB LD NIC MB P/C M B IOB（D）定 制 网 络（E）定 制 网 络图 1 MIMD 系统结构示意图 其中 B： （Bridge）是存储总线和 I/O 总线的接口；DIR： （Cache Directory）是高速缓存目录； IOB： （I/O Bus）是 I/O 总线；LD： （Local Disk）是本地硬盘；MB： （Memory Bus）是存储 器总线； NIC： （Network Interface Circuitry） 是网络接口电路； P/C： （Microprocessor and Cache） 是微处理器和高速缓存；SM： （Shared Memory）是共享存储器。 PVP 典型的并行向量处理机结构示意图如图 1 （A） 。 我国的银河 1 号、 目前全球 top500 中排名第一的地球模拟器等都是 PVP。专门设计定制的高带宽交叉开关网络将专门设计定 制的向量处理器 VP 与共享存储模块连接起来，一般不使用高速缓存，而是使用大量的向量 寄存器和指令缓冲器。 SMP 对称多处理机的结构示意图如图 1（B） 。我国曙光 1 号，SGI Power Challenge 等 大量的服务器或工作站都是这类机器。SMP 系统一般使用商品化微处理器，具有片上或外 置高速缓存，经由高速总线（或交叉开关）连向共享存储器。每个处理器可等同地访问共享 存储器、I/O 设备和操作系统服务。SMP 的主要特点是：单一操作系统映像，全系统只有一7个操作系统驻留在共享存储器中， 它根据各个处理器的负载情况， 动态地分配各个进程到各 个处理器，并保持各个处理器间的负载平衡；低通信延迟，各个进程通过读/写操作系统提 供的共享数据缓存区来完成处理器间的通信， 其延迟通常小于网络通信延迟； 共享总线带宽， 所有处理器共享总线带宽，完成对内存模块和 I/O 模块的访问。同时，SMP 也具有如下一 些问题：欠可靠，总线、存储器、操作系统失效可能导致系统崩溃；可扩展性较差，由于所 有处理器都共享总线带宽， 而总线带宽每 3 年才增加 2 倍， 赶不上处理器速度和存储容量的 增长步伐，因此 SMP 的处理器个数一般少于 64 个，且只能提供每秒数百亿次的浮点运算。 SMP 的典型代表有：SGI POWER Challenge XL 系列、DEC Alphaserver 、 HP 和 IBM RS6000/R40。 MPP 大规模并行处理机的结构示意图如图（C） 。我国曙光 1000、IBM SP2 都是这种类 型的机器。MPP 一般采用商品化微处理器和专门设计的互连网络，系统可以扩展到数千个 （甚至更多）处理器。 DSM 分布式共享存储多处理机的结构示意图如图 1（D） 。高速缓存目录 DIR 用以支持 分布高速缓存的一致性。处理器对物理分布的共享存储器的访问是不对称的，这也是 DSM 与 SMP 的区别所在。DSM 的典型代表为 SGI 的 Origin2000 和 Origin3000 系列并行机，图 1.2 列出了 SGI Origin2000 的体系结构。相对于 SMP，DSM 具有如下主要特征：物理上分 布存储，内存模块局部在各个节点上，并通过高速互连网络互连，避免了 SMP 访问总线的 带宽瓶颈，增强了并行机的可扩展能力；单一内存地址空间，尽管内存模块分布在各个节点 上， 但是所有这些内存模块都由硬件进行了统一编址， 并通过互连网络形成了并行机的共享 存储器。各个节点既可以访问局部内存单元（本地访问） ，又可以直接访问其他节点的局部 内存单元（远端访问） ；非一致内存访问模式（NUMA） ，由于远端访问必须通过高性能互 连网络， 而本地访问只需要直接访问局部内存模块， 因此远端访问延迟一般是本地访问延迟 的 3 倍以上；单一的系统映像，类似于 SMP，在 DSM 中，用户只看到一个操作系统，它可 以根据各节点的负载情况， 动态地分配进程； 基于 Cache 的数据一致性 通常采用基于目录的 Cache 一致性协议来保证各节点的局部 Cache 数据和存储器中数据的一致性。 同时， 这种 DSM 也称为 CC-NUMA 结构。 DSM 较好地改善了 SMP 的可扩展性能。一般地，DSM 可以扩展到上百个节点，能提 供每秒数千亿次的浮点运算功能。 但由于受 Cache 一致性要求和互连网络性能的限制， 当节 点数目进一步增加时，DSM 并行机的性能也将大幅下降。 机群（或工作站机群，COW）的结构示意图如图（E） 。我国的曙光 1000A、曙光 2000、 曙光 3000 以及前不久推出的曙光 4000L 等都是机群架构的并行计算机。COW 的每个系统 都是一个完整的工作站， 一个节点可以是一台 PC 或 SMP， 各个节点一般由商品化的网络互8连，每个节点一般有本地磁盘，节点上的网络接口是松散耦合到 I/O 总线上的，一个完整的 操作系统驻留在每个节点上。 SMP、MPP、DSM 和 COW 等并行结构趋向融合，DSM 是 SMP 和 MPP 的自然结合， MPP 和 COW 的界限逐渐模糊。 在中国现在使用 PVP 并行向量机很少， 使用最多的是 SMP、 DSM、Cluster 架构的并行计算机。国内主要的高性能计算机厂商如曙光、联想、浪潮生产 的都是 Cluster 架构的并行计算机。 节点为 2/4 个处理器的 SMP， 互连网络为千兆网、 myrinet 等，节点操作系统一般为 Linux。 和 SMP、DSM 等相比，机群在较低的费用下，具有高性能、可扩展性、高吞吐量、易 用性等特点。按照应用目的（科学计算/商业计算）分类，机群可分为高性能机群和高可用 机群；按照节点硬件分类，可以分为 PC 机群、工作站机群、SMP 机群；按照节点操作系统 分类，可以分为 Linux 机群、NT 机群等；按照节点体系结构和操作系统的类型，可分为同 构机群、异构机群等。1.4 机群系统的发展机群系统由节点机、互连网络与通信软件、机群中间件等构成。下面从这三方面叙述机 群系统的发展状况。1.4.1 机群节点的发展机群节点机一般为 PC、工作站、SMP，其基本组成为处理器、内存和缓存、磁盘、系 统总线等构成。20 多年来，微处理器结构（RISC、CISC、VLIW 和向量处理器）和工艺发 展迅速，今天单片 CPU 比 20 年前的超级计算机更为强大。 1）CPU 技术的发展 随着 CPU 主频向 GHz 时代的推进，长期处于实验室阶段的铜工艺取得了突破性进展， 有望取代铝工艺而成为 CPU 制造的主流技术。 铜工艺最大的好处是使 CPU 在高频率下的运 行更加稳定。要解决微处理器提速难题，改进制造工艺只是目前通用的一种方法，采用新型 晶体管结构也是目前业界正在研究的重点课题。从 2000 年底开始，Intel、AMD、IBM、贝 尔实验室都公布了类似的最新科研成果。 2001 年底， Intel 公司宣布发明了一种命名为 “TeraHertz”的晶体管结构，晶体管的切换速度可达每秒 1 万亿次，Intel 将利用该晶体管 制造微处理器，预计 2005 年前其微处理器速度将达 10GHz，2010 年将达 20GHz。AMD 公 司 2001 年底也宣布已成功开发一款迄今为止开关速度最快的 CMOS 晶体管， 开关速度高达 每秒 3.33 万亿(trillion)次，显示了 AMD 公司有能力在十年内将每一芯片的晶体管数目增加920 倍，而令微处理器的性能提升 10 倍。 当前，主流微处理器仍然是 Intel 的 IA-64、IBM 的 Power、Compaq 的 Alpha 和 SUN 的 UtraSPARC、HP 的 PA-RISC 系列、SGI 的 MIPS 和 AMD 的 Opteron 处理器。 Intel 推出第一代的 IA-64 Itanium 后，已成功进军高端服务器市场。新一代 Itanium 在一 枚芯片上集成一级缓存（16KB，数据传输带宽为 19.2GB/s） ，二级缓存（256KB，数据传输 带宽为 72GB/s） ，三级缓存（3MB，数据传输带宽达 64GB/s） ，工作频率达 1.2GHz 以上。 Compaq 在高速处理器领域曾处于领先地位。2001 年 6 月 Compaq 宣布向 Intel 转让 Alpha 微处理器和编译技术、工具及资源。Compaq 在 EV6 之后，曾计划开发 EV7、EV8 甚 至 EV9，具体是 2002 年推出 EV7（0.18?m） ，时钟超过 1 GHz；2004 年能期望获得 EV8， 时钟超过 1.5GHz。IBM 公司目前的主力型号有 POWER3 和 POWER4。POWER4 时钟频率 超过 1GHz。POWER4 之后将开发 POWER4+和 POWER4++或 POWER5。IBM 计划在其推 出 POWER5 之前，使每年的处理器时钟数提高 25%，性能增长 3 倍。 SGI 公司的 MIPS 系列微处理器主要用于 Origin 服务器。MIPS 系列微处理器目前的主 力产品是 R1MHz，800MFLOPS）和 R1MHz，1GFLPOS） 。2002 年将 推出 R1MHz，1.2GFLPOS） 。2003 年推出 R1MHz，3.2GFLPOS） 。2004 年推出 R20000（超过 1GHz，4GFLPOS） 。 AMD 公司 2002 年底推出的 Opteron 处理器是能够兼容 32 位的 64 位处理器，对 Intel 的 Itanium 构成巨大冲击， Itanium 现在为用户所诟病的就是对 Intel 以前的 32 位的应用兼容 性不好。刚刚推出的 Opteron 246（2.0GHz，4.0GFLOPS） 。 未来几年，各厂商将在增加可以同时执行的指令数；采用铜布线等新的半导体技术；采 用 SOI 等先进的加工工艺；安装大容量片内高速缓存；配备高速存储器输入输出的设备， 提高处理器与外部存储器及其他处理器之间的数据速率；增加多媒体功能等多方面持续改 进， 这些高性能微处理器在处理性能方面都将比现有产品有大幅提高。 当前及未来的一些典 型微处理器发展归纳为下表。 表 1 典型微处理器发展预测 2001 年 2002 年 2003 年 Itanium Mckinley Madison 800MHzZ 1.2GHz 2GHz？ R1 RMHz+ 650MHz 800MHz+ EV68C EV7 EV79 1.25GHz 1.2GHz 1.6-1.7GHz PA-8700 PA-8800 PA-MHz 900MHz 1.2G Hz POWER4 POWER4+ POWER4++？10制造商 Intel 公司 SGI 公司 Compaq HP 公司 IBM 公司2004 年 ? R20000 1 GHz+ 转向 IA-64 转向 IA-64 POWER5？SUN 公司 AMD 公司1GHz+ UltraSPARC IV 1GHz1.25GHz？ UltraSPARC V 1.5GHz1.55GHz？ ? Opteron 240~250; 1.4-2.4GHz2 GHz？ ? Opteron 252 2.6GHz2） 节点操作系统 现代操作系统位用户提供两个基本的功能， 第一是使计算机更容易使用， 用户使用的是 操作系统提供的虚拟机而无须与计算机硬件直接打交道。 第二是可让用户共享硬件资源。 多 任务操作系统为每个进程分配要执行的工作， 为每个进程分配内存和系统资源， 在一个进程 中， 至少要分配一个执行的线程或一个可执行单元。 现代操作系统还支持在程序内部对多线 程进行控制，因此并行处理可以进程内多线程的方式进行。 目前机群系统节点中最流行的操作系统恐怕是 Linux 了。linux 最初是由芬兰赫尔辛基 大学计算机系大学生 Linus Torvalds 在从 1990 年底到 1991 年的几个月中陆续编写的，1993 年，Linus 决定转向 GPL 版权。一些软件公司如 Red Hat、InfoMagic 等适时推出以 Linux 为 核心的操作系统版本，大大地推动了 Linux 的商品化。 linux 的主要特点是，开放性、标准化、多用户、多任务，Linux 可以连续运行数月、数 年而无须重新启动，一台 Linux 服务器支持 100-300 个用户毫无问题。Linux 向用户提供三 种界面：用户命令界面、系统调用界面和图形用户界面。Linux 一般由四个部分组成：内核、 Shell、文件系统和实用工具。内核是运行程序和管理磁盘、打印机等硬件设备的核心程序。 它从用户那里接受命令并把命令送到内核去执行。Shell 是系统的用户界面，提供了系统与 内核进行交互操作的一种接口。它接受用户输入的命令，并把它送到内核去执行。实际上 Shell 是一个命令解释器，Shell 有自己的编程语言，它允许用户编写由 Shell 命令组成的程 序。 每个 Linux 系统的用户可以拥有自己的用户界面和 Shell， 用以满足他们自己专门的 Shell 需要。 同 Linux 一样， Shell 也有多种不同的版本。 目前主要有下列版本的 Shell： Bourne Shell （贝尔实验室开发） 、Bash（GNU 的 Bourne Again Shell，是 GNU 操作系统上默认的 Shell） 、 Korn Shell（对 Bourne Shell 的发展，大部分与 Bourne Shell 兼容） 、C Shell（Sun 公司 Shell 的 BSD 版本） 。 Linux 实用工具可以分为三类：编辑器、过滤器、交互程序。 Linux 的内核版本是在 Linus 领导下的开发小组开发出的系统内核的版本号。 一般说来， 以序号的第二位为偶数的版本表明这是一个可以使用的稳定的版本。一些组织和厂商将 Linux 的系统内核与应用程序和文档包装起来， 并提供一些安装界面和系统设定的管理工具，11这样就构成了一个发行套件。1.4.2 机群互连网络机群节点通过使用标准网络协议（如 TCP/IP）或底层协议（如活动消息）来进行通信。 从性能（延迟和带宽）来看，以太网连接并不能提供足够的性能，它的带宽和延迟不能和目 前节点的计算能力很好地匹配，而其它如 SCI、Myrinet 等则提供比较好的性能。机群系统 一般会有几套网络，各有不同功能，根据其功能并考虑性能价格的平衡，选用相应的网络。 10/100/1000Mb 以太网 标准以太网（10Mb/S）已很少用于作为机群系统的互连网络， 目前快速以太网（100Mb/S）往往用于作为机群系统控制网络和监控网络。目前许多机群系 统采用千兆以太网（1000Mb/S）作为计算网络。千兆网络最大的优点是，机群系统计算网 络从快速以太网升级到千兆网， 应用可以平滑过渡。 千兆网络可以采用铜线或光缆进行连接。 Myrinet Myrinet 是 Myricom 提供的全双工互连网络，使用低延迟的开通式路由开关， 通过自动映射网络配置来提供容错。Myrinet 提供低延迟（5 微秒，单向点对点） 、高吞吐率 和可编程板上处理器，其主要缺点是价格比较昂贵。1.4.3 机群中间件和单一系统映像（SSI）如果一群互连的计算机被设计成看起来如同统一的资源， 我们就说该系统实现了单一系 统映像（SSI, Single System Image） 。SSI 是用中间件层实现的，处于操作系统和用户层环境 中间。 SSI 支持的服务包括： 单一入口点， 一个用户可以像连接到单一系统一样连接至机群， 而不是像分布式系统一样连接到单个节点； 单一文件层次， 用户看到的文件系统是文件的单 一层次，目录是在同一根目录下的；单点管理和控制，整个机群可以从用单一 GUI 工具创 建的单一窗口进行管理和控制；单一虚拟网络，任何节点可以通过机群域访问网络连接；单 一内存空间，将属于机群的各节点的内存作为共享内存；单一作业管理系统，用户可以用透 明的作业提交机制在任一节点提交作业等等。 SSI 的优点包括：为整个系统资源和运行情况在任一节点提供一个简单、直观的视图； 使最终用户无须了解应用在什么地方运行； 使操作者无须了解资源的物理位置； 使管理者在 一点上管理整个机群； 使得一个拥有多个进程的并行应用看起来就像一个串行应用等等。 目 前比较成熟的提供机群系统 SSI 的中间件/软件/工具有：NFS（网络文件系统） 、LSF（作业 管理系统）等。 曙光系列机群提供了一套包括机群管理系统、 机群作业管理系统、 机群并行文件系统等 在内的机群系统软件，一定程度上实现了机群的 SSI。122. 并行计算基本概念2.1 并行算法基础知识 2.1.1 并行算法定义与分类算法是解题的精确描述， 是一组有穷的规则， 它规定了解决某一特定类型问题的一系列 运算。并行计算是可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得 问题的求解。并行算法就是对并行计算过程的精确描述。 并行算法可以从不同的角度分类为数值计算并行算法和非数值计算并行算法； 同步并行 算法和异步并行算法；共享存储并行算法和分布存储并行算法。 数值计算是指基于代数关系运算的计算问题，如矩阵运算、多项式求值、线性代数方程 组求解等。求解数值计算问题的算法称为数值算法（Numerical Algorithm） 。科学与工程中 的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。非数值计算是指基于 比较关系运算的一类诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算 法（Non-numerical Algorithm） 。非数值计算在符号类信息处理中获得广泛应用，如数据库领 域的计算问题、海量数据挖掘等，近年来广泛关注的生物信息学主要也是非数值计算。2.1.2 并行算法复杂性对算法进行分析时， 常要使用上界 （Upper Bound） 、 下界 （Lower Bound） 和紧致界 （Tightly Bound）等概念。分别定义如下： 上界 令 f(n)和 g(n)是定义在自然数集合 N 上的两个函数，如果存在正常数 c 和 n0，使得对 于所有 n&=n0，均有 f(n)&=cg(n)，则称 g(n)是 f(n)的一个上界，记做 f(n)=O(g(n))。 下界 令 f(n)和 g(n)是定义在自然数集合 N 上的两个函数，如果存在正常数 c 和 n0，使得对 于所有 n&=n0，均有 f(n)&=cg(n)，则称 g(n)是 f(n)的一个下界，记做 f(n)=Ω(g(n))。 紧致界 令 f(n)和 g(n)是定义在自然数集合 N 上的两个函数，如果存在正常数 c1、c2 和 n0， 使得对于所有 n&=n0 ，均有 c1g(n)&=f(n)&=c2g(n)，则称 g(n)是 f(n)的一个紧致界，记做 f(n)=Θ(g(n))。 在分析算法时， 如果对算法的所有输入分析其平均性态时的复杂度， 则称之为期望复杂 度（Expected Complexity） ，在某些输入时，可以使得算法的时间、空间复杂度最坏，此时13的复杂度称为最坏情况下的复杂度（Worst-Case Complexity） 。2.1.3 并行算法运行时间进行并行计算的两个基本目的是：在问题规模一定的情况下，缩短求解时间；在给定时 间范围内，扩大问题求解规模。并行算法运行时间表示算法开始直到算法执行完毕的时间， 主要包括输入输出（I/O）时间、计算 CPU 时间和并行开销（包括通信、同步等时间） 。并 行开销是进行并行计算而引入的开销。 对于一个具体的并行算法， 对其计算时间的估计通常由上述三部分时间的界的估计所组 成。如果要求输入输出 N 个数据，则认为该算法的 I/O 时间界为 O(N)；如果问题规模为 n， 涉及的计算量一般为 t(n)，则该算法的计算 CPU 时间界为 O(t(n))；对要求通信和同步的次 数为 L、通信量为 M 个数据，则该算法的并行开销为 O(L+M)。2.1.4 问题规模与分类高性能计算机产生和发展的就是为了满足日益增长的大规模科学与工程计算、 事务处理 与商业计算的需求。 问题求解最大规模是并行计算机最重要的指标之一， 也是一个国家高新 技术发展的标志。一般地，问题规模分解为输入输出规模、计算规模、内存需求、通信（同 步）规模，分别表示问题求解所需要的 I/O 量、计算量、内存大小和通信量（包括通信次数 与通信数据量） 。 根据在求解中所消耗资源程度， 问题又相应分为 CPU 密集应用、 memory 密集应用、 disk 密集应用和网络密集应用。针对不同类型的问题，性能瓶颈也往往不同，并行算法就是要又 针对性的消除相应的瓶颈，从而达到缩短计算时间的目的。2.1.5 并行程序中数据相关性机群中的并行通常表现在程序级或任务级。能否将顺序执行的程序转换成语义等价的、 可并行执行的程序，主要取决于程序的结构形式，特别是其中的数据相关性。由于在机群上 并行运行的程序段是异步的， 所以在程序段之间会出现下面的 3 种数据相关。 为叙述简单起 见，仅以赋值语句表示程序段 P。 1) 数据相关 若 P1 左边变量出现在 P2 的右边变量集内时，则称 P2 数据相关于 P1。例如： P1： A＝B+C14P2： D＝A×B 其中，变量 A 是导致 P1 和 P2 发生数据相关的原因。为了保证程序执行的语义正确性，变 量 A 必须是先在 P1 中写入后方可从 P2 中读出，即必须先写后读。显然，P1 和 P2 不能并 行执行。 2) 数据反相关 若 P2 的左边变量出现在 P1 的右边变量集内时，则称 P1 数据反相关于 P2。例如： P1： A＝B×C P2： C＝E+D P1 通过变量 C 数据相关于 P2。为保证语义正确性，必须等 P1 将变量 C 读出后，P2 方可向 变量 C 进行写入操作，即必须先读后写。 3) 数据输出相关 若 P1 和 P2 的左边变量相同，则称 P2 数据输出相关于 P1。例如： P1： A＝B+C P2： A＝D×E 为保证语义正确性，必须保证 P1 先写入 A，然后允许 P2 再写入 A。 除了上述 3 种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。 此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步 读写。但若两个处理机各带有局部存储器，则可降低同步要求。 4） 数据相关判断准则 程序并行性检测主要是判别程序中是否存在前述的各种数据相关。 每个程序段在执行过 程中通常要使用输入和输出这两个分离的变量集。若用 Ii 表示 Pi 程序段中操作所要读取的 存储单元集，用 Oi 表示要写入的存储单元集，则 P1 和 P2 两个程序段能并行执行的伯恩斯 坦准则是： I1∩O2＝Φ，即 P1 的输入变量集与 P2 的输出变量集不相交； I2∩O1＝Φ，即 P2 的输入变量集与 P1 的输出变量集不相交； O1∩O2＝Φ，即 P1 和 P2 的输出变量集不相交。2.2 并行计算模型计算模型是对计算机的抽象。对于算法设计者而言，计算模型为设计、分析和评价算法 提供了基础。冯.偌依曼机就是一个理想的串行计算模型，但现在还没有一个通用的并行计 算模型。下面对 PRAM 模型、LogP 模型进行简单的介绍。152.2.1 PRAM 模型PRAM（Parallel Random Access Machine）模型，即并行随机存取模型，是一种抽象的 并行计算模型。在这个模型中，假设存在着一个容量无限大的共享存储器；每台处理器有简 单的算术运算和逻辑判断功能；在任何时刻各处理器均可以通过共享存储单元交换数据。 PRAM 可分为 SIMD-PRAM 和 MIMD-PRAM。SIMD-PRAM 模型又可以细分为不允许同时 读和同时写（Exclusive-Read and Exclusive-Write）的 PRAM 模型，简记为 PRAM-EREW； 允许同时读但不允许同时写（Concurrent-Read and Exclusive-Write）的 PRAM-CREW 模型； 允许同时读写的 PRAM-CRCW 模型。当然允许同时读写是不现实的，因而又进一步约定为 允许所有的处理器同时写相同的数，此时称为公共（Common）的 PRAM-EREW 模型，简 记为 CPRAM-EREW 模型；只允许最有优先（Priority）的处理器先写，此时称为优先的 PRAM-EREW，简记为 PPRAM-EREW；允许任意（Arbitrary）的处理器自由写，此时称为 任意的 PRAM-EREW，简记为 APRAM-EREW。控制单元控制器 1控制器 2控制器 nP1 LMP2 LMPn LMP1 LMP2 LMPn LM互连网络互连网络全局共享存储器全局共享存储器SIMD-PRAM 计算模型 图 2 PRAM 计算模型MIMD-PRAM 计算模型令 TM 表示某并行算法在并行计算模型 M 上的计算时间，则有： TEREW&=TCREW&=TCRCW TEREW=O(TCREW*logP)=O(TCRCW*logP) 其中，p 为处理器数目，上式的含义是，一个具有时间复杂度 TCREW 和 TCRCW 的算法，可以 在 PRAM-EREW 模型上，花费 logP 倍的时间模拟实现。 PRAM 模型有许多优点，它特别适合并行算法的表达、分析和比较；使用简单，很多 诸如处理器间的通信、存储管理和进程同步等并行计算机的低级细节均隐含在模型中。 PRAM 模型是一个同步模型，因此所有指令均按照锁步操作；共享单一存储器的假定，显 然不适合分布存储的异步的 MIMD 机器；假定每个处理器均可以在单位时间内访问任意存 储单元，而不考虑存取竞争也是不现实的。16为了更准确地抽象并行计算机系统，人们又对 PRAM 模型做了许多修改，主要有存储 竞争模型、延迟模型、局部 PRAM 模型、分层存储模型以及分相 PRAM 模型。分层模型和 分相模型都可看作异步模型。 分相模型（APRAM） ，由 P 个处理器组成，其特点是每个处理器都有其局存、局部时 钟和局部程序；处理器的通信经过共享全局存储器；无全局时钟，各处理器异步独立执行各 自的指令； 处理器任何时间依赖关系需明确地在各处理器的程序中加入同步路障； 一条指令 可以在非确定但有限的时间内完成。 APRAM 模型中有四类指令：全局读、局部操作、全局写、同步。同步是计算中的一个 逻辑点，在该点各处理器均需等待特别的处理器到达后才能继续执行其局部程序。APRAM 中，计算是由一系列用同步路障分开的全局相所组成。在各全局相内，每个处理器异步地运 行其局部程序， 每个局部程序中的最后一条指令是一条同步指令； 各处理器可以异步地读取 和写入全局存储器，但在同一相内，不允许两个处理器访问同一单元。处理器 1 read x1 read x2 * write to A 处理器 2 read x3 * write to B write to C 处理器 n read xn * * write to DPhase1同步路障 Phase2 同步路障 read B * write to A read A * write to D read C * *图 3 APRAM 中的异步计算，*表示局部操作同步路障使用 APRAM 模型计算算法的时间复杂度时，假定局部操作取单位时间；全局读/写时 间为 d，d 随机器中的处理器的增加而增加；同步路障时间为 B。令 tph 为全局相内各处理器 指令最长执行时间。则整个程序运行时间 T 为各相的时间之和加上 B 乘同步路障次数。2.2.2 LogP 模型1993 年， D.Culler 等人在分析了分布存储计算机特点的基础上， 提出了基于点对点通信 的多计算机模型。该模型充分说明了互连网络的性能特点，而未涉及网络的结构。模型主要 由 4 个参数描述。 L（Latency） 源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或 延迟时间的上限。 o（overhead） 处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开 销和网络软件开销） ，在这段时间里处理机不能执行其他操作。17g（gap） 一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即 为处理机的通信带宽。 P（Processor） 处理机的个数。 L、o、g 都可以表示成处理器周期数的整数倍。 LogP 模型揭示了分布存储并行计算机的性能瓶颈，用 L、o、g 三个参数刻画了通信网 络的特性，但屏蔽了网络拓扑、选路算法和通信协议等具体细节。参数 g 反映了通信带宽， 在任何时刻，最多只能有[L/g]条消息从一个处理器传到另一个处理器，这就是网络容限， 当一台处理机发送的消息达到这个容限时，在发送的消息就会被阻塞；在网络容限范围内， 点到点传送一条消息的时间为（2*o+L） 。 对于一个具体的并行计算机，由通道带宽为 w，经过 H 个跨步（Hops）的网络传送一 个 M 位的消息所花的时间为： T(M,N)=TSEND+[M/w]+H*r+TRECV 即在第一位数据上网之前， 处理器为网络接口准备数据的时间； TRECV 其中 TSEND 为发送开销， 为接收开销，即从最后一位数据数据到达直到处理器使用此数据进行处理的时间；[M/w]为 将消息的最后一位送到网上所花时间； H*r 为最后一位数据通过网络到达目的节点的时间 （r 为中继节点的延迟） ；那么，对于 LogP 模型而言，合理的参数选择为 o=(TSEND+TRECV)/2 L=H*r+[M/w] g=[M/b] 其中，b 为处理器对剖宽度，分析表明，在网络空载和轻载时，T(M,N)中起主要作用的是 o， 而对网络和结构不敏感；在网络重载时，就会出现竞争资源的现象，从而等待时间将迅速增 加，这也是 LogP 模型对网络容量进行限制的原因。 设想 LogP 模型中的 L、o、g 都为 0，那么 LogP 模型就等同于 PRAM 模型了。此外还 有 BSP 模型、C3 模型等。下表给出了这些计算模型的比较。 表 2 并行计算模型综合比较模型 属性 体系结构 计算模式 同步方式 模型参数 PRAM SIMD-SM 同步 自动同步 单位时间步 APRAM MIMD-SM 异步 路障同步 d,读/写时间 B,同步时间 BSP MIMD-DM 异步 路障同步 p,处理器数 g,带宽因子 l,同步间隔 LogP MIMD-DM 异步 隐式同步 L,通信延迟 o,额外开销 g,带宽因子 P,处理器数 C3 MIMD-DM 异步 路障同步 l,信包长度 s,发送建立时间 h,通信延迟18计算粒度 通信方式 地址空间细粒度/中粒度 读/写共享变量 全局地址空间中粒度/粗粒度 读/写共享变量 单地址空间中粒度/粗粒度 发送/接收消息 单/多地址空间中粒度/粗粒度 发送/接收消息 单/多地址空间粗粒度 发送/接收消息 多地址空间2.3 并行计算性能评测并行计算性能评测与并行计算机体系结构、并行算法、并行程序设计一起构成了“并行 计算”研究的四大分支。在并行计算系统上进行计算的主要目标就是要加速整个计算过程， 所以研究并行系统（并行算法、并行程序）加速性能十分重要。随着计算规模的增加和机器 规模的扩大， 研究计算系统的性能是否能随着处理器数目的增加而按比例的增加， 就是并行 计算的可扩展问题。为了方便地、可比较地评价并行计算机系统的性能，人们提出了许多基 准程序，了解这些基准测试程序对于我们客观公正地评价并行计算机系统非常重要。2.3.1 加速比定律在给定的并行计算系统上给定的应用，并行算法（并行程序）的执行速度相对于串行算 法（串行程序）加快的倍数，就是该并行算法（并行程序）的加速比。Amdahl 定律适用于 固定计算规模的加速比性能描述，Gustafson 定律适用于可扩展问题。 假定并行计算系统的处理器数为 p，W 为问题规模，WS 为应用程序中的串行分量，WP 为可并行化部分；f 为串行分量的比例（f=Ws/W） ，1-f 为并行分量的比例；Ts=T1 为串行执 行时间，Tp 为并行计算时间；S 为加速比，E 为并行效率。 1967 年 Amdahl 推导出如下固定负载的加速公式： S=(WS+WP)/(WS+WP/p)=1/(1/p+f(1-1/p) 显然，当 p→∞时，S=1/f 即对于固定规模的问题，并行系统所能达到的加速上限为 1/f。 由于并行程序运行时还需要一些额外开销 WO，因此上述公式还需要修改为： S=(WS+WP)/(WS+WP/p+WO)=1/(1/p+f(1-1/p+WO/W) 显然，当 p→∞时，S=1/(f+WO/W) 可见，串行分量越大和并行额外开销越大，则可加速率就越小。 对于部分问题，如实时性计算方面问题，一般为固定工作负载。但对于许多问题，扩大 计算机规模是为了解决更大规模的问题，因此在对并行程序（并行算法）进行评价时，采用19Amdahl 定律就不能反映算法的可扩展性。1987 年 Gustafson 给出了如下问题规模可扩展的 加速公式： S =（WS+pwp）/（WS+WP）=p-f（p-1）=f+p（1-f） 因此并行算法（并行程序）的可扩展性意味着，加速比与处理器数成斜率为（1-f）的 线性关系，这样串行比例 f 就不再是程序扩展性的瓶颈，当然，f 越低，斜率会越大，加速 性能越好。‘2.3.2 基准测试程序基准测试程序（benchmark）用于测试计算机系统的性能，试图提供一种客观、公正的 评价机器性能的标准。目前在高性能计算领域，比较有影响的基准测试程序有 HINT 测试、 Perf 测试、IOzone 测试，以及 Linpack 测试、NAS Parallel Benchmark、SPEC HPC 测试等。 这些基准测试可以在一定程度上对并行计算机系统方案进行评价， 可以对并行计算机系统的 市场销售提供参考， 另外， 在基准测试中形成的优化方法对应用程序设计与优化具有重要的 饿指导意义。 1） Linpack 由 J. Dongarra 编写的 Linpack 是在高性能计算领域最出名和使用最广泛的基准测试。 Linpack 采用主元高斯消去法在分布式内存计算机上求解双精度(64bits)稠密线性代数方程 组，结果按每秒浮点运算次数（flops）表示。Linpack 测试实际上包含三类测试，问题规模 与优化选择各不相同： ● 100×100 测试 在该测试中，不允许对 Linpack 测试程序进行任何修改（包括注释行） 。 ●
测试 在该测试中，允许对算法和软件进行修改或替换，并尽量利用系统的硬 件特点， 以达到尽可能高的性能。 但是所有的优化都必须保持和标准算法如高斯消去法相同 的相对精度，而且必须使用 Linpack 的主程序进行调用。 ● HPL 测试 针对大规模并行计算系统的测试，其名称为 High Performance Linpack (HPL)， 1.0 版于 2000 年 9 月发布，是第一个标准的公开版本并行 Linpack 测试软件包，一般用于 TOP500 超级计算机上的并行超级计算机。HPL 与其前辈不同，使用者可以改变问题规模。 要获得 Linpack 实测峰值，需要使用与内存匹配的最大的问题规模（一般接近内存总容量的 80%） 。 Linpack 测试可以获得的结果包括： Rpeak: 它是系统的最大的理论峰值性能，按 GFLOPS 表示。20Nmax: 给出达到最高 GFLOPS 值时的问题规模（矩阵规模） 。 Rmax: 在 Nmax 问题规模下，达到的最大峰值（GFLOPS） 。 NB: 矩阵分块大小，与高速缓存大小相关。一般在 32 到 256 之间。 2） NAS 并行基准测试 数值空气动力学模拟并行基准测试(NAS Parallel Benchmark,NPB)已经广泛地应用于并 行计算机的测试和比较中。目前 NPB2 的最新版本是 2002 年 11 月 19 日发布的 2.4 beta 版 本和 NPB3 alpha 版本。NPB 套件由八个程序组成，它来源于计算流体动力学(CFD)的代码。 这八个不同的程序从不同的观点提供性能特点的完整画面。每个基准测试有五类：A、B、 C、D、W (工作站)。A、B、C、D 代表四种不同问题的规模；A 是最小的，D 是最大的。 为了准确、精确的比较性能，应采用 B 或较大的。NPB 套件以每秒百万次运算为单位输出 结果。 整数排序(IS) 此项基准测试检测整数计算速度和通信能力，它不包含浮点运算，通信 数据显著。快速 Fourier 变换（FT） FT 基准测试检测长距离的通信，采用三维 FFT 求解三 维的偏微分方程（PDE） 。多栅格基准测试（MG） MG 需要高度结构化短距和长距通信， 求解二维 Poisson 方程。共轭梯度(CG) 基准测试 CG 需要不规则的长距离通信，采用共轭 梯度方法计算对称正定矩阵的最小特征值。稀疏矩阵分解（LU） LU 检测细小块通信，采 用对称的超松弛法求解规则的稀疏方块 5x5 的上下三角矩阵。五对角方程（SP）和块状三 角(BT)求解 SP 和 BT 检测计算和通信之间的平衡。与其它的不一样，SP 和 BT 需要整数平 方的处理器个数。密集并行(EP) 计算 GAUSS 伪随机数，EP 不执行任何处理器间的通信， 反映并行计算机系统最高计算能力，而不反映通信能力。 3） SPEC HPC 测试 SPEC（Standard Performance Evaluation Cooperation）成立于 20 世纪 80 年代末，它的 主要工作有两个：开发测试计算机性能的测试工具，这些工具以代码的形式发布；在 SPEC 网站（http://www.spec.org）上发布通过认证的测试结果。 High Performance Computing Group (HPC)是其一个分组织，主要测试高性能计算机。主 要测试程序有 SPEC HPC96、 SPEC HPC2002 和 SPEC OMP 2001 系列， 其中的 SPEC HPC96 已经于 2003 年 2 月被 SPEC HPC2002 取代。SPEC HPC 软件包有三大组成部分：SPEC CHEM(化学，量子化学计算)、SPEC ENV（环境，气象预报计算） 、SPEC SEIS（地震，波 动方程迭前偏移计算） 。SPEC HPC2002 软件包支持 MPI 和 OpenMP 并行程序设计环境，包 含 3 个测试程序，每个都有小规模和中规模测试数据集。 4） HINT 基准测试21用于检测 HPC 子系统的常用基准测试。HINT 得到的结果用图形表示，浮点运算性能、 整数性能、存储层次、单位幅度内存性能，数字精度以及非单位幅度内存。HINT 执行一次 由曲线 f(x)=(1-x)/(1+x)， for 0 &=x&=1 围成区域的面积计算。在程序运行时，每次迭代把 该区分成一半，计算在下边界、上边界，而后是里边的小块数目。因此，对内存的访问是从 小区域到非常大的区域。它可以检验系统存储的架构--从缓冲区到 RAM 而后到磁盘。在运 行 HINT 时，存储是从小区域开始而后到较大的尺寸。在初始的缓冲装满后，当计算机在缓 冲内存外运行并启动主内存时， 计算机由开始的快速而缓慢降低， 如果必须访问硬盘甚至更 慢。从 HINT 产生的数据容易看到这种改变。HINT 可以用来比较两个不同的平台的处理器 性能和存储子系统， 5） Perf 测量延迟和带宽 Perf 是一个测量在两个末端间的点对点通信的延迟和带宽的程序。在两个节点间发送 从一个字节到 1MB 的不同长度的消息。它计算延迟，即发送信息和接收该承认信息间的间 隔时间。Perf 是特殊的系统基准测试，一般用于比较机群互连网络的延迟和带宽。 6） IOzone 检测 I/O 性能 IOzone 基准一般用于测试系统 I/O 性能， 如读、 写、 重读、 重写、 回读、 跨读、 fread、 fwrite、 随机读、pread、mmap、aio_read 和 aio_write。IOzone 不仅测量子系统的吞吐量和比较不同 的文件系统的性能，而且也能用于测量和比较各种级别的独立的冗余磁盘阵列(RAID)的性 能。22第二章并行计算机体系结构内容提要： 2.1 并行机网络互联拓扑结构 2.2 并行机访存模型与多级存储结构 2.3 并行机分类 2.4 并行机举例 2.5 并行计算机的发展史2.1参考资料： 文献 1：第 1.2 节； 文献 2：详细阐述； 当代并行机拓扑结构：并行机网络互联拓扑结构并行机体系结构的几个要素： 结点：包含一个或多个 CPU，这些 CPU 通过 HUB 或全互联交叉开关相互联接， 并共享内存，也可以直接与外部进行 I/O 操作； 路由器：联接计算结点与互联网络，负责数据在结点间的路由寻址； 互联网络： 将所有路由器以某种拓扑结构相互联接， 保证它们之间可以自由地通信。 互联网络： 拓扑结构： 将并行机各结点之间物理上相互联接的关系用图来表示， 其中图中结点 代表并行机的结点， 图中连线代表它所联接的两个结点的路由器之间存在物理上的 直接联接关系，我们称该图为并行机互联网络拓扑结构；23拓扑结构的几个重要定义： 并行机规模：并行机包含的结点总数，或者包含的 CPU 总数； 结点度： 互联网络拓扑结构中联入或联出的一个结点的边的条数， 称为该结点 的度； 结点距离：两个结点之间跨越的图的边的条数； 网络直径：网络中任意两个结点之间的最长距离； 点对点带宽：图中边对应的物理联接的物理带宽； 点对点延迟：图中任意两个结点之间的一次零长度消息传递必须花费的时间。 延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟， 所有结点之间的最大延迟称为网络的最大延迟； 折半宽度：对分网络成两个部分（它们的结点个数至多相差 1）所必须去掉的 边的网络带宽的总和； 总通信带宽：所有边的带宽之和； 互联网络评价： 大：结点度、点对点带宽、折半宽度、总通信带宽； 小：网络直径、点对点延迟； 互联网络的分类：静态拓扑结构、动态拓扑结构、宽带互联网络； 静态拓扑结构：结点之间存在固定的物理联接方式，程序执行过程中，结点间的点 对点联接关系不变，例如：[文献 1：P10-P11，给出各类定义的具体值, 文献 2 详 细讨论]； 一维阵列（Array） 、环（Ring） ； 多维网格（Mesh） 、多维环（Torus） ； 树（Tree） ：二叉树、X-树、星树、胖树； 超立方体（Hypercube）; 动态拓扑结构： 结点之间无固定的物理联接关系， 而是在联接路径的交叉点处用电 子开关、路由器或仲裁器等提供动态联接的特性，主要包含单一总线、多层总线、 交叉开关、多级互联网络： 单一总线：联接处理器、存储模块和 I/O 设备等的一组导线和插座，在主设备 （处理器）和从设备（存储器）之间传递数据，特征有： 公用总线以分时工作为基础， 各处理器模块分时共享总线带宽， 即在同一 个时种周期，至多只有一个设备能占有总线； 总线带宽=总线主频×总线宽度，例如 ASUS 主板的总线频率=150MHz， 总线宽度为 64 位，则该总线的带宽=1.2GB/s； 监听协议与仲裁算法：选择哪个设备占有总线； 例如：微机主板外部数据总线、PCI 总线、ASCI White 每个结点包含 16 个 CPU，CPU 之间通过总线共享局部存储器； 多层总线：各设备内部存在本地总线（结点、存储器、I/O 设备） ，本地总线 之间以系统总线相互联接，系统总线一般在通信主板中实现，例如文献 1 P14 图 1.9。 交叉开关（Crossbar Switcher） ：所有结点通过交叉开关阵列相互连接，每个交 叉开关均为其中两个结点之间提供一条专用联接通路， 同时， 任意两个结点之 间也能找到一个交叉开关， 在它们之间建立专用联接通路。 交叉开关的状态可 根据程序的要求动态地设置为“开”和“关” 。例如 4×4 交叉开关联接 8 个结24点（黑板上画图说明） 。交叉开关特征： 结点之间联接：交叉开关一般构成 N×N 阵列，但在每一行和每一列同时 只能有一个交叉点开关处于“开”状态，从而它同时只能接通 N 对结点； 结点与存储器之间的联接： 每个存储器模块同时只允许一个结点访问， 故 每一列只能接通一个交叉点开关， 但是为了支持并行存储访问， 每一行同 时可以接通多个交叉点开关。 交叉开关的成本为 N2，N 为端口数，限制了它在大规模并行机中的应用， 一般适合 8-16 个处理器的情形. 多级互联网络（MIN：Multistage Interconnection Network） ：由多个单级交叉开 关级联接起来形成大型交叉开关网络， 相邻交叉开关级之间存在固定的物理联 接拓扑。为了在输入与输出之间建立联接，可以动态地设置开关状态。例如： 一般联接图：文献 1 图 1.11，其中 ISC 为该级互联网络，主要有混洗、蝶 网、纵横交叉等； （详细参考文献 2） 蝶网、CCC 网、Benes 网：均为超立方体网络的推广，参考文献 2 的 P215-P225。 ?网：等价于蝶网，参考文献 1 的 P16 图 1.12。 宽带互联网络： 快速以太网（10Mbps（82 年） 、100Mbps（94 年） 、1Gbps（97 年） ） ：IEEE802.3 国际标准， 三代网络性能比较参考文献 1 的 P18 表 1.6， 特征类似于单一总线： 分时共享、竞争仲裁：带宽 100Mbps，8 台处理机共享，每台处理机的平 均带宽为 12.5 Mbps。 FDDI：光纤分布式数据接口（Fiber Distributed Data Interface）采用双向光纤 令牌环，所有结点联接在该环中，提供 100-200Mbps 数据传输速度，双向环 提供冗余通路以提供可靠性，距离可达 100 米、2 公里、60 公里等，比快速以 太网具有更好的可靠性、适应性； Switcher：交叉开关，可同时为 N/2 对端口提供 100Mbps 的直接联接通路，其 中 N 为端口总数。多个 Switcher 堆叠（不多于 7 个）可形成多级 Switcher。 Beowulf 微机机群采用这种结构互联所有结点。 （参考张林波讲义之图） 。 ATM： 异步传输模式（ATM：Asynchronous Transfer Mode）是在光纤通信 基础上建立起来的一种新的宽带综合业务数字网的交换技术。 介质无关的信息 传输协议，采用 53 字节的定长短数据单元（cell）进行传输。大的数据包进入 ATM 网络时，分解成多个定长的单元，各个单元独立传输，到达目的地址后， 这些单元汇集成原来的数据包。ATM 网络适合高速度传输声音、图像、视频 和数据等的所有形式的媒体。 Myrinet：专用机群互联网络，带宽可达 88MB/秒，延迟小于 10us。 GigaNet：专用机群互联网络，采用 VIA 和 ATM 结构，带宽可达 113MB/秒， 延迟小于 20us。 HiPPI：高性能并行接口（High Performance Parallel Interface） ，1993 年标准 （ ANSIX3T9.3 ） 形 成 。 单 工 点 对 点 的 数 据 传 输 界 面 ， 带 宽 可 达 800Mb/s-1.6Gb/s。 互联网络的路由选择算法： 定义： 数据包（Packet） ：结点间数据在网络中传输的最小单位，一般为几十个、或25者几百个字节。 路由选择算法：网络中数据包传输的路径选择。 申请队列长度：在某条边上等待传输的数据包的个数。 常用路由选择算法： 贪心法：每个数据包沿最短路径传输（二维阵列举例） ，该方法容易在某一条 边上形成通信阻塞。 动态路由选择算法： 数据包根据当前边的申请队列长度， 动态地改变传输路径。 虫孔算法（Wormhole） ：数据包分解为长度更小的字节流，所有字节流在网络 中按动态路由选择算法在网络中传输，最后在目的地址合并还原成数据包。 作业： 作业 2.1： 假设网络包含 P=2N=M3 个结点， 请给出一维阵列 （环） 、 二维网格 （Torus） 、 三维网格（Torus） 、超立方体、二叉树（叶结点个数为 P） 、蝶网、Benes 网的结点 度、点对点延迟（以跨越的边的条数为单位） 、折半宽度（以边的条数为单位） 、网 络直径。 作业 2.2：假设存在 8 个结点，分别联接在 1Gbps 的快速以太网和 100Mbps 的 24 端口的 Switcher 上，请问任意两个结点间的平均带宽为多少，如果结点数增加一 倍，则平均带宽又为多少。262.2 并行机存储结构参考资料： 文献 1：第 1.3 节； 文献 8、文献 10； 并行机存储模块 内存模块与结点分离 结点 0 CPU0 Cache HUB CPU1 Cache 。 。 。 。 。 。 。 。 。 。 CPU0 Cache HUB 结点 P CPU1 CacheRouterRouter互 联 网 络M0M1 图 2.2.1M2。 。 。 。 。 。MP内存模块局部于结点内部 结点 0 CPU0 Cache HUB CPU1 Cache M0 。 。 。 。 。 。 。 。 。 。 CPU0 Cache HUB 结点 P CPU1 Cache MPRouterRouter互 联 网 络 图 2.2.227并行机访存模型 均匀访存模型（UMA：Uniform Memory Access） ：内存模块与结点分离，分别位于 互联网络的两侧（图 2.2.1） ，互联网络一般采用系统总线、交叉开关和多级网络， 称之为紧耦合系统（Tightly Coupled System） 。具有如下特征： 物理存储器被所有结点均匀共享； 所有结点访问任意存储单元的时间相同； 访存竞争时，仲裁策略对每个结点均是机会等价的； 各结点的 CPU 可带有局部私有高速缓存（Cache） ； 外围 I/O 设备也可以共享，且对各结点等价。 非均匀访存模型（NUMA：Nonuniform Memory Access） ：内存模块局部在各个结 点内部 （图 2.2.2） ， 所有局部内存模块构成并行机的全局内存模块。 具有如下特征： 任意结点可以直接访问任意内存模块； 结点访问内存模块的时间不一致： 访问本地存储模块的速度一般是访问其他结 点内存模块的 3 倍以上； 访存竞争时，仲裁策略对结点可能是不等价的； 各结点的 CPU 可带有局部私有高速缓存（Cache） ； 外围 I/O 设备也可以共享。 Cache 一致性非均匀访存模型（CC-NUMA：Coherent-Cache Nonuniform Memory Access） ：存在专用硬件设备保证在任意时刻，各结点 Cache 中数据与全局内存数 据的一致性，具有特征： 各 CPU 的局部 Cache 数据来源于全局内存，并保证所有结点中数据的一致性 （画图简单说明） ； 大多数访存可以局部在本地高速 Cache； 基于目录的 Cache 一致性协议（Cache 原理参考下章） 。 分布式访存模型（DMA：Distributed Memory Access） ：各个结点的存储模块只能 被局部 CPU 访问，其他结点无法直接访问局部存储模块，称之为分布式存储（图 2.2.2） ，具有特征： 内存模块分布局部于各个结点， 每个结点只能直接访问其局部存储模块， 对其 他结点的内存访问只能通过消息传递程序设计来实现； 每个结点均是一台由处理器、存储器、I/O 设备组成的自洽计算机。28多级存储结构： 500MHz Pentium-III Cluster CPU chip 寄存器 一级 Cache 二级 Cache 本地局部内存 远程内存（MPI 消息传递） 处理机 容量(B) 带宽(MB/s) 延迟(ns) 256 32K 512K 500M 海量 00
6 80 320 100,000访存延迟比例： P-III 微机机群 Origin 2000 1 : 3 : 40 : 160 : 50,000 1 : 3 : 30 : 50: 500一次消息传递延迟相当于峰值浮点运算的次数： P-III 微机机群 ： 50,000 次 Origin 2000 ： 1000 次通信与 CPU 计算速度不匹配：292.3参考资料： 文献 1：P21-P25； 文献 6：第 1 章； 文献 8、10、11；并行机分类指令与数据流分类： 单指令多数据流（SIMD） ：按同一条指令，并行机的各个不同的功能部件同时对不 同的数据进行不同的处理，例如：传统的向量机、80 年代初期的阵列机 CM-2，目 前已经退出历史舞台； 多指令多数据流（MIMD） ：不同的处理器可同时对不同的数据执行不同的指令， 目前所有并行机均属于这一类； 多指令单数据流（MISD） ：至今没出现 当前流行的高性能并行机体系结构分类： （五类） 对称多处理共享存储并行机（SMP：Symmetric MultiProcessing） ； 分布共享存储并行机（DSM：Distributed Shared Memory） ； 大规模并行机（MPP：Massively Parallel Processors） ； 工作站（微机）机群（COW：Cluster Of Workstation、Beowulf PC-Cluster） ； 并行向量多处理机（PVP：Parallel Vector Processors） 对称多处理共享存储并行机（SMP） ： 微处理器CPU微处理器CPU微处理器CPU…………Cache Cache Cache系统总线或交叉开关内存 模块内存 模块内存 模块I/O………模块图 2.3.1SMP 体系结构示意图SMP 具有如下特征： 对称共享存储： 系统中任何处理器均可直接访问任何存储模块中的存储单元和 I/O 模块联接的 I/O 设备，且访问的延迟、带宽和访问成功的概率是一致的。30所有内存地址单元统一编址。 各个处理器之间的地位等价， 不存在任何特权处 理器。操作系统可在任意处理器上运行。 单一的操作系统映像： 全系统只有一个操作系统驻留在共享存储器中， 它根据 各个处理器的负载情况， 动态地分配各个进程到各个处理器， 并保持各处理器 间的负载平衡。 局部高速缓存 Cache 及其数据一致性：每个处理器均配备局部 Cache，它们可 以拥有独立的局部数据，但是这些数据必须保持与存储器中数据是一致的。 低通信延迟：各个进程通过读/写操作系统提供的共享数据缓存区来完成处理 器间的通信，其延迟通常小于网络通信的延迟。 共享总线带宽：所有处理器共享总线的带宽，完成对内存模块和 I/O 模块的访 问。 支持消息传递、共享存储并行程序设计。 SMP 具有如下缺点： 欠可靠：总线、存储器或操作系统失效可导致系统崩溃。 可扩展性（scalability）较差：由于所有处理器共享总线带宽，而总线带宽每 3 年才增加 2 倍，跟不上处理器速度和内存容量的增加步伐，因此，SMP 并行 机的处理器个数一般少于 32 个，且只能提供每秒数百亿次的浮点运算性能。 SMP 典型代表： SGI POWER Challenge XL 系列并行机（36 个 MIPS R1000 微处理器） ； COMPAQ Alphaserver
（12 个 Alpha 21264 个微处理器） ； HP （12 个 HP PA9000 微处理器） ； IBM RS 个 RS6000 微处理器） 。 分布共享存储并行机（DSM） ： 结点 0 CPU0 Cache HUB CPU1 Cache M0 。 。 。 。 。 。 。 。 。 。 CPU0 Cache HUB 结点 P CPU1 Cache MPRouterRouter互 联 网 络图 2.3.2DSM 体系结构示意图31DSM 较好地改善了 SMP 并行机的可扩展能力，具有如下特征： 并行机以结点为单位，每个结点包含一个或多个 CPU，每个 CPU 拥有自己的局 部 Cache，并共享局部存储器和 I/O 设备，所有结点通过高性能互联网络相互联 接； 物理上分布存储：内存模块局部在各结点中，并通过高性能互联网络相互联接， 避免了 SMP 访存总线的带宽瓶颈，增强了并行机的可扩展能力。 单一的内存地址空间：尽管内存模块分布在各个结点，但是，所有这些内存模 块都由硬件进行了统一的编址，并通过互联网络联接形成了并行机的共享存储 器。各个结点即可以直接访问局部内存单元，又可以直接访问其他结点的局部 内存单元。 非一致内存访问（NUMA）模式：由于远端访问必须通过高性能互联网络，而 本地访问只需直接访问局部内存模块，因此，远端访问的延迟一般是本地访问 延迟的 3 倍以上。 单一的操作系统映像：类似于 SMP，在 DSM 并行机中，用户只看到一个操作系 统，它可以根据各结点的负载情况，动态地分配进程。 基于 Cache 的数据一致性：通常采用基于目录的 Cache 一致性协议来保证各结 点的局部 Cache 数据与存储器中数据的一致性。同时，我们也称这种 DSM 并行 机结构为 CC-NUMA 结构。 低通信延迟与高通信带宽：专用的高性能互联网络使得结点间的延迟很小，通 信带宽可以扩展。 例如， 目前最先进的 DSM 并行机 SGI Origin 3000 的双向点对 点通信带宽可达 3.2GB/秒，而延迟小于 1 个微秒。 DSM 并行机可扩展到上百个结点， 能提供每秒数千亿次的浮点运算性能。 例如， SGI Origin 2000 可以扩展到 64 个结点（128 个 CPU） ，而 SGI Origin 3000 可以 扩展到 256 个结点（512 个 CPU） 。但是，由于受 Cache 一致性要求和互联网络 性能的限制，当结点数目进一步增加时，DSM 并行机的性能也将大幅下降。 支持消息传递、共享存储并行程序设计。 DSM 典型代表： SGI Origin 2000； SGI Origin 3800。 大规模并行机（MPP） ：数百个乃至数千个处理器组成的大规模并行机。 典型代表：当前位于 TOP 500 前列（参考第 7 章并行机性能测试）的并行机均属 于这一类，其中包括 IBM ASCI White（8192 个处理器） 、Intel ASCI Red（9632 个 处理器） 、IBM ASCI Blue Pacific（5808 个处理器） 、SGI ASCI Blue Mountain（6144 个处理器） 、IBM SP POWER3（1336 个处理器） 、CRAY T3E 个处理器） 等。32典型体系结构： 结点 1 P/C …… P/C MEM 结点 N P/C …… P/C MEM局部总线或互联网络… I/O局部总线或互联网络NICNICI/O高性能互联网络 图 2.3.3 MPP 体系结构示意图I/OMPP 特征： 由数百个乃至数千个计算结点和 I/O 结点组成，这些结点由局部网卡（NIC） 通过高性能互联网络相互联接。 每个结点相对独立，并拥有一个或多个微处理器（P/C） 。这些微处理器均配备 有局部 Cache， 并通过局部总线或互联网络与局部内存模块和 I/O 设备相联接。 MPP 的各个结点均拥有不同的操作系统映像。一般情况下，用户可以将作业 提交给作业管理系统， 由它负责调度当前最空闲、 最有效的计算结点来执行该 作业。但是，MPP 也允许用户登录到某个特定的结点，或在某些特定的结点 上运行作业。 各个结点间的内存模块相互独立， 且不存在全局内存单元的统一硬件编址。 一 般情形下， 各个结点只能直接访问自身的局部内存模块， 如果要求直接访问其 他结点的局部内存模块，则必须有操作系统的特殊软件支持。 按存储结构的不同， MPP 又可以分为两类： 分布式存储大规模并行机 （DM-MPP） 、 多台 SMP 或 DSM 并行机通过高性能互联网络相互联接的大规模机群（SMP-MPP 或 DSM-MPP） ： DM-MPP：每个结点仅包含一个微处理器，早期的 MPP 均属于这一类。例如 CRAY T3D、CRAY T3E、Intel Paragon、IBM SP-2、YH-3 等。 SMP-MPP：每个结点是一台 SMP 并行机，例如当前位于 Top500 排名前列的 多台 MPP 并行机均属于这一类，其中包括 IBM ASCI White、Intel ASCI Red、 IBM Blue Pacific 等； DSM-MPP：每个结点是一台 DSM 并行机，其典型代表为包含 6144 台处理器 的 ASCI Blue Mountain MPP 并行机，它由 48 台 Origin 2000 构成，其中每台 含 128 个微处理器。33微机机群（Beowulf PC-Cluster） ：随着商用微处理器性能的飞速发展，低延迟、高带宽 商用网络交换机的出现，和 LINUX 操作系统等自由软件的成熟，并行计算机不再是一 个只有大型科研单位才能拥有的设备。例如，将 128 台当前市场上最高性能的 Intel Pentium-III/800MHz 的微机通过 6 个 24 端口的 100Mbps 的网络交换机相互联接，即可 构成浮点峰值性能在 1000 亿次左右的并行机，而其成本不超过 200 万元人民币，性能 价格比远远高于以上提到的各类并行机（30 倍以上） ，国际上称该类自行研制的并行机 为 Beowulf 机群。 尽管微机机群在通信性能、稳定性和使用方便等方面有待大幅度提高，但是，它们以其 他并行机无法比拟的性能价格比， 近年来已经成为了高性能并行计算中的一支不可忽视的重 要力量。目前，在我国的各个大学和科研机构，例如中科院、北京大学、清华大学等，微机 机群也得到了快速发展和推广应用。特别地，在 2000 年底的 Top 500 排名中，美国 Sandi 国家重点实验室自行研制的机群 Cplant 排名第 84 位。微机 N文件服务器外部网络网络交换机微机 微机 微机 微机 1图 2.3.4Beowulf 微机机群示意图（参考张林波讲义之图）Beowulf 微机机群的体系结构如图 2.3.4 所示，多台高性能微机通过商用网络交换机相 互联接，并拥有各自独立的操作系统、主板、内存、硬盘和其他 I/O 设备，构成机群的计算 结点。 配置一台或多台文件服务器， 一方面管理机群计算结点共享的所有软件和用户计算资 源， 另一方面充当机群与外部网络的联接桥梁， 外部科研网的用户只有通过文件服务器才能 使用机群的计算资源。 由于受商用交换机网络性能和操作系统功能的影响，Beowulf 微机机群的处理机规模一 般限制在 100 台左右。但是，如果将交换机替换成专用机群网络，例如 GigaNet、Myrinet 等，则它们的规模可以进一步扩大。因此，在当前技术条件下，微机机群一般可提供千亿次 左右的浮点峰值性能。 并行向量多处理并行机（PVP） ：体系结构类似于 DM-MPP，但是每个 CPU 为向量多处 理机。仅日本研制，应用不广。2.4并行机举例SMP 并行机：SGI Power Challenge XL R10000： 多个（&18）个 SGI R10000 微处理器、共享存储模块、I/O 设备通过系统总线相互 联接。 总线带宽：2.4GB/秒。34单一操作系统影像。 DSM 并行机：SGI Origin 2000、SGI Origin 3800： 单一影像操作系统。 Origin 2000 可扩展到 8 个机柜