采用确定性模式的结构化并行编程

作者:英特尔公司 Michael D. McCool

参加 HotPar ’10、第二届 USENIX 并行化热点话题研讨会,2010 年 14-15 日,Berkeley, CA.

下载 PDF 文档

下载采用确定性模式的结构化并行编程 [PDF 487KB]

多核处理器旨在利用各种形式的架构并行化(包括但不限于多核和矢量指令)提高计算性能。基于这些低等级并行机制的并行编程方法直接导致过于复杂、不可移植以及无法扩展的不可靠代码产生。

设计和部署并行算法的更具结构化的方法对于降低开发适用于此类处理器的软件的复杂度非常有用,与采用大量并行化和多个并行化机制的多核处理器息息相关。尤其是,高效可靠的并行程序可设计支持确定性算法骨架组合或模式。提高专家的工作效率时,具体的模式和模式组合还可指导经验相对较少的用户开发具有良好可扩展性的高效算法。

本文所述的并行化方法包括综合的“数据并行”模式(如映射和换算)和结构化的“任务并行”模式(如管线和超标量任务图)。基于结构化模式的方法,如数据并行模式,解决数据访问和通用框架中并行任务分配的问题。数据访问优化对于具有共享内存系统的多核处理器和自身具有内存的加速器(内存未与主机处理器直接相连)而言都非常重要。

后文将介绍一系列结构化顺序和并行模式。由于结构化并行编程可被视为顺序编程中结构化控制流的扩展,因此显示顺序模式。我们将重点说明确定性模式,以便支持自动避免不安全竞态条件和死锁的系统开发。


简介

出于多种原因,并行编程绝非易事。除了顺序计算的所有挑战外,并行编程还会受到竞态条件和死锁的影响,如果校正不确定,则加大了测试的难度。利用并行编程获得高性能还需要最大程度减少对有限资源,如通信和内存带宽的争用。如果未能恰当地解决这些问题,则会大幅降低程序性能。

本文讨论并建议采用结构化方法进行并行编程。该方法基于并行计算和数据管理的一系列通用组合模式,侧重于确定性和可扩展性。通过利用这些模式和关注算法设计中的少数因素(如数据本地化),采用该方法的程序可以在各种不同的并行电脑架构上运行和扩充。

此处讨论的结构化方法还称之为算法骨架方法。其基本原理是特定的计算和数据访问组合重复出现在多个不同的算法中。支持规格和“良好”模式组合的系统可以指导开发人员构建可靠的高性能结构化程序。模式可专用于域,但还具有存在于算法中来自多个不同域的通用模式。系统仅需支持少量的模式,以获得普遍性,即,能够实施任何算法。由于不同模式还可体现不同类型的数据相关性(可用于提高性能),因此该方法还有助于高效支持更多的通用子集。此外,这对于支持特定的“融合”模式组合也非常有用。

我们首先研究与并行模式、算法骨架及基于这些内容的一些系统有关的先期工作。在并行编程中使用模式与在顺序编程中使用结构化控制流及其相似。出于模拟原因,并且由于顺序计算是并行计算中重要的组成部分,我们将介绍和讨论支持顺序计算的一些基本模式以及基于这些模式通用子集的一些顺序编程模式。后文我们将介绍并讨论一系列实用的结构化和确定性并行模式。

背景

“算法骨架”(algorithmic skeleton)的概念最早由 Cole [1989,2004] 提出,后来由 Skillicorn [1998] 详加说明。它与现代设计模式 [Gamma 1994, Mattson 2004] 概念很相似,因此我们使用“并行模式”这一术语。我们将“并行模式 ”定义为计算和数据访问的特定经常性配置。在“View from Berkeley”[Asanovic 2006] 报告中确定了一些称为 dwarves 或 motifs 的典型的工作负载。这些是主要由一种类型模式组成的工作负载。其实在大多数应用中,各种模式以复杂的方式组成。编程系统可完全基于面向模式的运算符 [Bromling 2002, Tan 2003, Sérot 2002] 组合。

