pdf课件
今天的主题是并行编程中抽象(abstraction)和实现(implementation)的区别。
在讨论并行时，抽象和实现是非常容易混淆的。
简单说，抽象是一种思考方式，而实现是达到抽象的手段。
在并行编程中，抽象是用来表示并行和通信的，但在系统层面也有并行和通信的概念，前者指一种思想，一种抽象，而后者指在系统中的具体实现。

本文的第一部分以ISPC为例，介绍抽象和实现的区别；

本文的第二部分, 我们将关注不同通信抽象的差别和硬件上的实现，以及编程模型是如何影响程序员思考的。

1 Programming with ISPC

1.1 ISPC

我们将用ISPC举例。
ISPC，全称是intel SPMD Program Compiler（ISPC）, 官方网址：http://ispc.github.com。
官方定义是：The Intel® Implicit SPMD Program Compiler (Intel® ISPC) is a compiler for writing SPMD (single program multiple data) programs to run on the CPU and GPU.
SPMD是一种并行的抽象，指有一份代码（程序），运行并得到它的多个实例，不同实例实例处理不同的数据。
ISPC代码是C语言的变体。

这里需要区别一下SIMD，SIMD可以理解为一种并行的实现。而SPMD是更高级的抽象。

调用ISPC函数会产生一组ISPC程序实例，每个实例都是一样的代码，但处理不一样的数据（SPMD），每个程序实例不等于线程。 一组ISPC程序实例在ISPC中称为“gang”。

ISPC中有几个关键字：

1. programCount：gang中并发运行实例的数目。有意思的是，该值由ISPC自动生成，不需要程序员设定。
2. programIndex：当前实例在gang中的id
3. uniform: 修饰的变量在不同的实例中具有相同的值。

下图是计算一个数组x中每个元素的sin()的ISPC程序：
[图片上传中...(image.png-65e595-1653135037427-0)]

ISPC是为了更好地利用SIMD而设计的，因为直接写SIMD的指令有些困难，但它提供给程序员的抽象是SPMD。 ISPC编译器会生成使用SIMD指令的实现。

gang中实例的数量和SIMD硬件的宽度有关（128位，256位还是512位）(例如，假设256位宽度，如果是运算元素类型是float，那么实例数目就是256 / 8 /4 = 8个实例),ISPC编译器生成包含SIMD指令的二进制代码（.o文件）,C代码可以像平常代码一下链接到这些二进制文件。

有两种分配数据到实例的方式：交错型(interleaved)和分块型(blocked)；
如，有个ISPC函数需要对数组a[12]中的每个元素做某些运算，实例数为4，那么：

1. 交错型中每个实例计算的元素是不连续的
   1. 实例1计算：a[0],a[4],a[8]
   2. 实例2计算: a[1],a[5],a[9]
2. 分块型中每个实例计算的元素是连续的
   1. 实例1计算：a[0]，a[1],a[2]
   2. 实例2计算：a[3]，a[4],a[5]

交错有一些情况下会更好，例如对于一组按照时间顺序采集的数据，每个元素的计算量可能会缓慢变化，如从小变到大。交错执行时每个实例耗费的时间可以差不多，而分块执行时, 分配到后面元素的实例的执行时间会很长，导致计算快的实例等待，拉长整体的完成时间。

我们知道，分块型对空间局部性利用的更加充分，如果是一个多线程的程序的话，分块型和交错型到底哪个好需要根据数据特点分析；但在ISPC中，交错型是比分块型好，因为ISCP在实现上是单线程程序；
还有一个使得ISPC中交错型比分块型好的原因是，交错型可以使得每个时刻需要计算的元素在内存上是连续的，如时刻1时，实例1,2,3,4分别计算a[0],a[1],a[2],a[3]，使用_mm_load_ps1就可以将它们加载到SIMD寄存器中; 而在分块型中，因为需要将不连续内存的数据加载到SIDM寄存器，则要求使用_mm_i32gather，消耗的时钟周期是前者的好几倍。
因此，在ISCP中，交错型准没错。

