抽象VS实现

实例：ISPC程序

ISPC是一种SPMD（single program multiple data）编译器。

利用ISPC编写的计算sin(x)的程序如下图：

ISPC提供了一种抽象，当调用ISPC函数时（即程序中调用sinx的语句），会产生一个gang，这个gang含有多个ISPC实例，每个实例会执行自己的代码，当每个实例都执行完后，恢复原先的执行流。

两种ISPC程序

第一种ISPC程序如下图，共有4个实例，不同实例在同一时间访问的数据是连续的。

第二种ISPC程序如下图，不同实例在同一时间访问的数据不再连续。

ISPC通过SIMD指令实现gang这种抽象，而很显然由于局部性原理，第一种程序的性能更好，ISPC通过一条SIMD指令可以加载这些相邻的数据，第二种程序虽然也可以用SIMD指令实现，但是指令代价更高。

提高抽象的层次

继续提高抽象的层次，现在把ISPC程序中的for循环换位foreach循环，foreach循环，foreach表明下面的循环是由一个gang中的实例并行执行的，而为了实现foreach，ISPC把循环的不同部分分配给实例。

小结

从程序员的视角看，执行一个gang会产生programCount的逻辑指令流，程序员不需要了解逻辑指令流的执行方式。ISPC编译器通过生成SIMD指令来执行gang。

三种并行模型

共享地址空间模型

线程通过读写共享变量完成通信，共享变量就如同一个公告栏，任何线程都能对其读或写，用于同步的原语也是共享变量（例如锁）。

共享地址空间模型有多种实现方式，例如共享总线、多级网络。对于共享地址空间模型的多核处理器，任意的核访问一个不在Cache中的内存地址所需时间相同。

非一致性内存访问（NUMA）

与共享地址模型类似，所有核都可以访问任意地址，但是访问不同地址的代价不同。NUMA提供了良好的可扩展性，访问局部内存的延迟更低、带宽更高。

消息传递模型

与上面两种模型不同，消息传递模型中的每个线程有独立的内存空间，线程间通过传递、接受消息进行交流。

数据并行模型

同一个操作，运用在数组不同元素上。实现数据并行模型一般采用SPMD的方式，可以把其视作map(function, collection)，其中function是运动在每一个元素上的独立操作，collection指的是这些元素的集合。

下图中的ISPC程序行为是不确定的，数据并行模型没有提供迭代顺序的规范。

使用流编程模型来描述数据并行，kernel指没有副作用的函数，并且一次只会操作一个元素。

流编程模型的优点

流编程模型不用担心程序出现的不确定行为，并且编译器可以优化程序流，下图是一个例子，编译器可以得知tmp这一中间变量是不必要的，减少内存访问，提高内存带宽。

流编程模型的缺点

流编程模型通常需要大量的操作符来描述复杂的数据结构，下图显示了gather这一操作符，gather操作根据R0中的索引来把mem_base地址中的数据按顺序加载到R1中。

课程总结

三种编程模型提供了并行程序的组织形式，而现代的并行系统更多是多种模型混合，例如CUDA支持在kernel中支持访问共享内存。

现代机器提供不同的