据记载,在上世纪 70 年代,顺序程序比较容易被理解和推测出是否由少量特定控制流模式(顺序、选择和迭代(和/或递归))中的控制流组成。尽管存有争议[Dijkstra1968],但这种结构化编程方法消除了大多数程序的 Goto 语句。现在,结构化控制流已被广泛采纳,在大多数现代编程语言中,Goto 语句或被省略或被弃用。

同样,结构化模式可以消除显式线程化和同步处理的需求,使程序更易被理解。尤其是,结构化并行模式应具备的一个优势特性是与程序特定顺序指令一致的确定性语义。相反,在灵活性方面,线程与 Goto 语句极其相似,但同样缺乏结构 [Lee 2006]。由于无法将程序的一个代码部分带来的效果与另一部分隔离开来,因此与 Goto 语句类似,利用线程(至少与全局随机数据存取结合时)会使程序的局部关系推理变得困难。

一种方法是使用函数编程。但是,大部分主流编程语言并非函数式语言,有些算法,特别是图形和矩阵问题,很难通过单纯的函数式语言表达出来。我们可以仅利用一组有限的模式将函数编程解释为结构化并行编程的一个实例。

此外,还有一大类通过在完整的数组上运算来表达显示并行运算的汇集型语言。汇集型语言可以是命令式语言,也可以是函数式语言。集合运算可通过函数库使用或作为主流语言中的内置运算。NESL 是汇集型单纯函数式语言的示例 [Blelloch 1990, 1993, 1996];FORTRAN 2003 是具有内置集合运算的命令式语言示例。RapidMind [McCool 2006] 和 Ct 是基于集合运算的命令式语言示例。确定性命令式汇集型语言被赋予连续顺序解释,使语言行为的推理变得直接。

本文将不对编程模式中的模式实施或规范进行详细说明。模式可通过以下多种方式实施或受到支持:作为规则;利用代码生成器 [Herrington 2003];在新语言设计中受到显式支持;或在函数库中实施。如果动态代码生成用于支持优化和融合 [McCool 2002, McCool 2006],则“函数库”方法与编译语言一样高效。

以下我们将首先讨论顺序模式。顺序模式非常重要,因为:第一,编程系统的顺序语义需要与并行语义有效结合。第二,在任何程序中,顺序计算占很大部分,通过一系列转变,并行实施常常从顺序实施衍生而来(例如,在索引空间里将循环转变为一组并行任务)。第三,“常见”空间里的研究模式(如顺序计算)将为并行模式扩展奠定稳固的基础。

顺序控制流模式

早期的顺序编程语言具有与基础机器语言控制流机制类似的结构,并包含按顺序执行的命令,还具有跳转或转移至序列中不同位置的功能。但人们很快意识到,这种毫无限制地使用Goto 语句,会导致程序不可读和不可维护。结构化编程限制了控制流结构,使其成为具有理想属性的小型组合集。结构化控制流结构还使分类和局部推理程序成为可能 [Dijkstra1968]。

本节并未对支持通用计算的所有顺序模式进行说明。以下模式的两个通用子集形成命令式和函数编程语言的类。一般情况下可以选择递归或迭代(无需同时选择二者),这同样适用于用于动态内存分配和随机写入。

A. 顺序
如果第一项任务中的所有运算一旦完成后(包括所有内存更新),第二项任务才开始,此时,这两项任务被视为按顺序执行。

B. 选择
选择模式基于布尔值条件表达式的结果执行两项任务中的一项(评估构成第三项任务)。

C. 迭代

迭代任务重复一项任务(其“循环体”),直到满足某些条件。循环体的每次调用在下一次开始调用前结束,即按顺序执行。条件评估也按循环体的顺序执行。

可通过循环体读写的内存位置称为循环传递相关性。由于循环传递相关性经常用于计算索引,因此循环索引还可被视为循环模式本身的一部分。许多循环可并行执行,即使它们具有循环传递相关性也可实现。

D. 函数和递归
运算的顺序可存储于之后重复调用的函数内。借助用于特定函数激活的输入数据,函数可以实现参数化,并具有自己的局部状态。函数计算出数值并返回这些值。纯函数无法修改输入值或产生其它副作用,如修改内存。

函数可以具有自己的局部存储。如果借助每次函数激活为局部存储分配新位置,则可以实现函数递归调用。此类递归函数可以构成分治法算法模式。

