集成众核上快速独立成分分析降维并行算法

高光谱遥感影像快速独立成分分析(fast independent component analysis, FastICA)降维过程包含大规模矩阵计算及大量迭代计算.通过热点分析,面向集成众核(many integrated core, MIC)架构设计了协方差矩阵计算、白化处理和ICA迭代等热点并行方案,提出和实现一种M-FastICA并行降维算法,并构建算法性能模型;基于集成众核研究并行程序优化策略,针对各热点并行方案提出一系列优化策略,特别是创新性地提出一种下三角阵负载均衡方法,并量化测试其优化效果.实验结果显示M-FastICA算法最高可加速42倍,比24核CPU多线程并行快2.2倍;探讨了波段数与并行程序性能的关系;实验数据验证了算法性能模型的准确性.     

申威26010众核处理器上一维FFT实现与优化

根据申威26010众核处理器的特点提出了基于两层分解的一维FFT众核并行算法.该算法基于迭代的StockhamFFT计算框架和Cooley-TukeyFFT算法,将大规模FFT分解成一系列的小规模FFT来计算,并通过设计合理的任务划分方式、寄存器通信、双缓冲以及SIMD向量化等与计算平台相关的优化方法来提高FFT的计算性能.最后对所提出算法的性能进行了测试,相比于单主核上运行的FFTW3.3.4库,获得了平均44.53x的加速比,最高加速比可达56.33x,且其带宽利用率最高可达83.45%.     

有限元网格积分算法在MIC众核平台上的并行实现

基于英特尔集成众核(Many Integrated Core,MIC)架构,将有限元网格积分算法在至强融核(Xeon Phi)协处理器做了移植和性能分析。该应用全面测试了有限元分析的核心计算过程在MIC上的加速效果,实现了卸载模式(offload)[1]下利用OpenMP在MIC上的线程并行化。计算性能测试结果显示集成众核平台可以有效地加速有限元网格积分算法:1)一块被充分利用的MIC设备卡(3115A)的计算能力超过两路16核Intel XeonTM E5-2670 CPU;2)MIC并发的物理线程可能由于公共缓存访问存在竞争而降低程序的扩展性。测试结果还显示了在多CPU多MIC平台上进一步移植完整的MPI并行有限元模拟软件的可行性。这项工作有助于推动与有限元网格相关的科学和工程高性能计算的研究。     

LU分解在Godson-Tvl众核体系结构上的半行化研究

随着集成电路工艺的发展,众核体系结构成为人们日益关注的计算平台.LU分解是科学和工程计算中被广泛使用的核心算法之一,尽管在传统的并行体系结构上已有大量的并行化研究工作,但是结合新犁众核体系结构特征的工作还不多.文章从负载均衡、延迟容忍和性能分析模型3个方面系统研究了LU分解在众核体系结构上的并行化问题.该文的贡献在于:首先,针对二维卷帘负载分配方案难以达到良好负载均衡的缺点,提出一种新的"之"字形分配方案,实验表明不经任何优化的情况下性能比前者提高20%,优化后达到了40%;其次,提出了一个性能加速比的分析模型,并用实验定量研究了实测性能加速比和理论值之间的差距,发现在合理利用片上存储优化访存延迟,并恰当选择矩阵分块参数的情况下,实测加速效果能比较接近理论值;通过实验还证明实测性能难以达到理论预测值的两个主要原因:访存带宽有限和片上网络的资源竞争.     

Godson-T众核体系结构上的Broadcast性能优化

Godson-T是中国科学院计算技术研究所计算机系统结构重点实验室先进微系统组正在研制开发的适合于超深亚微米工艺实现的大规模片上众核系统.Godson-T片上存储的单端口结构节省了芯片面积但制约了共享数据的读取效率.直接在Godson-T上实现传统的Broadcast算法需要大量的同步互斥开销,无法达到很好的性能提升.基于Godson-T体系结构,对数据共享的重要并行算法Broadcast进行优化,提高了Godson-T体系结构下的数据共读的效率.主要采取了以下3项技术：消除大规模的线程同步,建立源地址到目的地址的映射表和用汇编语言实现Broadcast的核心部分.优化后Broadcast在小核数为32时即可达到5.8倍加速比.     

众核平台上广度优先搜索算法的优化

图算法在多个领域具有重要的应用价值。随着社会信息化程度的提高,需要处理的图数据量越来越大,图算法的性能已成为研究热点。广度优先搜索算法是一种重要的图算法,研究它的性能优化技术可以为其他图算法的性能优化提供借鉴。目前,在新一代Xeon Phi众核处理器上的工作均基于自顶向下算法且没有考虑到非均匀访存(NUMA)对性能的影响。文中以混合广度优先搜索算法为基础,结合NUMA拓扑结构,从任务分配、向量化和数据预处理3个方面展开优化,在Xeon Phi平台上设计并实现了高性能并行广度优先搜索算法。一系列实验结果表明,优化后的算法在不同规模的测试数据上与Graph500官方优化的算法相比取得了50%~145%的性能提升。     

