图形硬件加速反向传播学习神经网络的计算性能

理论计算机科学电子笔记225（2009）379-389www.elsevier.com/locate/entcs在图形硬件上评估反向传播学习的计算性能1泷泽博之2 千田达也3东北大学大学院情报学研究科日本仙台小林宏明4东北大学日本仙台摘要虽然志愿者计算与数量庞大的高性能游戏机连接到互联网是有希望实现大规模的数据挖掘，这种游戏机的编程模型数据挖掘任务是受限制的。由于游戏机具有用于最先进的视频游戏的高性能图形硬件，因此如何有效地利用其计算能力进行数据挖掘是一个关键数据挖掘被映射到硬件作为图形处理。因此，在本文中，一个流行的数据挖掘工具，称为反向传播学习神经网络实现为图形硬件上运行的应用程序。由于最近的图形硬件具有许多矢量处理单元和高存储器带宽，因此有希望加速涉及大量数据并行计算的反向传播学习任务。评估结果表明，我们的原型实现大规模反向传播学习任务的巨大潜力。图形硬件可以有效地工作，特别是如果任务被实现为使用硬件支持的数据并行指令。关键词：反向传播学习神经网络，可编程图形处理单元，通用计算图形硬件。1本研究部分得到了优先领域科学研究补助金#18049003，青年科学家（B）#19700020和战略信息和通信研发项目的支持。运动方案（SCOPE-S）#061102002。2电子邮件：tacky@isc.tohoku.ac.jp3电子邮件：tatsuya@sc.isc.tohoku.ac.jp4电子邮件：koba@isc.tohoku.ac.jp1571-0661/© 2008 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2008.12.087380H. Takizawa等人/理论计算机科学电子笔记225（2009）3791介绍今天，每天都在产生和积累大量的数据。因此，从海量数据中手动检索有价值的信息和有用的知识是非常困难的。由于社会需求的需要，在数据库中进行知识发现的计算机技术，即所谓的数据挖掘[4]，正受到越来越多的关注。 虽然数据挖掘很有帮助为了限制我们的信息搜索范围，数据挖掘系统必须处理大量的数据在一个实际的时间。随着数据库的快速增长，我们需要越来越多的计算能力来进行未来的数据挖掘。SETI@home项目[1]已经证明了volunteer计算的巨大潜力，它使用互联网上的空闲计算资源来实现一个大型数据挖掘系统。此外，最新的游戏机具有出色的计算能力。因此，在不久的将来，大量的闲置游戏机将无处不在地存在于互联网上。志愿者计算有效地利用这些闲置的游戏机，有望实现规模空前的数据挖掘任务。考虑到最近的视频游戏的要求，游戏机必须配备高性能的图形硬件，即所谓的图形处理单元（GPU）。然而，由于特定于应用程序的架构，为GPU编程非图形应用程序可能会受到限制。因此，一个可靠的方法来利用他们的高性能的数据挖掘项目是有效地映射数据挖掘计算的图形过程。在本文中，反向传播神经网络的学习任务[11]，这是最流行的数据挖掘工具之一[2]，被实现为在GPU上运行的应用程序。由于反向传播学习算法涉及大量数据并行性，GPU有望加速学习任务。因此，作为建立这种有效实现方案的第一步，本文展示了GPU实现大规模反向传播学习任务的巨大潜力。本文的提纲如下。第2节和第3节分别简要介绍了反向传播学习算法和GPU。然后，我们提出了一种使用GPU的反向传播学习任务的实现方案。第4节展示了我们的实验结果，以评估GPU实现的性能。最后，第五部分给出了结论和我们未来的工作。2反向传播学习人工神经网络是数据挖掘的基本工具[2]。它们的学习算法大致可以分为监督学习和无监督学习算法;监督学习假设给定一组理想的输入-输出向量映射，即训练数据集，而无监督学习则没有。下面讨论的反向传播算法是用于多层前馈神经网络的典型监督学习算法[11]。H. Takizawa等人/理论计算机科学电子笔记225（2009）379381--Σ−·ΣXiOJyk输出层（M/O神经元）输入层（MI神经元）隐藏层（MH神经元）Fig. 1.多层前馈神经网络。多层神经网络由一些人工神经元层组成，这些层通过加权链接连接。假设一个3层神经网络由一个输入层、一个隐藏层和一个输出层组成。 设MI、MH和MO分别是输入层、隐藏层和输出层图1展示了这样一个神经网络。训练数据集X={x1，x2，.，xN}表示为x1= x11，x21，.，xM11。输入向量的每个分量xil被给予输入神经元，并经由加权链路传播到隐藏神经元。隐藏神经元的输出值ojl由下式计算：MIojl=f（wijxil），（1）i=0其中，是连接第i个输入神经元和第j个隐藏神经元的链路的权重，并且f（）是非线性传递函数，例如，S形函数f（x）= 1/（1+exp（x））。这里，x0l和o0l总是等于1，因此w0j表示第j个隐藏神经元的阈值隐藏神经元的输出值再次传播到输出神经元以计算神经网络的输出MHykl=f（wjkojl），（2）j=0其中ykl是第k个输出神经元的输出值，MH是隐藏神经元的数量，并且wjk是连接第j个隐藏神经元的链路的权重，并且第k个输出神经元。以这种方式，输入信号在前向方向上传播通过神经网络以计算M个0维输出向量。反向传播学习算法是一种迭代梯度下降算法，用于优化链接权重，以最小化382H. Takizawa等人/理论计算机科学电子笔记225（2009）379N2ΣLLl=1当前实际输出和理想输出：E（W）= 1|y（W）− t|第二条第（三）项其中N是数据集中训练数据的数量，yi和ti分别是第i个训练数据的实际和理想输出向量。反向传播学习算法通过下式调整链路权重W：W：=W−·E（W）N=W−n·（yl（W）−tl）nyl（W），l=1（四）其中，k是学习率，它指定了权重值在 一次迭代。因此，反向传播学习算法由三个阶段组成：输入信号的前向传播，误差的反向传播和权重更新。通过正向传播输入信号，反向传播学习算法首先计算训练数据集中每个输入向量的输出。然后，它累积每个输入向量的权重修改。 计算非直连链路的权重修改对于输出层中的任何神经元，输出神经元处的误差在从输出层到输入层的反向方向上传播。最后，根据等式（4）更新3图形处理单元GPU具有许多并行处理元件和高速专用存储器，以高效地执行计算机图形应用中通常涉及的细粒度数据并行任务[9]。这促使许多研究人员甚至将GPU的计算能力用于非图形应用程序。使用GPU进行非图形计算被称为GPU上的通用计算（GPGPU）[10]。 然而，GPU由于其特定于应用程序的架构而无法普遍工作。因此，如何有效地将非图形应用程序映射到GPU现代GPU在图形管道上有两种可编程处理器，顶点着色器和片段着色器来渲染图像。这些处理器具有类似于Intel CPU的SIMD流扩展（SSE）的SIMD5 位寄存器图2显示了GPU的可编程部分及其典型的数据流。一个三维物体由一组多边形表示，顶点着色器首先将多边形的每个顶点投影到视图上。SIMD是Single Instruction，Multiple Data的缩写H. Takizawa等人/理论计算机科学电子笔记225（2009）379383图二. 可编程图形处理单元。坐标系然后，将投影的多边形分解成片段，每个片段对应于屏幕上的一个像素。随后，片段着色器执行每片段操作以确定每个片段的颜色和深度最后，将合成操作应用于片段着色器的输出，以确定屏幕上的最终像素颜色以上述方式渲染一次多边形称为渲染过程。由于GPU最初设计用于快速确定屏幕上的像素颜色，因此其架构非常适合于大型数据阵列中独立分量的SIMD并行计算GPU上的非图形应用程序通常利用片段着色器的可编程性。片段着色器可以并行操作多个片段的颜色。片段着色器还可以从视频存储器上的纹理图像获取数据;纹理图像可以用作片段着色器上计算的源操作数此外，片段着色器的SIMD指令可用于同时操作四个颜色通道：红色、绿色、蓝色和阿尔法（RGBA）通道6。因此，我们可以将片段着色器视为多粒度SIMD并行处理器，它可以并行计算多个片段颜色，并且还可以使用细粒度SIMD并行指令进行计算。因此，片段着色器可以高效地执行逐分量矩阵操作，其以SIMD并行方式独立地确定每个矩阵分量，诸如两个巨大矩阵的相加如果四个数组元素被打包到一个纹素7中，则片段着色器可以使用SIMD指令来同时操作四个值，并且因此更有效地执行分量矩阵操作将四个值打包成6 alpha值表示像素的不透明度7纹素是纹理图像的最小分量384H. Takizawa等人/理论计算机科学电子笔记225（2009）379i=0×一个纹素被称为数据打包[8]。数据打包对于片段着色器的多粒度并行处理是必要的。由于数据打包可以将碎片或渲染通道的数量减少到四分之一，因此它可以显著加速许多GPGPU应用程序。4GPU上的反向传播学习本文提出了一种高效的GPU上的反向传播学习映射方案。多层神经网络需要累积每个神经元的所有输入，如等式（1）和（2）所示;对于前向传播，来自前一层的信号和它们相应的权重值相乘，然后像矩阵乘法[3]那样累加。由于乘法是并行执行的，GPU可以加速向前传播。类似地，误差的反向传播也可以通过同时执行输出神经元处的误差与其对应的权重值的乘法来加速。此外，由于每对两层之间的链路的权重修改可以并行计算，因此权重更新也涉及大量数据并行计算。 然而，GPU很难累积这些值因为在单遍中可执行的指令的数量是有限的。 因此，在我们的实现方案中， 在反向传播学习算法被组合成更少的矩阵-矩阵分量操作，并且多遍渲染方法用于矩阵-矩阵加法以实现累加。为了计算N个输入向量从输入神经元到隐藏神经元的信号传播，每个渲染通道计算从一个输入神经元到MH个隐藏神经元的所有N个因此，对应于第i个输入神经元的单个渲染遍次执行NXMH次乘法：wi1 xi1，wi1 xi2，wi1 xi3，...，wi1 ×1N，wi2 xi1，wi2 xi2，wi2 xi3，...，w为2×1N，..........................................wiMHxi1，wiMHxi2，wiMHxi3，.，wiNHxiN。（五）包括隐藏神经元阈值的计算，因此，（MI+1）次渲染通过需要对每个隐藏神经元的所有输入求和，然后，NMH个输出值是从另一个渲染通道，如等式（1）所述。就像隐藏的对于输出神经元，在总共（MH+ 2）个渲染遍次中计算输出神经元的输出值。因此，N个输入向量通过神经网络的前向传播在（MI+MH+4）个渲染通道中完成输入向量的数量N决定了渲染过程中使用的纹理图像的大小，但并不影响正向传播所需的渲染过程的数量。H. Takizawa等人/理论计算机科学电子笔记225（2009）379385×−Σ更新隐藏层和输出层之间的所有权重需要N个渲染遍次以实现等式（4）中的累积。因此，单个渲染通道执行MO（MH+1）个并行任务来计算与一个训练数据相关的权重修改：.........................................Δ wMH1，Δ wMH2，Δ wMH3，.，ΔwNHMO，（六）哪里Δwjk =−（ykl-tkl）Kl.（七）J.K.如果使用S形函数f（x）= 1/（1+exp（x））作为传递函数，则等式（7）中的偏导数由下式计算：kl=y （1−y）O。（八）金莎娱乐城KL JL然后，进行误差的反向传播以更新输入层和隐藏层之间的所有权重，因为计算训练数据l的这些修改需要输出神经元的误差之和MOΔ wij=− ojl（1 − ojl）xilwjk（ykl− tkl）ykl（1 − ykl）。（九）k=1由于一个输出神经元处的误差到所有隐藏神经元的反向传播与正向传播一样在单个渲染通道中执行，因此反向传播总共需要M ~0个渲染通道。更新输入层和隐藏 层 之 间 的 所 有 权 重 也 需 要 N 个 渲 染 通 道 。 因 此 ， GPU 可 在 总 共（MI+MH+MO+2N+ 4）个渲染遍次中执行反向传播学习算法的一个学习步骤。数据打包将四个信号存储到一个纹素中[3]。在我们的原型实现中，这种包装是用来减少每个矩阵的大小（片段的数量）在向前和向后传播阶段的四分之一，包装也允许每个片段程序通过采样纹理一次来获取四个矩阵分量。此外，由于权重更新阶 段 的 渲 染 通 道 数 减 少 到 四 分 之 一 ， 因 此 可 以 将 渲 染 通 道 数 减 少 到（MI+MH+MO+N/2+因此，打包对于提高GPU实现的计算性能是非常有效的Δw01，Δw02，Δw03，...，Δw0MO，Δw11Δw12Δw13...，Δw1MO，386H. Takizawa等人/理论计算机科学电子笔记225（2009）3795绩效评价本节评估在GPU上运行的反向传播学习算法的原型实现。对于性能评估，我们实现了一个3层神经网络。程序代码是用C++和OpenGL [12]编写的，带有NVIDIA的扩展，并由Microsoft Visual Studio 2003编译器编译。 它的所有着色器程序都是用高级编程语言编写的，称为Cfor Graphics[5]。首先，使用AMD Athlon64 3500+和NVIDIA GeForce 7800 GTX评估数据打包带来的性能提升，最新的游戏机在MI= 2，MH= 64，MO= 1，N= 1024的情况下，GeForce 7800GTX只需要0。008秒来执行GPU实现的一个学习步骤，而它需要0. 026秒不打包。此外，具有打包的GPU实现可以执行比没有打包的GPU实现更大的学习任务。这是因为最大纹理大小是有限的，并且打包可以将前向和后向传播阶段中使用的所需纹理大小减少到四分之一。图3显示了每个学习步骤的执行时间，测量改变MH和固定其他。对于少数神经元的小型网络，传统的CPU实现优于我们的GPU实现，因为在GPU上启动处理有一定的开销。 然而，GPU实现的计算性能随着隐藏神经元数量的增加而提高，因为对于较大的网络，开销变得相对较小。因此，对于许多神经元的大型神经网络，GPU实现优于CPU实现。这些结果表明，GPU实现非常适合于高维数据挖掘，例如高分辨率图像数据挖掘，这至少需要在输入层中的许多神经元一般来说，具有打包的GPU实现优于没有打包的GPU实现。然而，它们的差异随着网络大小的增加而变小，因为通过减少渲染通道数量而获得的性能增益相对于总执行时间变得很小。随着隐藏神经元数量的增加，网络大小成为渲染通道数量的主导因素。虽然打包可以减少前向和后向传播阶段中使用的纹理大小，但它不能减少这些阶段中所需的渲染通道。效率，即有效性能与峰值性能的比率，通常随着纹理大小的减小而降低，即使总执行时间随着纹理大小而减小。因此，这些实验结果清楚地表明，渲染通道数量的减少可以比纹理大小的减少更显著地加速GPU实现。为了提高效率，应尽可能采用数据打包，以减少绘制通道数而不是纹理尺寸图4示出了改变N和MH测量的每个学习步骤的执行时间。 如图所示，GPU实现的优越性， 随着N的增加，堆积变得显著数量的减少H. Takizawa等人/理论计算机科学电子笔记225（2009）379387Athlon64 3500+GF7800GTX w/ packingGF7800GTX w/o packingAthlon64 3500+GF7800GTX w/ packingGF7800GTX w/o packing每个学习步骤的每个学习步骤的100十比一10-210-34 8 1632641282565121024隐藏单位图三. 每个学习步骤的执行时间改变网络大小。101 101100 10010-110-110-210-210-310-310-410-410-510-510-6222324252627282921021121221321410-62223242526272829210211212213214数据的数目(a) MH= 4数据的数目(b) 男/女=64101 101100 10010-110-110-210-210-310-310-410-410-510-510-6222324252627282921021121221321410-62223242526272829210211212213214数据的数目(c) MH= 256数据的数目(d)MH= 1024图四、每个学习步骤的执行时间增加数据的数量通过打包获得的渲染通道是3N/ 2，并且仅取决于N。此外，在前向传播阶段中使用的纹理图像的大小随着N的增加而变大，并且效率因此而提高对于具有许多数据和/或许多神经元的更大的学习任务，我们的原型类型GPU实现可以优于传统的CPU实现。因此，我们得出结论，GPU实现是一种很有前途的方法，Athlon64 3500+GF7800GTX w/packingGF7800GTX w/o packingAthlon64 3500+GF7800GTX w/ packingGF7800GTX w/o packingAthlon64 3500+GF7800GTX w/ packingGF7800GTX w/o packing每个学习步骤的每个学习步骤的每个学习步骤的388H. Takizawa等人/理论计算机科学电子笔记225（2009）379高效率的志愿者计算与许多游戏控制台的大量数据挖掘任务。有人可能会说，我们的GPU实现应该更快，因为GeForce 7800 GTX在单精度浮点运算中的理论峰值性能要比Athlon64 3500+好得多。事实上，我们的GPU实现仍然是不够的，鉴于GPU的峰值性能。 这主要是由于内存带宽不足，如[3]中所述。一个更复杂的实现方案，考虑到GPU内存层次结构[7]，将需要克服这个不一致性问题。6总结发言我们的项目的目标是实现一个大规模的数据挖掘系统的志愿者计算的游戏机与高性能的GPU。作为第一步，本文讨论了一种流行的数据挖掘工具，反向传播学习神经网络的GPU实现。然后，我们的原型实现已经清楚地证明了GPU实现的高性能，特别是 进行大规模的学习任务。我们的GPU实现的优越性在很大程度上取决于数据大小和参数配置。我们需要估计GPU实现对于给定任务的性能，并且只有在GPU比CPU更好的情况下才应该使用GPU。一个有前途的替代方案是CPU和GPU的互补使用，并仔细考虑它们之间的负载平衡[6]。另一个重要的研究问题是如何在GPU的数据量限制下高效地实现数据挖掘算法。视频存储器通常小于主存储器，并且最大纹理大小也受到限制。 因此， 必须使用这种有限的存储器空间来执行其数据大小超过限制的任务。 这些问题将在我们未来的工作。引用[1] Anderson，D.例如，SETI@home：An experiment in public resource computing，Communications ofthe ACM45（2002），pp. 56比61[2] 贝里，M。和G. Lino，一九九七年。[3] Fatahalian，K.，J. Sugerman和P. Hanrahan，了解GPU算法对矩阵-矩阵乘法的效率，图形硬件2004（2004），pp. 133-138[4] 法耶兹，美国M.，G. Piatetsky-Shapiro和P. Smyth，从数据挖掘到数据库中的知识发现，AI杂志17（1996），pp.37比54[5] 费尔南多河和M. J. Kilgard，[6] Gierlinger，T.和P. Prabhu，Towards load balanced computations using GPU and CPU，2004 ACMworkshop on general-purpose computing on graphics processors（GP2）（2004），pp.C-14[7] Govindaraju，N.，S. Larsen，J. Gray and D. Manocha，图形处理器，2006年ACM/IEEE超级计算会议（SC 06），2006年。H. Takizawa等人/理论计算机科学电子笔记225（2009）379389[8] Hall，J.，N. Carr和J. Hart，GPU上的高速缓存和带宽感知矩阵乘法，Uiuc技术报告，UIUCDCS-R-2003-2328（2003）。[9] Kilgari、E.和R. Fernando，The GeForce 6 series GPU architecture，in：GPU Gems 2：Programmingtechniques for high-performance graphics and general-purpose computation，Addison-Wesley，2005pp. 471-491.[10] 欧文斯，J. D.例如，图形硬件上的通用计算的调查，Eurographics 2005，最新技术报告（2005），pp。21比51[11] Rumelhart ， D. E 、 G. E. Hinton 和 R. J. Williams ， Learning representations by back-propagatingerrors，Nature323（1986），pp.533-536[12] 喔，M.，J. Neider，T. Davis和D. Shreiner，