顺序数据管理模式

随机读取和写入数据存取模式直接映射至基础硬件机制中。堆栈和动态内存(堆)分配时通用的高等级模式。

A. 随机存取读取
一个索引通过随机存取读取,检索与该索引有关的值。数组是随机存取内存的最简单形式,所有其它数据结构可构建于数组之上:物理计算机的 RAM 不过是大型的固定长度整数 1D 数组。

索引可被计算出来并存储于其它内存部件中。前一个属性支持构建高等级模式,如堆栈,同时能够在内存中存储索引,支持基于指针的复杂数据结构(只是对索引的抽象化)。

B. 堆栈分配
堆栈支持内存分配的先进先出(LIFO)模式,常用于嵌套函数调用,支持对局部状态最新副本的分配。无论在空间上还是时间上,堆栈分配都具有出色的相关属性。

堆栈分配可以发生在支持局部变量的顺序嵌套的激活函数中。

C. 动态内存(堆)分配
当堆栈支持的 LIFO 模式内存分配并不适合时,可以采用更常用的内存分配模式,在需要时分配新的内存位置。

D. 集合与数据抽象
除了简单的数组外,集合抽象可以包括嵌套数组和数据库。嵌套数组内可以包含一组其它数组。子数组的大小可以固定也可以变化。我们将前一个嵌套数组类型称为分块数组,后一个成为称为分段数组。

可利用辅助索引和标志数组 [Blelloch 1990] 表达一维分段数组并在该数组上高效执行运算。同样,利用数据本身的压缩表达式和辅助数据结构来跟踪分块界限,也可以高效地表达分块数组并在该数组上高效执行运算。

数据库保存一组数据元素,并支持搜索运算。尤其是,通过部分匹配内容可以搜索到数据元素。

顺序编程模式

现在,我们将介绍两类最常见的顺序编程模式。

A. 命令式编程
在命令式模式计算中,程序员直接告知电脑做什么和按什么顺序做。为了实现普遍性,顺序命令式编程模式需要至少支持序列、选择和迭代控制流模式,一般支持随机读取和随机写入模式。

通常命令式编程还支持递归和函数,尽管在技术上不需要这二者。特别是 FORTRAN,该语言在不久前才添加有递归支持。

命令式编程是目前主要的顺序编程模式。从并行化的角度来看,其主要缺点是对运算顺序的要求过高。对于命令式程序而言,顺序限制对于程序的正确运算非常重要,并且是程序员表达计算的方式所带来的意外结果,因此自动确定运算顺序非常困难。尤其是,由于指针可以指向全局数组的任何地方,因此全局内存数组是所有运算的潜在来源和目的地,这使得命令式程序具有普遍的数据相关性。

B. 函数编程

函数模式计算基于重新写入嵌套式树或嵌套图。纯函数语言一般只支持控制流的选择和递归,支持数据存取的随机读取。可创建数据结构(利用动态内存分配)但不可修改结构。纯函数语言虽然简单,但具有通用性。一些依赖于数据递增式修改的算法很难通过纯函数语言表达出来。

从并行化角度而言,函数语言的主要优势是只表达基本的数据相关性,只有这些数据相关性限制运算的顺序。

并行计算模式

现在,我们将介绍一系列并行计算模式。我们将并行模式划分为两类:通过数据值进行运算的计算模式和无法通过数据值进行运算的数据存取模式。两类模式常常组合使用,本节所述的许多计算模式还以特定(通常相关)的方式存取和更新数据。

A. 映射
映射并行计算将函数应用于集合的每个元素中(或具有相同形式的数据集),利用来自函数调用的结果创建新的集合(或一组集合)。此处未指定支持并行执行的函数调用的执行顺序。如果函数是不产生任何副作用的纯函数,那么映射运算具有确定性,同时支持大量并行化要求。一般情况下,映射使用的(纯)函数还可递归支持其它类型的顺序和并行模式及数据管理。

映射运算以体现空间相关性的方式访问输入和输出数据。它一次性执行许多函数,并事先知道哪些函数访问输入和输出集合中的邻近值。这有助于实现在映射函数实施中执行各种顺序、并行和内存优化,包括软件流水线、高速缓存预取和收回以及高速缓存边界对齐。假定映射中邻近元素的行为导致类似的控制流行为产生,那么采取一些简单的方法实现基于屏蔽的矢量化也会非常有效。

