Bounding Variable Values and Round-Off Effects Using Handelman Representations
Bounding Variable Values and Round-Off Effects Using Handelman Representations
复制标题
使用 Handelman 表示法限制变量值和舍入效应
DOI：
10.1109/tcad.2011.2161307
复制
发表时间：
2011
影响因子：
2.9
通讯作者：
Boland D
中科院分区：
文献类型：
--
作者：
Boland D
算法中使用的精度会影响单个计算的误差和性能、内存使用以及固定硬件预算的潜在并行性。本文描述了一种确定由基本代数运算组成的算法满足给定误差规范所需的最小精度的新方法。使用这种方法，与现有方法相比，可以显著减少计算字长，这可以带来更好的硬件设计。我们在共轭梯度算法的迭代上演示了所提出的过程，实现了可以转化为全局字长节省的范围的证明，从几个比特到证明在使用竞争方法时必须假设无界的范围的存在。我们还在一小部分执行时间内实现了与最近文献相当的范围，具有更大的可伸缩性。
The precision used in an algorithm affects the error and performance of individual computations, the memory usage, and the potential parallelism for a fixed hardware budget. This paper describes a new method to determine the minimum precision required to meet a given error specification for an algorithm consisting of the basic algebraic operations. Using this approach, it is possible to significantly reduce the computational word-length in comparison to existing methods, and this can lead to superior hardware designs. We demonstrate the proposed procedure on an iteration of the conjugate gradient algorithm, achieving proofs of bounds that can translate to global word-length savings ranging from a few bits to proving the existence of ranges that must otherwise be assumed to be unbounded when using competing approaches. We also achieve comparable bounds to recent literature in a small fraction of the execution time, with greater scalability.