Automatic Generation of Staged Geometric Predicates

Algorithms in Computational Geometry and Computer Aided Design are often developed for the Real RAM model of computation, which assumes exactness of all the input arguments and operations. In practice, however, the exactness imposes tremendous limitations on the algorithms—even the basic operations become uncomputable, or prohibitively slow. In some important cases, however, the computations of interest are limited to determining the sign of polynomial expressions. In such circumstances, a faster approach is available: one can evaluate the polynomial in floating-point first, together with some estimate of the rounding error, and fall back to exact arithmetic only if this error is too big to determine the sign reliably. A particularly efficient variation on this approach has been used by Shewchuk in his robust implementations of Orient and InSphere geometric predicates.We extend Shewchuk's method to arbitrary polynomial expressions. The expressions are given as programs in a suitable source language featuring basic arithmetic operations of addition, subtraction, multiplication and squaring, which are to be perceived by the programmer as exact. The source language also allows for anonymous functions; the use of such functions enables the common functional programming technique of staging. The method is presented formally through several judgments that govern the compilation of the source expression into target code, which is then easily transformed into SML or, in case of single-stage expressions, into C.     

高性能浮点DSP芯片加法运算单元的研究与设计

详细讨论了浮点加法的算法及其特性,研究了现行的一些浮点加法运算单元所采用的改进算法及其电路实现,并介绍了这个领域的一些新技术。     

单片机上一种新颖实用的ex函数计算方法

详细介绍了一种在8096／98系列单片机实现的新颖的e^x函数的计算方法，该算法是在数的二进制分解的基础上，充分利用了指数函数的特性和浮点数在单片机中的存储特点，计算速度快，精度高，有很强的实用性。     

Formal Verification of Square Root Algorithms

We discuss the formal verification of some low-level mathematical software for the Intel® Itanium® architecture. A number of important algorithms have been proven correct using the HOL Light theorem prover. After briefly surveying some of our formal verification work, we discuss in more detail the verification of a square root algorithm, which helps to illustrate why some features of HOL Light, in particular programmability, make it especially suitable for these applications.     

有效的浮点运算消除技术与椭圆的快速生成

为了改善椭圆基本生成算法的效率和消除算法中存在的错误边界像素问题,提出了一种浮点数消除技术和标准椭圆的生成算法.与现存算法采用中间量进行浮点数先期消除方法不同,该算法直接利用曲线上相邻两点所满足的表达式的差值构造包含残差的递推关系,再通过最近准则和1/2处的残差将其转换为整数形式的决策参数.分析和实验结果表明,该算法消除了递推关系中每步迭代时的常数项,比目前普遍采用的中点椭圆算法具有更高的效率,且有着与中点法一致的简单性.该算法不会产生特殊情况的错误边界像素,由于残差与亮度具有对应关系,可以实现整数形式的反走样绘制.     

基于FPGA的高性能浮点型FFT处理器设计

根据基2分解的FFT算法理论,采用了流水线与并行结合的方式,设计了一种基于FPGA芯片的FFT计算模块.该模块由地址控制单元和存储单元配合蝶形运算单元,实现了计算长度为1 024点、数据类型为32位浮点型的FFT计算.测试结果表明,该模块在CycloneIII芯片中耗用3 928个LE和123kb的存储器资源,稳定工作频率可达110 MHz,完成1 024点FFT变换时间为95.66μs,具有良好的运算性能.     

浮点矩阵相乘IP核并行改进的设计与实现

基于Altera浮点IP核实现浮点矩阵相乘运算时,由于矩阵阶数的增大,造成消耗的器件资源虽增加但系统性能反而下降的问题,针对现有IP核存在数据加载不连贯、存储带宽不均匀的不足,提出采用并行化数据存储、依据查找表加载数据和处理数据的方式对IP核进行改进。然后将改进的浮点矩阵运算在FPGA中实现,经过Quartus、Matlab软件联合仿真并进行结果比对,其误差不超过万分之一,且节省了器件资源、提升了系统性能。仿真结果表明该设计可行,有利于提高诸多高性能领域浮点矩阵的运算速度。     

参数化可配置IP核浮点运算器的设计与实现

将参数化可配置IP核的设计方法引入到浮点运算器设计中,通过设计时提取的可用参数,将浮点运算器设计成为参数化、可配置、可重用的IP核.通过仿真验证了实现参数化IP核浮点运算器的可行性和有效性.     

标志前缀加法器的结构优化设计

标志前缀加法器运算速度快但存在面积大的缺点。为满足实际应用中对浮点乘加单元面积的要求,对其进行结构优化得到基于Kogge-stone树结构的51位标志前缀加法器,采用模块级联减少运算单元个数,达到减小浮点乘加单元面积、降低功耗的目的。在TMSC 0.18 μm工艺下,该51位加法器的面积、总功耗、关键路径时延分别减少了10%, 10.5%, 6.4%。     

基于启发式搜索的浮点表达式设计空间探索方法

为了提高浮点表达式设计空间的探索效率,提出一种基于启发搜索的浮点表达式设计空间探索方法。在每次迭代过程中首先对非支配表达式的设计空间进行探索,同时将非支配表达式和可支配表达式分别添加到非支配列表和可支配列表中。当迭代完成后对可支配列表中的表达式进行探索,从中选择非支配的表达式,并对其邻域进行探索。将新的非支配表达式添加到非支配列表中,有效提高了非支配表达式的多样性和随机性。最后再次对非支配列表进行探索,得到最终的等价表达式,并进一步提高最优表达式的性能。与现有的浮点表达式设计空间的探索方法相比较,所提出的方法使计算精度提高了2%~9%,并减少了5%~19%的计算时间和4%~7%的资源消耗。实验结果表明,该方法可有效提高空间探索效率。