高速缓存优化的并行连接算法

由于嵌套循环连接操作过程中存在较大的高速缓存缺失,严重影响了连接查询的性能。提出了一种基于缓冲的高速缓存参数无关的嵌套循环并行连接算法。通过高速缓存参数无关和缓冲技术,提高了连接算法的空间局部性和时间局部性。理论分析和实验结果表明,高速缓存优化后的串行连接算法的性能是原来的2倍,其并行算法效果近似线性加速比。

模型检测MESIF Cache一致性协议

在处理器从单核向多核演进的过程中,为了获得更好的性能和可扩展性,适用于多核处理器系统的Cache一致性协议变得越来越复杂。Cache一致性协议的验证一直是模型检测在工业界主要应用之一,被工业界和学术界关注。相对传统方法而言,微结构级的模型检测能够描述和验证更多的协议细节。利用NuSMV工具对Intel公司的MESIF Cache一致性协议进行模型检测在微结构层次上进行了建模,并对该协议进行模型检测,试验结果证明了此方法的有效性。

On optimal message vector length for block single parallel partition algorithm in a three-dimensional ADI solver

It has long been recognized that many direct parallel tridiagonal solvers are only efficient for solving a single tridiagonal equation of large sizes, and they become inefficient when naively used in a three-dimensional ADI solver. In order to improve the parallel efficiency of an ADI solver using a direct parallel solver, we implement the single parallel partition (SPP) algorithm in conjunction with message vectorization, which aggregates several communication messages into one to reduce the communication costs. The measured performances show that the longest allowable message vector length (MVL) is not necessarily the best choice. To understand this observation and optimize the performance, we propose an improved model that takes the cache effect into consideration. The optimal MVL for achieving the best performance is shown to depend on number of processors and grid sizes. Similar dependence of the optimal MVL is also found for the popular block pipelined method.

循环优化序列自动定制方法研究

现代计算机在体系结构和应用场景复杂性的增长使得程序性能的增长、保持程序性能的可移植性以及程序开发效率的提升越来越困难，程序自动调优(auto-tuning) 是解决此问题的一个可行途径。本文研究一种通过为循环嵌套自动定制循环优化序列来进行程序自动调优的方法，提高了被编译程序的性能和可移植性，也有助于提升开发效率。 在综述相关工作的基础上，本文首先分析了循环优化序列自动定制研究需要解决的几个关键问题：循环优化的形式化描述及实施、循环优化序列的性能评估、循环优化序列的自动定制方法以及相关的原型工具。本文围绕这几个问题进行研究。 本文采用了Polyhedron模型来描述循环优化，并基于此实施了循环优化的仿射变换。这一工作基于URUK/WRaP-IT开源软件包实现，并作出了若干重要改进。借助Polyhedron模型，本文还给出了部分常见循环优化之间的使能(enable)关系。循环优化之间的相互影响较为普遍，一个循环优化的执行可能会破坏后续优化的实施条件，也可能不破坏甚至创造相应条件。这一关系可以用于过滤循环优化序列定制过程中产生的无效序列从而加快定制速度。本文分析了两个循环优化以先后次序执行时，循环嵌套内所有依赖距离向量均得以保持的条件，给出了它们之间的使能关系。并且给出了使能关系在Polyhedron模型下的计算方法，以及在序列搜索过程中通过维护依赖距离向量状态计算使能关系的方法。 对于循环优化序列性能评估方法，本文采用了高速缓存失效率简化方程(CMES方程)以动态给出循环嵌套中的高速缓存失效率数据，提出了LoopCost模型以静态分析方式发现循环嵌套中对性能影响最大的维度，这两种评估方法分别适用于不同的序列定制方法。 给出了Cache 失效率简化方程(CMES, Cache Miss Equation Simplified)在Polyhedron 模型下的求解方法。CMES方程可在编译时给出循环嵌套中的Cache失效率数据，不需要实际编译运行目标程序，从而避免相关文献中使用运行时信息来评价优化序列带来的巨大编译开销。给出了CMES方程各个参数从循环嵌套的Polyhedron模型中提取的方法，并给出了具体计算过程。 提出了一种可发现循环嵌套中对性能影响最大维度的循环优化性能评估模型LoopCost。相关文献中所使用的性能评估模型可给出一个循环嵌套的整体性能，但无法给出哪个维度对其性能影响最大；而大多数循环优化实际上是对某一个维度所做的变换，因此这些评估模型不能直接指导优化序列的搜索，只能是在一个迭代过程中提供性能信息。LoopCost模型基于数据依赖关系对一个循环嵌套估算出其每个维度使用的cache行数，作为衡量局部性优劣的指标，适用于紧嵌套循环和非紧嵌套循环，并且其复杂度与循环嵌套个数和引用个数成线性关系。通过对SPEC CPU 2006中5,703个循环嵌套的实验，LoopCost模型对其中98.3%的循环嵌套都能给出正确的性能评估数据。 对于循环优化序列自动定制方法，本文首先提出了一种基于CMES方程的Custom方法，使用迭代方式搜索可行优化序列；为了进一步提升优化效率，又提出了一种基于LoopCost模型的快速定制方法FastCustom。 Custom方法使用CMES方程评估优化序列，使用遗传算法作为序列搜索方法。在遗传算法中的各个算子中利用循环优化的enable关系加速搜索速度。该方法可以避免使用运行时刻信息评估性能所带来的巨大编译开销，又可避免相关工作中利用Polyhedron模型中语句实例执行次序矩阵的性质来搜索带来的局限性，适用的循环优化范围广，编译效率高，同时能取得与相关工作基本相当的加速比。 FastCustom方法优化效率高，并且与Custom方法不同，适用于所有场合。它基于LoopCost模型寻找对性能影响最大的维度，并根据一个启发式策略给出一个循环优化序列。该方法编译速度快，优化效果与Custom方法基本相当。与Custom相比，该方法需要给出启发式策略，因此适用的循环优化范围不如Custom，适用于迭代编译无法进行的情形。 对于循环优化序列自动定制原型工具，本文设计并实现了原型工具CPOLO。该工具改进了URUK/WRaP-IT开源软件包，使其能够支持较为复杂的程序；增强了代码重生成的效率；并且实现了本文所提出的优化序列性能评估模型和自动定制方法。 最后，总结了全文并探讨了进一步的工作方向。

