基于MPI的高精度归约函数设计与实现

随着科学工程计算大规模、高维数和长时程的特性越来越显著,浮点舍入误差的累积效应往往使得计算结果不可信,提高计算精度成为了并行计算领域研究的热点之一。基于MPICH3框架,采用无误差变换技术构建新的数据格式和相应运算操作符,设计了高精度归约函数MPI_ACCU_REDUCE,实现了高精度的求和、求积和求L2范数3种MPI归约运算。数值实验结果表明,提出的3种高精度归约运算有效提高了数值计算的精度。     

基于申威1621的高精度点积算法实现与优化

点积函数是BLAS库中的一级基础函数,其被科学计算等领域广泛调用.由于浮点计算会引入舍入误差,现有BLAS库中双精度点积函数不足以满足某些应用领域的精度要求,因此需要高精度算法来实现更精确可靠的计算.在本文中,面向国产申威1621平台,在现有的BLAS库的基础上,新增高精度点积函数的实现接口,来满足应用的高精度需求.同时,对于高精度点积算法运用循环展开、访存优化、指令重排等优化策略,实现汇编级手工优化.实验结果显示,文中高精度点积算法的计算结果精度,近似达到了双精度点积的两倍,有效提升了原始算法精度.同时,在保证精度提升的基础上,文中优化后的高精度点积函数相比未优化前,平均性能加速比达到了1.61.     

高精度曲面建模优化方案

目的 为了进一步提高高精度曲面建模（HASM）方法的模拟精度和计算速度,进而拓宽该模型的应用领域,提出了新的HASM模型算法。方法 采用新的差分格式计算HASM高斯方程中的一阶偏导数,以HASM预处理共轭梯度算法为例分析改进的差分格式对HASM的优化效果。结果 数值实验表明：在计算耗时及内存需求不变的情况下,采用新的差分格式的HASM算法可以显著提高单次迭代的模拟精度,同时能够降低关键采样点缺失对模拟结果精度的影响。进一步研究发现,当HASM采用新差分格式与原始差分格式（中心差分）交替迭代时,能够快速降低模拟结果的误差。结论 本文算法当达到指定的精度条时能够显著减小计算耗时,同时还能降低关键采样点缺失对模拟结果的影响。     

高精度曲面建模优化方案研究

目的：为了进一步提高高精度曲面建模（HASM）方法的模拟精度和计算速度,进而拓宽该模型的应用领域。方法：本研究采用新的差分格式计算HASM高斯方程中的一阶偏导数,以HASM预处理共轭梯度算法为例分析了改进的差分格式对HASM的优化效果。结果：数值试验表明：在计算耗时及内存需求不变的情况下,采用新的差分格式的HASM算法可以显著提高单次迭代的模拟精度,同时能够降低关键采样点缺失对模拟结果精度的影响。进一步研究发现,当HASM采用新差分格式与原始差分格式（中心差分）交替迭代时,能够快速降低模拟结果的误差。结论：本文基于HASM模型控制方程的离散差分改进格式,提出了新的HASM模型算法,新算法一方面当达到指定的精度条时能够显著减小计算耗时,另一方面还能降低关键采样点缺失对模拟结果的影响。     

基于高精度乘累加的LU分解加速器的设计

本文首先分析LU分解中舍入误差的积累过程,建立精度损失与矩阵规模的关系模型来预测大规模LU分解的精度;然后,根据定点加法的简单、快速、无精度损失的特点,设计高精度乘累加器(HPMAcc),并基于此实现一个细粒度并行LU分解加速器。实验结果表明,和高精度软件库QD或MPFR相比,4PE结构的LU分解加速器能够取得100倍的加速比,同时取得90多位的计算精度。     

一种用于加速椭圆曲线数量乘的Signed—Binary整数表示法

椭圆曲线公开加密系统已经得到了广泛的应用，其中最重要并且花费运行时间最多的运算就是计算数量乘。为了提高数量乘的运算度，本文提出了一种用于加速椭圆曲线数量乘的容易实现的Signed—Binary整数表示法，在不增加计算数量乘算法中预处理的复杂度的前提下，减少了点倍乘的次数，有效地提高了计算椭圆曲线点数量乘的速度。     

基于SCILAB的多精度算法研究与实现

当前,通用处理器一般支持64位浮点运算,在大规模和长时程数值计算中,由于浮点运算的舍入误差累积效应,可能导致数值结果不可信。因此,有效控制误差,设计高精度、高效可靠的浮点数值算法至关重要。基于SCILAB软件平台,通过使用无误差变换和double double数据格式,实现了高精度的算法库。对幂指数、Bernstein和Chebyshev基多项式函数估值,在Intel平台和国产飞腾处理器平台上进行了数值实验,实验结果证实了该高性能数值算法库的有效性。该多精度算法库具有独立知识产权,可有效应用于国产自主可控处理器平台,为国家重大科研项目提供技术支持。     

