第二章并行计算基础学习课件

1
0
、
倚
南
窗
以
寄
傲
，
审
容
膝
之
易
安
。
▪
26、要使整个人生都过得舒适、愉快，这是不可能的，因为人类必须具备一种能应付逆境的态度。——卢梭
▪
27、只有把抱怨环境的心情，化为上进的力量，才是成功的保证。——罗曼·罗兰
▪
28、知之者不如好之者，好之者不如乐之者。——孔子
▪
29、勇猛、大胆和坚定的决心能够抵得上武器的精良。——达·芬奇
▪
30、意志是一个强壮的盲人，倚靠在明眼的跛子肩上。——叔本华
谢谢！
109
并行计算技术概述
6
、
露
凝
无游氛Fra bibliotek，天
高
风
景
澈
。
7、翩翩新 来燕，双双入我庐 ，先巢故尚在，相 将还旧居。
8
、
吁
嗟
身
后
名
，
于
我
若
浮
烟
。
9、 陶渊 明（ 约 365年 —427年 ），字 元亮， （又 一说名 潜，字 渊明 ）号五 柳先生 ，私 谥“靖 节”， 东晋 末期南 朝宋初 期诗 人、文 学家、 辞赋 家、散
文 家 。汉 族 ，东 晋 浔阳 柴桑 人 （今 江西 九江 ） 。曾 做过 几 年小 官， 后辞 官 回家 ，从 此 隐居 ，田 园生 活 是陶 渊明 诗 的主 要题 材， 相 关作 品有 《饮 酒 》 、 《 归 园 田 居 》 、 《 桃花 源 记 》 、 《 五 柳先 生 传 》 、 《 归 去来 兮 辞 》 等 。

N-1，对剖宽度为1 ▪ 当首、尾节点相连时可构成循环移位器，在拓扑结
构上等同于环，环可以是单向的或双向的，其节点 度恒为2，直径或为 N / 2（双向环）或为N-1（单向 环），对剖宽度为2
国家高性能计算中心（合肥）
8
静态互连网络（2）
▪ N N 二维网孔（2-D Mesh）：
▪ 每个节点只与其上、下、左、右的近邻相连（边界节点除外）， 节点度为4，网络直径为 2( N 1) ，对剖宽度为 N
MIN 或 交叉开关
10 Gb/s
局部总线 SCI
HiPPI
网络带宽
1
Myrinet
Gb/s
千兆位 以太网
100
I/O 总线
光纤 通道
FDDI
Mb/s
快速以太网
100 Base T
ATM
10 Mb/s
IsoEnet 以太网 10 Base T
总线或开关
SAN
LAN
MAN
WAN
国家高性能计算中心（合肥）
并行计算
Parallel Computing
主讲人 徐 云
Spring, 2019
并行计算——结构•算法•编程
▪ 第一篇 并行计算的基础
▪ 第一章 并行计算与并行计算机结构模型 ▪ 第二章 并行计算机系统互连 ▪ 第三章 典型并行计算机系统介绍 ▪ 第四章 并行计算性能评测
国家高性能计算中心（合肥）
1010 1110 0110 0010
0110
0111
0100
0101
国家高性能计算中心（合肥）
0010
0011
0000
0001
1110
1111
1100

▪ n,节点规模 w，数据宽度
国家高性能计算中心（合肥）
2021/4/12
22
标准互联网络（1）
▪ Myrinet:
▪ Myrinet是由Myricom公司设计的千兆位包交换网络，其目的 是为了构筑计算机机群，使系统互连成为一种商业产品。
▪ Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及 在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任 意拓扑结构，不必限定为开关网孔或任何规则的结构。
▪ 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、 快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等
CPU板
LM
CPU
本地外围设备 (SCSI总线)
IOC
存储器板 存储器单元
本地总线
存储器总线
高速缓存
IF
IF
MC
系统总线
I/O板
IOP
IF
数据总线
缓冲
IF
(底板上)
通信板
IF
开关，在Ilinois大学的
Cedar[2]多处理机系统中采用了Ω网络
▪ Cray Y/MP多级网络，该网络用来支持8个向量处理器和256 个存储器模块之间的数据传输。网络能够避免8个处理器同时 进行存储器存取时的冲突。
国家高性能计算中心（合肥）
2021/4/12
21
动态互连网络比较
动态互连网络的复杂度和带宽性能一览表
▪ 一个交换开关模块有n个输入和n个输出，每个输入可连接到任 意输出端口，但只允许一对一或一对多的映射，不允许多对一 的映射，因为这将发生输出冲突
▪ 级间互连（Interstage Connection ）：

