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

在科学计算中，稀疏矩阵向量乘（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的缺失率，实验结果与模型分析的结果一致。

高级微机ISA总线上的多功能接口板

介绍了一个应用于 Pentium机型上 ISA总线的接口电路 ,这个接口电路具有高速度、高可靠性的特点 ,是为光谱测量与能级寿命测量装置的控制及数据获取系统专门设计研制的。

光谱测量与能级寿命测量的数据获取电子学系统

随着物理实验要求的提高，利用先进的计算机技术来改造现有的物理实验设备具有重要意义。因此，我们设计研制了光谱测量与能级寿命测量数据获取电子学系统。本文全面论述了这一系统的组成结构。本系统由微机进行控制，通过基于Pentium机上工SA总线的接口电路来控制数据采集过程，实现了测量设备的智能化，并具有高速度、高可靠性的特点。配合软件工作可完全实现实验的无人监控。论文第一部分介绍了这个系统开发的背景及意义。第二部分是这个系统的组成和硬件结构、性能。这个系统完成的主要功能是：（1）采集数据并处理；（2）控制外设马达的运动；（3）显示系统的状态。第三部分是调试过程以及针对在调试中出现的各种实际问题提出的解决办法和预防措施。在设计工作完成之后，本系统在兰州近代物理研究所的加速器实验大厅中进行了模拟实验，并采集了部分数据。通过对获取数据的处理，获得了比较满意的结果。在论文的最后一部分中给出了本系统在实际运行后得出的实验结果以及此系统中可待完善之处。