抽象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
中支持访问共享内存。
现代机器提供不同的
- Abstractions Programming Parallel Lecture 418abstractions programming parallel lecture abstractions programming lecture3 parallel programming lecture4 parallel lecture programming parallel lecture basics abstractions programming笔记242 abstractions programming笔记84 abstractions programming笔记127 abstractions programming boilerplate笔记 abstractions programming笔记106 abstractions programming笔记114