B. 约简(Reduction)
约简将成对关联运算应用于集合的所有元素中,将其约简为一个元素。

有时,写入一个用于在映射运算中使用的函数时,还需要同时计算约简。其中一个很好的示例是迭代解算器。此类解算器的内部循环通常既执行矩阵矢量运算也执行约简运算(用于测试融合)。一般情况下,高效的运算实施需要将模式融合在一起。还有其它许多示例,如压缩,在压缩中,融合对于性能而言更重要。

有时还会使用其它一些形式的约简。这些形式被视为纯约简与其它模式融合。 多维约简(例如,一个数组行的约简)可通过组合分块模式与映射和约简来表达。在类别约简运算中,利用运算符标记元素,然后将约简运算应用于所有具有相同标记的元素中。Google 映射-约简编程模式是单融合映射以及与顺序执行模式组合的类别约简运算的基础。

C. 超标量序列
序列是基本的顺序模式。在序列模式中,一个运算完全结束后另一个运算才开始执行。但是,当运算是不产生副作用的纯函数时,序列中的运算只需要按数据相关性排序(在这种情况下,纯函数为显式函数)。

通常,一个序列生成一个数据相关性 DAG(任务图)。简单的异步执行规则支持并行化,同时仍允许程序员进行顺序推理:如果任务试图读取尚未准备好的数据,它会进行阻止直到数据准备好。

尽管在该模式中,输入代码从概念上来说属于顺序代码,但图中的数据相关性使独立的任务能够并行执行。

在超标量模式下,不允许使用讯息传递在任务之间进行直接通信和同步化。实际上,任务无需同步激活,它们可以按顺序执行。不使用非结构化的低等级通信,可以使用两种其它结构化模式:流水线模式和嵌套式并行化,来支持同步活跃任务之间共享和通信数据。流水线模式支持生产者-消费者通信,而嵌套式并行化则支持子进程-父进程通信。

D. 流水线
流水线是一组同步活跃的任务,或者说以生产者-消费者关系进行通信的“阶段”。流水线不能作为超标量任务图表达,因为在流水线中,阶段中的数据是持续的,从概念上来说可同时激活,不同于超标量任务图中的任务。在图像和信号处理中,流水线非常常见。其局部状态更新模式是一种相关形式,未包含在其它模式中。此外,流水线还可用于并行化处理顺序上独立的活动(“文件夹”),如压缩和解压。

只使用流水线并不能完全解决并行化问题,因为流水线具有固定数量的阶段。因此,它们无法自动扩展至大量核心。但是,流水线可提供一个以其它方法很难并行化处理问题的支持并行化的实用乘法器。

E. 嵌套
递归也是一种重要的串行控制流程模式。它同样与基于堆栈的数据分配有关,在数据一致性方面表现良好。当并行模式通过递归方式嵌套时,它们可用于生成大量的额外并行任务,从而让程序生成任意数量的嵌套并行性。这种形式的嵌套并行性明显不同于源自嵌段式集合运算的嵌套并行性。然而,在许多情况下,或许可以确定更加普通的递归嵌套并行性的某些模式,并将这些模式映射到嵌段式运算,以提高编程效率。

通过调用其它并行模式中的并行模式可以轻松调用嵌套并行性,例如使用其它归纳或映射函数内部的归纳或映射。这样可以生成一个分级任务图表,按需扩展该图表,又可以生成更多并行性。嵌套并行性可以是任务并行,也可以是数据并行。

事实上,任意数量的并行性可能毫无用处。确定性并行模式的优势之一是,它们与具体的串行排序完全一致。实施需要针对一个对于实现既定硬件目标最有效的“粒度”。太小的任务需要合并到较大的串行任务中,而较大的串行任务则需要分解为多个并行任务,整个过程最好能自动完成。串行一致性允许这个过程自动完成,但最后生成的程序不会发生改变。

