Optimization Of Numerical Programs Via Stochastic Algebraic Transformation

Writing correct,efficient and maintainable software is a challeging task in software engineering.This is especially true for numerical programs as numerical software is of-ten the core components in the safety-critical but resource-limited area.Engineers want to develop efficient numerical programs,which often involves floating-points numbers with limited precision.In this case,engineers need to implement the software care-fully with stable numerical algorithms and a lot of precision-specific operations,which makes the software complicated and difficult to maintain.On the other hand,infinite precision arithmetic hatches neat and correct numerical code,which makes the software easy to maintain.But it is thousands of times slower with large memeory requirments.In order to solve above problems,this paper proposes a global optimization frame-work that transforms numerical programs directly following the mathematical formu-lation to the efficient floating-point numerical programs with numerically stable algo-rithms.The numerical software developer just needs to provide a numerical program that is programing directly following the mathematical formulation from software re-quirments.Our framework changes the calculation of the direct program and generates an equivalent program in fixed-precision floating-point arithmetic with stable numerical algorithms.The main contriutions of this paper are as follows:We design an optimization framework that transforms a numerical program to its stable fixed-precision implemention.The framework is able to optimize the cal-culation globally,which allows numerical software developers to think and design their numerical programs in terms of real number directly.We propose a stochastic algebraic transformation algorithm,which randomly searches the mathematically equivalent process of the input program with a few algebraic algorithms and generates the optimized code with an automatic verification of nu-merical stablility.Based on the above optimization framework,we implement an optimization tool consisting of four different modules,including stablility analysis,trace extraction,stochastic algorithm transformation and trace merging.The tool takes an arbitrary-precision program as input and can generate more efficient floating-point program that are equivalent to the original program.We evaluate our approch on a few test subjects from the literature and also the GNU Scientific Library.Our toolchain successfully detects and diagnoses instablilities in the subjects.