linear algebra basic blocks
Matthieu Martel, Amine Najahi, Guillaume Revy · 2016
In embedded systems, ecient implementations of numerical algorithms typ- ically use the xed-point arithmetic rather than the standardized and costly oating-point arithmetic. But, xed-point programmers face two diculties: First, writing xed-point codes is tedious and error prone. Second, the low dynamic range of xed-point numbers leads to the persistent belief that xed- point computations are inherently inaccurate. In this article, we address these two limitations by introducing a methodology to design and implement tools that synthesize xed-point programs. To strengthen the user's condence in the synthesized code, analytic methods are presented to automatically assert its numerical quality. Furthermore, we use this framework to generate xed-point code for linear algebra basic blocks such as matrix multiplication and inversion. For example, the former task involves trade-os such as choosing to maximize the code's accuracy or minimize its size. For the two cases of matrix multi- plication and inversion, we describe, implement, and experiment with several algorithms to nd trade-os between the conicting goals.