基于双倍双精度施密特正交化方法的QR分解算法

当矩阵的规模较大或者条件数较高时，格拉姆-施密特(Gram-Schmidt)正交化算法和其相关修正算法时常表现出数值不稳定性的现象。为了解决该问题，探索了修正Gram-Schmidt算法(MGS)中舍入误差的累积效应，然后基于无误差变换技术和双倍双精度算法，设计并实现了双倍双精度修正Gram-Schmidt正交化算法(DDMGS)。该算法的精度测试中显示所提算法较分块施密特正交化(BMGS＿SVL,BMGS＿CWY,BCGS＿PIP与BCGS＿PIO)的变体算法具有更好的数值稳定性，证明了DDMGS算法能够有效地减少矩阵的正交性损失，提升数值精度，展示了所提算法的可靠性。在算法的性能测试中，首先计算并比较了不同算法的浮点计算量(flops),随后将所提DDMGS算法与修正施密特正交化算法在ARM和Intel两款处理器上作比较，虽然DDMGS算法的运行时间分别是MGS的5.03倍和18.06倍左右，但获得了明显的精度提升效果。     

关键点选取的最小二乘渐进迭代逼近

目的 最小二乘渐进迭代逼近（LSPIA）方法多以均匀参数化或弦长参数化的形式均匀地确定初始控制点,虽然取得了良好效果,但在处理复杂曲线时,迭代速度相对较慢且误差精度不一定能达到预期设定值。为了进一步提高迭代效率和误差精度,本文提出了基于关键点（局部曲率最大点和极端曲率点）的最小二乘渐进迭代逼近方法。方法 首先计算所有数据点的离散曲率,筛选出局部曲率最大点;接着设定初始的曲率下限,筛选出极端曲率点;然后将关键点与均匀选取的控制点按参数顺序化,并将其作为迭代的初始控制点;最后利用LSPIA方法对数据点进行拟合。结果 对同一组数据点,分别采用LSPIA方法和基于关键点的LSPIA方法,本文方法较好地提高了收敛速度;在相同的控制点数目下,与LSPIA算法相比,本文方法的误差精度较小。结论 本文方法适合于比较复杂的曲线,基于曲率分布的关键点的选取,可以更好地反映曲线的几何信息。数值实例表明,结合关键点筛选策略的LSPIA算法提高了计算效率,取得了更好的拟合效果。     

区域求和表算法的改进

查找表技术可以使纹理过滤变得容易处理,其计算精度不再依赖于纹理的密度.目前常用的有Mipmap技术和区域求和表技术.区域求和表技术使用一张预先计算的表格,该表格的每一个值代表由纹理图像左下角和当前点所确定的长方形区域的纹理值之和,它在相同性能的情况下能提供比mipmap过滤算法更好的视觉效果.由于该算法需要更多的内存空间和内存读写次数,本文对算法进行了改进,使之更适合于硬件实现.     

快速成型中一种改进的轮廓线生成算法

在对STL模型分层求交线过程中,针对三角面片的边与切平面很接近时,浮点运算引起的精度损失可能导致的错误交线问题,提出一种基于STL模型局部拓扑的分层算法。将所有可能引起错误交线的三角面片提取出来,建立拓扑结构,以接近切平面的边在切平面的投影替代交线,消除了由于浮点运算误差导致的轮廓线缺边和重边的错误。实验结果表明,该算法在计算出交线段集后不需要再进行修复,简单连接后就能得出正确的切片轮廓线。     

Implicit matrix multiplication with maximum accuracy on various transputer networks

The majority of numerical algorithms employs floating-point vector and matrix operations. On a parallel computer these algorithms should be solved fastand reliably in order to avoid a time-consuming error analysis. The XSC-languages (high-level language extensions for eXtended Scientific Computation) are well-suited for this purpose since they support the design of numerical algorithms delivering correct and automatically verified results. This goal is attained by an arithmetic with maximum accuracy (especially for vector and matrix operations), highly accurate standard functions, and exact evaluation of dot product expressions. Within theESPRIT Parallel Computing Action, one XSC-language, PASCAL-XSC, was implemented on a Supercluster Transputer System under the operating system HELIOS. Parallel algorithms for computationally intensive and maximally accurate matrix operations were implemented and tested on various transputer architectures. We will sketch some features of these architectures and present some benchmarks for the algorithms used. These algorithms form a parallel C runtime library of PASCAL-XSC (or any other XSC-language that uses a C runtime library) and are called automatically. This can be considered a basis for implicit parallelization in an XSC-language.     

Numerical reproducibility for the parallel reduction on multi- and many-core architectures

