计算机算术中若干前缀计算问题的研究

摘要

计算机算术是一个亘古而恒新的论题。随着微电子技术的飞速进步，以硬件电路来实现的算术运算种类越来越丰富、运算器的位宽越来越大。但是二进制定点整数加法始终是通用微处理器、数字信号处理器（DSP）和专用集成电路（ASIC）等各类集成电路中最常用和最基础的算术运算。透彻而系统地研究整数加法器以及各种算术运算单元中的各项处理技术意义重大。 本文以前缀计算的基本概念和图示方法为基础提出前缀计算图的张度、张度空间等一系列相关概念、定义和定理与推论，完善和丰富了前缀计算的理论体系，为本文的后续研究和证明提供理论基础。 本文对各种经典加法器的计算原理深入、系统地进行分析和必要的证明，一方面从逻辑功能的角度将加法器分解成“计算各单个位上的进位条件”、“进位链计算”和“根据进位情况计算最终和”三部分计算，另一方面将各种加法器的进位链构成方式统一成四种分块递归扩展组织方式，提出了整数加法器计算和构成的内在统一模型。 本文通过对“根据进位情况计算最终和”这一部分进行演化，指出能够以各种不同进位链结构的整数加法器为基础而仅以极少量电路逻辑改变“根据进位情况计算最终和”就实现各种“拓广加法”运算，如双加运算、模加运算和差的绝对值求解。 本文提出并分析、证明“模2″－1加”和“模2″＋1加”的新算法。对于“模2″－1加”运算，提出了拆环式的新方案，既可以用于1补码，也可以用于二进制原码和补码；对于“模2″＋1加”运算，改变了传统的基于缩一码的作法，改为基于原码直接进行计算，不仅改进了计算性能还减少了为了实现计算而进行的编码转换开销。 本文将构建的前缀计算理论体系和整数加法器的内在统一模型应用于构造三类前缀计算图：最小深度前缀计算图的规则构造、最小深度前缀计算图的混合结构构造以及任意深度最小延迟前缀计算图的构造。进一步定义一系列概念（如计算自由度、可行区间等）、提出并证明一系列定理和推论，并以此为基础构造求解算法并对算法的正确性进行形式证明。 本文将前缀计算理论应用于前导零问题。从前缀计算的角度，提出一系列的定义、定理，证明了前导零检测算法本质上都可以归结为前缀计算问题，因而适用递归式求解方法。在此基础之上，给出了前导零的二分递归检测算法，并加以证明；对于前导零的预测方法，通过对加法运算量做“借位留存”减法，将对两个运算量的预测转换为对｛1，0，-1｝数字字符集上的数字串的特征检测问题，从而能够应用二分递归求解方法；经过细致分析、通过采用了消除连续的“-1”串的重编码技术而提出了一种统一位串形式来预测前导零的位数，并设计出一组位串构成形式的递归判别方法和前导零位数的递归推断方法，解决了前人预测方案对有些情况有可能存在误差为1的问题。 本文还进一步将前导零预测的新方法应用于乘法－加法熔合运算单元，提出了加法与舍入处理相结合的双路径处理设计，对前人的设计作了改进，针对不同类型的运算数据采用不同的数据通路进行计算，降低了平均节拍数、提高了计算效率。

目录

文摘

英文文摘

论文说明：插图清单、表格清单

独创性声明及学位论文版权使用授权书

第一章绪论

1.1研究动机

1.2相关工作

1.2.1整数加法器

1.2.2前导零问题

1.3研究目标

1.4本文的内容组织

第二章整数加法器内在的前缀计算模型

2.1引言

2.2前缀计算模型

2.2.1前缀计算的一些基本概念

2.2.2前缀计算的图示方法

2.2.3前缀计算的若干重要定义、定理

2.3定点整数加法内在的前缀计算

2.3.1全加器分析

2.3.2进位(链)计算算符的推导与定义

2.3.3进位计算算符的有关性质

2.4经典加法器的前缀计算原理分析

2.4.1行波进行加法器

2.4.2Brent-Kung加法器

2.4.3Sklansky加法器

2.4.4Kogge-Stone加法器

2.4.5Han-Carlson加法器

2.5经典加法器的结构组织分析

2.5.1进位跳跃加法器

2.5.2进位选择加法器

2.5.3超前进位加法器

2.6进位链的分块递归组织策略

2.6.1块的并行式扩展

2.6.2块的级联式扩展

2.6.3位宽的减数式扩展

2.6.4块的混合式扩展

2.7进位链网络的功能拓展

2.7.1复合加法器——同时计算算术和A+B与A+B+1

2.7.2模加运算

2.7.3差的绝对值

2.8本章小结

第三章几类前缀计算图的构造

3.1最小深度前缀计算图的规则结构构造法

3.2加法器最小深度前缀计算图的一般性构造方法——混合结构

3.3任意深度最小延迟加法进位链前缀计算图的构造

第四章前导零问题的求解

4.1浮点数加法运算中的前导零检测与预测问题

4.2前导零检测算法

4.2.1前缀计算角度的分析

4.2.2二分递归算法及实现

4.3浮点加法中的前导零预测算法

4.3.1算法的记号约定

4.3.2数字串的构成分析

4.3.3数字串的重编码及进一步分析

4.3.4识别数字器前导零构成的统一位串形式

4.3.5数字串构成形式的递归判别方法

4.3.6数字串前导零位数的递归推断方法

4.3.7方法的对比

4.4小结

第五章乘法-加法熔合运算单元的设计

5.1引言

5.2常规方案

5.3加法与舍入相结合的方案

5.4加法与舍入相结合的双路径方案

5.5小结

第六章结论

6.1本文的工作成果

6.2未来工作展望

参考文献

攻读博士学位期间发表的论文

致谢