异构并行编程模型

刘颖, 吕方, 王蕾, 陈莉, 崔慧敏, 冯晓兵. 异构并行编程模型研究与进展[J].软件学 ,2014, 25(7): 1459-1475.http://www.jos.org.cn/1000-9825/4608.html

近年来,处理器从单核转变到多核,芯片的并行计算能力得到增强,性能显著提高^[1, 2].然而,由于结构复杂,传统处理器遭遇了严重的功耗瓶颈,无法通过增加核数继续带来性能提升.在这样的背景下,出现了CPU与一个或多个加速设备在片上或主板上相互连接组成的异构系统,以进一步增强计算能力:CPU作为控制设备,负责复杂的控制、调度等工作;而加速设备则负责大规模的并行计算或专业领域的计算任务.加速设备通常在指令集、微结构、功能或计算能力等方面与CPU有很大区别,GPU是目前最为常见的加速设备之一.GPU在片上集成了几十甚至上百个每指令耗能(energy per instruction,简称EPI)较低的简单核^{[3, 4, 5, 6]},它不包含分支预测、乱序执行等耗费资源的模块,借助高度的并行性隐藏单个任务的延迟,达到远高于CPU的计算吞吐量.除GPU外,可重构硬件(如FPGA)也常作为加速设备.目前,异构系统已十分普遍,遍布于服务器、个人电脑、嵌入式终端中,异构系统通过高速互联相互连接可构成异构集群,而异构集群通过互联 络连接在一起可构成大规模的云服务环境,如图 1所示.在2013年6月发布的超级计算机Top500排名中,前10名中有4个采用了异构架构^[7],其中,排名第一的天河2 是由Intel通用处理器与MIC(many integrated core)架构协处理器构成的异构集群.

在硬件异构设备与架构逐渐普遍化的同时,上层应用的需求也发生了巨大改变:大数据的出现,带来了大量高并发、低计算密度的应用^[8, 9];云计算的兴起,则带来了数量繁多的非传统服务^[10].这些应用不再单纯地追求处理速度,而是在同时处理大量数据以及在可忍受的时间内提供服务方面有更多诉求.这些诉求与CPU对单个任务快速响应的特征并不一致,迫切需要微结构与CPU不同的加速设备协助完成.

异构系统的发展,伴随着新兴应用的需求,使原有的并行编程模型(例如OpenMP,Cilk等)不再适用,直接推动了异构并行编程模型的研究.近几年,研究人员开展了大量的工作,例如:2007年,NVIDIA提出的CUDA^[11];2008年,Khronos Group提出的OpenCL^[12];2011年,PGI等公司提出的OpenAcc^[13];2008年,Intel提出的Merge^[14];2010年,IBM提出的Lime^[15];2012年,微软提出的C++AMP^[16]等,都是面向异构系统的并行编程模型.

1 异构并行编程模型概述

异构并行编程模型是异构系统与上层应用之间的桥梁,与传统并行编程模型一样,它的设计也需要考虑任务划分、任务映射、数据分布、同步、通信5个关键因素^[17].然而在异构架构的背景下,这些关键因素的作用范围有所扩大或改变,因此,传统并行编程模型在异构系统中不再适用,需要进行异构并行编程模型的研究.同时,新兴应用也为异构并行编程模型提出了新的挑战.

1.1 异构并行编程模型面临的技术挑战1.1.1 异构架构带来的技术挑战

异构并行编程模型的一个重要任务是:为程序员提供一个合理的硬件平台抽象,使其在编程时既可以充分利用丰富的异构资源、又不必考虑复杂的硬件细节.然而,异构系统与传统的同构系统相比,在设备内部微结构、设备间互联架构两方面都更加复杂化和多样化,这使得异构并行编程模型在建立平台抽象方面遇到了巨大的困难,在任务划分、任务映射、数据分布、同步、通信5个方面都面临着新的技术挑战.

1) 任务划分与任务映射面临的新问题:异构系统中设备之间并行计算能力不同.

同构系统中的计算设备为完全相同的多核CPU,尽管同一CPU不同核之间、同一核内的SIMD部件等可承担粒度不同的并行计算任务,但是不同设备具有相同的微结构,其并行计算能力是完全相同的.而在异构系统中,不同设备(如CPU与GPU,FPGA)的微结构具有本质差异,其并行计算模式与并行计算能力完全不同,设备的特长也完全不同,如图 2所示.这种设备间并行计算能力的差异,使得任务映射与任务划分不再是均一的,而是具有显著特异性的,这也更利于表达实际应用的特点.

