高性能云计算复习

并行计算概述

什么是并行计算？

并行计算（Parallel Computing）,同义词：高性能计算（High Performance Computing）、超级计算（Super Computing）

在并行机上，将一个应用分解成多个子任务，分配给不同的处理器，各个处理器之间相互协同，并行地执行子任务，从而达到加速求解速度，或者求解应用问题。

基本条件

硬件（并行机）：

并行机至少包含两台或两台以上处理机，这些处理机通过互连网络相互连接，相互通信。
并行算法设计：

也就是说，应用可以分解为多个子任务，这些子任务可以并行地执行。将一个应用分解为多个子任务的过程，称为并行算法的设计。
并行编程环境：

在并行机提供的并行编程环境上，具体实现并行算法，编制并行程序，并运行该程序，从而达到并行求解应用问题的目的。

主要目标

提高求解速度：

例如，在单处理器上，串行执行需要2 个星期（14 天），借助并行计算，使用100 台处理器，加速50 倍，将执行时间缩短为6.72 个小时。
扩大问题规模：

例如，在单处理器上，受内存资源2GB的限制，只能计算10 万个网格，也可以借助并行计算，使用100 个处理器，将问题求解规模线性地扩大100 倍。

并行计算体系结构（1）

概述

并行计算机网络性能指标

节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。
网络直径（Network Diameter）：网络中任何两个节点之间的最长距离，即最大路径数。
对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数
如果从任一节点观看网络都一样，则称网络为对称的（Symmetry）
对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数
网络规模：网络包含的结点总数，或者包含的CPU 总数。

在固定网络规模的情况下，对剖带宽越高、对剖宽度越大、网络直径越小，则互联网络的质量就越高。

静态互联网络

静态连接

处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变

• 典型的静态网络

一维线性阵列、二维网孔、树连接、超立方网络、立方环等。

一维线性阵列

二维网孔

改进：

二叉树

标准二叉树拓扑结构包含P=2^N个叶结点和2^N-1个内结点
- 叶结点分别对应并行机的结点；
- 内结点负责这些叶结点之间的通信。
二叉树的网络直径仅为2 log P，非常有利于叶结点之间的全局通信。
它的折半宽度只为1，不利于结点之间的大数据量通信。

改进：（胖树）

超立方

是一个具有很好性质的拓扑结构，其网络直径仅为logP，折半带宽为2^(d-1)。
结点的度为d，随并行机规模的增加而增加，这给网络实现带来了一定的困难。
通常地，超立方体一般不超过5 维。

k-立方环

静态互联网络特性比较（记）

动态互联网络

···

并行计算体系结构（2）

Flynn分类

指令流/数据流分类法，即费林-Flynn分类法。（计算机系统分类）

（1）指令流（Instruction Stream）：机器执行的指令序列。

（2）数据流（Data Stream）：指令调用的数据序列，包括输入数据和中间结果。

（3）多倍性（Multiplicity）：在系统性能瓶颈部件上同时处于同一执行阶段的指令或数据的最大可能个数。

• 两个独立的维度——指令流和数据流的不同组织方式，将计算机系统分为四类：

单指令单数据流（Single Instruction stream and Single Data stream , SISD）系统
单指令多数据流（Single Instruction stream and Multiple-Data stream , SIMD）系统
多指令单数据流（Multiple-Instruction stream and Single Data stream , MISD）系统
多指令多数据流（Multiple-Instruction stream and Multiple-Data stream , MIMD）系统

• SISD：SISD系统是一种传统的顺序执行的单处理器计算机，它的硬件不支持任何形式的并行计算，所有的指令都是串行执行。在任何一个时钟周期内，CPU只能处理一个数据流，因此这种机器被称作单指令流单数据流机器

• SIMD：SIMD系统有多个处理单元，由单一的指令部件控制，按照同一指令流的要求为它们分配各不相同的数据流并进行处理。系统结构由一个控制器、多个处理器、多个存储模块和一个互连总线（网络）组成

• MISD：MISD系统有多个处理单元，每个处理单元按照多条不同的指令要求同时对同一数据流及其处理输出的结果进行不同的处理，把一个单元的输出作为另一个单元的输入

