2024年5月27日发(作者：象雨文)
ＣＮ４３ １２５８／ＴＰ
ＩＳＳＮ １００７一ｌ３ＯＸ
计算机工程与科学
ＣＯＭＰＵＴＥＲ ＥＮＧＩＮＥＥＲＩＮＧ ８Ｌ ＳＣＩＥＮＣＥ
２０１１年第３３卷第３期
Ｖｏ１．３３，Ｎｏ．３。２０１１
文章编号：１００７—１３０Ｘ（２０１１）０３ ００４１—０５
模板操作在ＧＰＵ上的实现与优化
Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｎｄ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ
Ｓｔｅｎｃｉｌ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｎ ＧＰＵｓ
方旭东，唐玉华，王桂彬，唐滔
ＦＡＮＧ Ｘｕ—ｄｏｎｇ，ＴＡＮＧ Ｙｕ—ｈｕａ，ＷＡＮＧ Ｇｕｉ—ｂｉｎ。ＴＡＮＧ Ｔａｏ
（国防科学技术大学计算机学院，湖南长沙４１００７３）
（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ ４１００７３，Ｃｈｉｎａ）
摘 要：随着ＧＰＵ的快速发展，使用ＧＰＵ来加速科学计算应用已成为必然趋势。本文抽取了
ＳＰＥＣ２０００中富含模板操作的Ｍｇｒｉｄ的两个典型子程序Ｒｐｒｊ３和Ｉｎｔｅｒｐ，使用Ｂｒｏｏｋ＋语言把它们移植到
ＡＭＤ ＧＰＵ上运行。采用Ｂｒｏｏｋ＋语言提供的线程调节机制，我们实现了不同线程粒度下的程序版本，并
分析了加速比不同的原因，总结了线程粒度调节对模板程序移植的指导意义。我们使用ＡＭＤ Ｒａｄｅｏｎ
ＨＤ４８７０ ＧＰＵ作为实验平台，对比Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５４０５ ＣＰＵ上的运行结果发现，在最大规模下，Ｒｐｒｊ３获得
的相对于ＣＰＵ版本的加速比为５．３７×，Ｉｎｔｅｒｐ获得的相对于ＣＰＵ版本的加速比为１２．８×。
Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｔｈｅ ｆａｓｔ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ＧＰＵｓ，ｕｓｉｎｇ ｔｈｅｍ ｔｏ ａｃｃｅｌｅｒａｔｅ ｓｃｉｅｎｔｉｆｉｃ ｃｏｍｐｕｔｉｎｇ ａｐｐｌｉｃａ—
ｔｉｏｎｓ ｉｓ ｂｅｃｏｍｉｎｇ ａｎ ｉｎｅｖｉｔａｂｌｅ ｔｒｅｎｄ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐｏｒｔ ｔｗｏ ｔｙｐｉｃａｌ ｓｕｂｒｏｕｔｉｎｅｓ Ｒｐｒｊ ３ ａｎｄ Ｉｎｔｅｒｐ
ｆｒｏｍ Ｍｇｒｉｄ ｗｈｉｃｈ ｃｏｎｔａｉｎｓ ｒｉｃｈ ｓｔｅｎｃｉｌ ｏｐｅｒａｔｉｏｎｓ ｉｎ ＳＰＥＣ２０００ ｔｏ ｒｕｎ ｏｎ ａｎ ＡＭＤ ＧＰＵ ｕｓｉｎｇ Ｂｒｏｏｋ＋．
Ｕｓｉｎｇ ａ ｔｈｒｅａｄ ｇｒａｎｕｌａｒｉｔｙ ｔｕｎｉｎｇ ｍｅｃｈａｎｉｓｍ ｐｒｏｖｉｄｅｄ ｂｙ Ｂｒｏｏｋ＋，ｗｅ ｉｍｐｌｅｍｅｎｔ ｄｉｆｆｅｒｅｎｔ ｐｏｒｔｅｄ ｐｒｏ—
ｇｒａｍ ｖｅｒｓｉｏｎｓ ａｎｄ ａｎａｌｙｚｅ ｔｈｅｉｒ ｐｅｒｆｏｒｍａｎｃｅｓ．Ｗｅ ａｌｓｏ ｃｏｎｃｌｕｄｅ ｈｏｗ ｔＯ ｕｔｉｌｉｚｅ ｔｈｒｅａｄ ｇｒａｎｕｌａｒｉｔｙ ｔｕｎｉｎｇ
ｔｏ ｏｐｔｉｍｉｚｅ ｓｔｅｎｃｉｌ ｐｒｏｇｒａｍ ｔｒａｎｓｐｌａｎｔａｔｉ０ｎ． Ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｕｎｄｅｒ ｔｈｅ ｌａｒｇｅｓｔ ｐｒｏｂ—
ｌｅｍ ｓｉｚｅ，Ｒｐｒｊ３ ｏｂｔａｉｎｓ ａ ｓｐｅｅｄｕｐ ｏｆ ５．３７ ｏｖｅｒ ｉｔｓ ＣＰＵ ｖｅｒｓｉｏｎ ｗｈｉｌｅ Ｉｎｔｅｒｐ ｇａｉｎｓ ａ ｓｐｅｅｄｕｐ ｏｆ １２．８ ｏｖｅｒ
ｉｔｓ ＣＰＵ ｖｅｒｓｉｏｎ．
关键词：ＧＰＵ；优化；模板
Ｋｅｙ ｗｏｒｄｓ：ＧＰＵ；ｏｐｔｉｍｉｚａｔｉｏｎ；ｓｔｅｎｃｉｌ
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—１３０Ｘ．２０１１．０３．００８
中图分类号：ＴＰ３０３ 文献标识码：Ａ
解图形编程的细节，便可以着手在ＧＰＵ上编写通
引言
近年来，随着ＧＰＵ技术的发展，ＧＰＵ的浮点
处理能力变得越来越强大。新的ＧＰＵ体系结构
具有更好的可编程性和通用性，使编程人员无需了
用程序。这方面的语言有ＡＭＤ的Ｂｒｏｏｋ＋ｌ】 和
ＮＶＩＤＩＡ的ＣＵＤＡｌ２ｊ。ＧＰＵ的强大计算能力现已
被用于生物医学、计算流体动力学模拟和分子动力
学模拟等科学计算领域 。
现在的ＧＰＵ虽然具有很强的计算能力，但由
收稿日期：２００９—０７ ２６；修订日期：２００９ １０－２１
基金项目：国家自然科学基金资助项目（６０６２１００３）
通讯地址：４１００７３湖南省长沙市国防科学技术大学计算机学院
Ａｄｄｒｅｓｓ：Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ ４１００７３，Ｐ．Ｒ．Ｃｈｉｎａ
４１
于ＧＰＵ最初用于图形处理，偏重处理的实时性，
其编译器自动优化程序的能力较弱。这就给编程
人员手工优化ＧＰＵ程序提供了空间。本文从
Ｓｐｅｃ２０００测试程序中选取了用于解偏微分方程的
Ｍｇｒｉｄ应用，从中抽取了典型的函数Ｉｎｔｅｒｐ和
Ｒｐｒｊ３，将它们移植到ＡＭＤ ＧＰＵ平台上运行。Ｉｎ—
ｔｅｒｐ和Ｒｐｒｊ３中大量的模板（Ｓｔｅｎｃｉｌ）计算为优化
ＧＰＵ程序提供了很好的机会 。我们采用通过调
节线程问并行性、增加线程内局部性的方法优化初
始的ＧＰＵ代码。我们将ＡＭＤ Ｒａｄｅｏｎ ＨＤ４８７０
ＧＰＵ和Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５４Ｏ５ ＣＰＵ上的测试结果进
行对比发现，在最大规模下，Ｒｐｒｊ３获得的相对于
ＣＰＵ版本的加速比为５．３７×，Ｉｎｔｅｒｐ获得的相对
于ＣＰＵ版本的加速比为ｌ２．８×。
２ 背景
本节介绍在ＡＭＤ ＧＰＵ上用Ｂｒｏｏｋ＋进行编
程的背景。
２．１异构平台介绍
使用ＧＰＵ和通用ＣＰＵ构建异构并行系统已
成为高性能计算领域的研究热点一ｓ］。ＧＰＵ强大的
浮点计算能力和超高的性能功耗比使得它们成为
非常好的ＣＰＵ计算加速部件。一个典型的ＣＰＵ—
口叩口叩口叩口叩口口叩叩口叩口叩＝【 一ｌ一一
ＧＰＵ异构系统如图１所示。ＣＰＵ和ＧＰＵ之间存
在数据通信开销和调用开销。数据通信开销是指
口叩口叩口叩口叩口口叩叩口叩口叩ｌｌ～一椰一
计算前数据从ＣＰＵ加载到ＧＰＵ的开销和计算后
口口口口口口口口＝叩叩叩叩叩叩叩叩一椰一～一
结果从ＧＰＵ加载到ＣＰＵ的开销。调用开销是指
从ＣＰＵ发出调用指令到指令到达ＧＰＵ命令处理
器的延迟。
ＰｒＴ Ｅ
１ ＣＰＵ ＧＰＵ异构系统
２．２微体系结构
本文中我们采用ＡＭＤ Ｒａｄｅｏｎ ＨＤ４８７０ ＧＰＵ
作为ＣＰＵ的加速器。ＡＭＤ ＨＤ４８００系列是
ＡＭＤ ＧＰＵ的最新产品，具有双精度浮点处理能
力，其使用的核心是ＲＶ７７０。如图２所示，在
ＲＶ７７０的数据并行阵列中拥有１Ｏ个ＳＩＭＤ引擎，
它们同时处理一个Ｋｅｒｎｅｌ程序；每个ＳＩＭＤ引擎
又由１６个线程处理器组成，这ｌ６个线程处理器共
用一个程序计数器，所以它们之间是完全同步执行
４２
的；线程处理器是一个超长指令字（ＶＩ ＩＷ）处理单
元，这个ＶＩ １ｗ包括４个标量计算核和１个超越
计算单元，一个线程处理器通过阻塞多线程的方式
同时运行４个线程。经过上述分析我们发现，
Ｒ７７０拥有８００（１０＊１６＊５）个计算核，可以提供巨
大的计算能力。表１概括了Ｒａｄｅｏｎ ＨＤ４８７０的详
细性能参数。
线程分配处理器
圆
线程处理单元ｌ ｌ指令流和控制流
图２ ＲＶ７７Ｏ微体系结构
表１ ＡＭＤｓ ＨＤ４８７０性能参数
参数 值 参数 值
Ｍ。 。 ｙ ＣＩ。ｃｋ ９９３ ＭＨ
ｚ
ｒｏｃｅｓｓｏｒｓ
８ＯＯ
Ｓｐｅｅｄ
Ｘｔ 。 ４ｏ Ｍ
ｅｍｏｒｙ Ｉｎｔｅｒｆａｃｅ ２５６ ｂｉｔｓ
Ｕｎｉｔｓ
Ｃｏｒｅ Ｃｌｏｃｋ ７５０ Ｍ 。 ｙ Ｂ “ｄ １ ｌ５ ＧＢ／
Ｓｐｅｅｄ ＭＨｚ ｗｉｄｔｈ ｓ
Ｍｅｒｅ。 ｙ ＧＤＤＲ５ Ｓｉｎｇｌｅ（ｄｏｕｂｌｅ） １．２ Ｔ（２４０Ｇ）
ｌ ｙｐｅ Ｐｅａｋ ｆｌｏｐｓ
在ＡＭＤ流编程模型中，流（Ｓｔｒｅａｍｓ）指可以
被并行操作的相同类型的数据集合，核（Ｋｅｒｎｅ１）是
指可以在每个输出流元素上进行操作的并行函数。
线程（Ｔｈｒｅａｄ）是指线程处理器上核的一次执行实
例。线程被映射到流处理器上执行，并以波阵面
（Ｗａｖｅｆｒｏｎｔ）为单位调度。波阵面是指在ＳＩＭＤ引
擎上被同时执行和调度的一组线程。ＧＰＵ硬件调
度通用寄存器（ＧＰＲｓ）、存储带宽等资源，直至所有
线程处理完毕。多个波阵面交织运行以隐藏访问
延迟。不同的ＳＩＭＤ引擎可以执行不同的指令，另
外流水线技术也被ＧＰＵ硬件采用以获得性能提
升 。
２．３ Ｂｒｏｏｋ＋流编程环境
ＡＭＤ提供了完整的ＧＰＵ编程环境，使得编
程人员可以方便快速地着手进行ＧＰＵ上的程序
开发。程序员可以在两级抽象层次上编程，高层使
用Ｂｒｏｏｋ＋，底层使用ＣＡＩ （Ｃｏｍｐｕｔｅ Ａｂｓｔｒａｃｔｉｏｎ
Ｌａｙｅｒ，简称ＣＡＩ ）。Ｂｒｏｏｋ＋基于ＢｒｏｏｋＧＰＵＬ ，
（２）使用多输出流（Ｍｕｌｔｉｐｌｅ Ｏｕｔｐｕｔ
Ｓｔｒｅａｍｓ）。Ｂｒｏｏｋ＋语言最多支持８条输出流ｌ】］。
和使用单条输出流相比，使用多输出流后线程可以
执行更多的计算，同样增大了线程粒度。例如，使
用两条输出流可以把线程粒度增大一倍。而如果
是对Ｃ语言的扩展，支持显式的计算和数据并行。
Ｂｒｏｏｋ＋作为一种高层的编程语言，屏蔽了体系结
构细节，保留了和现代图形硬件相关的特征。
ＣＡＬ作为一种设备驱动库，提供向前兼容的接口，
可以直接和流处理器交互，所以ＣＡＬ提供了更多
的优化机会。我们只在Ｂｒｏｏｋ＋一级进行了移植
和优化。
３ 优化策略
ＧＰＵ更适合于处理计算密集型应用而非访存
密集型应用¨７］。为了充分发挥ＧＰＵ的计算优势，
应该有足够多的线程来占用ＧＰＵ提供的大量的
线程处理器。线程之间以波阵面为粒度调度，可以
有效隐藏访存延迟。另一方面，线程局部性
（Ｔｈｒｅａｄ Ｌｏｃａｌｉｔｙ）对于发掘计算中的数据复用、提
高程序性能也有很重要的作用。Ｍｇｒｉｄ中包含大
量的模板操作。所谓模板操作，是指在计算每个点
时都需要访问这个点的相邻点。所以，模板操作提
供了丰富的时间局部性和空间局部性优化的机会。
在Ｍｇｒｉｄ的模板操作中，有许多中间结果可以被
复用，这些复用不但可以增加线程内局部性，同时
能减少访存次数。一般来说，线程粒度越大，线程
内的计算密集性也越大，可以发掘的数据局部性也
更多。在ＡＭＤ ＧＰＵ中，线程的数目和线程的粒
度呈反比关系，线程粒度的大小决定了线程数量的
多少，所以我们可以调节线程粒度来达到线程内局
部性和线程间并行性的最佳平衡。Ｂｒｏｏｋ＋中的
线程粒度是指一个线程可以计算模板操作网格点
的数目，调节线程粒度有如下两种方法：
（１）使用向量数据类型（Ｖｅｃｔｏｒ Ｔｙｐｅｓ）。
Ｂｒｏｏｋ＋语言提供的内置短向量由基本数据类型
加上它们的长度后缀构成，如“ｆｌｏａｔ４”和
“ｄｏｕｂｌｅ２”。使用向量数据类型可以将输出流的长
度缩小向量长度倍，从而以相同倍数增大线程粒
度。例如，使用ｄｏｕｂｌｅ２可以把线程粒度增大两
倍。和使用ｄｏｕｂｌｅ的线程相比，使用ｄｏｕｂｌｅ２的
线程可以在一个线程内同时计算两个点，从而两点
间计算的中间结果可以被复用。此外，使用向量数
据类型可以最多把４条标量访存指令打包到一条
向量访存指令中。如果Ｋｅｒｎｅｌ程序访问的地址是
连续的，向量访存指令可以显著减少访存次数。
把向量数据类型和多输出流结合使用，我们可以得
到更大的线程粒度。例如，把ｄｏｕｂｌｅ２和４条输出
流结合，线程的粒度就增大到了８倍。
需要注意的是，使用向量数据类型需要修改
Ｋｅｒｎｅｌ中的数据索引，而使用多输出流需要分输
入流。而且，两种方法都增加了线程所需的通用寄
存器数量，从而减少了可被创建的线程数量。这些
附加的开销是否可以被调节线程粒度所获得的加
速比抵消，取决于Ｋｅｒｎｅｌ的大小和特性。我们需
要通过实验来判定什么样的线程粒度是最好的。
４ 实验测评
为了验证我们提出的优化方法的有效性，我们
用Ｂｒｏｏｋ＋语言在ＡＭＤ Ｒａｄｅｏｎ ＨＤ４８７０ ＧＰＵ平
台上实现了Ｍｇｒｉｄ应用中的Ｒｐｒｊ３和］ｎｔｅｒｐ子函
数，并对其做了优化。所有的实验结果都和单线程
的ＣＰＵ版本相比较。使用的ＣＰＵ为Ｉｎｔｅｌ Ｘｅｏｎ
Ｅ５４Ｏ５ ＣＰＵ，主频２ＧＨｚ，带有２５６ＫＢ的一级缓存
和１２ＭＢ的二级缓存。我们使用Ｉｎｔｅｌ ｉｆｏｒｔ编译
器，优化选项为～Ｏ３。Ｍｇｒｉｄ是ＳＰＥＣ２０００和
ＮＡＳＣＡＲ ｂｅｎｃｈｍａｒｋ中的重要测试程序，常用来
求解偏微分方程。
图３是Ｍｇｒｉｄ程序的结构图，可以看出Ｍｇｒｉｄ
的主要计算过程呈Ｖ字型，计算在多层网格和多
次迭代上进行。Ｒｐｒｊ３和Ｉｎｔｅｒｐ是Ｍｇｒｉｄ中的重
要子程序，被多次调用。其中Ｒｐｒｊ３进行精细网格
（Ｆｉｎｅ Ｇｒｉｄ）到粗糙网格（Ｃｏａｒｓｅ Ｇｒｉｄ）的投影计
算；Ｉｎｔｅｒｐ的计算方向相反，它进行从粗糙网格到
精细网格的插值计算。
Ｆｉ ｔＣ ｄ
【一一
图３ Ｍｇｒｉｄ程序结构图
我们使用４种线程粒度，分别是ｄｏｕｂｌｅ，ｄｏｕｂ
４３
ｌｅ２，ｄｏｕｂｌｅ２和２条输出流，ｄｏｕｂｌｅ２和４条输出
流。假设使用ｄｏｕｂｌｅ的线程可以计算Ｎ个点，那
么使用ｄｏｕｂｌｅ２，ｄｏｕｂｌｅ２和２条输出流，ｄｏｕｂｌｅ２
和４条输出流的线程分别可以计算２Ｎ、４Ｎ和８Ｎ
个点。为叙述方便起见，我们用Ｎ、２Ｎ、４Ｎ和８Ｎ
来指代不同的线程粒度。
４．１对Ｒｐｒｊ３的优化效果
我们采用第３节提出的优化方法，对Ｒｐｒｊ３进
行移植和优化。从图４ａ可以看出，除了问题规模
为１６。时，４种线程粒度下加速比都小于１．０，其它
规模下程序的加速比都大于１．Ｏ。这是因为把计
算移植到ＧＰＵ上运行会引起数据通信开销和调
用开销，小规模的情况下，移植程序所得的收益不
足以抵消附带开销。所以，把程序移植到ＧＰＵ上
运行需要考虑问题的计算规模。
在问题规模为３２。时，加速比随着线程粒度的
增大而增大。说明此时线程粒度的增大更好地开
发了线程内数据局部性，同时又没有影响线程间的
并行性。在问题规模为６４。时，线程粒度的增加都
使得加速比得到了提高。特别是线程粒度为２Ｎ
时，加速比达到了最大值６．０１，说明此时线程内数
据局部性和线程问数据并行性达到了最佳平衡。
在最大问题规模１２８。时，加速比随着线程粒
度的增大反而减小。这是因为在较大的问题规模
下，线程数越多，越有利于开发并行性。而线程粒
度的增加虽然提高了线程内数据局部性，但是大大
减少了线程数量，最终使得加速比下降。在该规模
下，增加线程粒度并没有得到预期的优化效果，说
明本文提出的优化方法对不同的程序特征有不同
的适用性。
４・２对ｈ‘ｅｒｐ的优化效果
Ｉｎｔｅｒｐ在６４。、１２８。、２５６。三种规模下的加速
比都呈现相同的特征，如图４ｂ所示。即加速比首
先随着线程粒度的增大而增大，在线程粒度为４Ｎ
时达到最大值，随后虽然线程粒度进一步增大，加
速比反而减小。这是由于在不影响线程数量的情
况下，线程粒度的增大可以提高线程内的局部性，
所以在４Ｎ之前加速比随线程粒度增大而增大。
但是，当线程粒度大到影响线程的创建数目时，线
程粒度的增加反而不利于性能的提高。在最大规
模时，采用４Ｎ线程粒度比采用Ｎ线程粒度加速比
提高了２．１５×。这说明本文提出的通过调节线程
粒度、优化模板操作的策略是有效的。
我们最终的优化效果表现为在最大规模下，
４４
《一
ｌ６ ３２ ６４ １２８
Ｐｍｂｌｅｍ Ｓｉｚｅ＾Ｐ
ａ Ｒｐｒｊ３
１４
１２
ｌＯ
８
６
４
２
０
３２ ６４ １２８ ２５６
Ｐｍｂｌｅｍ Ｓｉｚｅ
ｂ Ｉｎｔｅｒｐ
图４ Ｒｐｒｊ３和Ｉｎｔｅｒｐ在不同规模不同线程粒度下的加速比
Ｒｒｐｒｊ３获得的相对于ＣＰＵ版本的加速比为５．３７
×。Ｉｎｔｅｒｐ获得的相对于ＣＰＵ版本的加速比为
１２．８×，相对于初始的ＧＰＵ版本的加速比为２．１５
×。Ｒｐｒｊ３计算的是投影，所以最大规模是１２８。；
Ｉｎｔｅｒｐ计算的是插值，所以最大规模是２５６。。
４．３ 线程粒度调节对程序移植的指导意义
本文采用手工的方法调节线程粒度，通过实验
分析发现了线程粒度对程序性能有至关重要的影
响。从上文的分析可以得出在移植模板操作中调
节线程粒度的一个基本原则，即在不影响线程间并
行的情况下，尽可能增大线程粒度，在取得最大并
行性的同时充分发掘线程内数据局部性。针对特
定程序的线程粒度取决于程序特征及ＧＰＵ体系
结构参数。在优化过程中，如何建立一个完整的线
程粒度选择模型是需要进一步研究的课题。
５ 相关工作
当前越来越多的研究人员开始用ＧＰＵ来优
化科学计算应用，他们都是使用Ｂｒｏｏｋ＋和ＣＵＤＡ
之类的通用编程语言。Ｒｙｏｏ等人提出了把计算有
效映射到图像硬件上的优化原则 ］，他们着眼于平
衡线程资源的使用和同时活跃线程的数目。Ｊａｎｇ
等人通过体系结构信息定义了优化Ｂｒｏｏｋ＋程序
的优化空间＿ｇｊ。Ｗａｎｇ等人使用ＣＵＤＡ在ＧＰＵ
上实现了完整的Ｍｇｒｉｄ程序，但他们实现的是单
精度浮点的版本口 。我们可以看出，ＧＰＵ可以有
效加速传统的计算密集的ＣＰＵ程序。本文选取
Ｍｇｒｉｄ作为优化对象是因为它含有大量的模板操
作，给程序员提供了很大的优化空间。在ＣＰＵ上
2024年5月27日发(作者：象雨文)
ＣＮ４３ １２５８／ＴＰ
ＩＳＳＮ １００７一ｌ３ＯＸ
计算机工程与科学
ＣＯＭＰＵＴＥＲ ＥＮＧＩＮＥＥＲＩＮＧ ８Ｌ ＳＣＩＥＮＣＥ
２０１１年第３３卷第３期
Ｖｏ１．３３，Ｎｏ．３。２０１１
文章编号：１００７—１３０Ｘ（２０１１）０３ ００４１—０５
模板操作在ＧＰＵ上的实现与优化
Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｎｄ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ
Ｓｔｅｎｃｉｌ Ａｐｐｌｉｃａｔｉｏｎｓ ｏｎ ＧＰＵｓ
方旭东，唐玉华，王桂彬，唐滔
ＦＡＮＧ Ｘｕ—ｄｏｎｇ，ＴＡＮＧ Ｙｕ—ｈｕａ，ＷＡＮＧ Ｇｕｉ—ｂｉｎ。ＴＡＮＧ Ｔａｏ
（国防科学技术大学计算机学院，湖南长沙４１００７３）
（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ ４１００７３，Ｃｈｉｎａ）
摘 要：随着ＧＰＵ的快速发展，使用ＧＰＵ来加速科学计算应用已成为必然趋势。本文抽取了
ＳＰＥＣ２０００中富含模板操作的Ｍｇｒｉｄ的两个典型子程序Ｒｐｒｊ３和Ｉｎｔｅｒｐ，使用Ｂｒｏｏｋ＋语言把它们移植到
ＡＭＤ ＧＰＵ上运行。采用Ｂｒｏｏｋ＋语言提供的线程调节机制，我们实现了不同线程粒度下的程序版本，并
分析了加速比不同的原因，总结了线程粒度调节对模板程序移植的指导意义。我们使用ＡＭＤ Ｒａｄｅｏｎ
ＨＤ４８７０ ＧＰＵ作为实验平台，对比Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５４０５ ＣＰＵ上的运行结果发现，在最大规模下，Ｒｐｒｊ３获得
的相对于ＣＰＵ版本的加速比为５．３７×，Ｉｎｔｅｒｐ获得的相对于ＣＰＵ版本的加速比为１２．８×。
Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｔｈｅ ｆａｓｔ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ＧＰＵｓ，ｕｓｉｎｇ ｔｈｅｍ ｔｏ ａｃｃｅｌｅｒａｔｅ ｓｃｉｅｎｔｉｆｉｃ ｃｏｍｐｕｔｉｎｇ ａｐｐｌｉｃａ—
ｔｉｏｎｓ ｉｓ ｂｅｃｏｍｉｎｇ ａｎ ｉｎｅｖｉｔａｂｌｅ ｔｒｅｎｄ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐｏｒｔ ｔｗｏ ｔｙｐｉｃａｌ ｓｕｂｒｏｕｔｉｎｅｓ Ｒｐｒｊ ３ ａｎｄ Ｉｎｔｅｒｐ
ｆｒｏｍ Ｍｇｒｉｄ ｗｈｉｃｈ ｃｏｎｔａｉｎｓ ｒｉｃｈ ｓｔｅｎｃｉｌ ｏｐｅｒａｔｉｏｎｓ ｉｎ ＳＰＥＣ２０００ ｔｏ ｒｕｎ ｏｎ ａｎ ＡＭＤ ＧＰＵ ｕｓｉｎｇ Ｂｒｏｏｋ＋．
Ｕｓｉｎｇ ａ ｔｈｒｅａｄ ｇｒａｎｕｌａｒｉｔｙ ｔｕｎｉｎｇ ｍｅｃｈａｎｉｓｍ ｐｒｏｖｉｄｅｄ ｂｙ Ｂｒｏｏｋ＋，ｗｅ ｉｍｐｌｅｍｅｎｔ ｄｉｆｆｅｒｅｎｔ ｐｏｒｔｅｄ ｐｒｏ—
ｇｒａｍ ｖｅｒｓｉｏｎｓ ａｎｄ ａｎａｌｙｚｅ ｔｈｅｉｒ ｐｅｒｆｏｒｍａｎｃｅｓ．Ｗｅ ａｌｓｏ ｃｏｎｃｌｕｄｅ ｈｏｗ ｔＯ ｕｔｉｌｉｚｅ ｔｈｒｅａｄ ｇｒａｎｕｌａｒｉｔｙ ｔｕｎｉｎｇ
ｔｏ ｏｐｔｉｍｉｚｅ ｓｔｅｎｃｉｌ ｐｒｏｇｒａｍ ｔｒａｎｓｐｌａｎｔａｔｉ０ｎ． Ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｕｎｄｅｒ ｔｈｅ ｌａｒｇｅｓｔ ｐｒｏｂ—
ｌｅｍ ｓｉｚｅ，Ｒｐｒｊ３ ｏｂｔａｉｎｓ ａ ｓｐｅｅｄｕｐ ｏｆ ５．３７ ｏｖｅｒ ｉｔｓ ＣＰＵ ｖｅｒｓｉｏｎ ｗｈｉｌｅ Ｉｎｔｅｒｐ ｇａｉｎｓ ａ ｓｐｅｅｄｕｐ ｏｆ １２．８ ｏｖｅｒ
ｉｔｓ ＣＰＵ ｖｅｒｓｉｏｎ．
关键词：ＧＰＵ；优化；模板
Ｋｅｙ ｗｏｒｄｓ：ＧＰＵ；ｏｐｔｉｍｉｚａｔｉｏｎ；ｓｔｅｎｃｉｌ
ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—１３０Ｘ．２０１１．０３．００８
中图分类号：ＴＰ３０３ 文献标识码：Ａ
解图形编程的细节，便可以着手在ＧＰＵ上编写通
引言
近年来，随着ＧＰＵ技术的发展，ＧＰＵ的浮点
处理能力变得越来越强大。新的ＧＰＵ体系结构
具有更好的可编程性和通用性，使编程人员无需了
用程序。这方面的语言有ＡＭＤ的Ｂｒｏｏｋ＋ｌ】 和
ＮＶＩＤＩＡ的ＣＵＤＡｌ２ｊ。ＧＰＵ的强大计算能力现已
被用于生物医学、计算流体动力学模拟和分子动力
学模拟等科学计算领域 。
现在的ＧＰＵ虽然具有很强的计算能力，但由
收稿日期：２００９—０７ ２６；修订日期：２００９ １０－２１
基金项目：国家自然科学基金资助项目（６０６２１００３）
通讯地址：４１００７３湖南省长沙市国防科学技术大学计算机学院
Ａｄｄｒｅｓｓ：Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ ４１００７３，Ｐ．Ｒ．Ｃｈｉｎａ
４１
于ＧＰＵ最初用于图形处理，偏重处理的实时性，
其编译器自动优化程序的能力较弱。这就给编程
人员手工优化ＧＰＵ程序提供了空间。本文从
Ｓｐｅｃ２０００测试程序中选取了用于解偏微分方程的
Ｍｇｒｉｄ应用，从中抽取了典型的函数Ｉｎｔｅｒｐ和
Ｒｐｒｊ３，将它们移植到ＡＭＤ ＧＰＵ平台上运行。Ｉｎ—
ｔｅｒｐ和Ｒｐｒｊ３中大量的模板（Ｓｔｅｎｃｉｌ）计算为优化
ＧＰＵ程序提供了很好的机会 。我们采用通过调
节线程问并行性、增加线程内局部性的方法优化初
始的ＧＰＵ代码。我们将ＡＭＤ Ｒａｄｅｏｎ ＨＤ４８７０
ＧＰＵ和Ｉｎｔｅｌ Ｘｅｏｎ Ｅ５４Ｏ５ ＣＰＵ上的测试结果进
行对比发现，在最大规模下，Ｒｐｒｊ３获得的相对于
ＣＰＵ版本的加速比为５．３７×，Ｉｎｔｅｒｐ获得的相对
于ＣＰＵ版本的加速比为ｌ２．８×。
２ 背景
本节介绍在ＡＭＤ ＧＰＵ上用Ｂｒｏｏｋ＋进行编
程的背景。
２．１异构平台介绍
使用ＧＰＵ和通用ＣＰＵ构建异构并行系统已
成为高性能计算领域的研究热点一ｓ］。ＧＰＵ强大的
浮点计算能力和超高的性能功耗比使得它们成为
非常好的ＣＰＵ计算加速部件。一个典型的ＣＰＵ—
口叩口叩口叩口叩口口叩叩口叩口叩＝【 一ｌ一一
ＧＰＵ异构系统如图１所示。ＣＰＵ和ＧＰＵ之间存
在数据通信开销和调用开销。数据通信开销是指
口叩口叩口叩口叩口口叩叩口叩口叩ｌｌ～一椰一
计算前数据从ＣＰＵ加载到ＧＰＵ的开销和计算后
口口口口口口口口＝叩叩叩叩叩叩叩叩一椰一～一
结果从ＧＰＵ加载到ＣＰＵ的开销。调用开销是指
从ＣＰＵ发出调用指令到指令到达ＧＰＵ命令处理
器的延迟。
ＰｒＴ Ｅ
１ ＣＰＵ ＧＰＵ异构系统
２．２微体系结构
本文中我们采用ＡＭＤ Ｒａｄｅｏｎ ＨＤ４８７０ ＧＰＵ
作为ＣＰＵ的加速器。ＡＭＤ ＨＤ４８００系列是
ＡＭＤ ＧＰＵ的最新产品，具有双精度浮点处理能
力，其使用的核心是ＲＶ７７０。如图２所示，在
ＲＶ７７０的数据并行阵列中拥有１Ｏ个ＳＩＭＤ引擎，
它们同时处理一个Ｋｅｒｎｅｌ程序；每个ＳＩＭＤ引擎
又由１６个线程处理器组成，这ｌ６个线程处理器共
用一个程序计数器，所以它们之间是完全同步执行
４２
的；线程处理器是一个超长指令字（ＶＩ ＩＷ）处理单
元，这个ＶＩ １ｗ包括４个标量计算核和１个超越
计算单元，一个线程处理器通过阻塞多线程的方式
同时运行４个线程。经过上述分析我们发现，
Ｒ７７０拥有８００（１０＊１６＊５）个计算核，可以提供巨
大的计算能力。表１概括了Ｒａｄｅｏｎ ＨＤ４８７０的详
细性能参数。
线程分配处理器
圆
线程处理单元ｌ ｌ指令流和控制流
图２ ＲＶ７７Ｏ微体系结构
表１ ＡＭＤｓ ＨＤ４８７０性能参数
参数 值 参数 值
Ｍ。 。 ｙ ＣＩ。ｃｋ ９９３ ＭＨ
ｚ
ｒｏｃｅｓｓｏｒｓ
８ＯＯ
Ｓｐｅｅｄ
Ｘｔ 。 ４ｏ Ｍ
ｅｍｏｒｙ Ｉｎｔｅｒｆａｃｅ ２５６ ｂｉｔｓ
Ｕｎｉｔｓ
Ｃｏｒｅ Ｃｌｏｃｋ ７５０ Ｍ 。 ｙ Ｂ “ｄ １ ｌ５ ＧＢ／
Ｓｐｅｅｄ ＭＨｚ ｗｉｄｔｈ ｓ
Ｍｅｒｅ。 ｙ ＧＤＤＲ５ Ｓｉｎｇｌｅ（ｄｏｕｂｌｅ） １．２ Ｔ（２４０Ｇ）
ｌ ｙｐｅ Ｐｅａｋ ｆｌｏｐｓ
在ＡＭＤ流编程模型中，流（Ｓｔｒｅａｍｓ）指可以
被并行操作的相同类型的数据集合，核（Ｋｅｒｎｅ１）是
指可以在每个输出流元素上进行操作的并行函数。
线程（Ｔｈｒｅａｄ）是指线程处理器上核的一次执行实
例。线程被映射到流处理器上执行，并以波阵面
（Ｗａｖｅｆｒｏｎｔ）为单位调度。波阵面是指在ＳＩＭＤ引
擎上被同时执行和调度的一组线程。ＧＰＵ硬件调
度通用寄存器（ＧＰＲｓ）、存储带宽等资源，直至所有
线程处理完毕。多个波阵面交织运行以隐藏访问
延迟。不同的ＳＩＭＤ引擎可以执行不同的指令，另
外流水线技术也被ＧＰＵ硬件采用以获得性能提
升 。
２．３ Ｂｒｏｏｋ＋流编程环境
ＡＭＤ提供了完整的ＧＰＵ编程环境，使得编
程人员可以方便快速地着手进行ＧＰＵ上的程序
开发。程序员可以在两级抽象层次上编程，高层使
用Ｂｒｏｏｋ＋，底层使用ＣＡＩ （Ｃｏｍｐｕｔｅ Ａｂｓｔｒａｃｔｉｏｎ
Ｌａｙｅｒ，简称ＣＡＩ ）。Ｂｒｏｏｋ＋基于ＢｒｏｏｋＧＰＵＬ ，
（２）使用多输出流（Ｍｕｌｔｉｐｌｅ Ｏｕｔｐｕｔ
Ｓｔｒｅａｍｓ）。Ｂｒｏｏｋ＋语言最多支持８条输出流ｌ】］。
和使用单条输出流相比，使用多输出流后线程可以
执行更多的计算，同样增大了线程粒度。例如，使
用两条输出流可以把线程粒度增大一倍。而如果
是对Ｃ语言的扩展，支持显式的计算和数据并行。
Ｂｒｏｏｋ＋作为一种高层的编程语言，屏蔽了体系结
构细节，保留了和现代图形硬件相关的特征。
ＣＡＬ作为一种设备驱动库，提供向前兼容的接口，
可以直接和流处理器交互，所以ＣＡＬ提供了更多
的优化机会。我们只在Ｂｒｏｏｋ＋一级进行了移植
和优化。
３ 优化策略
ＧＰＵ更适合于处理计算密集型应用而非访存
密集型应用¨７］。为了充分发挥ＧＰＵ的计算优势，
应该有足够多的线程来占用ＧＰＵ提供的大量的
线程处理器。线程之间以波阵面为粒度调度，可以
有效隐藏访存延迟。另一方面，线程局部性
（Ｔｈｒｅａｄ Ｌｏｃａｌｉｔｙ）对于发掘计算中的数据复用、提
高程序性能也有很重要的作用。Ｍｇｒｉｄ中包含大
量的模板操作。所谓模板操作，是指在计算每个点
时都需要访问这个点的相邻点。所以，模板操作提
供了丰富的时间局部性和空间局部性优化的机会。
在Ｍｇｒｉｄ的模板操作中，有许多中间结果可以被
复用，这些复用不但可以增加线程内局部性，同时
能减少访存次数。一般来说，线程粒度越大，线程
内的计算密集性也越大，可以发掘的数据局部性也
更多。在ＡＭＤ ＧＰＵ中，线程的数目和线程的粒
度呈反比关系，线程粒度的大小决定了线程数量的
多少，所以我们可以调节线程粒度来达到线程内局
部性和线程间并行性的最佳平衡。Ｂｒｏｏｋ＋中的
线程粒度是指一个线程可以计算模板操作网格点
的数目，调节线程粒度有如下两种方法：
（１）使用向量数据类型（Ｖｅｃｔｏｒ Ｔｙｐｅｓ）。
Ｂｒｏｏｋ＋语言提供的内置短向量由基本数据类型
加上它们的长度后缀构成，如“ｆｌｏａｔ４”和
“ｄｏｕｂｌｅ２”。使用向量数据类型可以将输出流的长
度缩小向量长度倍，从而以相同倍数增大线程粒
度。例如，使用ｄｏｕｂｌｅ２可以把线程粒度增大两
倍。和使用ｄｏｕｂｌｅ的线程相比，使用ｄｏｕｂｌｅ２的
线程可以在一个线程内同时计算两个点，从而两点
间计算的中间结果可以被复用。此外，使用向量数
据类型可以最多把４条标量访存指令打包到一条
向量访存指令中。如果Ｋｅｒｎｅｌ程序访问的地址是
连续的，向量访存指令可以显著减少访存次数。
把向量数据类型和多输出流结合使用，我们可以得
到更大的线程粒度。例如，把ｄｏｕｂｌｅ２和４条输出
流结合，线程的粒度就增大到了８倍。
需要注意的是，使用向量数据类型需要修改
Ｋｅｒｎｅｌ中的数据索引，而使用多输出流需要分输
入流。而且，两种方法都增加了线程所需的通用寄
存器数量，从而减少了可被创建的线程数量。这些
附加的开销是否可以被调节线程粒度所获得的加
速比抵消，取决于Ｋｅｒｎｅｌ的大小和特性。我们需
要通过实验来判定什么样的线程粒度是最好的。
４ 实验测评
为了验证我们提出的优化方法的有效性，我们
用Ｂｒｏｏｋ＋语言在ＡＭＤ Ｒａｄｅｏｎ ＨＤ４８７０ ＧＰＵ平
台上实现了Ｍｇｒｉｄ应用中的Ｒｐｒｊ３和］ｎｔｅｒｐ子函
数，并对其做了优化。所有的实验结果都和单线程
的ＣＰＵ版本相比较。使用的ＣＰＵ为Ｉｎｔｅｌ Ｘｅｏｎ
Ｅ５４Ｏ５ ＣＰＵ，主频２ＧＨｚ，带有２５６ＫＢ的一级缓存
和１２ＭＢ的二级缓存。我们使用Ｉｎｔｅｌ ｉｆｏｒｔ编译
器，优化选项为～Ｏ３。Ｍｇｒｉｄ是ＳＰＥＣ２０００和
ＮＡＳＣＡＲ ｂｅｎｃｈｍａｒｋ中的重要测试程序，常用来
求解偏微分方程。
图３是Ｍｇｒｉｄ程序的结构图，可以看出Ｍｇｒｉｄ
的主要计算过程呈Ｖ字型，计算在多层网格和多
次迭代上进行。Ｒｐｒｊ３和Ｉｎｔｅｒｐ是Ｍｇｒｉｄ中的重
要子程序，被多次调用。其中Ｒｐｒｊ３进行精细网格
（Ｆｉｎｅ Ｇｒｉｄ）到粗糙网格（Ｃｏａｒｓｅ Ｇｒｉｄ）的投影计
算；Ｉｎｔｅｒｐ的计算方向相反，它进行从粗糙网格到
精细网格的插值计算。
Ｆｉ ｔＣ ｄ
【一一
图３ Ｍｇｒｉｄ程序结构图
我们使用４种线程粒度，分别是ｄｏｕｂｌｅ，ｄｏｕｂ
４３
ｌｅ２，ｄｏｕｂｌｅ２和２条输出流，ｄｏｕｂｌｅ２和４条输出
流。假设使用ｄｏｕｂｌｅ的线程可以计算Ｎ个点，那
么使用ｄｏｕｂｌｅ２，ｄｏｕｂｌｅ２和２条输出流，ｄｏｕｂｌｅ２
和４条输出流的线程分别可以计算２Ｎ、４Ｎ和８Ｎ
个点。为叙述方便起见，我们用Ｎ、２Ｎ、４Ｎ和８Ｎ
来指代不同的线程粒度。
４．１对Ｒｐｒｊ３的优化效果
我们采用第３节提出的优化方法，对Ｒｐｒｊ３进
行移植和优化。从图４ａ可以看出，除了问题规模
为１６。时，４种线程粒度下加速比都小于１．０，其它
规模下程序的加速比都大于１．Ｏ。这是因为把计
算移植到ＧＰＵ上运行会引起数据通信开销和调
用开销，小规模的情况下，移植程序所得的收益不
足以抵消附带开销。所以，把程序移植到ＧＰＵ上
运行需要考虑问题的计算规模。
在问题规模为３２。时，加速比随着线程粒度的
增大而增大。说明此时线程粒度的增大更好地开
发了线程内数据局部性，同时又没有影响线程间的
并行性。在问题规模为６４。时，线程粒度的增加都
使得加速比得到了提高。特别是线程粒度为２Ｎ
时，加速比达到了最大值６．０１，说明此时线程内数
据局部性和线程问数据并行性达到了最佳平衡。
在最大问题规模１２８。时，加速比随着线程粒
度的增大反而减小。这是因为在较大的问题规模
下，线程数越多，越有利于开发并行性。而线程粒
度的增加虽然提高了线程内数据局部性，但是大大
减少了线程数量，最终使得加速比下降。在该规模
下，增加线程粒度并没有得到预期的优化效果，说
明本文提出的优化方法对不同的程序特征有不同
的适用性。
４・２对ｈ‘ｅｒｐ的优化效果
Ｉｎｔｅｒｐ在６４。、１２８。、２５６。三种规模下的加速
比都呈现相同的特征，如图４ｂ所示。即加速比首
先随着线程粒度的增大而增大，在线程粒度为４Ｎ
时达到最大值，随后虽然线程粒度进一步增大，加
速比反而减小。这是由于在不影响线程数量的情
况下，线程粒度的增大可以提高线程内的局部性，
所以在４Ｎ之前加速比随线程粒度增大而增大。
但是，当线程粒度大到影响线程的创建数目时，线
程粒度的增加反而不利于性能的提高。在最大规
模时，采用４Ｎ线程粒度比采用Ｎ线程粒度加速比
提高了２．１５×。这说明本文提出的通过调节线程
粒度、优化模板操作的策略是有效的。
我们最终的优化效果表现为在最大规模下，
４４
《一
ｌ６ ３２ ６４ １２８
Ｐｍｂｌｅｍ Ｓｉｚｅ＾Ｐ
ａ Ｒｐｒｊ３
１４
１２
ｌＯ
８
６
４
２
０
３２ ６４ １２８ ２５６
Ｐｍｂｌｅｍ Ｓｉｚｅ
ｂ Ｉｎｔｅｒｐ
图４ Ｒｐｒｊ３和Ｉｎｔｅｒｐ在不同规模不同线程粒度下的加速比
Ｒｒｐｒｊ３获得的相对于ＣＰＵ版本的加速比为５．３７
×。Ｉｎｔｅｒｐ获得的相对于ＣＰＵ版本的加速比为
１２．８×，相对于初始的ＧＰＵ版本的加速比为２．１５
×。Ｒｐｒｊ３计算的是投影，所以最大规模是１２８。；
Ｉｎｔｅｒｐ计算的是插值，所以最大规模是２５６。。
４．３ 线程粒度调节对程序移植的指导意义
本文采用手工的方法调节线程粒度，通过实验
分析发现了线程粒度对程序性能有至关重要的影
响。从上文的分析可以得出在移植模板操作中调
节线程粒度的一个基本原则，即在不影响线程间并
行的情况下，尽可能增大线程粒度，在取得最大并
行性的同时充分发掘线程内数据局部性。针对特
定程序的线程粒度取决于程序特征及ＧＰＵ体系
结构参数。在优化过程中，如何建立一个完整的线
程粒度选择模型是需要进一步研究的课题。
５ 相关工作
当前越来越多的研究人员开始用ＧＰＵ来优
化科学计算应用，他们都是使用Ｂｒｏｏｋ＋和ＣＵＤＡ
之类的通用编程语言。Ｒｙｏｏ等人提出了把计算有
效映射到图像硬件上的优化原则 ］，他们着眼于平
衡线程资源的使用和同时活跃线程的数目。Ｊａｎｇ
等人通过体系结构信息定义了优化Ｂｒｏｏｋ＋程序
的优化空间＿ｇｊ。Ｗａｎｇ等人使用ＣＵＤＡ在ＧＰＵ
上实现了完整的Ｍｇｒｉｄ程序，但他们实现的是单
精度浮点的版本口 。我们可以看出，ＧＰＵ可以有
效加速传统的计算密集的ＣＰＵ程序。本文选取
Ｍｇｒｉｄ作为优化对象是因为它含有大量的模板操
作，给程序员提供了很大的优化空间。在ＣＰＵ上