2) 数据分布与通信面临的新问题:异构系统中加速设备内数据分布可配置、设备间数据通信渠道多样.

从编程模型的角度看,同构系统中,CPU片内存储是软件透明的cache结构,片外存储则遵从共享内存模型,除访问延迟可能不同(例如NUMA架构)之外,不存在其他的差异性.因此在同构系统中,数据仅可分配在片外内存中,具有存储位置单一的特点,也不需要进行显式通信.但在异构系统中,加速设备片内通常包含软件可分配的快速局部存储(如SPM);而设备间的连接方式则差异很大,目前,CPU与一个或多个加速设备多数通过PCIe连接,也有将它们集成在一个芯片内的尝试,例如AMD提出的HSA(heterogeneous system architecture)^[18],这使得加速设备可能无法采用与CPU相同的方式完成地址映射,导致它们的虚存空间分立,存在某一设备无法访问另一设备片外存储的问题.因此在异构系统中,数据可以被分配在CPU和加速设备片外内存、加速设备片内多层次局部存储等多个位置,数据分布问题变得十分复杂;设备间的数据通信也可能需要显式进行,如图 3所示.

3) 同步操作面临的新问题:异构系统中多层次数据共享位置及多范围同步操作.

如前所述,异构系统中数据可以分布在多个存储位置上,使得同步操作需要在众多位置上保证共享数据的一致性.同时,由于异构系统的不同设备具有不同的并行计算能力,并行任务将以更加差异化的形式分布在整个系统中,这使得同步操作的范围变得十分复杂.此外,GPU等加速设备通常具有局部硬件同步机制,这也使得异构系统中的同步操作形式更加多样.

1.1.2 上层应用带来的技术挑战

从上层应用的角度来看,用户希望以接近自然语言的表达方式编写程序,近年来出现的Map Reduce^[19]等编程框架,就更加符合人类的思维方式.然而,异构架构使得这种前进发生了严重倒退,带来了以下两个技术挑战:

1) 缺乏良好的异构抽象及统一的编程接口.

目前,通用CPU编程通常使用Java,Python等高级语言,GPU编程通常使用C的变体,而FPGA等可重构硬件设备通常使用Verilog或VHDL等硬件描述语言,这导致在异构系统中程序员无法使用统一的接口编写程序.

2) 应用程序的性能优化难度显著增加.

同构系统中,已有许多面向特定应用领域的并行优化,程序员可以直接调用这些优化接口.然而,异构系统中的加速设备种类繁多,例如,不同的FPGA可能具有编码/解码、流量控制、消息转发等特定功能,目前还没有足够多的工作为这些加速设备分别提供像在CPU上那样完善的并行优化,因此,程序员没有现成的接口可以使用,必须亲自在任务划分、任务映射、数据分布、同步与通信5个方面仔细权衡,程序优化难度极大.

1.2 异构并行编程接口与编译/运行时支持机制概述

异构并行编程模型依靠编程接口及编译/运行时系统解决上述技术挑战:异构并行编程接口是编程模型暴露给程序员使用的界面,它既需要为程序员提供合理的异构架构抽象,使程序员可以对异构计算资源加以合理利用,又需要保证接口的易用性,避免程序员陷入复杂的硬件细节中;编译/运行时系统是异构并行编程模型的软件工具层,它将程序员编写的加速器代码编译为可执行文件,并通过运行时系统完成任务的加速执行.

异构并行编程接口可以为任务划分、任务映射、数据分布、通信、同步这5个关键因素中的4个提供保障,提供显式的任务划分、数据分布与通信和同步机制.然而,程序员通常更专注于所编写的应用的特点,从这个角度来看,只有显式的任务划分机制对于程序员来说是必不可少的,而数据分布与通信、同步机制在一定程度上增加了程序员的编程负担.

异构编译/运行时支持机制的主要任务是保障任务映射,即,任务具体在哪个设备或计算单元上执行、以何种顺序执行.同时还负责对任务划分、数据分布与通信、同步等机制进行全系统级别的优化.