ISCP还提供自动确定数据分配方式的关键字foreach:

image.png

使用foreach是程序员告诉编译器说：这里有个循环，我需要它可以并行执行。
然后，ISPC编译器会自动将循环迭代分配给程序实例，当前的ISPC默认是交错型分配

1.2 summary

1. SPMD是一种编程模型，一种抽象
   1. 程序员认为：SPMD程序在运行时会产生多个指令流
   2. 程序员根据这种抽象编写程序
2. SIMD是一种实现
   1. ISPC编译器生成SIMD向量指令去完成并行任务。
   2. ISPC将条件控制流映射到向量指令
   3. ISPC程序只在一个线程中执行
3. ISPC的语义还是有点棘手的
   1. ISPC等于SPMD的抽象+uniform变量

看到这里应该可以明白抽象和实现的区别了，重点在于抽象的具体实现可以和抽象本身没半毛钱关系，如ISPC的抽象是通过多个实例达成并行，而ISPC的实现则只是用了SIMD向量指令达成并行。

到目前为止我们讲的ISPC都是基于gang这种抽象，gang抽象的实现是在单核上通过SIMD指令实现并行。实际上，ISPC还有一种基于task的抽象，它可以实现多核的并行执行，后面会介绍。

2 Three parallel programming models

本节我们将关注不同通信抽象的差别和对应的机器硬件结构，以及编程模型是如何影响程序员思考的。
下图展示了系统结构层次，其中编程模型处于最上层。

image.png

不同的编程模型的实现路径不同，如线程模型中pthread会调用操作系统API来创建线程，而ISPC的实现则绕过了操作系统，直接产生机器码。

接下来介绍3个通信模型：共享地址空间（shared address space），消息传递（message passing），以及数据并行（data paralle）。

2.1 shared address space

2.1.1 抽象

在该通信模型中，线程间通过共享变量进行通信。这些共享的变量可看做一个黑板，如线程1在黑板上写下x的值，线程2去黑板看一眼得到x变量的值。
在共享地址空间通信模型中，需要有同步机制(synchronization)用于互斥和同步消息。互斥是指你不能两个线程同时对一个变量写，这会发生错误；而同步消息指，当线程2想去读x的值时，它如何确定该值已经被线程2写入了；

共享地址空间通信模型需要手动设置同步原语，它是顺序编程的自然扩展；

2.1.2 实现

共享地址空间需要硬件支持。
在多处理器机器上，每个处理器都需要可以访问任意一个内存地址； 这里存在两种不同的结构，即对称多处理器以及非对称多处理器；
对称多处理器中每个处理器到任意内存的时间都是一样的(uniform memory access, UMA)，而非对称多处理器中不同处理器，不同内存的存取时间不一样(Non-uniform memory access, NUMA)。(这里的内存指memory，不是cache)

UMA的多处理器扩展性较弱，因为需要花费很多来保证内存存取时间一致。并且为了坚持UMA，有些时候会导致内存存取时间变得一样的bad（为了达成UMA的远大理想，每个处理器不得不都离内存很远）。
下图是2种对称多处理器的结构：

image.png

而NUMA的多处理器则更加易于扩展，对于local memory可以达到低延迟和高带宽。
如下图的机器中，每一个处理器都有一个自己的local内存，任意一个处理器可以通过interconnect访问任意其他内存。处理器x对local内存x的存取速度快于对其他内存的存取速度。这种设计会给程序员编写代码带来新的挑战，程序员要更加努力地探索程序的局部性，避免从non-local内存中取数据

image.png

2.1.3 总结

共享内存空间通信抽象：

1. 通过读写共享变量
2. 需要手动添加同步原语，如锁，信号量
3. 从程序员的角度，这是一个简单的模型，只是单处理器编程的逻辑扩展（但对于NUMA实现需要额外考虑局部性）

要求硬件提供有效支持：