商品网络(以太网，ATM，etc.)
Google云计算数据中心
并行计算机发展食物链
并行计算的性能分析
2、并行效率
MPI产生背景
• 并行程序设计方式：
设计全新的并行语言 扩展串行语言语法，使其支 持并行特征 为串行语言提供可调用的并 行库
实 现 难 度
• MPI(Message
Passing
• 并行算法设计（略） • 并行编程环境
系统环境：常见主流Unix/Linux操作系统 编程语言：Fortran 77/90/9, C/C++
并行计算机的分类
并行计算科学中主要研究的是空间上的并行问题。 空间上的 并行导致了两类并行机的产生，按照Flynn的说法分为：单 指令流多数据流（SIMD）和多指令流多数据流（MIMD）。 我们常用的串行机也叫做单指令流单数据流（SISD）。
… 并行代码; …
MPI_Fainalize();
只能有串行代码;
一个简单的MPI程序 — Hello.c
运行： • 启动机器集群中的3个机器节点： • 编译Hello.c程序： • 执行Hello程序：
注意：可执行程序Hello.o必须同时位于3个机器节点的test3目录下。
MPI消息
• 消息(message)： MPI程序中在进程间通信所传送 的所有信息称为消息。
简单消息发送与接收案例— HelloWord.c
#include “mpi.h” main(int argc, char* argv[]) { int p; int my_rank; MPI_Status status; char message[100]; MPI_Init(&argc, &argv); /*进程数,该变量为各处理器中的同名变量 */ /*我的进程ID,存储也是分布的 */ /*消息接收状态变量,存储也是分布 */ /*消息buffer,存储也是分布的 */ /*初始化MPI*/

使用HiPPI通道和开关构筑的 LAN主干网
超级计算机
帧缓冲器 RGB 显示器
300米 HiPPI 串行
Байду номын сангаас25米
存储器 服务器
25米 HiPPI HiPPI 交换开关
直至10千米
光纤扩展器
光纤扩展器
HiPPI 交换开关
25米
文件 服务器
串行
HiPPI
300米
300米 串行
大规模并行 处理系统
小型机
工作站 工作站
系统互连
▪ 不同带宽与间隔 的互连技术: 总线、SAN、LAN、MAN、WAN
100 Gb/s
MIN 或 交叉开关
10 Gb/s
局部总线 SCI
HiPPI
网络带宽
1 Gb/s
Myrinet 千兆位 以太网
100
I/O 总线
光纤 通道
FDDI
Mb/s
快速以太网
100 Base T
ATM
10 Mb/s
▪ 环网可完美嵌入到2-D环绕网中 ▪ 超立方网可完美嵌入到2－D环绕网中
嵌入〔2〕
1000
1001
1011
1010
1100
1101
1111
1110
0100
0101
0111
0110
0000
0001
0011
0010
0100
0110 0101
0111
0000
0010 0001
0011
1100
1110 1101
1111
1000
1010 1001
1011
静态互连网络特性比较

N 1
2
2
N
2-D网孔 Illiac网孔 2-D环绕 二叉树

N N N N

4 4 4 3
非
N
2( N N )
2N
非
2 N
N

N /2

是
2 N
2N
N
2log N 1
1
非 非 是
N 1
星形
N
N 1
2
N / 2
N 1
超立方 立方环
N 2
n
n
3
国家高性能计算中心（合肥）
2013-8-14
11
静态互连网络（2）

N N
二维网孔（2-D Mesh）：
每个节点只与其上、下、左、右的近邻相连（边界节点除外）， 节点度为4，网络直径为 2( N 1) ，对剖宽度为 N 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了， 节点度恒为4，网络直径为 N 1 ，而对剖宽度为 2 N 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus）， 节点度恒为4，网络直径为 2 N / 2 ，对剖宽度为 2 N
1.3 并行计算机系统结构
1.3.1 并行计算机结构模型 1.3.2 并行计算机访存模型
国家高性能计算中心（合肥） 2013-8-14 4
并行计算
并行计算：并行机上所作的计算，又称高性能 计算或超级计算。 计算科学：计算物理、计算化学、计算生物等 科学与工程问题的需求：气象预报、油藏模拟、 核武器数值模拟、航天器设计、基因测序等。 需求类型：计算密集、数据密集、网络密集。 美国HPCC计划：重大挑战性课题，3T性能 美国Petaflops研究项目：Pflop/s。 美国ASCI计划：核武器数值模拟。

并行计算机的分类

并行向量机（PVP） 对称多处理共享存储多处理机（SMP） 大规模并行处理机（MPP） 工作站（微机）机群（COW） 分布式共享存储多处理机（DSM）
COW(Cluster of Workstation)




ቤተ መጻሕፍቲ ባይዱ

一个节点可以是一台PC或SMP； 各节点一般由商品化的网络互连；机群 节点通过使用标准网络协议（TCP/IP） 来通信。使用的是千兆网。 每个节点一般有本地磁盘； 节点上的网络接口是松散耦合到I/O总线 上； 每个节点有一个完整的操作系统,但是通 过中间层实现了单一系统映像（SSI）。
并行计算基础知识
赵俊锋 西北工业大学理学院 zhaojf_77@
主要内容

并行计算环境 并行算法基础 什么问题可以并行化 串行程序如何改为并行程序
为什么需要并行计算机
问题: 科学和工程问题的数值模拟与仿真 计算密集 数据密集 网络密集 三种混合 要求:在合理的时限内完成计算任务 秒级 制造业 分钟级 短时天气预报(当天) 小时级 中期天气预报(3~10日) 尽可能快 长期天气预报(气候) 可计算 湍流模拟
并行算法的分类

非数值计算并行算法 数值计算并行算法，基于矩阵运算、多 项式求解、线性方程组求解等代数关系 运算的计算问题。
进程 1
进程 2
传统的串行计算，分为“指令” 和“数据”两个部分，并在程序 执行时“独立地申请和占有”内 存空间，且所有计算均局限于 该内存空间。
进程 1
进程 2
发送信息
接收信息
并行计算将进程相对独立的 分配于不同的节点上，由 各自独立的操作系统调度， 享有独立的CPU和内存资源 （内存可以共享）；进程间 相互信息交换通过消息传递；

▪ 课程内容、特点和授课方式 ▪ 教材和主要参考书目 ▪ 课程在并行计算技术中的地位 0.3 课程考核和评分要求 0.4 并行计算介绍 ▪ 什么是并行计算? ▪ 为什么需要并行计算? ▪ 几种实现方案 ▪ 并行计算的粒度 ▪ 并行计算的研究领域 ▪ TOP500和China TOP100 ▪ 问题示例
2021/3/12
《并行算法》 4 / Ch0
0.2 课程介绍: 内容、特点和学习方式
课程内容： ▪ 并行机结构模型、并行计算模型、并行算法基本知识； ▪ 非数值并行算法：排序、选择、组合搜索、串匹配、图论算法等； ▪ 数值并行算法：矩阵运算、线性方程组求解、FFT算法等； ▪ 并行计算理论。 ▪ 新增内容：多核计算和GPU上的并行算法
nature. But their existing applications are designed for uniprocessor systems. Their parallelization is required.
2021/3/12
《并行算法》 13 / Ch0
0.4 并行计算介绍: 几种实现方案
2021/3/12
《并行算法》 11 / Ch0
0.4 并行计算介绍: 为什么需要并行计算？(1)
Interest in parallelism since the very ancient era of computers(e.g. ILLIAC IV of 1967 had 64 processors)
0.2 课程简介: 课程在并行计算技术中的地位
算法理论
可计算性与
算法研究的
计算复杂性
数学基础
专业面博向士计生算机
算法设计与分析并行排序和 选择算法

▪ 中国联想： 1Tflops,Top43,2002
精选
2020/10/3
14
系统互连
▪ 不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN
100 Gb/s
MIN 或 交叉开关
10 Gb/s
局部总线 SCI
HiPPI
网络带宽
1 Gb/s
Myrinet 千兆位 以太网
100
I/O 总线
精选
2020/10/3
2
并行计算——结构•算法•编程
▪ 第三篇 并行数值算法
▪ 第八章 基本通信操作 ▪ 第九章 稠密矩阵运算 ▪ 第十章 线性方程组的求解 ▪ 第十一章 快速傅里叶变换
▪ 第四篇 并行程序设计
▪ 第十二章 并行程序设计基础 ▪ 第十三章 并行程序设计模型和共享存储系统编程 ▪ 第十四章 分布存储系统并行编程 ▪ 第十五章 并行程序设计环境与工具
▪ 1.3 并行计算机系统结构
▪ 1.3.1 并行计算机结构模型 ▪ 1.3.2 并行计算机访存模型
精选
2020/10/3
4
并行计算
▪ 并行计算：并行机上所作的计算，又称高性能计算或超级计 算。
▪ 三大学科：计算科学，理论科学和实验科学 所有的学科都转向定量化和精确化。 计算科学是一个交叉学科，用计算的方法来解决应用问题。 适用于理论模型复杂或尚未建立，实验费用昂贵或无法进行
并行计算
——结构•算法•编程
精选
2020/10/3
1
并行计算——结构•算法•编程
▪ 第一篇 并行计算的基础
▪ 第一章 并行计算机系统及其结构模型 ▪ 第二章 当代并行机系统：SMP、MPP和Cluster ▪ 第三章 并行计算性能评测