综上所述,异构并行编程模型依靠编程接口以及编译/运行时系统来解决异构系统中的新问题.其中,异构并行编程接口主要解决任务划分问题,同时为数据分布与通信、同步提供保障;而编译/运行时系统主要解决任务映射问题,同时为系统进行性能优化.

1.3 异构并行编程模型的发展

异构并行编程模型是随着GPU的发展而兴起的,由于GPU保留了许多流式处理器的特征,因此早期的异构并行编程模型(例如2004年出现的BrookGPU^[20])秉承了流式编程思想.流(stream)是这类编程模型的核心, stream是一组数据的集合,计算在stream的每个数据元素上并行执行,符合单指令多数据(SIMD)或多指令多数据(MIMD)的执行模式.然而,SIMD或MIMD对stream中每个数据元素的操作在控制流上是完全相同的,这虽然符合多数流媒体应用的特点,但是对范围更为广泛的数据并行应用来说要求过于苛刻.在这种背景下,伴随着NVIDIA GPU在商业上获得的巨大成功,2007年出现的CUDA得到了大力推广,它以单程序多数据(SPMD)的形式表达数据并行性:同一段操作作用在不同数据上时,不必采取控制流中完全相同的路径.然而,CUDA仅能在以NVIDIA GPU为加速设备的异构系统中使用,于是,2008年底出现了多家公司共同制定的跨平台异构并行编程框架标准OpenCL,它适用于任何并行系统.OpenCL将实际的硬件平台抽象为一个统一的平台模型,这也是OpenCL与CUDA最大的不同.但是CUDA和OpenCL的编程接口都较为低级,程序员的编程效率不高,其原因首先是遗产代码需要重新改写,其次是它们基于C语言进行扩展,Java,Python等更高级的语言无法使用这种扩展.针对遗产代码的问题,2011年出现了OpenAcc异构并行编程模型,它支持在遗产C/Fortran代码上直接加入制导命令;而针对Java,Python程序员使用异构计算平台困难的问题,2010年~2011年就出现了Copperhead^[21], Lime等编程接口与Java/Python类似的异构并行编程模型以及JOCL^[22],JCUDA^[23],PyCUDA^[24],PyOpenCL^[25]等辅助工具.

2 异构并行编程接口研究

异构并行编程接口的研究,致力于解决第1.1.1节所述的异构架构带来的3个技术挑战,同时为上层应用提供统一的编程接口.因此,异构并行编程接口需要将图 2和图 3所示的异构架构特征体现出来,同时尽量降低编程难度.针对异构架构带来的3个技术问题,异构并行编程接口的研究可以分为异构任务划分机制、异构数据分布与通信机制、异构同步机制这3个方向,下面将分别介绍这3个方向的研究成果.

2.1 异构并行编程接口的分类

异构并行编程接口从接口形式的角度可以划分为两类:一类是新的异构并行编程语言,一类是现有语言的异构并行扩展.对现有语言进行异构并行扩展,可以通过库(library)或制导(directive)的方式,它们通常基于C/ Java/Python等应用范围较广泛的语言.其中,基于Python/Java的新语言或语言扩展通常更容易掌握和使用,属于较为高级的异构并行编程接口;而基于C的新语言或语言扩展通常编程复杂,属于较为低级的异构并行编程接口.从异构并行编程接口的功能来说,也大致可以分为两类:有些编程接口屏蔽了较多的异构系统硬件细节,通常仅为程序员显式提供异构任务划分机制,而异构数据分布与通信机制以及异构同步机制由运行时系统完成,使程序员编程效率有所提高;而有些编程接口将多数异构系统的硬件细节通过上述机制暴露给程序员使用,为程序员编程及优化带来更大自由度,但同时也带来一些使用上的困难,降低了效率.

在图 4给出的异构并行编程接口的分类示意图中,空心圆代表新的异构并行编程语言,斜线圆代表现有语言的异构并行扩展;纵坐标表明了编程接口的形式:类似于Python,Java或C/C++;而横坐标体现了编程接口的功能:屏蔽了较多硬件细节的编程接口以任务划分为主,而暴露这些细节的编程接口则显式提供任务划分、数据分布与通信、同步等多种机制.