• MIMD ：MIMD系统又称为多处理机系统，是指能实现指令、数据作业、任务等各级全面并行计算的多机处理系统，可以将一个主任务分解为众多子任务并行执行以缩短工作时间

内存访问模型

并行计算机的体系结构

组成要素
- 处理器（processor）:计算单元
- 互联网络（interconnect network）:连接
- 内存（memory）:多个存储模块的组成

并行机的基本特征是具备多个计算单元和存储模块，各个模块通过互联网络耦合

根据耦合的紧密程度可分为紧耦合和松耦合。
不同的并行计算机，其各模块耦合的松紧程度可以有区别

共享内存vs分布式内存

共享内存

通常也称为紧密耦合多处理机，它具有一个所有处理器都可以访问的全局物理内存。

共享内存系统的特性有：

对称性：系统中任何处理器都可以访问任何的内存单元和I/O设备
单地址空间：内存中每一个位置在整个的内存地址范围内有一个唯一的地址
低通信延迟：处理器间的通信可以利用共享内存来进行数据交换
高速缓存及其一致性：多级高速缓存可以支持数据的局部性，而其一致性可由硬件来增强

分布式内存

分布式内存系统中处理器都有各自的内部寄存器，一个核内的内存地址对其他核不可见，只能由该处理器所访问，对于所有CPU都没有单一全局地址空间的概念，这类的分布式计算机系统称为非远程存储访问（No-Remote Memory Access, NORMA）

并行计算机访问模型

UMA（Uniform Memory Access）模型：均匀存储访问模型。
NUMA（Non-Uniform Memory Access）模型：非均匀存储访问模型。
COMA（Cache-Only Memory Access）模型：全高速缓存存储访问。
CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型：高速缓存一致性非均匀存储访问模型。
NORMA（No-Remote Memory Access）模型：非远程存储访问模型。

UMA（Uniform Memory Access）

物理存储器被所有处理器均匀共享；
所有处理器访问任何存储字取相同的时间；
每台处理器可带私有高速缓存；
外围设备(I/O)也可以一定形式共享；
发生访存竞争时，仲裁策略平等对待每个结点，即每个结点机会均等；

NUMA（Non-Uniform Memory Access）

非均匀存储访问

被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；
处理器访问存储器时间是不一样的；
每台处理器照例可带私有高速缓存。

CC-NUMA（高速缓存一致性非均匀存储访问模型）

Coherent-Cache Nonuniform Memory Access

特点：

大多数使用基于目录的高速缓存一致性协议；
保留SMP结构易于编程的优点，也改善常规SMP的扩张性；
CC-NUMA实际上是一个分布共享存储的DSM多处理机系统;
它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。

COMA

特例：全高速缓存存储访问（Cache-Only Memory Access, COMA）模型，COMA各个处理器节点没有存储层次结构，所有节点的高速缓存构成了全局地址空间

(NORMA)（非远程存储访问）

优点：

内存可以随着CPU的数量进行扩展，增加处理器数量将使内存的大小等比例增加
各个处理器可以无冲突地快速访问自己的内存，也不存在维护缓存一致性的开销
成本效益上，可以使用商用、现成的处理器和网络

局限性：

程序员将要负责所有处理器间数据通信相关的细节问题
很难从基于全局内存空间的数据结构上建立起到分布式内存管理的映射。
非一致的内存访问时间使得驻留在远程节点上的数据比节点本地数据的访问需要更长时间。

PVP（Parallel Vector Processor）

并行向量处理器

SMP（Symmetric Multiprocessing）

对称多处理器

内存模块和处理器对称地分布在互联网络的两侧;
内存访问属典型的均匀访问模型。

特点：

优点：

对称共享存储

系统中任何处理器均可直接访问任何存储模块中的存储单元和I/O 模块，且访问的延迟、带宽和访问成功的概率是一致的。所有内存单元统一编址。各个处理器之间的地位等价，不存在任何特权处理器。操作系统可在任意处理器上运行。
单一的操作系统映像

全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程到各个处理器，并保持各处理器间的负载平衡。
局部高速缓存cache 及其数据一致性

每个处理器均配备局部cache，它们可以拥有独立的局部数据，但是这些数据必须与存储器中的数据保持一致。
低通信延迟

各进程通过读/写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信的延迟。
共享总线带宽