F. 扫描和递归
就之前的输出而言,递归表示一个函数输出。由于使用了循环体间的相关性,递归通常发生在串行代码中,但是在某些情况下它们可以被并行化。如果相关性是关联的,一维递归可以被并行化为对数时间实施,在这种情况下,它通常被称作扫描 [Blelloch 1990]。对于嵌套深度为 n 的多维递归,即使运算符号不是关联的,也可以一直使用 Lamport 的超平面理论在 n-1 维上进行并行处理 [Lamport 1974]。

一维递归(即使是不关联的)也很常见,通常被称作褶皱。尽管映射中的褶皱序列可以使用管道被转化为并行实施,但是褶皱往往需要通过串行方式实施。与归纳一样,确定允许在扫描中执行并行化的关联函数存在一个重要问题,而且半关联运算(例如浮点算法)也存在问题。

递归示例包括积分和无限脉冲响应(递归)滤波器。许多矩阵因式分解算法,例如切比雪夫因式分解也通常用递归表示。

嵌段式和分区式集合上的扫描(以及普通意义上的递归)也可以以负载均衡形式高效实施,甚至在子阵列尺寸不尽相同的嵌段式阵列中也可以。使用此类负载均衡式基本运算,或许可以实施均衡式并行递归和“不规则”算法,例如快速排序算法。

并行数据管理模式

数据访问和管理模式可以组织数据访问,但是不能自行使用这些值进行运算。许多具体数据访问和计算模式的组合都是通用的,可以被视作它们的自有模式。这是因为对于高效实施而言,数据访问模式通常必须与具体并行计算模式相融合。

A. 采集
考虑到索引集合和非索引集合,采集需要从索引提供的所有位置进行并行读取来生成输出集合。

随机读取是一种串行模式,但是在映射内部使用时,它将变成集合式采集。另外,采集或许由明确的集合运算提供支持。

B. 搜索
搜索模式类似于采集,但是可以根据内容匹配从“数据库”集合检索数据。同时搜索所有关键词,或者在数据库的不同部分进行并行搜索,可以实现并行性。

C. 细分
在并行算法中,我们通常想把输入分为多个片段,然后在各个片段上进行并行运算。

细分有许多可能的变体。通过分区可以将集合分为多个尺寸相同的非重叠区域,构成一个嵌套集合。通过分段可以将集合分为多个不同尺寸的非重叠区域,构成一个嵌段集合。集合分块可以为更大集合中的区域创建一个可能重叠参考集合。

D. 模板
有意义的映射扩展(也可被视作映射之前分块的规则变体)是相邻模板。在这种模式中,输入阵列中的相邻规则模板只使用单个元素进行运算。在信号处理中,这叫做有限卷积,但是这种模式也会出现在多种模拟(PDE 解算程序)和矩阵计算中。

我们必须注意超出阵列边缘的相邻模板。我们应当改变此类访问(例如通过约束索引),使它映射到定义确切的值。

使用低级运算高效实施这种模式极为复杂,这就是将其列入基本模式的原因。针对输入阵列的内部和边界生成独立版本的任务对此有所帮助。另外,在输入阵列的部分重叠区域上使用滑动窗口也有帮助。

然而,对于移植性,这些优化可以而且应当在语言实施中自动发生,因为它们有着不同的硬件目标。 另外,尽管归纳可变分析可以而且应当在可能的时候用于确定模板模式,但是接口也应当允许直观地列出模板规格。

E. 散射
散射可以将数据写入集合中的随机位置(由整数索引提供),覆写该位置存储的任何数据。散射的多个变体可以被确定,具体情况视冲突(并行写入同一位置)的解决方法而定。

假设有一个数据集合,优先散射允许将其写入现有集合中的位置集合。使用确定性规则可以解决冲突(重复写入同一位置)。

优先散射运算很有用,因为循环体的串行排序可用于生成消除二义性规则。带散射运算的循环(只要它们也没有循环体间的相关性)可以安全转化为优先散射。

高效实施优先散射的方法有很多。如果证明不可能与其它线程发生冲突,则可以使用普通串行语义实施优先散射。例如,如果映射输出是分区,函数的每次调用只可能散射到它自己的输出分区。另一种情况是,输出数据由线程动态分配。