具体地说,在类Python和类Java类别中,Copperhead是一种新的异构并行编程语言,是Python的子集;Garg等人^[26]提出的编程接口属于现有语言的扩展,在Python的基础上增加了一些注释;IBM提出的Lime属于新的异构并行编程语言,兼容Java.它们与Python/Java类似,易于使用且无需程序员进行显式的数据分布、通信与同步操作,属于较为高级的异构并行编程接口.在类C/C++类别中,Intel提出的Merge是一种采用Map Reduce模式的新的异构并行编程语言;微软提出的C++AMP是C++11的异构扩展,更偏重于利用C++语言标准中的特性支持异构编程;Stanford提出的BrookGPU是一种新的异构并行编程语言,采用流式编程思想.它们都在一定程度上简化了数据分布、通信与同步,相对容易编程.OpenACC基于C/Fortran进行了异构扩展,支持在串行源程序中添加制导命令;NVIDIA的CUDA目前使用得最为广泛,它属于C语言的异构扩展,为程序员提供大量API.它们都需要程序员显式地进行任务划分、数据分布与通信、同步等操作,编程难度较大.为了解决这个问题,出现了诸如hiCUDA^[27],CUDA-lite^[28],OpenStream^[29]等基于CUDA的改进的异构并行编程模型,它们对CUDA编程接口进行了简化,在一定程度上提升了编程效率,尤其是国内的国防科学技术大学提出的OpenStream融合了BrookGPU与CUDA的特点,使编程更加容易;OpenCL的使用也较为广泛,它打破了CUDA只能支持包含NVIDIA GPU的异构系统的局限,但也正因如此,程序员在使用OpenCL编写程序时需要进行额外的平台选取工作,使得编程更加复杂.

2.2 异构任务划分机制

在同构系统中,并行编程接口仅需提供面向单一设备的并行任务划分机制,例如任务并行、数据并行等.异构并行编程接口在此基础上还需要提供描述任务在不同设备(如CPU与GPU)间分配的机制,因此,异构并行编程接口的任务划分机制需包含“异构特征描述”以及“并行性表达”两个维度,其中,异构特征描述是异构并行编程模型不同于其他并行编程模型所特有的特征.

Brook是Stanford大学2003年推出的一种流式编程语言,最初服务于Merrimac流式超级计算机和Imagine等流式处理器^[30],后来增加了对GPU的支持,称为BrookGPU.在异构特征描述方面,BrookGPU采用特殊函数kernel来标明需要在GPU上执行的代码段,kernel函数必须作用于流(stream)上.在并行性表达方面,BrookGPU采用流式编程思想,通过stream表达了细粒度的数据并行.

OpenCL/CUDA在C语言的基础上提供了异构扩展,它们的异构特征描述机制与BrookGPU的kernel函数类似.但在并行性表达方面,OpenCL/CUDA支持SPMD计算模型,而非流式编程思想.与BrookGPU的另一个不同之处是:除了数据并行之外,OpenCL还通过命令队列(command queue)提供了任务并行机制.hiCUDA是CUDA的扩展,其任务划分机制与CUDA相同,但是呈现给程序员的编程接口更加高级,可以直接在串行C代码上使用注释实现异构特征描述;进一步地,并行性表达也通过注释完成.

Lime是新的异构并行编程语言,它通过语言结构为程序员提供了丰富的操作符用于任务的划分^[31].在异构特征描述方面,Lime并没有显式的接口,这一点与BrookGPU,OpenCL/CUDA完全不同.其本质原因是因为Lime采用了基于任务的并行执行模型,而BrookGPU,OpenCL/CUDA则以数据并行为主.除任务并行之外,Lime在并行性表达方面也通过map/reduce操作符提供了细至中粒度的数据并行机制.

Merge是一种新的异构并行编程语言,它基于Intel已有的异构多核多线程系统编程环境EXOCHI^[32],采用Map Reduce思想,因此,它的异构编程接口与上述方式均不同.在异构特征描述方面,Merge提供了平台变体(target variant)机制,程序员需为异构系统中的不同设备提供不同版本的代码实现.在并行性表达方面,Merge可以描述完全独立的任务之间的并行性,但无法刻画它们之间的制约关系.Merge还通过粒度变体(granularity variant)构建了层次化的数据并行性,但是该机制无需程序员干预,因此它是一种层次较高的异构并行编程接口.

C++AMP是C++的异构扩展,它利用C++11中的lambada表达式进行异构特征描述,标明程序员希望在加速设备上执行的代码;在并行性表达方面,C++AMP与OpenCL/CUDA的SPMD执行模式类似.