基于序列模式的Servlet容器缓存替换

Servlet缓存能够有效地提高Servlet容器的吞吐量,缩短用户请求的响应时间.然而,Servlet缓存的性能受到缓存替换算法的影响.Servlet容器中的Servlet对应着一定的业务功能,挖掘Servlet之间的业务关联来指导缓存替换算法的设计可以提高Servlet缓存的命中率,进而提高Servlet容器的性能.然而,目前常见的LRU(least recently used),LFU(least frequently used),GDSF(greedy dual size frequency)等缓存替换算法均没有考虑上述问题.将Servlet对应的业务关联定义为Servlet容器序列模式,并提出k步可缓存转移概率图的概念加以表示,给出了序列模式发现算法KCTPG_Discovery.最后,基于Servlet容器序列模式设计了缓存替换算法KP-LRU(k-steps prediction least recently used)和KP-GDSF(k-steps prediction least frequently used).实验结果表明,KP-LRU与KP-GDSF算法比对应的LRU算法和GDSF算法具有更高的缓存命中率,有效地提高了Servlet容器的性能.

稀疏矩阵向量乘的存储访问复杂度及自动性能优化技术应用研究

在科学计算中，稀疏矩阵向量乘（SpMV, y=Ax）是一个十分重要的，且经常被大量调用的计算内核，广泛应用在科学计算、信息检索、气象、航天、油藏模拟、天体物理、数据挖掘等科学计算和实际应用中。在实际工程应用中，重复调用稀疏矩阵向量乘内核的次数常常会达到成千上万次。但在现代基于Cache存储层次的计算平台上，稀疏矩阵向量乘的性能很低。如果能够提高稀疏矩阵向量乘的运算速度，整个工程计算的运行效率将会得到很大的改善，计算时间也会大幅度的减少。因此优化稀疏矩阵向量乘的性能成为提高工程效率的关键，在实际应用中有着十分重要的意义。 SpMV的传统算法实现形式运行效率很低，主要原因是浮点计算操作和存储访问操作比率非常低，且稀疏矩阵非零元分布的不规则性使得存储访问模式非常复杂。寄存器分块算法和启发式选择分块算法,通过自适应选择性能最佳的分块大小，然后将稀疏矩阵分成小的稠密分块，所有的非零子块顺序计算，达到重用保存在寄存器中向量x元素的目的，减少存储访问次数和时间，从而提高这一重要内核的性能。我们在Pentium IV、Alpha EV6和AMD Athlon三个平台上，分别测试了十个矩阵下的两种不同算法形式(压缩行存储算法和寄存器分块算法)的性能，平均加速比分别达到1.69、1.90和 1.48。同时也测试了不同次数调用SpMV两种算法所用的时间，发现在实际的迭代算法应用过程中，若想采用启发式-寄存器分块算法达到性能提高的目的，一般情况下，迭代次数需要达到上百次才能有加速效果。 DRAM(h)模型是基于存储层次的并行计算模型，指出算法的复杂性包括计算复杂性和存储访问复杂性，具有近乎相同时间和空间复杂性的同一算法的不同实现形式，会有不同的存储访问复杂度，导致程序实际运行性能的差异；利用DRAM(h)模型进行分析并比较不同算法实现形式的存储访问复杂度，可以判断两种算法形式的优劣，从而为选取性能更高的实现形式提供指导。但利用DRAM(h)模型分析SpMV存储访问复杂度的工作以前没有人做过，并且SpMV的计算性能和存储访问行为跟具体的稀疏矩阵有关，只有到程序运行的时候才能知道。本文中，我们提出模板法和动态统计分析法两种分析SpMV存储访问复杂度的方法。在Pentium IV和Alpha EV6平台上，用RAM(h) 模型分析和计算了稀疏矩阵向量乘两种算法实现形式（即压缩行存储算法和寄存器分块算法）的存储访问复杂度，通过分析和计算在SpMV过程中需要访问的所有数据的存储访问复杂度，可知存储访问行为对整体程序的实际性能有直接影响。我们还在Pentium IV平台上，测试了七个稀疏矩阵的SpMV性能，并统计了两种算法中L1, L2,和TLB的缺失率，实验结果与模型分析的结果一致。