超级计算机
超级计算机
天河一号 A
2.57 PFlops
天河二号
33.9PFlops
升级至2A
神威太湖之光
CNGrid
性能
响应时间
提交作业到完成作业所花费的时间，CPU执行时间，CPI：指令平均执行时钟周期数，不起决定性作用
吞吐量
一定时间间隔内完成的作业数(速率度量)，吞吐指标：IPC
MFlpos:百万浮点数操作每秒，与整数、浮点数比例有关，1MFlops与等于3MIPS
性能影响因素
指令数：ISA(指令集体系结构）、编译器
CPI
时钟周期
高性能计算机的基本性能
峰值性能（排榜）、持续性能（更看重）
加速比Sn=T1/Tn,并行算法的加速性能
高性能计算机体系结构
高性能计算
向量计算
并行计算
硬件结构上作成并行结构，完成高性能计算
分布式计算
分结点同时计算
网络计算
网格计算（Grid Computing)
像电网一样，把算力连接到一起形成基础设施，算力网。并行计算+分布式计算
云计算
HPC发展历程
专用时代
不是只能运行某种应用，是组成部件专门设计
普及时代
商品化和标准化趋势。
集群系统：一种高性能计算机架构。
巨型机萌芽阶段
CDC6600：世界上第一台巨型计算机
向量机鼎盛阶段
MPP蓬勃发展
2000排名前十均为MPP，成为高性能的主流架构
集群架构发展并成主流，各种体系结构并存（2000年-）
NOW、COW不断发展。
高性能计算机和并行计算机
并行机：一系列能够通过协同和通信来快速解决大规模问题的处理单元的集合。主流架构异构，不是同一种处理单元，能力不同。CPU（串行）+ GPU（并行），分开来处理不同需求的指令。
互联网络的结构：bus、crossbar
评价指标：成本、延迟、可扩展性。
能够协同：同步允许按顺序操作保证正确性：原语的使用；粒度要与程序中的子任务大小相对应：减小粒度、粒度与指令数的平衡；自治性（autonomy）：tradeoff
快速解决大规模问题：要考虑应用和机器的规模，考虑解决问题的类型，使用通用还是专用？
并行计算机系统类型
Flynn分类
根据硬件对指令流和数据流的支持不同来区分并行的组织：SISD（单指令集操作单数据元素，机器架构并不是并行，但也存在并行结构）、SIMD（单指令流多数据流，数据并行，无依赖性）：GPU，向量处理器，阵列处理器（专用设计，与应用算法相关、指令广播瓶颈）、MISD（流处理器、脉动阵列处理器）、MIMD（多线程处理器，不同的指令流执行不同的程序）
结构模型
PVP（大规模向量处理器组成的结构）、SMP（对称结构）、MPP（大规模并行组成系统，物理和逻辑上都是分布内存）、DSM（分布式共享存储系统，逻辑上共享，物理上分开）、Cluster（每个节点都是一个完整的计算机）、COW（所有结点都可以用商用结点，采用Cluster集群）
访存模型
多处理机：UMA（物理存储器与所有器件的距离等关系一致）、NUMA（单地址空间共享存储器，访问时间随存储字的位置不同而变化，有的器件访问更快）、COMA（只用高速缓存，远程高速缓存访问借助于分布高速缓存目录进行）；多计算机：NORMA（多地址空间非共享存储器，结点之间并不是共享内存的）
多处理器
松耦合~ （无共享的全局存储地址空间、通过显式调用通信、多机网络）、紧耦合~（共享全局存储地址空间、SMP、操作共享数据需要同步）
编程模型等其他分类
共享内存
一种通信的方式，系统中所有处理器可以直接访问系统中的所有存储器，提供多处理器共享数据的便捷，可集中式也可分布式，一种单一地址空间的结构，支持各种并行模型，并行的线程通过共享内存实现通信和同步，很容易模拟其他模型，问题：可拓展性差。
动态线程
静态线程
消息传递
处理器可直接访问本地存储器，所有的通信和同步通过消息机制实现。
发送消息通常会带来额外开销：
构造一个消息（增加消息头部），拷贝数据到缓冲区，发送数据，接收数据到缓冲区，拷贝数据到用户进程地址空间。
很多步骤需要操作系统参与
利用消息同步通常基于各种握手（两军问题）协议
最大好处：容易扩展。
支持多种编程模型
使用范围：
集群系统
云计算
高性能计算
数据流
非冯诺依曼体系中”最靠谱“的结构
数据流模型中，指令激活与否取决于指令中操作数是否准备好（非冯诺依曼）并行
控制流模型中，计算按照指令间的显式或隐式顺序执行（冯诺依曼）串行
数据流优点：所有的数据依赖关系都清晰的表现在数据流图中。
问题：调试极为困难，每一次run的结果可能不同。
脉动阵列
像MISD
用处理单元的规则阵列替代单个的处理单元，精心处理不同处理单元间的数据流
在不增加内存带宽的前提下获得高的吞吐量
多用于信号处理
与常规流水线相比有显著特色。
应用：深度学习：谷歌的TPU，卷积神经网络。
数据并行
编程模型假设每一个处理器斗鱼一组数据有关联
所有处理器执行类似的操作处理不同的数据
GPU
硬件和软件
串行的硬件和软件
计算机只执行一个程序
冯诺依曼结构：
图灵机：先输入机器要执行的程序或总的指令，在接着处理相应的输入。
几乎所有计算机都采用的控制流架构
两个基本特征：存储程序和顺序执行指令（控制流）
关键术语
主存储器：一组位置的集合，每个位置都能够存储指令和数据
CPU：负责决定程序中应该执行哪条指令的控制部件（Boss），ALU执行计算
寄存器：非常快的存储，属于CPU
程序计数器：存储下一条要执行的指令的地址（PC，类似jal执行时存储下一条地址至$ra的作用）
总线（bus）：访存
操作系统的“进程”
正在执行的“计算机程序的实例”，所有信息的抽象
组成成分
可执行的机器语言程序
一块内存空间
操作系统分配给进程的资源描述符
多任务处理
多个线程或多个进程
每个进程轮流执行（时间片轮转）
时间到了之后，会等待直到再次获得时间片（block）
操作系统的线程
包含在进程中。
希望当一个线程因等待资源而阻塞时，另一个线程有工作要做并可运行。
改进冯诺依曼结构
高速缓存Cache
主存数据的一个copy
一种存储单元的集合，存取时间比其他一些存储单元短
CPU Cache通常在同一芯片上，因为CPU与内存距离太远了，将CPU一部分放在里内存更近的地方，便于访问。
局部性原理
空间局部性：访问相邻的位置
时间局部性：在下一个时刻访问
Cache的层次结构
Cache命中（hit）和缺失（miss）
Cache的问题
当CPU将数据写入Cache时，Cache中的值可能与主存中的值不一致
写直达
写入Cache时同时更新主存中的数据
写回
将Cache中被修改的数据标记为脏数据，当Cache行被来自主存的新数据替换时，脏数据写入主存
写分配
拿上来写
写不分配
Cache的映射
全相联
内存中所有位置的数，Cache中所有地方都可以放
直接映射
内存中的一个位置的数，Cache中只有一个地方可以放
n路组相联
每个Cache行可以被放置在n个不同位置之一
分成多个组
全相联+直接映射
虚拟内存
使用计算机的客户端
虚拟内存的功能相当于二级存储的Cache
交换空间：当前不活跃的部分被保存在辅助存储器的一个块中
交换单位：段、页（固定大小，典型值从4k到16k字节）
虚拟页号
程序被编译时，其页面编号被分配虚拟页号
程序执行时，创建一个将虚拟页号映射到物理地址的表
页表
快表TLB：
在非常快的内存中缓存来自页表的少量条目
页失效：试图访问页面表中的页面，但该页面不在内存中
指令级并行性
试图通过让多个处理器或功能单元同时执行指令来提高处理器性能
流水线——功能单元分阶段组织
多发射——同时发起多个指令
乱序执行
分层存储结构
Cathe的应用，更多的Cathe的层次。把计算拉近数据，减少冯诺依曼瓶颈的影响。
投机
编译器或处理器对一条指令进行猜测，在猜测的基础上执行这条指令
若系统投机失败，就重新执行
硬件多线程
在硬件层面上提供线程的切换——细粒度和粗粒度，前者指处理器在每个指令后在线程间切换，跳过停滞的线程，会拉长每个指令的执行时间，但是提高了系统的吞吐，避免因停顿而导致的算力浪费；后者指仅切换等待耗时操作完成而停顿的线程，处理器可以较短暂停时间内空闲，导致切换也会导致延迟，线程切换几乎不需要时间
不过这两者都只能在同一条线程上取指，
SMT（同时多线程）：细粒度多线程的变体，允许多个线程同时取指。
并行硬件和软件
SIMD
通过在处理器间划分数据实现并行性
对多个数据项应用相同的指令
缺点：所有ALU都被要求执行相同的指令，或保持空闲；在复杂的数据运行情况下，会有大量的串行化的情况出现，导致效率的降低。
向量处理器
对数据的数组或向量进行操作
向量存取器能够存储操作数向量同时对其内容进行操作
交叉存取：多个内存“bank”，多少可独立访问；向量的元素分布在多个存储体上，减少或消除读/写连续元素的延迟
跨步内存访问和硬件scatter/gather
优点：快、便于使用、向量化编译器擅长识别要利用的代码、编译器还可提供关于无法向量化的代码信息、高内存带宽、Cathe行中每个数据都可使用
缺点：不是向量或难以向量化的数据结构不能像其他并行结构一样被处理；扩展性差。
图形处理单元（GPU)
使用点、线和三角形在内部表示对象的表面
图形处理流水线将内部表示转换成可发送到显示器的像素阵列
通常可使用SIMD并行来优化性能，当前的GPU就是使用了SIMD
MIMD
支持多个数据流上同时执行多个指令流
互联网络
影响分布式和共享内存系统的性能
共享内存互连
总线互连
并行通信连线和一些控制总线访问的硬件的集合
交换互连
使用交换机来控制相连设备间的数据路由，交叉开关：允许不同设备间同时通信、比总线快但成本高
mesh
类似交换互连，网状结构，交换机集成到网状结点上，扩展高维mesh：torus网状结构上相距远的的结点再接一根线相连构成三维结构。
分布式存储互连
直接互连
对分带宽、带宽：前者衡量“同时通信的数量”或连接性的指标、两半网络之间可以同时进行多少通信，后者是链路传输数据的速率
全连接网络：任意两个结点间均有线相连
超立方体：高度连接的直接互连，三维超立方体是由两个二维超立方体对应顶点相连
间接互连
交叉开关
Omega网络
通常显示为单项链路和一组处理器，每个处理器都有一个输出链路和一个输入链路，以及一个交换网络。
问题
Cache一致性
程序员无法控制Cache及何时更新Cache
基于监听的Cache一致性
核共享一根总线，通过总线广播相应信息——更新协议或者标记更新的数据（置无效，打标签，避免不必要的更新，但会带来开销）
基于目录的Cache一致性
使用称为目录的数据结构来存储每个缓存行的状态
当有变量更新时，查询目录，且在其高速缓存中具有该变量的高速缓存行被置无效
内存一致性
多人访问共享内存空间，在并行运行情况下，每个人认为的访问顺序并不相同。
软件并行
SPMD—单程序多数据
MPMD—多程序多数据
写并行程序
在共享内存程序中：启动单个进程并创建线程，通过线程执行任务
在分布式存储程序中：启动多个进程，进程执行任务
注意：
每个线程/进程被分配到的工作量大致相同、通信最小化
安排线程/进程同步和之间的通信（依赖性少）。
任务并行(对不同的数据采用均分的方式)
数据并行(对相同的数据采取均分的方式)
同步方法
临界区、互斥、忙等
输入输出
是串行的
并行编程的Foster方法论
划分
将要执行的计算和计算操作的数据划分为小任务，确定可并行执行的任务
通信
确定在上一步确定的任务中需要进行什么样的任务
聚集或聚合
负载重新分配的过程
映射
写程序，将上一步中确定的复合任务分配给进程/线程，如何使通信最小化
性能
性能层次
峰值性能
LINPACK性能，求线性方程组的一组程序，大概平均性能是峰值性能的80%
Gordon Bell Prize（应用性能），超算应用水平最高的工作
平均持续应用性能
HPCG:能够利用的性能（1%~5%）
时间尺度
加速比：S（未加速前/加速后）=T并行/T串行，最理想情况：线性加速比：T并行=T串行/p（核数），并行程序效率：E = S/p
Amdahl’s Law
除非几乎所有串行程序都被并行化，否则可能的加速将非常有限，（不论有多少可用的核）
启示：可以并行化的部分要尽可能的大，才能使增加的资源的有意义，或者适当的增加问题的规模。
可拓展性：一般来说，若一个问题规模增大后仍能处理，则其可拓展。若增加线程/进程的数量，并不在增加问题规模的情况下保持固定的效率（如：加速比），则问题具有强扩展性。
计算时间
比较墙钟时间来确定性能效率。
吞吐指标
超算的应用
复杂的物理问题
数值模拟核反应全过程；多介质、多区、多尺度的特点；高温高压、高压缩比、大变形等极端物理现象；多物理过程紧耦合的非线性、非定常的大型系统
复杂数值天气预报
海洋学
空气动力学
风洞试验、模型自由飞和数值模拟
数值风洞模拟，减少进风洞的次数，节省成本，CFD软件系统
多学科优化
地理信息处理
数字地球
工业设计制造
高速列车
车身碰撞模拟
排水量船舶数值水槽
溃坝水流精细仿真模拟
大型循环流化床模拟
互联网网络舆情
演习、仿真：大样本、超实时
新能源新材料
风电设计全生命周期
纳米材料研究
先进功能材料与能源材料研究
生物医药健康
智慧城市
金融风险分析
文化创意设计
动漫、渲染
深度学习
HPDA,模型和算法的进化+计算能力的提升
协同
通信、负载均衡、同步（使得实现动态调度）
开始做
学习编写显式并行的程序
C语言
三种不同c扩展：消息传递端口、
创建并行程序
思考：
1.明确可以并行的任务
2.划分任务（包括与任务关联的数据）
3.处理数据读写、通信和同步
主要目标是加速比（T1/Tp）
分解
是动态的。随着程序的进行，需要识别新的任务。想办法创建足够多的任务使得系统中所有的执行的单元保持忙碌。阿姆达尔定律——依赖性限制了最大的并行加速比
串行程序的自动任务分解始终是具有挑战性的研究问题（相当难）：
编译器必须分析程序，识别依赖性：有些数据依赖在编译时无法知晓（例如：对同一内存地址的sw和lw对于编译器认为会是不具有依赖性的）
指派
负载均衡，降低通信开销
可以静态完成，也可运行时动态完成，通常语言/运行时会负责完成。
程序员负责的指派：静态指派，pthread，利用ISPC任务进行动态指派
编排
建立通信
若有必要，添加同步保护依赖
组织内存中的数据结构
调度任务
映射到硬件
映射“线程”到硬件执行单元，如：由操作系统映射、编译器映射、硬件映射
一些映射策略：将相关线程放在同一处理器上（最大化局部性和数据共享，最小化通信/同步开销）、将 不相关线程放在同一处理器上更有效的使用机器（可能受限不同）
基于2维网格的求解器
求解偏微分方程
迭代求解
识别依赖性
向处理器指派任务的可能方式
分块指派和交叉指派
考虑依赖（数据流）
barrier同步原语：
一种保守的表示依赖的方式，将计算分成阶段，其之前所有线程的所有计算完成前，其之后的所有线程的所有计算不能开始
共享地址空间求解器：一个barrier
通过牺牲空间来消除依赖
MPI编程
一个消息传递接口标准
提供一个可移植、高效、灵活的消息传递接口库
提供与C/C++和Fortran语言的绑定
6个基本函数组成的MPI子集
MPI初始化
1 | |
MPI结束
获取进程的编号
获取指定通信域的进程数
发送消息
消息接受
MPI消息
消息的内容在MPI中称为消息缓冲（Message Buffer）
消息的接收/发送者即信的地址，在MPI中称为消息信封
消息缓冲由三元组<起始地址，数据个数，数据类型>组成，消息信封
数据类型
预定义数据类型和派生数据类型，前者用来解决异构计算中的互操作性问题，建立与具体语言的对应关系；后者可用类型图来描述，是一系列二元组组成
附加类型：MPI_BYTE(一个字节)、MPI_PACKED(实现传输地址空间不连续的数据项)
构造函数来定义派生数据类型
消息标签
当发送者连续发送两个相同类型消息给同一接收者，若没有消息标签接收者将无法区分这两者
通信域
进程组
进程的有限（个数有限）、有序（按编号排序）集，组的大小和进程编号可以调用函数获得
通信上下文
安全的区别不同的通信以免相互干扰，不是显式的对象，只作为通信域的一部分出现
MPI提供丰富的函数管理通信域：
组间通信域
本地进程组和远程进程组
消息状态
是消息接收函数MPI_Recv的最后一个参数，存放接收消息的状态信息
通信方式
点对点通信
通信机制：阻塞和非阻塞。
通信模式：同步、缓冲、标准和就绪
机制和模式的组合产生不同的点对点通信的方式。
同步：
只有相应的接受过程已启动，发送过程才正确返回
缓冲：
不管操作是否已启动都可执行，需要用户程序提前申请缓冲区，（空间换时间）
标准：
是否对发送数据进行缓冲由MPI的实现决定，程序员不可见，发送可以是同步或缓冲，取决于实现
就绪：
发送操作只有在接收进程相应的接收操作已经开始才进行发送。
阻塞：
通信还没结束时，处理器只能等待，浪费了计算资源，常见技术是设法使计算与通信重叠，非阻塞通信可以用来实现这一目的
非阻塞：
通信返回后并不意味着通信操作的完成，MPI提供了对非阻塞通信完成的检测
双缓冲是一种常用的方法，为X和Y各自准备两个单独的缓冲
需确保缓冲中数据在缓冲被更新前使用
send_handle和revc_handle分别用于检查发送接收是否完成
集合通信
通信
组内数据传输
聚集
同步
实现组内进程的一致性
广播是一对多通信的典型例子，
收集格式：多对一，接收缓冲、发送缓冲
散播与收集相反，一对多
多对多通信：Allgather每个进程都作为ROOT进程执行一次Gather
全局交换：Alltoall，等价于每个进程作为Root进程进行了一次散播操作，每个进程发送一个消息发给所有进程
栅障同步：保持调用的函数参数的通信域中同步
归约和扫描，前者对每个进程的发送缓冲区中的数据按给定的操作进行运算，将最终结果放在Root进程的接收缓冲区中，参与计算操作的数据项的数据类型在Datatype域中定义，由Op域定义。允许贡献向量值，不只是标量值，长度由Count定义。后者可以被看做特殊的归约，即每个进程都对排在其前的进程进行归约操作
微信