所有处理器共享总线的带宽，完成对内存模块和I/O 模块的访问。
支持消息传递、共享存储并行程序设计。

缺点：

欠可靠

总线、存储器或操作系统失效可导致系统崩溃。
可扩展性（scalability）较差

由于所有处理器共享总线带宽，而总线带宽每3 年才增加2 倍，跟不上处理器速度和内存容量的增加步伐，因此，SMP 并行机的处理器个数一般少于32 个，且只能提供每秒数百亿次的浮点运算性能。

大规模并行处理机（Massively Parallel Processor，MPP）

由大规模“紧密”互连的节点组成的
内存访问属于非远程访问模型（NORMA）
也被称为“message-passing”系统

由数百个乃至数千个计算结点和I/O 结点组成，每个结点相对独立，并拥有一个或多个微处理器。
- 这些结点配备有局部cache，并通过局部总线或互联网络与局部内存模块和I/O设备相连接。
- 这些结点由局部高性能网卡(NIC)通过高性能互联网络相互连接。
- 各个结点均拥有不同的操作系统映像。
  - 一般情况下，用户可以将作业提交给作业管理系统，由它负责调度当前最空闲、最有效的计算结点来执行该作业。但是，MPP也允许用户登录到某个特定的结点，或在某些特定的结点上运行作业。
- 各个结点间的内存模块相互独立，且不存在全局内存单元的统一硬件编址。
- 仅支持消息传递或者高性能Fortran并行程序设计，不支持全局共享的OpenMP并行程序设计模式。

集群、机群（Cluster）/COW

松耦合。分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统。
优点：
- 投资风险小
- 系统结构灵活
- 性能/价格比高
- 能充分利用分散的计算资源
- 可扩放性好
问题
- 通信性能
- 并行编程环境

例子：Berkeley NOW，Alpha Farm, FXCOW

MPP vs Cluster

Cluster的每个结点都是一台完整的计算机。 Cluster的每个结点上都有完整的操作系统，而MPP的每个结点上通常只有操作系统的微核。 Cluster的网络和操作系统均不是定制的。
Cluster的每个结点内有本地磁盘，而MPP的结点内没有。
Cluster各结点的网络接口是连接到I/O总线上的（松耦合），而MPP各结点的网络接口是连接到存储总线上的（紧耦合）。

DSM（Distributed Shared Memory ，DSM）

内存体系

五种结构特性

并行计算模型及性能评测

并行计算模型

将并行计算机的基本特征抽象出来，形成一个抽象的计算模型，作为并行算法分析、设计、性能预测的基础。

PRAM模型

基本概念

由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。

Parallel Random Access Machine

优点

适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。

缺点

不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素

BSP模型

基本概念

由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。

模型参数：

p：处理器数(带有存储器)
l：同步障时间(Barrier synchronization time)
g：带宽因子(time steps/packet)=1/bandwidth

LogP模型

概念

由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。

模型参数：

L(Latency) 表示源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限，表示网络中消息的延迟。
o(overhead)表示处理机准备发送或接收每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理不能执行其它操作。
g(gap)表示一台处理机连续两次发送或接收消息时的最小时间间隔，其倒数即微处理机的通信带宽。
P(Processor)处理机/存储器模块个数

注：L和g反映了通讯网络的容量

性能评测

性能评测：性能评价和性能分析

• 性能评价和性能分析可以揭示高性能计算机、并行算法和并行应用程序的性能特点和性能瓶颈，指导高性能计算机、并行算法和应用程序的设计与改进

机器级性能评测

CPU和存储器的某些基本性能指标；并行和通信开销分析；并行机的可用性与好用性以及机器成本、价格与性/价比

算法级性能评测

加速比（Speedup）：对于一个给定的应用，并行算法（或并行程序）相对于串行算法（或串行程序）的性能提高程度。
- Amdahl定律
- Gustafson定律
- Sun Ni定律

可扩展性（Scalability）：当系统和问题的规模增大时，可维持相同性能的能力，即指应用、算法和结构能否充分利用不断增长的处理器的能力
- 等效率度量标准
- 等速度度量标准
- 平均延迟度量标准

Amdahl定律

增强的Amdahl定律

Gustafson定律

Sun & Ni定律

程序级性能评测

等效率测速（Efficiency Metrics）

效率：加速比 / 处理器数
简单情况下能得出分析结果

