应用编译技术优化核外计算程序

开篇：润墨网以专业的文秘视角，为您筛选了一篇应用编译技术优化核外计算程序范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：阐述了一种适用于核外计算程序的变换技术，它通过联合使用循环变换和数据变换这两种编译优化技术来增强程序的局部性，提高数据存取效率。该方法不仅能优化单独一个嵌套循环，还能同时处理多个嵌套循环。实验结果表明了该方法能显著提高核外计算的性能。

关键词：循环变换；数据变换；局部性；核外计算

中图分类号： TP311.5

文献标识码：A

0引言

越来越多的工程涉及到处理大量数据的问题，比如大规模网络病毒防范的数据库系统、信息检索、超文本和多媒体系统以及地震数据处理等等。在这些程序中，一次用到的数据量可能是1GB到4000GB之多，即海量数据。内存无法同时容纳如此多的数据，待处理的数据只能存放在硬盘上，并通过某种策略实现内外存数据的交换。由于数据没有全部存放在内存中，我们称这样一种大规模数据计算为核外计算[1]。核外计算要处理的数据量可能超出内存容量，所以数据应该被划分为若干个块，当用到某个数据块时，将其从硬盘读到内存中，然后程序处理该数据块。当该数据块被处理完毕后，它将被重新存入硬盘。所以核外计算的速度很大程度上取决于数据在内外存之间的交换速度也即数据输入/输出速度。在研究这种应用程序时，我们考虑的重点应该放在“内存―硬盘”这一层次，而不是“cache―内存”这一层。为了提高效率，被读入内存的数据块应该尽量被重用。这要求我们必须增强程序的局部性，因为当一个程序具有好的局部性时，它的存取指令大多数数据访问的位置是相同的或者是很接近于刚执行过的存取指令的数据访问位置。

目前很多对核外计算的优化技术都是基于计算过程的重排序，而不考虑重新组织数据（驻留在硬盘上的核外数组）的存储布局。本文阐述了一种综合变换方法，它联合运用循环变换（或称为迭代空间变换）和数据变换（或称为文件布局变换）这两种编译优化技术来获得良好的程序局部性。本文采用的循环变换和数据变换矩阵都是非奇异方阵，并且本文的方法能同时优化多个嵌套循环。

1解决方案

假设核外计算程序中有一系列嵌套循环，它们都访问程序中声明过的数组（核外数组）。我们的优化步骤如下：

（1） 通过循环分布，循环合并和循环展开等程序变换将这些循环转化为一系列独立的循环。

（2） 构造一个冲突图并在图上识别出连通子图（connected component）。冲突图是一个二分图，记作（Vn，Va，E），其中Vn是所有代表循环的节点集合，Va是所有代表数组的节点集合，E是所有连接循环节点和数组节点的边的集合。若v1∈Vn，v2∈Va，当且仅当v1引用了v2时，才存在一条边e连接v1和v2，且e∈E。

（3） 对每一个连通子图：

（a） 对所有嵌套循环，根据profile信息计算出它的代价，然后根据这一代价来对这些循环进行排序。

（b） 首先仅用数据变换来优化代价最大的循环；然后对该循环进行迭代空间划分。

（c） 根据上面的排序，对连通子图中的其他每个循环：运用非奇异线性循环变换和数据变换（要考虑到当前已经访问过的数组的布局）来优化该循环，然后对其进行迭代空间划分；将当前已经访问过的数组的布局传播到下一个将被处理的循环。

图1用一个例子演示了以上算法中步骤（1）和步骤（2）的工作过程。左边是由两个嵌套循环组成的一个未经过优化的程序序列。U、V、W、X、Y是循环过程中访问到的核外数组。第一步，编译器运用循环合并（loop fusion）处理第一个嵌套循环，用循环分布（loop distribution）来处理第二个嵌套循环；第二步，编译器构造出冲突图，并识别出其中的连通子图（connected component）。根据冲突图，可以将程序重新划分为两段，这两段程序访问的数组构成的集合没有交集（第一个程序片段只访问U、V、W数组，第二个程序片段只访问X、Y数组）。由于各个连通子图涉及的数组集合的交集为空，所以步骤（3）只需要对每一个连通子图对应的程序段分别进行处理。

1.1联合使用数据变换和循环变换的必要性

我们通过下面的例子来说明为什么必须联合使用数据变换和循环变换。下面的程序段对应于图1中的第一个连通子图；数组U、V、W都是驻留在硬盘上的核外数组，所有数组在硬盘上都是按列分布的。

如果仅仅使用循环变换，不可能同时对第一个嵌套循环中的两个数组的访问得到良好的空间局部性，因为这两个数组的重用轨迹是正交的；第二个嵌套循环中也存在这样的情况。如果仅仅使用数据变换，将U变换为按行分布，W保持按列分布，但是前后两个嵌套循环对V的存储布局的需求产生冲突，不能同时按最优方式来访问。下文主要研究如何联合使用数据变换和循环变换使所有循环中对所有数据的访问都能获得良好的局部性。

1.2技术细节

1.2.1超平面和数组布局

一个k重嵌套循环对m维数组元素的访问轨迹可以用一个m×k访问矩阵L和m维偏移向量来描述。例如在上例中的第一个嵌套循环里对数组元素V（i，j）的访问可以用运算式L+来表示，其中

在m维数据空间中，一个超平面可定义为m元组的集合：

