pdf课件
本节将介绍lecture2中提到的三种通信模型(共享地址空间，消息传递，数据并行)的实际例子。
今天的课不会介绍并行代码的优化，只讲讲如何构建并行程序，优化相关在后面的课程。
1 Examples of applications to parallelize
第一个例子是海洋的物理模拟，他们将3D海洋离散化为2D网格的层叠。需要计算每个网格点的物理性质随着时间的变化。
第3节中会提到如何针对2D网格做并行计算。
第二个例子是星系演化的模拟，需要计算星球之间的引力。提到了使用四叉树对星系进行表示和计算的方法。
这部分看一下就好了，没有详细研究的必要。
2 Creating a parallel program
首先明确我们并行的主要目标是什么？
提升加速比。
如何编写一个并行计算程序那？
主要分为4个步骤：
- (decompostion)分解问题至多个子问题(tasks)
- 需要分析、研究问题中可以并行的部分
- 目标：创建足够多的tasks，可以让机器可以充分地忙碌。
- 分解的关键是识别程序中的依赖。因为根据阿姆达尔准则，程序的最大加速比取决于程序的依赖。例如，假设S为程序中必须顺序执行的部分耗时的占比，那么最大加速比小于1/s，这个应该挺好理解的。
- 一般由程序员负责问题的分解。
- (assignment)将子问题(tasks)分配到并行的线程(workers)
- 需要考虑局部性，负载均衡等
- 目标：负载均衡，减少通信消耗
- 负载均衡和减少通信消耗是很难同时做到的，例如负载均衡最好的方法是随机分配到各个worker，但这样会使得局部性变弱，加大通信的时间。
- 可以一开始分配完(静态分配, 如程序员使用pthread API将tasks分配)，也可以边执行，边根据情况分配（动态分配，如ISPC中tasks到线程的分配）。
- 一般由程序员负责(如lecture2中讲ISPC时的前两个版本)，有些语言或者runtimes也会负责（如ISPC中的
foreach，以及ISPC中tasks到线程的分配)
- (orchestration)协调多个workers的执行
- 需要结构化workers间的通信(如消息传递模型中消息的结构)，添加同步, 组织数据在内存中的存储以减少时间消耗， 调度tasks等
- 目的：减少通信和同步的消耗，保留数据引用的局部性（局部性原理），减少overhead。
- 实现和细节依赖于使用的通信模型，编程抽象,如共享地址空间还是消息传递等。
- 硬件细节会影响该过程。例如，如果同步消耗很大的话，需要减少它的使用。
- (mapping)将workers分配到具体的硬件上执行。
- 需要考虑局部性，硬件特性等
- 相关线程放到一个处理器或者core可以更好地利用局部性，减少通信和同步的消耗
- 不相关的线程放到一个处理器或者core可以使得机器运行的更加高效，如一个是计算型线程，一个是IO型线程。
- 目的：将workers放置到具体的机器执行单元
- 操作系统，编译器，硬件，程序员都可以负责这个部分
- 操作系统负责：将线程分配到哪个core
- 编译器负责：将ISPC的程序实例映射到向量指令
- 硬件负责：将CUDA线程放置到GPU cores
- 程序员负责：设置线程对core的亲和性，可以使操作系统将线程分配到指定core。
- 需要考虑局部性，硬件特性等
当我们说一个问题的计算量很大时，该问题有三种类型，分别是计算型，数据型和混合型。
旅行商问题就是计算型，它的数据就只有几十个坐标，但需要很大的计算量。
而计算几百亿个数的sin，则属于数据型，单个数的sin计算很快，计算量大是因为数据多。
而对几亿个数的排序，是混合型，数据和计算是混在一起的。
面对一个问题，我们可以尝试从计算和数据两个维度对问题进行分解。
3 A parallel programming example
3.1 A 2D-grid problem
本节将以一个2D网格的偏微分方程计算为例（简化了的海洋模拟），分析并行编程的步骤，并且使用lecture 2提到的3种通信模型进行并行编程。
我们的目标如下图，即多次对全图中的每个点进行右边的计算，直到全图收敛。
首先给出一个最简单的，非并行的算法：
我们将在这个基础上进行并行。
3.1.1 decomposition
首先，我们要分析他并行的可能性，我们可以看到对角线计算时是可以并行的，如下图：
但这种并行的潜力太小了，一次还是只能计算一条对角线，并且需要频繁地同步。
实际上，我们可以改变算法，使得该算法可以更好地并行，但这个改变需要我们对这个偏微分方程有足够的理解。
新的方法是将网格分为红色和黑色，先并行计算红色格子，计算完后再计算黑色格子，这样多次迭代，直到收敛，如下图：
3.1.2 assignment
然后，如何将计算分配到不同的works? 这里有两个方法，分别是分块型和交叉型，如下图：
右边的Px表示将该行分配到对应的work。
两者谁更好取决于运行的系统。（?？这里没完全理解）
我们来看一下该并行的运行过程：
- 首先更新红色节点
- 等待所有红色节点更新完成
- 多个处理器之间通信，同步红色节点的更新数据
- 更新黑色节点
- 等待所有黑色节点更新完成
- 多个处理器之间通信，同步黑色节点的更新数据
- 重复
我一开始很疑惑为什么有步骤3,6，不都是存在内存里吗？然后我意识到他这里讲的是多处理器，甚至多机的情况。单处理器的时候，多个core之间有缓存一致性，因此多个线程之间根本不需要显式地通信。而多处理器和多机器时，就需要显式通信了 .
update：就算单处理器，缓存一致性也是需要耗时间的，也能算一种通信吧。
3.1.3 orchestration
我们来看一下不同分配方式下workers之间的协作。
灰色部分是每次迭代时，需要发送到P1的数据，如当P2开始计算第一行时，需要知道P1中第三行的数据（可以认为，现在讨论的是多机器的情况，他们不是共享地址空间的，每个机器只有当前计算部分的数据）
可以看到左图的通信比右图少很多，因此在大多数情况下，左图更好。
接下来，我们分别将用三种通信模型实现并行。
3.2 Data-parallel solver
下图是数据并行的伪代码，数据并行的特点是编程语言和runtime为你做了很多工作，你不需要去写具体的实现代码，你只需要声明什么地方你想做什么事即可。
3.3 Shared address space solver with SPMD
在共享地址空间模型中程序员负责同步，需要在临界区lock以便线程互斥进入，并在合适的地方设置barriers以便线程可以在此处停下。
具体代码如下：
barrier是一个同步原语，用来表达依赖关系。barrier可以将计算划分为几个步骤，只有所有线程在barrier前都完成了计算，才能继续执行之后的代码。
上面这个代码很简单，但有性能问题，红框中每一次计算都需要互斥一下，因此我们可以对每个线程设置一个diff的临时变量，在计算完成后汇总所有的diff结果，如下图：
现在，总结一下数据并行模型和共享地址空间模型：
- 数据并行
- 同步：单个线程，没啥同步
- 通信：隐式地load和store（和共享地址空间一样）；或者更加复杂的内置通信原语，如reduce
- 共享地址空间
- 同步：共享变量的互斥访问；使用barriers表达依赖（不同的计算阶段间）
- 通信：隐式地load和store（和共享地址空间一样）
3.4 Message-passing solver
我们假设每个线程都有自己的私有地址空间，线程间的通信需要使用send和receive发送消息。
每个线程只有属于自己的数据，如下图：
当所有红色节点计算完成后，开始计算黑色节点。此时，线程1和线程3要将某些行的数据发送给线程2，用于计算线程2的数据中边缘行的数据，如下图:
因此，整个程序大致是这个样子：
上面的send和recv的调用是阻塞的，也就是说在数据没发送完或接收完，并对方给答复之前，他们不会返回，如下图：
然而，上面的程序会死锁，因为线程们一开始都是send，而不是recv。而如果没有recv的话，send是不会return的，大家就一起死锁了。因此，我们要将一开始的send，recv改一下，使得大家不是都从send开始，如下：
if(tid%2==0){
sendDown();recvDown(;
sendup(); recvUp();
}else{
recvUp(); sendUp();
recvDown();sendDown();
}
上面介绍了阻塞型的send和recv，实际上还有非阻塞型的，他们可以在调用后不等对方的确认就立刻返回, 调用线程可以做其他的事。
主程序可以使用checksend，checkrecv检测是否发送或接收完毕。如下图：
4 总结
- 首先介绍了阿姆达尔定律，即并行的最大加速比取决于程序中必须顺序执行的部分的耗时占比
- 介绍了编写并行程序的步骤，分别是分解problem至tasks，分配tasks到workers，然后协调各个workers之间的通信和同步，最后将workers放置到具体的物理设备。
今天我们关注的是如何识别程序依赖
马上我们要介绍识别局部性，和减少同步。
