前导0预测算法前缀模型的研究与实现

计算机工程与科学

前导0预测算法前缀模型的研究与实现

富坤1,2,魏思捷1,2,耿跃华3

(1.河北工业大学计算机科学与软件学院，天津 300401;

2.河北省大数据计算重点实验室，天津 300401;3.河北工业大学电气工程学院，天津 300130)

收稿日期:2015-10-10 修回日期:2016-10-05 出版日期:2017-10-25 发布日期:2017-10-25
基金资助:
国家自然科学基金（51577131）

Design and implementation of a prefix computation

model of leading zero anticipator algorithm

FU Kun1,2，WEI Si-jie1,2，GENG Yue-hua3

(1.School of Computer Science & Engineering,Hebei University of Technology,Tianjin 300401;

2.Hebei Province Key Laboratory of Big Data Calculation,Tianjin 300401;

3.School of Electrical Engineering,Hebei University of Technology,Tianjin 300130,China)

Received:2015-10-10 Revised:2016-10-05 Online:2017-10-25 Published:2017-10-25

摘要/Abstract

摘要：

前导0预测算法对浮点加法运算的研究非常重要，通过对现有浮点加法分析发现，前导0预测模块处于运算的关键路径，提高前导0预测模块的性能会使整体性能提高。从前缀计算角度提出一系列的定义、定理,并证明了前导0检测算法本质上都可以归结为前缀计算问题，从而该问题可以采用二分递归方法求解。在前导0预测过程中，首先通过对加法运算量做“借位留存”的减法，把两个运算量的预测转换为{1，0，-1}数字字符集上的数字串的特征检测问题。接着采用消除连续“-1”串的重编码技术得到一种统一的位串形式。最后设计出基于位串构成形式前导0位数的二分递归判断方法。

关键词: 前导0预测, 前缀模型, 重编码, 二分递归

Abstract:

The leading zero anticipator (LZA) algorithm is very important for studying floating-point addition operation, and the analysis of floating-point addition indicates that the LZA module plays a critical role in the performance improvement of floating-point addition operations. We define a series of definitions and theorems from the perspective of prefix computation, and prove that the LZA algorithm can be attributed to a prefix computation problem in nature. Thus, the problem can be solved by the dichotomy recursive method. In LZA process, we firstly convert the prediction problem of two operations to a digital string feature detection problem on numeric character set of {1,0, 1} by performing the subtraction of "Borrow Retirement" on addition operations. Secondly, a unified form of bit strings is obtained via the recoding technique which eliminates the continuous string of "1". Finally, the dichotomy recursive algorithm is designed based on the bit string structure of leading zero digits.

Key words: leading zero anticipator, prefix model, recoding, dichotomy recursive

富坤1,2,魏思捷1,2,耿跃华3. 前导0预测算法前缀模型的研究与实现[J]. 计算机工程与科学.

FU Kun1,2，WEI Si-jie1,2，GENG Yue-hua3.

Design and implementation of a prefix computation

model of leading zero anticipator algorithm

[J]. Computer Engineering & Science.