嗯~隔了一段时间没有看并行计算，做作业的小偷做不完，不得不写博客记录复习=预习的内容。
并行计算性能评价并行机的基本性能指标中，对并行计算机性能的关注点在于CPU和内存，毕竟CPU和内存决定了计算机处理问题速度的上限。
https://www.top500.org/收录了500台世界上计算能力最强的计算机
可见，超算top 5领域的美国位居三，我国神威太湖之光排名第四，让我们来看看神威的详细布局：
即使是这么多核内存orz…处理器的频率似乎也不是很高，其实是1.45GHz，个人笔记本电脑都可以达到2.2GHz，台式机可以达到3.5GHz。 也许，因为有千万个核心，所以不需要太高的频率。 再次是Orx。 稍后将讨论浮点运算的计算能力。 还有，这个耗电量也很厉害…操作系统是Sunway RaiseOS操作系统
是说了top 500，还是回到标题内容，评价一个平行机有什么指标？ 有一些可以借鉴的，一些我们刚才在上面的神威中学习的。
上面的mention达到逐次执行时间和并行执行时间时，一般以下公式成立：
程序执行时间=计算时间并行开销时间相互通信时间
加速比性能定律这个加速比其实去年已经说过了。 《计算机组成与设计》这里： https://blog.csdn.net/weixin _ 44026604/article/details/112167660，但加速比不仅仅是Amdahl定律
并行加速比实际上是指相对于串行时间，对于某个APP应用程序，并行算法的执行速度比串行算法的执行速度快了多少倍。
金额，以下参数的意思，在继续说之前需要理解。
n:并行系统中处理器数量W:问题规模(定义为计算负载、工作负载和给定问题的总计算量(ws : APP应用的串行成分Wp: W中的可并行部分) Ws Wp=W ) f:串行成分比率f WTS:串行分量的执行时间Tp:并行分量的执行时间s:加速比E:效率Amdahl定律Amdahl定律的出发点是，在工作负载变化固定的情况下，增加处理器的数量来提高计算速度
上述公式表示，随着处理器个数无限增加，加速比并不是无限提高，而是达到了作为串行占有率倒数的上限。 串行成分越大，并行得到加速比的上限越低的程序； 串行成分越小，即能够并行化的成分的比例越大，通过并行化得到的加速比的上限(天花板)越高。
从上图可以看出，即使串行部分在程序中只占4%，加速比的上限也只有31。 因此，也可以理解平时编写OpenMP程序，执行时间与处理器核心数不成比例，但原本常见的程序包含串行部分，相当于一次函数而不是正比例函数。
考虑另一个并行开销，Amdahl表达式如下：
Gustafson定律Gustafson的出发点与Amdahl不同： Gustafson在固定的时间内，认为完成越多，加速比越高。 除学术研究外，实际应用中是在没有必要固定工作负载上使计算程序在不同数量的处理器上运行。 Gustafson定律认为，要增加处理器，必须相应地增加问题的规模，才有实际意义，公式如下所示：
该公式看起来比Amdahl更乐观，这表明如果计算负载增加，处理器的数量也会相应地增加，所得到的加速比也在增加。 从公式中可以看出，这个加速比好像没有天花板吗？ orz
串行只占4%左右时，加速比维持得较高。 考虑到另一个并行开销：
关于加速的讨论的一般经验是高速的，我们认为：
可线性加速的应用问题
矩阵加法、内积运算等这种问题几乎没有通信开销
导致p/logp加速的APP应用问题
分而治之内的应用问题，与二叉树相似，树兄弟可以并行执行，但随着向根逐渐推进，并行度逐渐减少
超线性加速：由于高速缓存和内存的增加
绝对加速：将最佳串行算法所需的时间除以同一问题的并行算法所需的时间
相对加速：同一算法在单个处理器上运行的时间除以多个处理器上运行的时间
基准测试程序top 500的排名不是主观评价的，而是程序出来的，测试计算机性能的程序一般被称为基准测试程序。 请知道一下：
基本测试程序综合型基准测试程序Whetstone
为不同计算机浮点性能设计的综合基准程序包括整数运算和浮点运算，包括数组索引、子程序调用、参数传递、条件分支和三角/超越函数等综合型基准测试程序Dhrystone
旨在测试整数和逻辑运算性能的综合基准程序CPU密集型测试程序标准基准测试程序SPEC
主要是测试CPU性能的强调开发能反映真实应用(如实际负载)的基准测试程序，并已推广到客户-服务器计算、商业应用、I/O子系统等 数学库测试程序基准测试程序LinPACK
用全精度64位字长的子程序求解100阶线性方程组的速度测试的结果以MFLOPS作单位给出作用BLAS1的第一个线性代数软件包基准测试程序LAPACK
使用了数值线性代数中最新、最精确的算法采用了将大型矩阵分解成小块矩阵的方法，从而可有效地使用存储器建立在BLAS1、 BLAS2和BLAS3基础上基准测试程序ScaLAPACK
是LAPACK的增强版 ，主要为可扩放的、分布存储的并行计算机而设计的 并行测试程序NAS Parallel Benckmark
1991年美国NAS项目所开发的并行测试程序其目的是为了比较各种并行机性能系由8个程序组成，测试范围从整数排列到复杂的数值计算PARKBENCH
在1992年超级计算会议上确定的项目主要目标是确定并行机用户与厂商双方都能接受的、内容丰富的一批并行测试程序及标准4类PARKBENCH底层基准程序核心基准程序密集应用基准程序HPF编译基准程序【本章小结】掌握Amdhl定律和Gustafson定律，理解其计算基本的出发点，了解并行计算机常见的性能指标和测试程序
并行算法与并行计算模型 并行算法概述 算法表达 算法复杂性这里的复杂度不仅仅是时间或者空间复杂度，正是由于并行算法运行在多核上的特殊性，因此其复杂性指标多，举一些来介绍：
运行时间t(n) 算法运行在给定模型上求解问题所需的时间，包含计算时间和通信时间，分别用计算时间步和选路时间步作单位 处理器数p(n) 求解给定问题所用的处理器数目 并行算法成本c(n) c(n)=t(n)p(n)成本最优 总运算量W(n) 并行算法所完成的总的操作数量 同步与通信同步就是多处理器之间要相互协作，在一些具有先后次序的问题上需要等待。譬如下面的求和算法：
通信简单理解就是数据交换。
特点：
具有有限个或者无限个功能相同的处理器一个容量无限大的共享存储器在单位时间内，每个处理器能访问任一存储单元所有处理器同步执行PRAM指令（某些处理器可以空闲）一个算法的运行时间是指令周期数根据处理器对共享存储单元同时读、同时写的限制，PRAM模型又可分为：
不允许同时读和同时写（PRAM-EREW）不允许两个处理器在同一时间访问同一存储单元，但允许访问不同的存储单元允许同时读不允许同时写（PRAM-CREW）允许同时读和同时写，但需要解决写冲突（PRAM-CRCW）
下面是一个运行在PRAM模型上的求和算法：
内层循环是可并行的，因此这个求和并行算法的时间t(n)=O(logn)，处理器数p(n)=n/2，成本c(n)=O(nlogn)，总运算量W(n)=n-1，加速比S(n)=O(n/longn)。
PRAM模型的优点：
适合于并行算法的表达、分析和比较使用简单，隐含了通信和同步等细节易于设计算法，稍加修改便可运行在不同的并行计算机上可推广，加入一些诸如同步和通信等需要考虑的问题PRAM模型的缺点：
所有的指令均按锁步方式操作，很费时共享单一存储器的假定不适合于分布存储的MIMD机器假设每个处理器均可在单位时间内访问任何存储单元而略去存取竞争和有限带宽等是不现实的 APRAM模型（异步PRAM模型）特点：
由p个处理器组成，每个处理器有其局部存储、局部自觉的画板和局部程序处理器之间的通信需要经过共享全局存储器无全局自觉的画板，各处理器异步独立执行各自的命令处理器间任何时间依赖关系需要明确地在各处理器地程序中加入同步路障一条指令可在非确定但优先的时间内完成 局部操作：单位时间全局读和全局写：时间为d，d随p的增加而增加同步：时间为B，是p的非降函数一般有 2 ≤ d ≤ B ≤ p计算过程：
计算由同步障分开的全局相组成在各全局相内，每个处理器异步执行在同一相内不允许两个处理器访问统一存储单元运行时间为：（tph为全局相内各处理器指令执行时间中的最清爽的铃铛）下面是一个运行在APRAM模型上的求和算法：
各处理器先求n/p个数的局部和，然后通过树自底向上逐层求和运行时间t(n) =处理器数p(n) =成本c(n) =加速比S(n) =
APRAM模型的优点：
比起PRAM更接近于实际的并行计算机保留了PRAM编程的便捷性使用了同步障，确保程序正确成本参数定量化，易于分析算法APRAM模型的缺点：
与实际的并行计算机仍然相差较远不适合于消息传递并行计算机 BSP模型（下面两个模型简单了解一下就可以了）
结构：
计算过程：
垂直结构： 局部计算全局通信路障同步 水平结构： p个处理器之间并发执行 一个超级步的运行时间 MAX(w+hg)+L，w为执行局部计算的时间，h为发送/接收消息的数目BSP模型的优点：
强调了计算和通信的分离在一个超级步内，可将消息作为一个整体传递易于分析算法复杂性提供了一个用于编程的BSP函数库BSP模型的缺点：
需要特殊的硬件支持全局路障同步，否则同步代价较大 LogP模型一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它并不涉及到具体的网络结构
参数说明：
L表示在网络中消息从源到目的地所产生的延迟o表示处理器发送或接收一条消息所需的额外开销 在此期间内它不能进行其他操作 g表示处理器可连续进行消息发送或接收的最小时间间隔 g的倒数相应于处理器的通信带宽L和g反映了通信网络的容量 p表示处理器/存储器模块数L、o和g都可以表示成处理器周期的整数倍
LogP模型的优点：
LogP模型的缺点：
难以对算法进行描述、设计和分析BSP模型和logP模型不同之处
LogP基于成对消息传递，BSP进行整体通信LogP增加了一个参数o，表示传递消息的额外开销LogP鼓励计算与通信重叠，BSP强调计算与通信分离 常见问题的并行算法 向量运算这个十分简单，一点依赖关系都没有，直接上OpenMP，串行的时间复杂度为O(n)，并行时间复杂度为O(1)，并行伪码为：
在我看来，归约总是有点“归并”的味道，归约适用于求和、求最大值、计数等场景。下面是求总和的并行算法，时间复杂性为O(n)，并行算法的复杂性为O(logn)，所需的处理器数为n/2：
使用场景如求前缀和。下面是求前缀和的并行算法，串行时间复杂度为O(n)，并行算法运行时间为O(logn)，处理器数为n/2：
求前缀和也有另外的解法，这种解法处理器数为n，运行时间为O(logn)
矩阵相乘的串行算法时间复杂度为O(n³)，算法可优化到O(n2.81)，但使用并行，可以降到更低，下面是两种并行算法：
处理器数为n²，运行时间为O(n)处理器数为n³，运行时间为O(logn)
无序数组的秩
所谓数组的秩，就是指定x，求数组中小于x的元素的个数，串行算法时间显然为O(n)，并行算法为：
这里是把求无序数组A的秩，转化为求数组B的和，直接使用前面的求和并行算法就好。
处理器数为n/2，运行时间为O(logn)
有序数组的秩串行可以使用二分，时间复杂度为O(logn)。一个简单的并行算法如下：
处理器数为n，运行时间为O(1)
若处理器数为根号n，则可以分段并行求解：
这样子的运行时间仍旧为O(1)
所谓归并，就是指将两个有序数组合并为一个整体有序数组，这里为了方便，在原先的两个数组末尾加上了哨兵，这两个哨兵都是正无穷。下面是归并的两种并行算法：
并行算法1
这个算法的示意图：
核心是分段，分段进行排序，使用秩保证了分段之后的数字序列可以直接合并。
这个算法的处理器数为p，平均运行时间为O(n/p)
并行算法2
先引入一个定义，由这个定义所引出来的一个定理可以帮助我们归并序列：
双调序列：与单调序列相对，双调序列允许一个序列先增后降，或者先降后增（注意这里允许首尾相接），也就是下面几种情况都是属于双调序列
Batcher定理
由此我们可以设计以下算法：先将序列分为小序列和大序列，这样子就保证了小序列中的每个数都比大序列中的任意一个数小，那么采用递归方法就可以完成归并。
以上算法适用于数组个数为2k的情形
如果数组个数大小不是2k，则并行算法改为：
算法首先将原来两个有序数组赋值到一个新数组c里面（这里还强制把数组长度变成2的幂次方），然后调用前面的双调归并算法。这种情况下所需要的处理器数m+n，运行时间是O(log(m+n))
插入排序
我们发现，插入排序最终其实就是将每个数放到它的秩的位置上，其实不仅是插入排序，其他排序也可以利用这个思想。这种情形下的处理器数为n，运行时间为O(n)
tips：冒泡排序没法并行化
选择排序
处理器数为n²，运行时间为O(logn)
前面我们已经讲了归并，知道了一般情形下归并的时间复杂度为O(logn)，则按照归并排序的算法思想，易得归并排序的算法时间复杂度为O(log²n)，处理器数为n/2。伪码如下（其实和串行伪码是一样的，只不过加上了并行）
自上而下构造一棵二叉排序树，中序遍历可得到一个有序序列
root=i，选择根节点，每个处理器将自己的处理器号写入变量root，根据CRCW模型原理，最终只有一个处理器号会被写入变量root
f[i] = root，设置所有节点的父亲为根节点
LC[i] = RC[i] = n，设置所有节点的左右孩子为空
并行构造树的第二层
每个Pi比较a[i]和a[f[i]]的大小
<a[f[i]]的节点竞争成为f[i]的左孩子
>a[f[i]] 的节点竞争成为f[i]的右孩子
竞争失败的节点将其父亲指向胜利者循环构造树的第三层…
构造一级树的时间：O(1)
平均树高：O(logn)
平均时间复杂度：O(logn)
并行中序遍历平均时间：O(logn)
PSRS假设只有p个处理器，（p远小于要排序的数组的元素数），这个算法是怎么做的呢？
这个算法的示意图如下：
这里假设了数组大小为27，一共有3个处理器
多路归并，既可以使用串行归并，也可以使用并行归并