Copperhead属于新的异构并行编程语言,在异构特征描述方面,它提供了@cu修饰符,用于标明需要在加速设备上执行的函数.在并行性表达方面,它为程序员提供了数种并行原语,它们的操作对象都是一维数组,称为序列(sequence).Sequence可以嵌套,因此,Copperhead可以同时表达扁平的数据并行性和嵌套的数据并行性. Copperhead具有较高的编程效率,其平均代码量仅为CUDA程序的约四分之一.

Garg等人在文献^[26]中提出了一个面向Python程序的简单异构编程接口,它提供一个特殊的迭代器prange,用于表明该循环需要分配到加速设备上并行执行,以实现异构特征描述.在并行性表达方面,prange仅指明了该循环需要并行执行,该循环具体如何并行执行则由对应的编译和运行时支持系统完成.

OpenAcc在C/Fortran上进行了异构扩展,它为程序员提供多组制导命令进行任务划分^[33].在异构特征描述方面,OpenAcc支持并行区域(parallel region)与内核区域(kernel region),这两种区域将被加载到加速设备上执行.在并行性表达方面,OpenAcc提供了与OpenCL/CUDA类似的机制.

国防科学技术大学提出的OpenStream是一种对OpenMP进行扩展的异构并行编程接口,它具有一组带有流处理特征的编译制导命令,融合了BrookGPU与CUDA的特点,提升了编程效率.

2.3 异构数据分布与通信机制

传统的并行编程模型主要关注共享存储平台,数据分为共享和私有两种存储属性,通过共享数据进行通信.然而在异构系统中,数据分布不仅具有共享和私有的属性,还需要指明分布在哪个设备上;数据通信也不再单一地通过共享数据方式来实现,而是增加了设备间显式数据传输方式.因此,异构数据分布机制可以划分为“设备间分布”和“设备内分布”两个维度,数据通信机制则主要依靠“显式传输”机制.

BrookGPU中,加速设备处理的输入或输出即被定义为stream,体现设备间分布;而stream在CPU与加速设备之间的通信则依靠特定的接口函数完成,体现显式传输.

OpenCL为存储在加速设备上的数据定义了特定的类型cl_mem,以体现设备间分布.同时,通过__global/__ local关键字分别指定数据分布在加速设备的共享存储和局部存储中,以体现设备内分布.数据通信则通过特定API完成,以体现显式传输.CUDA和hiCUDA也提供了与OpenCL功能类似的编程接口.

尽管OpenCL/CUDA为程序员提供了丰富的异构数据分布与通信接口,但是普通程序员一般无法充分利用这些接口获得性能上的提升.这是因为加速设备通常设计了多种硬件加速机制,例如GPU的全局内存访存合并机制:如果程序员没有为数据分配合理的存储位置或者设定足够多的线程,就会导致无法进行加速,影响程序执行效率.为了解决这个问题,出现了基于CUDA的CUDA-lite,它允许程序员在CUDA程序中加入简单的制导语句,数据分布相关的优化工作依靠CUDA-lite运行时系统完成,从而降低了CUDA程序的编写难度.

OpenAcc与OpenCL/CUDA的异构数据分布与通信机制大体类似,区别主要体现在:首先,在异构数据分布方面,OpenAcc允许程序员将数据分配在不同设备上,但是无法指定数据分配在加速设备的何种存储中,即,不具有设备内分布机制;其次,在异构通信机制方面,OpenAcc提供了在通信之前确定数据是否已在目的地存在的机制,保证仅在数据不存在的情形下进行数据传输,而OpenCL/CUDA没有相应机制.

C++AMP提供了两个类,以分别标明数据仅存放于加速设备中或在CPU与加速设备间共享.这两个类体现了设备间分布,与OpenAcc类似.但是对于那些在CPU与加速设备间共享的数据,程序员无需显式地进行数据传输操作,而是由编译器和运行时系统自动地负责通信操作以及一致性保证的工作.因此,C++AMP节省了程序员的一部分编程工作,是比OpenCL/CUDA/OpenAcc等更加高级的异构并行编程接口.

OpenStream与OpenCL/CUDA/OpenAcc均不同,它采用流结构进行加速设备中的数据管理,它在程序中定义了一个区域,描述相关的GPU数据流在程序中的生存周期,并给出在流结构内活跃的数据流.

