论文部分内容阅读
近年来，蓬勃发展的大数据技术和机器学习技术为大规模数据分析应用提供了必要的基础支撑和技术手段。然而，数据规模的持续增长和日趋复杂的数据挖掘算法，对系统的性能和处理速度提出了严峻的考验。人们研究了各类新型硬件架构来满足数据分析应用的加速需求，众核架构就是其中的一种。然而，由于数据分析应用的多样化，以及新兴众核与现有多核在体系结构上的固有差异，使得在众核架构上优化数据分析应用变得极富挑战性。本文围绕数据分析应用在众核架构上的优化方法展开了一系列研究，主要内容如下: 1)鉴于目前尚没有众核架构(Intel Xeon Phi)上针对数据分析应用的基准测试集，本文基于BigDataBench提出了首个Intel Xeon Phi上的基准测试集PhiBench。PhiBench包含8个负载，覆盖6个应用领域，针对Intel Xeon Phi做了充分的优化，且包含两种数据集大小和两个并行实现版本(OpenMP，Cilk Plus)。 2)本文在两代Intel Xeon Phi平台上设计了一系列的实验来分析PhiBench的性能和行为特征，如SMT(Simultaneous Multi-thread)利用率、cache行为、矢量化密度、分支预测效率等。通过在KNC上的实验，我们发现矢量化密度不能单独作为衡量矢量化性能的指标，矢量化指令比例的作用也很大。另外，我们还发现SpMV与PageRank，IBCF等应用在体系结构特征上很相似，优化SpMV可以帮助大量数据分析应用提升性能。 3)本文设计了一种面向矢量化的稀疏矩阵存储格式，CVR，其基本思想是，将原有的CSR格式中的逐行处理，改为多行同时处理，每个SIMD通道只处理同一行的数据。由此可以大幅度降低矢量化的复杂度，并提升cache内的数据重用率。在58个常用的数据集上的实验表明，CVR在绝大多数的scale-free数据集上获得了最优的性能，平均优于Intel MKL2.84×(最高39.53×);在HPC数据集上，平均优于MKL1.22×(最高17×)。CVR的预处理开销在绝大多数数据集上都低于其它SpMV方法，表明了其实用价值。另外，CVR可大幅提升数据局部性，将SpMV的LLC失效率降低一个数量级。 4)稀疏矩阵中非零元的分布模式，即稀疏模式，决定了SpMV的访存模式，从而很大程度上影响了其性能。为理解该稀疏模式与SpMV性能之间的联系，本文选定了Intel Xeon Phi和GPU平台上的27个不同的SpMV方法进行横向对比，并抽取了43个矩阵特征来描述稀疏模式，分析稀疏模式与各SpMV方法的性能之间的相关性。实验发现，CVR的综合表现最好，可在70％的数据集上逼近最优性能（误差10％以内）。