BLAS 库在多核处理器上的性能测试与分析

BLAS 库是高性能计算中最基本的数学库,它的性能对超级计算机的性能有着极大的影响.而且随着CPU多核化的发展,BLAS 的多核并行性能已经变得比与体系结构相关的单核性能更加重要.实验以流行于高性能计算的Xeon、Opteron 系列多核X86 处理器为例,全面测试了GotoBLAS、Atlas、MKL 和ACML 四种主流的BLAS 库的所有1,2,3 级函数,并覆盖了不同计算规模和多核并行方面的测试.通过测试结果,分析源代码、BLAS 库资料和论文的方式,分析BLAS 有效的优化和并行方法,以及它们所适合的平台.为BLAS 的优化、使用,甚至高性能处理器的发展上提供有益的建议.实验结果表明,比起一个逻辑处理强大但是复杂的处理器,一个cache 更大、性能更好,内存带宽更宽、延迟更小,主频更高的处理器往往能在高性能计算中取得更好的性能.同时,X86 平台上的状况对其他体系结构也有巨大的借鉴意义.     

基于软硬件的协同支持在众核上对1-DFFT算法的优化研究

随着高性能计算需求的日益增加,片上众核(many-core)处理器成为未来处理器架构的发展方向.快速傅立叶变换(FFT)作为高性能计算中的重要应用,对计算能力和通信带宽都有较高的要求.因此基于众核处理器平台,实现高效、可扩展的FFT算法是算法和体系结构设计者共同面临的挑战.文中在众核处理器Godson-T平台上对1-D FFT算法进行了优化和评估,在节省几乎三分之一L2 Cache存储开销的情况下,通过隐藏矩阵转置,计算与通信重叠等优化策略,使得优化后的1-D FFT算法达到3倍以上的性能提升.并通过片上网络拥塞状况的实验分析,发现对于像FFT这样访存带宽受限的应用,增加L2 Cache的访问带宽,可以缓解因为爆发式读写带给片上网络和L2 Cache的压力,进一步提高程序的性能和扩展性.     

面向国产申威26010众核处理器的SpMV实现与优化

世界首台峰值性能超过100P的超级计算机——神威太湖之光已经研制完成,该超级计算机采用了国产申威异构众核处理器,该处理器不同于现有的纯CPU,CPU-MIC,CPU-GPU架构,采用了主-从核架构,单处理器峰值计算能力为3TFlops/s,访存带宽为130GB/s.稀疏矩阵向量乘SpMV（sparse matrix-vector multiplication）是科学与工程计算中的一个非常重要的核心函数,众所周知,其是带宽受限型的,且存在间接访存操作.国产申威处理器给稀疏矩阵向量乘的高效实现带来了很大的挑战.针对申威处理器提出了一种CSR格式SpMV操作的通用异构众核并行算法,该算法从任务划分、LDM空间划分方面进行精细设计,提出了一套动静态buffer的缓存机制以提升向量x的访存命中率,提出了一套动静态的任务调度方法以实现负载均衡.另外还分析了该算法中影响SpMV性能的几个关键因素,并开展了自适应优化,进一步提升了性能.采用Matrix Market矩阵集中具有代表性的16个稀疏矩阵进行了测试,相比主核版最高有10倍左右的加速,平均加速比为6.51.通过采用主核版CSR格式SpMV的访存量进行分析,测试矩阵最高可达该处理器实测带宽的86%,平均可达到47%.     

基于核最小噪声分离变换的高光谱遥感影像特征提取研究

高光谱遥感影像具有高维非线性的特点,线性特征提取方法容易造成信息丢失和失真。在最小噪声分离变换(MNF)线性特征提取算法的基础上,引入核方法,提出核最小噪声分离变换(KMNF)高光谱遥感影像非线性特征提取方法。KMNF通过核函数,将样本映射到高维特征空间,在特征空间中运算线性MNF,实现原始空间中的非线性KMNF算法。进行基于KMNF的高光谱影像特征提取实验,分析样本个数对KMNF特征提取的效果,发现样本数量对KMNF特征提取的结果影响很小,较少的样本数即可达到较多样本时特征提取的效果。对比KMNF与MNF特征提取的效果,分析它们降维的效率与保留的信息量,发现KMNF总体降维效率与MNF相当,且体现出高光谱图像的非线性特征;在KMNF和MNF特征提取的基础上,利用SVM进行高光谱图像分类,KMNF+SVM的分类精度优于MNF+SVM。