并行算法设计

…

PCAM设计方法学，并行算法的一般设计过程

设计并行算法的四个阶段

划分（Partitioning）
通信（Communication）
组合（Agglomeration）
映射（Mapping）

划分

划分方法描述

充分开拓算法的并发性和可扩放性；

分为两类划分：

域分解(domain decomposition)/数据分解
功能分解(functional decomposition)

• 先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)；

• 使数据集和计算集互不相交

• 划分阶段忽略处理器数目和目标机器的体系结构

域划分

划分的对象是数据，可以是算法的输入数据、中间处理数据和输出数据
将数据分解成大致相等的小数据片
划分时考虑数据上的相应操作
如果一个任务需要别的任务中的数据，则会产生任务间的通信

功能划分

划分的对象是计算，将计算划分为不同的任务，其出发点不同于域分解；
划分后，研究不同任务所需的数据。
- 如果这些数据不相交的，则划分是成功的；
- 如果数据有相当的重叠，意味着要重新进行域分解和功能分解；
功能分解是一种更深层次的分解。

通信

通信是PCAM设计过程的重要阶段；
划分产生的诸任务，一般不能完全独立执行，需要在任务间进行数据交流；从而产生了通信；
功能分解确定了诸任务之间的数据流；
诸任务是并发执行的，通信则限制了这种并发性；

四种通信模式

局部/全局通信（Local/Global communication）
结构化/非结构化通信（Structure/Unstructured communication）
静态/动态通信（Static/Dynamic communication）
同步/异步通信（Synchonous/Asynchronous）

组合

组合是由抽象到具体的过程，是使得组合的任务能在一类并行机上有效的执行
合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则也完成了映射过程
通过增加任务的粒度和重复计算，可以减少通信成本
保持映射和扩展的灵活性，降低软件工程成本

表面-容积效应（Surface-to-Volume Effects）

通信量与任务子集的表面成正比，计算量与任务子集的体积成正比
增加重复计算有可能减少通讯量

映射

每个任务要映射到具体的处理器，定位到运行机器上；
任务数大于处理器数时，存在负载平衡和任务调度问题；
映射的目标：减少算法的执行时间
- 并发的任务 -> 不同的处理器
- 任务之间存在高通信的 -> 同一处理器

• 映射实际是一种权衡，属于NP完全问题；

两种策略

使得任务可以被不同的处理器并发地执行，增强并发性（concurrency）
将通信频繁的任务放到同一个处理器上，增强局部性（locality）

负载平衡算法

任务调度算法

并行程序设计基础

Cannon

算法描述

复杂度分析

DNS

OpenMP

进程： 进程是操作系统资源分配的基本实体
线程： 线程是CPU调度和分配的基本单位
在Linux系统下是没有线程的概念的，它是用进程模拟的线程，因此把线程叫做轻量级进程。

OpenMP 是一个应用程序接口(API)，由一组主要的计算机硬件和软件供应商联合定义。OpenMP 为共享内存并行应用程序的开发人员提供了一个可移植的、可伸缩的模型。该API在多种体系结构上支持 C/C++ 和 Fortran。

什么是OpenMP

OpenMP中文教程 - 简书 (jianshu.com)

OpenMP是：

一种应用程序接口(API)，可用于显式地指示多线程、共享内存并行性。
由三个主要的API组件组成：
- 编译器指令
- 运行时库函数
- 环境变量
Open Multi-Processing的缩写

`Fork-Join`模型

OpenMP 使用并行执行的 fork-join 模型：

所有 OpenMP 程序都开始于一个主线程。主线程按顺序执行，直到遇到第一个并行区域结构。
FORK：主线程然后创建一组并行线程。
之后程序中由并行区域结构封装的语句在各个团队线程中并行执行。
JOIN：当团队线程完成并行区域结构中的语句时，它们将进行同步并终止，只留下主线程。
并行区域的数量和组成它们的线程是任意的。

编译器指令

格式

#pragma omp	directive-name	[clause, …]	newline
所有 OpenMP C/C++ 指令都需要。	一个有效的 OpenMP 指令。必须出现在 `pragma` 之后和任何子句之前。	可选的。除非另有限制，子句可以按任何顺序重复。	必需的。在此指令所包含的结构化块之前。

