程序数值误差的扰动检测与优化

很多用于关键领域的数值计算程序使用浮点数格式作为数据的内部表示,但由于浮点数在表示上存在误差,这类程序的正确性很难得到完全的保障.本文提出了一种自动的检测途径来帮助应用程序的开发人员获得他们所写代码的稳定性信息.它通过两种具体的扰动技术——数值扰动与算式扰动,来扰动底层的数值量和计算步骤,统计扰动下的运算差异,并最终评估数值计算代码的稳定性.数值扰动随机动态地改变程序数值的有效数字尾数,通过模拟误差的引入来观测程序的计算结果是否稳定;而算式扰动针对程序中算术表达式的计算过程,通过程序变换方法,将其转换成在实数域等价,但语法上不同的形式,然后以这些算式在浮点数下执行结果的差异来判断数值计算过程的稳定性.更进一步,本文使用了并行扰动算法和蒙特卡罗（Monte Carlo）方法来提高扰动技术的处理规模.当用户的硬件资源较丰富时,扰动技术将利用并行算法来提高运行效率;而当硬件资源不足时,蒙特卡罗方法也能在较短时间内得到一个可以接受的结果.我们对本文所提出的技术做了实现,并对文献中采用的一系列数值程序和GNU科学计算库（GSL）做了评估,评估结果显示,本文为数值计算稳定性的自动测试提供了一种实用技术.

Program instability detection based on systematically optimized numerical perturbation

For efficiency, Many numerical programs are based on fixed-precision floating point numbers. How- ever, it is very hard to guarantee the correctness of these programs during the propagation of the numerical errors. This paper presents an automatic approach that helps the developers detect the instabilities in their programs. The insight of our approach is by systematically perturbing the underlying numerical calculation, we can estimate the potential instabilities of numerical programs. We presents two concrete perturbations in our approach： value perturbation and expression perturbation. Value perturbation replaces the least significant bits of each floating-point value in the code, while expression perturbation changes the numerical expressions in programs to mathematically equivalent forms. We then compare the executions of these ＂equivalent＂ forms to help discover and remedy potential instabilities. We use a few techniques to optimize our perturbation approach. When users have powerful computing hardwares, a multi-core algrithm helps them to improve the performance of our perturbation. And when users have limited computing resources in their platform, we also present a Monte Carlo method to get acceptable results efficiently. The evaluation results on a few literary programs and the GNU scientific library （GSL） show the practicability and effectiveness of our perturbation approach.