然而,由程序员指定数据存储的位置并显式地完成数据通信,会增加程序员的编程负担,降低编程效率,因此,较为高级的异构编程接口,如前述的Lime,Merge,Copperhead等,均不提供显式的异构数据分布与通信接口,而是依靠运行时系统代为完成这部分工作.

2.4 异构同步机制

同步机制与任务并行执行的模式息息相关,如前所述,异构任务划分机制与传统并行编程模型相比更加复杂,因此,异构同步操作的范围可以存在于设备间(如CPU与GPU并行任务之间)、加速设备内全局(如GPU内所有并行任务之间)、加速设备内局部(如GPU内部分并行任务之间),范围比同构系统更加多样.与同构系统一样,异构同步点也保证了指令执行的先后顺序,或维护了不同线程的内存视图一致.

OpenCL提供了两种不同范围内的显式同步机制:第1种是加速设备内局部同步,它维护了一组线程内部共享数据的一致性;第2种是加速设备内全局同步,它保证了不同任务执行的先后顺序.

与OpenCL不同,CUDA中的同步具有显式同步与隐式同步两种形式^[34],且它们都属于加速设备内的局部同步.CUDA以thread/thread block/grid方式组织线程,且在程序执行过程中,一个thread block中线程 连续的数个thread将以SIMD模式执行,这些thread组成了一个warp.隐式同步是指:一个warp内部的各个thread在执行时是严格同步的,若存在没有执行完当前指令的thread,则任何thread都不会开始下一条指令的执行.显式同步是指:CUDA提供API用于完成一个thread block内部所有warp的同步.CUDA的隐式同步更强调相邻指令之间的执行顺序,而显式同步则强调thread block内部各个thread的内存视图一致.

与OpenCL/CUDA仅提供加速设备内同步机制不同,OpenStream还提供设备间同步机制,即,显式的设备同步结构,用于CPU与GPU之间的同步.

然而,更多异构并行编程接口并不提供任何显式同步机制,而是在程序中的特殊位置(通常是并行执行的循环迭代之间)设置隐式同步点.例如在OpenAcc中,并行区域包含的循环迭代间存在隐式的同步,但是程序员可以显式去除这些隐式同步点.文献^[26]提出的Python的异构扩展接口没有提供显式的同步机制,但在每个prange标明的并行循环末尾都默认存在一个隐式的同步点;并行循环是可以嵌套的,但隐式同步点仅存在于最外层循环的末尾.显式同步点的减少,极大地减轻了编程负担,因此,多数高级异构并行编程接口都选择不提供或少提供同步操作.但是隐式同步给编译器分析程序带来了诸多困难,极易带来执行效率的下降.

2.5 小 结

本节详细介绍了异构并行编程接口在任务划分、数据分布与通信、同步操作这3个领域的最新研究成果,它们与传统并行编程接口之间存在着本质差异,为异构架构以及上层应用带来的技术挑战提出了部分解决

方案:

1) 在解决第1.1.1节所述的异构架构带来的3个新问题方面,异构并行编程接口具有如下特点:

· 为了解决异构系统中设备间并行计算能力不同的问题,异构任务划分机制在传统并行编程模型的基础上增加了“异构特征描述”维度,用于描述任务在不同设备间的分配情况;

· 为了解决异构系统中加速设备内数据分布可配置、设备间数据通信渠道多样的问题,异构数据分布和通信机制在传统并行编程模型的基础上增加了“设备内数据多层分布”维度和“设备间显式通信”接口,不同于利用共享数据进行通信的方式;

· 为了解决异构系统中多范围同步操作的问题,异构同步机制在传统并行编程模型的基础上增加了“设备间同步”机制,同时,依据加速设备硬件特征,提供加速设备内的局部和全局同步.

2) 在解决上层应用带来的新问题方面,异构并行编程接口侧重于解决统一的编程接口问题,它尝试着将多种设备上的编程接口通过“异构特征描述”融合起来.但是这个问题目前仍然没有完全得到解决,表现在多数异构并行编程接口需要使用特殊的方式编写加速设备代码.

表 1总结了不同异构并行编程接口提供上述机制的方式.其中,

^*并行性表达一栏中,“数据”和“任务”分别代表数据并行和任务并行,其中,数据并行具有多种表达方式;

^{/sup>数据分布一栏中,“设备间”代表CPU与加速设备间的数据分布,“设备内”代表加速设备内的数据分布;}