#pragma omp 指令 [子句]

下面是一些常见的OpenMP编译器指令格式的示例：

#pragma omp parallel：用于创建并行区域，指示编译器将其中的代码并行执行，并创建一个线程团队。

#pragma omp parallel [clause]
{
    // 并行执行的代码块
}

#pragma omp for：用于并行化循环，将循环迭代分配给不同的线程执行。

#pragma omp for [clause]
for (int i = 0; i < n; i++) {
    // 循环体
}

循环增量操作：循环增量操作会由编译器自动处理，保证每个线程独立地更新自己的循环变量。
如果循环体内部存在对共享变量的修改操作，可能会导致竞争条件。在这种情况下，需要使用适当的同步机制

#pragma omp critical：用于标记一个临界区，保证在任意时刻只有一个线程可以进入该临界区。

#pragma omp critical
{
    // 临界区代码
}

#pragma omp barrier：用于插入一个隐式的同步点，确保所有线程在此处等待，直到所有线程都到达该点。

#pragma omp barrier

#pragma omp parallel for：结合了并行区域和循环并行化的指令，用于并行化循环并创建线程团队。

#pragma omp parallel for [clause]
for (int i = 0; i < n; i++) {
    // 循环体
}

常用的子句如下：

num_threads(num)：指定并行域内线程的数目；
shared(var1,var2)：指定一个或者多个变量为多个线程的共享变量；
private(var1,var2)：指定一个变量或者多个变量在每个线程中都有它的副本；　
reduction(operator:product):指定归约操作。该子句用于指定在并行循环中进行归约操作的变量，并指定归约操作的类型，如求和、求积、求最大值等。（变量同名）（并行区里的变量是私有的）

运行时库函数

下面是一些常用的OpenMP函数：

omp_get_thread_num()：返回当前线程的线程号。

omp_get_num_threads()：返回并行区域中的线程数。

omp_set_num_threads(int num_threads)：设置并行区域中的线程数。

omp_get_max_threads()：返回可用的最大线程数。

omp_get_wtime()：返回当前时间，用于计算程序的执行时间。

omp_get_num_procs()：返回系统中的处理器核心数。

#include<iostream>
#include<omp.h>
using namespace std;

long num_threads=128;
long num_steps=100000000;

int main(){
    double sum,pi;
    double step = 1/(double)num_steps;
    for(int i=1;i<=num_threads;i++){
        double start = omp_get_wtime();
        sum=0.0;
        pi=0.0;
        double x;
        #pragma omp parallel for num_threads(i) private(x) reduction(+:sum)
        for(int j=0;j<num_steps;j++){
            x=step*(j+0.5);
            sum+=4/(1+ x*x);
        }
        pi=sum*step;
        cout<<pi<<"   time="<<omp_get_wtime()-start<<endl;
    }
}

环境变量

MPI

基本概念

MPI 全名叫 Message Passing Interface，即信息传递接口，作用是可以通过 MPI 可以在不同进程间传递消息，从而可以并行地处理任务，即进行并行计算。需要注意的是，尽管我们偶尔会说使用 MPI 编写了某某可执行程序，但是 MPI 其实只是一个库，而不是一种语言，其可以被 Fortran、C、C++、Python 调用。

MPI并不是多线程编程模型，而是多进程编程模型。它强调进程间的消息传递和同步，而不是共享内存。因此，MPI适用于分布式内存系统（如集群）上的并行计算，而不适用于共享内存系统（如多核处理器）上的并行计算。

通讯域

通信域定义了一组能够互相发消息的进程。在这组进程中，每个进程会被分配一个序号，称为 rank，进程间显性地通过指定 rank 作为标识来进行通信，一个进程 rank 可以指定另一个进程的 rank 以及独一无二的消息标签 tag 来发送消息。接收者也可以发送一个特定标签标记的消息的请求。类似于这样的涉及一个发送者以及一个接收者的通信被称为点对点(point-to-point)通信。

常用函数

MPI_Init是MPI库中的一个函数，它用于初始化MPI运行环境。在一个MPI程序中，通常在主函数的开始处调用MPI_Init函数。

函数原型如下：

int MPI_Init(int *argc, char ***argv)