原子散射是一种非确定性模式(本文只讨论这一种),它只能保证发生冲突时输入位置有一个结果。如果需要通过锁定来保存原子写入,那么实施原子散射仍然可能需要高额成本。

置换散射是一种只在没有冲突的情况下才可生成的散射。由于它是一种不安全的散射,所以通常可以高效实施。然而,这意味着,如果错误地与一些包含重复地址值的写入位置搭配使用,它可能生成错误的结果,因此,应当提供调试模式,查找此类错误使用。

当发生冲突时,合并散射可以使用关联运算符号合并元素。这条规则也可用于合并散射值和阵列中的现有数据。柱状图运算就是一个典型的例子。

F. 打包
打包模式可用于消除稀疏集合中被浪费的空间,处理变速映射输出。在映射内部,每个函数激活都可以保留或丢弃自己的输出结果。然后,保存下来的结果被打包到一个集合里。打包模式的变体是扩展模式,它可以生成“0”或更多值。独立打包集合运算不像可以与映射融合的运算那样有用,因为后者不需要为已丢弃的数据分配内存空间。

结论

使用计算和数据访问组成确定性并行模式,可以彻底构建确定性并行程序。然而,根据这些模式实施编程模型不仅要支持各种各样的模式,还要能够按需控制执行、扩展和融合的粒度。

参考文献

[Aldinucci 2007] M. Aldinucci and M. Danelutto, 《基于骨架的并行编程:单次编程中的函数和并行语义》,计算机语言系统结构,33(3-4),第 179-192 页,2007 年。

[Asanovic 2006] K. Asanovic et al, 《并行计算前景研究:Berkeley 的观点》,加州大学 EECS 专业,Berkeley EECS-2006-183,2006 年。

[Blelloch 1993] G. E. Blelloch, J. C. Hardwick, S. Chatterjee, J. Sipelstein and M. Zagha, 《实施可移植的嵌套数据并行语言》,PPOPP '93:第四届ACM SIGPLAN 并行编程原理与实践论坛记录,第 102-111 页,1993 年。

[Blelloch 1996] G. E. Blelloch, 《编程并行算法》,Commun.ACM 通讯,39(3),第 85-97 页,1996 年。

[Blelloch 1990] G. E. Blelloch, 《基于向量的数据并行计算模型》,MIT Press,1990 年。

[Bosch 1998] J. Bosch. 《设计模式即语言结构》,面向对象编程期刊,11(2),第 18-32 页,1998 年。