On modern multi-core, many-core, and heterogeneous architectures, floating-point computations, especially reductions, may become non-deterministic and, therefore, non-reproducible mainly due to the non-associativity of floating-point operations. We introduce an approach to compute the correctly rounded sums of large floating-point vectors accurately and efficiently, achieving deterministic results by construction. Our multi-level algorithm consists of two main stages: first, a filtering stage that relies on fast vectorized floating-point expansion; second, an accumulation stage based on superaccumulators in a high-radix carry-save representation. We present implementations on recent Intel desktop and server processors, Intel Xeon Phi co-processors, and both AMD and NVIDIA GPUs. We show that numerical reproducibility and bit-perfect accuracy can be achieved at no additional cost for large sums that have dynamic ranges of up to 90 orders of magnitude by leveraging arithmetic units that are left underused by standard reduction algorithms.     

Line Segment Intersection Testing

A method for accurately determining whether two given line segments intersect is presented. This method uses the standard floating-point arithmetic that conforms to IEEE 754 standard. If three or four ending points of the two given line segments are on a same vertical or horizontal line, the intersection testing result is obtained directly. Otherwise, the ending points and their connections are mapped onto a 3×3 grid, and the intersection testing falls into one of the five testing classes. The intersection testing method is based on our method for floating-point dot product summation, whose error bound is 1ulp. Our method does not have the limitation in the method of Gavrilova and Rokne (2000) that the product of two floating-point numbers is calculated by a twice higher precision floating-point arithmetic than that of the multipliers. Furthermore, this method requires less than one-fifth of the running time used by the method of Gavrilova and Rokne (2000), and our new method for calculating the sign of a sum of n floating-point numbers requires less than one-fifteenth of the running time used by ESSA.     

Arithmetically improved algorithmic performance

An augmented set of floating-point arithmetic operations which includes the accurate inner product can be routinely employed with benefit in some standard iterative numerical algorithms. Benefits include the requirement of fewer iterations for achieving computational convergence criteria and more accurate results for a given number of iterations. Not all algorithms are benefited, but favorable results have been obtained for the QR algorithm, the conjugate gradient algorithm and the separating hyperplane algorithm.     

大整数Comba和Karatsuba乘法的多核并行化研究

大整数运算广泛地应用于公钥加密算法、大规模科学计算中高精度浮点数运算类以及构建大特征值等领域,然而其大部分算法空间和时间开销都很大,尤其对于核心运算之一的大整数乘法,当数据达到一定规模时,超长的串行计算时间已成为制约算法应用的巨大瓶颈.近几年来,伴随着多核、众核芯片的迅猛发展,通过充分挖掘算法本身的并行度以利用并行处理器的强大计算能力,进而高效地提升算法性能,成为一种研究趋势.本文基于通用多核并行计算平台,研究了大整数乘法Comba及Karatsuba快速算法的并行化,提出了高效的多核并行算法.在算法实现及性能优化上,采用了OpenMP+SIMD的多级并行技术,使性能获得巨大提升.在性能测试上,我们使用优化的并行算法与原始串行算法进行对比试验,结果显示,8线程并行Comba算法和Karatsuba算法相比串行对应算法分别实现了5.85倍以及6.14倍的性能加速比提升.     

决策树分类算法中C4.5算法的研究与改进

C4.5算法是用于生成决策树的一种经典算法,虽然其有很强的噪声处理能力,但当属性值缺失率高时,分类准确率会明显下降,而且该算法在构建决策树时,需要多次扫描、排序数据集、以及频繁调用对数,针对以上缺点,本文提出一种改进的分类算法.采用一种基于朴素贝叶斯定理方法,来处理空缺属性值,提高分类准确率.通过优化精简计算公式,在计算过程中,改进后的计算公式使用四则混合运算代替原来的对数运算,减少构建决策树的运行时间.为了验证该算法的性能,通过对UCI数据库中5个数据集进行实验,实验结果表明,改进后的算法极大的提高了运行效率.     

基于深度编码器的复杂网络社区发现算法 #br#

复杂网络是复杂系统的典型表现形式,社区结构是复杂网络最重要的结构特征之一。针对目前社区发现算法精确度低以及不适合大规模网络的问题,提出一种新的算法DA-EF和用于度量节点之间相似度的影响力扩散指标。DA-EF利用多层自动编码器与森林编码器构成二级级联模型,相似度矩阵进行降维和表征学习处理,转化成低维高阶特征矩阵,最终使用K-means得到准确的社区划分结果。级联结构在保持算法同等深度的情况下,大幅降低了算法时间复杂度。在人工合成数据集和真实数据集上的实验表明,DA-EF与同类算法K-means、DA-EML和CoDDA相比,其标准互信息NMI和模块度Q值高,而且聚类运行时间最少,具有精确度高和效率快的优势。在算法性能实验中,验证了算法的级联结构、自动编码器的深度以及影响力扩散指标的合理性和有效性。