参数argc和argv是主函数的参数，它们是用于命令行参数传递的。在调用MPI_Init之后，MPI库会解析并处理这些参数，并从中提取MPI相关的信息。这样做是为了确保MPI库能够正确地获取运行MPI程序所需的全部资源。

调用MPI_Init后，MPI运行环境会被初始化，MPI库将为每个MPI进程分配必要的资源，并建立MPI进程间的通信通道。每个进程都会被分配一个唯一的标识符（rank），可以通过调用MPI_Comm_rank函数获取自己的rank值。

MPI_COMM_WORLD:

MPI_COMM_WORLD是MPI中的一个预定义的通信器（communicator）。它表示一个包含所有MPI进程的通信组，也就是所有进程之间的默认通信环境。

在MPI程序中，通信器（communicator）是一个抽象的概念，用于指定一组进程之间的通信关系。通信器定义了一个进程组，进程组中的进程可以相互通信。MPI提供了多种创建和使用通信器的方法，其中MPI_COMM_WORLD是最常用的一个。

MPI_COMM_WORLD通信器由MPI库在程序启动时自动创建，并且包含了运行MPI程序的所有进程。它是一个全局的通信器，可以在程序中直接使用，无需显式创建或销毁。在MPI函数中，通过指定MPI_COMM_WORLD作为通信器参数，可以将操作应用于所有进程之间的通信。

MPI_Comm_rank是MPI库中的一个函数，用于获取当前进程在指定通信器中的标识符（rank）。

函数原型如下：

int MPI_Comm_rank(MPI_Comm comm, int *rank)

参数comm是一个MPI通信器，用于指定进程组的通信关系。通常可以使用MPI_COMM_WORLD作为通信器，表示全局的通信组。参数rank是一个指向整数的指针，用于存储当前进程在指定通信器中的rank值。

调用MPI_Comm_rank函数后，当前进程会获取指定通信器中的rank值，并将其存储在rank指向的变量中。rank值从0开始，表示进程在通信组中的唯一标识符。

MPI_Comm_size是MPI库中的一个函数，用于获取指定通信器中的进程总数。

函数原型如下：

int MPI_Comm_size(MPI_Comm comm, int *size)

参数comm是一个MPI通信器，用于指定进程组的通信关系。通常可以使用MPI_COMM_WORLD作为通信器，表示全局的通信组。参数size是一个指向整数的指针，用于存储指定通信器中的进程总数。

调用MPI_Comm_size函数后，当前进程会获取指定通信器中的进程总数，并将其存储在size指向的变量中。

MPI_Reduce是MPI库中的一个函数，用于在通信组中进行归约操作（reduce）。归约操作将多个进程的数据进行聚合，得到一个全局的结果。

函数原型如下：

int MPI_Reduce(const void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

参数说明：

sendbuf：发送缓冲区的起始地址，指定了每个进程要发送的数据。
recvbuf：接收缓冲区的起始地址，用于存储归约操作的结果。只在根进程（root）中有效。
count：发送和接收缓冲区中的元素数量。
datatype：数据元素的类型。
op：归约操作的类型，例如MPI_SUM表示求和操作。
root：根进程的rank值，指定了接收归约结果的进程。
comm：通信器，用于指定通信组。

调用MPI_Reduce函数后，在通信组中的每个进程将把自己的数据（位于sendbuf中）根据指定的归约操作（op）进行归约，最终的结果将存储在根进程的recvbuf中。

MPI_Finalize是MPI库中的一个函数，用于结束MPI运行环境，释放相关资源。

函数原型如下：

int MPI_Finalize()

调用MPI_Finalize函数会终止当前MPI程序的执行，并释放与MPI相关的资源。通常，MPI_Finalize应该在主函数的结尾处被调用。

MPI_Send是MPI库中的一个函数，用于发送消息（数据）给其他进程。

函数原型如下：

int MPI_Send(const void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)

参数说明：

buf：发送缓冲区的起始地址，指定了要发送的数据。
count：发送缓冲区中的元素数量。
datatype：数据元素的类型。
dest：目标进程的rank值，指定了消息的接收进程。
tag：消息的标签，用于区分不同的消息。
comm：通信器，用于指定通信组。

MPI_Recv是MPI库中的一个函数，用于接收其他进程发送的消息（数据）。

函数原型如下：

int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)

参数说明：