[Bromling 2002] S. Bromling, S. MacDonald, J. Anvik, J. Schaefer, D. Szafron, K. Tan, 《基于模式的并行编程》,加拿大温哥华并行编程国际大会记录(ICPP'2002),第 257-265 页,2002 年 8 月。

[Buck 2007] I. Buck, 《GPU 计算:大规模并行处理器编程》,代码生成与优化国际论坛记录,IEEE 计算机协会,2007 年 3 月 11-14 日。

[Cole 1989] M. Cole. 《算法骨架:并行计算的结构化管理》,Pitman/MIT Press,1989 年。

[Cole 2004] M. Cole, 《公开骨架:基于骨架的并行编程实用宣言》,并行计算,30(3),第389-406 页,2004 年 3 月[Czarnecki 2000] K. Czarnecki and U. Eisenecker, 《产生式编程:方法、工具和应用》,2000 年,ACM Press/Addison-Wesley。

[Darlington 1995] J. Darlington, Y. Guo, H. W. To and J. Yang, 《结构化组合并行骨架》, SIGPLAN Not.,30(8),第 19-28 页,1995 年。

[Dijkstra 1968] E. Dijkstra, 《转向语句被认为是有害的》,ACM 通讯,11 (3),第 147-148 页,1968 年 3 月。

[Dorta 2006] A. Dorta, P. López and F. de Sande, 《11c 中的基本骨架》,并行计算,32(7),第 491-506 页,2006 年 9 月。

[Gamma 1994] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. 《设计模式:可复用面向对象软件的基础》,Addison-Wesley,1994 年。

[Gorlatch 1999] S. Gorlatch, C. Wedler and C. Lengauer, 《集合运算编程的优化规则》,第十三届并行处理国际论坛记录和第十届并行处理与分布式处理论坛记录,第 492-499 页,1999 年 4 月 12-16 日。

[Herrington 2003] J. Herrington, 《代码生成实践》, Manning Publications,2003 年。

[Kessler 2004] C. Kessler, 《并行算法理论实践》,ACM SIGCSE Bulletin,36(1),2004 年 3 月。

[Klusik 2000] U. Klusik, R. Loogen, S. Priebe, F. Rubio, 《Eden 中的实施骨架:轻松并行编程》,第十二届函数语言实施国际研讨会指定论文,第 71-88 页,2000 年 9 月。

[Lamport 1974] L. Lamport, 《DO 循环的并行执行》,ACM 通讯,17(2),第 83-93 页,1974 年 2 月。

[Lee 1996] P. Lee and M. Leone, 《通过运行时代码生成优化 ML》,1996 年 ACM SIGPLAN 编程语言设计与实施大会记录,第 137-148 页,1996 年 5 月。

[Lee 2006] E. A. Lee, 《线程问题》,IEEE 计算机协会,39(5),第 33-42 页,2006 年 5 月。

[MacDonald 2002] S. MacDonald, J. Anvik, S. Bromling, D. Szafron, J. Schaeffer and K. Tan. 《从模式到框架到并行程序》,并行计算,28(12),第 1663-1683 页,2002 年。

[Massingill 1999] M. Massingill, T. Mattson, and B. Sanders. 《面向并行应用程序的模式语言》,技术报告 CISE TR 99-022,弗罗里达大学,1999 年。

[Mattson 2004] T. Mattson, B. Sanders, B. Massingill, 《并行编程模式》, Pearson Education,2004 年。

[McCool 2002] M. McCool, Z. Qin, and T. Popa, 《Shader 元编程》,HWWS '02:ACM SIGGRAPH/EUROGRAPHICS 图形硬件大会记录,第 57-68 页,2002 年。

[McCool 2004] M. McCool, S. Du Toit, T. Popa, B. Chan and K. Moule, 《Shader 代数学》,ACM Trans. Graph.,23(3),第 787-795 页,2004 年。

[McCool 2004] M. McCool and S. Du Toit, 《采用 Sh 的元编程 GPU》, AK Peters,2004 年。

[McCool 2006] M. McCool. 《使用 RapidMind 开发平台进行 Cell BE 和 GPU 数据并行编程 》,GSPx 多核应用大会,共 9 页,2006 年。

[Pelagatti 1998] S. Pelagatti, 《并行程序的结构化开发》,Taylor & Francis, Inc.,宾夕法尼亚布里斯托尔,1998 年。

[Owens 2005] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krueger, A. E. Lefohn, and T. J. Purcell, 《关于图形硬件的普通计算调查》,Eurographics 2005,State of Art Report。

[Schmidt 2000] D. Schmidt, M. Stal, H. Rohnert, and F. Buschmann. 《面向模式软件架构:并发和网络对象模式》,第 2 卷,Wiley & Sons,2000 年。

[Sérot 2002] J. Sérot, D. Ginhac, 《并行镜像处理:SKIPPER 项目概述》,并行计算,28(12),第 1685-1708 页,2002 年 12 月。

[Siu 1996] S. Siu, M. De Simone, D. Goswami, and A. Singh. 《并行计算的设计模式》,1996 年并行与分布式处理国际大会记录,技术与应用(PDPTA'96),第 230-240 页,1996 年。

[Skillicorn 1998] D. B. Skillicorn and D. Talia, 《并行计算模型与语言》,ACM 通讯调查,30(2),第 123-169 页,1998 年。

[Tan 2003] K. Tan, D. Szafron, J. Schaeffer, J. Anvik and S. MacDonald, 《使用产生式设计模式为分布式内存环境生成并行代码》,PPoPP '03,第九届 ACM SIGPLAN 并行编程原理与实践论坛记录,第 203-215 页,2003 年。

[Veldhuizen 1999] T. L. Veldhuizen, 《C++ 模板即部分赋值》,ACM SIGPLAN 基于部分赋值和语义的程序处理研讨会,1999 年。
For more complete information about compiler optimizations, see our Optimization Notice.