{(a1,a2,…,am)|g1a1+g2a2+…gmam=c}

其中有理数g1，g2， …, gm中至少有一不为0，称它们为超平面系数；有理数c称为超平面常数。可以采用行向量gT=（g1,g2, …,gm )来标记一个超平面族(c取不同的值对应不同的平面)。为了简便起见，本文只讨论二维数组，但是本文的结论都适用于更高维数组。在二维数据空间里，超平面族可以用行向量（g1,g2）来标记，当c取不同值时，它实际上是一组平行线。当硬盘上的2个数据点（数组元素）（a,b）和点（c,d）满足以下关系时，他们位于同一超平面上：

例如，对于超平面族（0,1），只要2个元素的列坐标相等（行坐标可以不同），则它们就同时属于超平面族（0,1）中的某个超平面。我们可以用超平面族来标记数组的存储布局。例如对于一个二维数组，我们可以用向量（0,1）来说明它的每一列（对应于具有特定c值的超平面）的元素被连续存储在硬盘上（此时如果循环程序按列访问这个数组，则该数组将体现出最好的局部性）。可见，向量（0,1）可用来表示数组按列分布的存储布局。同理，可得（1,0）可表示按行分布，(1,-1)可表示按对角分布，(1,1)表示按反对角分布，等等。

1.2.2循环变换

一个k重循环的迭代空间可以被看作是一个k维空间里的多面体，其每个点可以用k维向量（迭代向量）= （i1,i2, …,ik）T来表示。其中in代表循环索引变量，并且i1代表最外层循环索引变量，ik代表最内层循环索引变量。循环变换可以用一个线性非奇异转换矩阵来表示。对于一个k重嵌套循环，其循环变换（迭代空间变换）矩阵T是一个k×k方阵。迭代空间变换将原嵌套循环的迭代向量变换成新的迭代向量′，同时也就获得了新的嵌套循环。变换后，对数组元素的访问轨迹可用LT-1′+来表示。参考文献［2］和［3］讨论了如何选择合适的变换矩阵T来改善数据访问的局部性，同时确保不改变原先嵌套循环中存在的数据依赖关系。例如在一个2重嵌套循环中，循环变换可以由非奇异变换矩阵来表示:

1.2.3循环变换和数据变换的结合使用

下面的定理说明了在对嵌套循环中的数组进行访问时，为了使得最内层循环对数组的访问能获得最好的空间局部性，循环变换矩阵、超平面和访问矩阵之间应满足的关系，定理的证明见参考文献［4］。

定理设k重嵌套对二维数组的访问轨迹为L+，其中

为了使得最内层循环对该数组的访问能获得最好的空间局部性，代表数组存储布局的超平面(g1,g2)应满足关系式：

对于(g1,g2)和(q1k,q2k,…,qkk)T，只要其中一个已知，很容易就能将另一个求出。如果矩阵Q的最后一列已知，则

同理，如果(g1,g2)已知，则

通常情况下求出的Ker集含有多个向量，我们选择其中一个向量，它的各个元素的最大公约数应该最小。再看1.1小节的那个例子，可以发现第一个嵌套循环的访问矩阵是

第二个嵌套循环的访问矩阵是

按前面所说的优化步骤，对第一个嵌套循环仅施加数据变换，已知(q12,q22)T=(0,1)。对数组U，运用上面给出的式（1），可得：

其中符合条件的特解是(g1,g2)=(1，0)，也就是说数组U应当按行分布。同样，对数组V可得：

符合条件的特解是(g1,g2)=(0,1)，所以数组V应该按列分布。

确定好数组U和V的存储布局之后，我们再继续处理第二个嵌套循环。已经确定数组V的存储布局为(g1,g2)=(0,1)，运用上面的式（2），可得：

一个满足条件的特解是(q12,q22)T=(1,0)T。根据参考文献［5］中的方法，可以最终求得：

QT即为循环转换矩阵。最后一步工作就是要确定数组W的最优存储布局。因为Q已知，所以对数组W使用式（1），可得：

这意味着数组W应该按行分布。优化后的最终程序如下：

图2是上面的二维数组U、V、W从没有优化到优化后的核内不同访问形式：

2实验结果

我们从几个基准测试程序库和数学计算程序库中选择6个测试程序，它们的特点如表1所示。我们对这六个程序运用各种变换技术进行优化，分别得到5个版本的优化程序：

-col：核外数组固定为按列分布

-row：核外数组固定为按行分布

-lopt：仅用循环变换来优化程序

-dopt：仅用数据变换来优化程序

-copt：联合使用循环变换和数据变换

其中col和row版本都是未经过优化的原始程序；lopt版本是运用参考文献[3]中算法产生的；dopt版本是运用参考文献[6]中的算法得到的；copt版本是用本文中的方法产生的。表格2中列出了将优化后的各版本的程序在具有16个CPU的SMP机器上运行的结果（单位s）。从这些结果我们可以推断出：仅仅使用循环变换优化lopt的经典局部优化策略效果可能不好,而基于数据变换dopt的性能提高了许多，我们的copt方法相对于col方法减少了42%的执行时间，可以看出copt版本的程序运行效率最高。

3结语

本文阐述了如何联合使用循环变换和数据变换两种编译优化技术来改善核外计算程序的性能。在此过程中运用了大量的线性代数知识，具有理论上的可靠性。实验结果证实了本文提出的方法的优点。