buf：接收缓冲区的起始地址，用于存储接收到的数据。
count：接收缓冲区中的元素数量。
datatype：数据元素的类型。
source：源进程的rank值，指定了消息的发送进程。
tag：消息的标签，用于区分不同的消息。
comm：通信器，用于指定通信组。
status：用于返回接收操作的状态信息。

MPI_Bcast是MPI库中的一个函数，用于将数据广播给所有进程，使得每个进程都能接收到相同的数据。

函数原型如下：

int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm)

参数说明：

buffer：发送缓冲区的起始地址（对于根进程）或接收缓冲区的起始地址（对于非根进程）。
count：缓冲区中的元素数量。
datatype：数据元素的类型。
root：广播操作的根进程的rank值，即广播操作的发送方。
comm：通信器，用于指定通信组。

#include<iostream>
#include<mpi.h>
using namespace std;

int main(int argc,char *argv[]){
    int rank,size;
    int n = 0;
    MPI_Init(&argc,&argv); // 初始化MPI环境，创建MPI_COMM_WORLD
    MPI_Comm_rank(MPI_COMM_WORLD,&rank); // 获取当前进程在指定通信器中的标识符
    MPI_Comm_size(MPI_COMM_WORLD,&size); // 获取指定通信器中的进程总数

    if(rank == 0){
        MPI_Send(&rank,1,MPI_INT,1,0,MPI_COMM_WORLD); // 发送数据
        cin>>n;
    }

    MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD); // 广播，对于0是发，非0是收
    
    if(rank==1){
        int t=-1;
        MPI_Status status;
        MPI_Recv(&t,1,MPI_INT,0,0,MPI_COMM_WORLD,&status); // 接收数据
        //cout<<t<<endl;
    }
    cout<<n<<endl;
    MPI_Finalize(); // 结束MPI环境，释放资源
}

#include<iostream>
#include<mpi.h>
using namespace std;

int main(int argc,char *argv[]){
    long num_steps; // 步数
    double step; // 步长
    double sum=0.0,x; 
    double pi;
    int rank;
    int size;
    MPI_Init(&argc,&argv); // 初始化MPI环境
    MPI_Comm_rank(MPI_COMM_WORLD,&rank); // 获取进程标识
    MPI_Comm_size(MPI_COMM_WORLD,&size); // 获取进程数

    if(rank==0){
        cout<<"请输入步数："<<endl;
        cin>>num_steps;
    }
    MPI_Bcast(&num_steps,1,MPI_LONG,0,MPI_COMM_WORLD); // 广播
    step = 1/(double)num_steps;
    for(int i=rank;i<num_steps;i+=size){
        x=step*(i+0.5);
        sum+=4/(1+x*x);
    }
    MPI_Reduce(&sum,&pi,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD); // 归约
    if(rank==0){
        pi = pi*step;
        cout<<pi<<endl;
    }
    MPI_Finalize(); // 结束MPI环境
}

Hadoop and MapReduce

深入浅出大数据：到底什么是Hadoop？ - 知乎 (zhihu.com)

https://juejin.cn/post/7143767067907325982

Hadoop是什么？

1）Hadoop是一个由Apache基金会所开发的分布式系统基础架构。

2）主要解决，海量数据的存储和海量数据的分析计算问题。

3）广义上来说，Hadoop通常是指一个更广泛的概念——Hadoop生态圈。

Hadoop特点

高可靠性

Hadoop底层维护多个数据副本，所以即使Hadoop某个计算元素或存储出现故障，也不会导致数据的丢失。

高扩展性

在集群间分配任务数据，可方便的扩展数以千计的节点。

高效性

在MapReduce的思想下，Hadoop是并行工作的，以加快任务处理速度。

高容错性

能够自动将失败的任务重新分配。

Hadoop组成

Hadoop1.x、2.x、3.x区别

在这里插入图片描述

HDFS

Hadoop Distributed File System，简称 HDFS，是一个分布式文件系统。

1）NameNode（nn）：存储文件的元数据，如文件名，文件目录结构，文件属性（生成时间、副本数、文件权限），以及每个文件的块列表和块所在的DataNode等。

2）**DataNode(dn)**：在本地文件系统存储文件块数据，以及块数据的校验和。

3）**Secondary NameNode(2nn)**：每隔一段时间对NameNode元数据备份。。