^{/sup>异构同步机制一栏中,“设备间”代表CPU与加速设备之间的同步,“全局”和“局部”分别代表加速设备内部的全局和局部同步.}

从表 1可以看出:目前几乎所有的异构并行编程接口都提供显式的任务划分机制,且大多通过kernel函数标记加速设备代码;在异构数据分布机制方面,只有一半左右提供了显式接口用于表达数据在不同设备之间或加速设备内部的分布,而采用显式通信机制的并不占多数;在异构同步机制方面,只有少数显式提供了加速设备内部的局部同步操作,多数均选择隐式同步的方式.

3 异构编译/运行时支持机制研究

异构编译/运行时系统的研究,致力于解决第1.1.1节所述的异构架构带来的3个技术挑战以及上层应用带来的性能优化难度高的问题.具体地说,异构任务映射机制负责解决不同设备间并行计算能力不同的问题,将程序员划分好的并行任务映射到实际的物理计算单元中执行;异构编译/运行时优化负责解决性能优化难度高的问题,在数据分布可配置、通信渠道多样、多种同步范围的背景下,合理权衡异构系统整体资源利用率,提升程序性能.下面分别详细介绍异构任务映射机制及异构编译/运行时优化两个领域的研究成果.

3.1 异构任务映射机制

异构编译/运行时系统的任务映射机制有两类:一类是直接映射,即,独立完成并行任务向异构平台映射的工作;另一类是间接映射,即,需要借助其他异构编译/运行时系统协助完成部分任务映射工作.直接映射机制通常在运行时系统中实现,而间接映射机制则采取编译时源到源变换与运行时分析相结合的方式实现.

在图 5给出的异构编译/运行时系统的分类示意图中,纵坐标体现了运行时系统任务映射机制的不同.采取直接映射机制的并行编程模型,一般由工业界的知名公司提出并维护,例如Intel的Merge、微软的C++AMP、NVIDIA的CUDA和以AMD为代表进行推广的OpenCL,它们通常针对特定的异构系统进行任务映射与优化,有相应的硬件产品支撑.采用间接映射机制的并行编程模型,则通常选取工具链较为成熟、应用较为广泛的其他异构并行编程模型作为辅助,目前选择CUDA,OpenCL的居多,图 5标明了采用间接映射的异构并行编程模型分别利用哪种其他的编程模型实现任务映射的大致情况.

3.1.1 直接映射机制

OpenCL的任务映射机制相对简单,这是因为OpenCL编程接口为程序员提供了一个平台模型,把实际的异构系统抽象为具有统一的架构:异构系统由主机(host)与加速设备(device)构成,其中,加速设备可以是多个.每个加速设备包括数个结构一致的计算单元(compute unit,简称CU),而每个CU由数个结构一致的PE(processing element)构成.OpenCL kernel映射到device上执行:一个CU执行一组并行的线程,每个PE执行一个线程.因此, OpenCL可适用于任意异构系统 ,只需将异构系统实际的硬件架构与OpenCL平台模型对应起来即可,这也是OpenCL与只能应用于以NVIDIA GPU为加速设备的异构系统中的CUDA最大的不同.

与OpenCL相比,Merge的任务划分及映射工作较为复杂,需要将程序员使用Map Reduce函数编写的程序动态地映射到异构系统中合适的设备上执行,映射时的重要工作是确定粒度.如前所述,Merge提供了granularity variant机制,但是程序员无需确认实际粒度的大小;Merge运行时系统采用轮廓分析(profiling)的方式确定粒度:程序在不同设备上分别使用数量较少的数据点执行一次,记录它们的相对性能数据,并据此为不同的设备选择不同数目的数据点.

针对加速设备包含向量执行部件(即SIMD部件)的异构系统,文献^[35]提出了一种将OpenCL/CUDA这类SPMD程序变换为显式向量指令的方法,将kernel的计算任务映射到SIMD部件上.该方法的核心思想是:将几个相邻的kernel计算实例合并为一个向量操作,该方法将kernel函数作为一个整体,称为“全函数向量化”,它在程序的静态单赋值(static single assignment,简称SSA)^[36]表示上进一步实施数据流分析,以明确并行数据的取值范围,用于保障SIMD部件所需的数据对齐、连续等约束,同时生成模板处理不同的控制流.

针对包含多种微结构不同CPU(即,加速设备为CPU)的异构系统,文献^[37