1. 任意一个处理器可以存取任意内存地址
2. 即使是NUMA处理器，扩展也是很耗钱的，这就是为什么超级计算机这么贵。
3. 然而，当考虑cache之后，事情就变得复杂了起来，会遇到一致性问题，即同一个变量在不同cache中的值很难保持一致，这个会在以后讨论。

当然共享地址空间只支持单个机器内部的通信。

2.2 Message passing model

2.2.1 abstraction

该通信模型中，线程运行在自己私有的地址空间，线程间通过sending/Receiving messages来通信。如下图所示:

image.png

发送信息是两个线程间唯一交换数据的方式。
由于不共享变量，该通信模型没有缓存一致性的问题。
他的优点是不需要硬件支持，只需要有网络就可以了，并且支持机器之间的通信。

2.2.2 implementation

不需要硬件支持。
一个受欢迎的软件库：MPI（message passing interface）

2.2.3 编程模型与机器类型没对应关系

编程模型和具体机器类型没有对应关系！！！
消息传递通信模型也需要机器有共享地址空间的硬件；
在没有共享地址空间硬件的机器上，也可以用软件实现共享地址空间，虽然会很低效。

2.3 data-parallel model

回顾一下之前讲的几种编程模型，这些编程模型实际上对程序强加了一种结构，必须按照这种结构写，多个线程才能正常的通信。如：

1. 共享地址空间：限制较少
   1. 通过共享变量通信
2. 消息传递：限制较多
   1. 所有通信必须通过消息的形式传递
   2. 由于消息传递很慢，你需要尽可能少的通信。
3. 数据并行：一种非常刚性的计算结构，限制最大
   1. 程序对每个数据元素执行相同的函数。

早期的机器专注于对数组中的每个元素执行相同的操作，利用SIMD等向量指令，如80年代的超级计算机，以及克雷超级计算机（向量处理器），一个典型的例子是matlab 。
现在，大家专注点在SPMD编程，它在重点在于将相同的函数应用在所有数据上，如同一个map函数:map(function, collection),这个函数可以是很复杂的函数如循环。（想起来谷歌的分布式计算框架map-reduce）
之前的ISCP中的foreach就是一个map，将数组x通过泰勒展开函数映射到数组y。

之后，课程介绍了一种基于stream的数据并行编程，它将元素的集合看做流(stream)，并通过调用不同的kernel对流中的每个元素进行相应计算，由kernel保证并行计算。（感觉和tensorflow啥的有点像了）

总结：

1. 数据并行在代码中加入了一些结构来简化编程并优化计算。
2. 数据并行的基本结构是将一个函数映射到一组数据
3. 现代的许多面向性能的数据并行语言不是严格遵循上面的基本结构，如ISPC，OpenCL，CUDA，etc.
   1. 他们选择了C style的语法

当你的计算是将相同的操作应用到大量数据时，数据并行模型汇很有用。GPU就是围绕数据做了很多优化

3 summary

1. 共享地址空间
   1. 限制少
   2. 顺序编程的扩展，很自然，不过性能可能有所限制
2. 消息传递
   1. 将所有通信结构化为消息
   2. 编程上比共享地址空间难一点
   3. 结构化的程序有利于获得更具可扩展性的编程
3. 数据并行
   1. 限制大，将计算结构化为map
   2. 因为处理的独立性，map之间无法通信

4 modern pratice: mixed programming models

实践中会混合使用上面的三种通信模型，如一个处理器中的多个核之间使用共享内存，因为缓存一致性解决了缓存问题。而处理器、机器之间由于没有缓存一致性只能用消息传递机制。
未来的课程中会介绍CUDA和OpenCL，他们在多个核之间使用数据并行模型，而运行在单个核上的线程们则使用共享地址空间模型。

5 summary

1. 编程模型提供了一种思考并组织并行程序的方法，它提供了一种抽象，而这种抽象可以有多种实现方式。
2. 编程模型和机器类型不是对应的
3. 在实践中，你需要思考多种不同的方法
   1. 现代机器提供了多种不同类型的通信模型在不同的尺度上
   2. 不同的通信模型适用的场景不同