YARN架构

Yet Another Resource Negotiator 简称 YARN ，另一种资源协调者，是 Hadoop 的资源管理器。

在这里插入图片描述

MapReduce

MapReduce将计算过程分为两个阶段：Map和Reduce

1）Map阶段并行处理输入数据

2）Reduce阶段对Map结果进行汇总

在这里插入图片描述

package org.creaational;

import org.apache.hadoop.*;
import java.util.StringTokenizer;


public class WordCount {

    public static class TokenizerMapper extends Mapper<Object,Text,Text,IntWritable>{
        private final static IntWritable one = new IntWritable(1);
        private Text word = new Text();
        public void map(Object key,Text value,Context context) throws Exception{
            StringTokenizer tks = new StringTokenizer(value.toString());
            while(tks.hasMoreTokens()){
                word.set(tks.nextToken());
                context.write(word,one);
            }
        }
    }

    public static class IntSumReducer extends Reducer<Text,IntWritable,Text,IntWritable>{
        private IntWritable result = new IntWritable();
        public void reduce(Text key,Iterable<IntWritable> values,Context context) throws Exception{
            int sum = 0;
            for(IntWritable val : values){
                sum += val.get();
            }
            result.set(sum);
            context.write(key,result);
        }
    }




    public static void main(String[] args) throws Exception{
        Configuration conf = new Configuration();
        Job job = new Job。getInstance(conf,"word count");

        job.setJarByClass(WordCount.class);
        job.setMapperClass(TokenizerMapper.class);
        job.setCombinerClass(IntSumReducer.class);
        job.setReduceClass(IntSumReducer.class);

        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);

        FileInputFormat.addInputPath(job,new Path(args[0]));
        FileOutputFormat.setOutputPath(job,new Path(args[1]));

        System.exit(job.waitComplete(true)?0:1);
    }
}

Container and Docker

制定容器镜像格式
构建容器镜像 docker build
管理容器镜像 docker images
管理容器实例 docker ps
运行容器 docker run
实现容器镜像共享 docker pull/push

docker ps:查看容器实例

docker stats:查看容器资源使用情况

Docker commands

Command	Note
docker network ls	列出当前Docker主机上的所有网络
docker network inspect NETWORK_ID	检查Docker网络的详细详细信息
docker exec CONTAINED_NAME cat /etc/host	查看指定容器中，文件内容
docker exec -it CONTATNED_NAME /bin/bash	打开交互式的Bash shell
docker logs –details CONTAINTED_NAME	查看容器的日志信息

并行计算概述

什么是并行计算？

基本条件

主要目标

并行计算体系结构（1）

概述

并行计算机网络性能指标

静态互联网络

静态连接

一维线性阵列

二维网孔

二叉树

超立方

k-立方环

静态互联网络特性比较（记）

动态互联网络

并行计算体系结构（2）

Flynn分类

内存访问模型

并行计算机的体系结构

共享内存vs分布式内存

共享内存

分布式内存

并行计算机访问模型

UMA（Uniform Memory Access）

NUMA（Non-Uniform Memory Access）

CC-NUMA（高速缓存一致性非均匀存储访问模型）

COMA

(NORMA)（非远程存储访问）

PVP（Parallel Vector Processor）

SMP（Symmetric Multiprocessing）

大规模并行处理机（Massively Parallel Processor，MPP）

集群、机群（Cluster）/COW

MPP vs Cluster

DSM（Distributed Shared Memory ，DSM）

内存体系

五种结构特性

并行计算模型及性能评测

并行计算模型

PRAM模型

基本概念

BSP模型

基本概念

LogP模型

概念

性能评测

机器级性能评测

算法级性能评测

Amdahl定律

Gustafson定律

Sun & Ni定律

程序级性能评测

等效率测速（Efficiency Metrics）

并行算法设计

划分

域划分

功能划分

通信

四种通信模式

组合

表面-容积效应（Surface-to-Volume Effects）

映射

两种策略

负载平衡算法

任务调度算法

并行程序设计基础

Cannon

算法描述

复杂度分析

DNS

OpenMP

什么是OpenMP

Fork-Join模型

编译器指令

格式

运行时库函数

环境变量

MPI

基本概念

通讯域

`Fork-Join`模型