文档介绍：合肥工业大学
博士学位论文
计算机算术中若干前缀计算问题的研究
姓名:孙海平
申请学位级别:博士
专业:精密仪器及机械
指导教师:高明伦
20061001
摘要计算机算术是一个亘古而恒新的论题。随着微电子技术的飞速进步,以硬件电路来实现的算术运算种类越来越丰富、运算器的位宽越来越大。但是二进制定点整数加法始终是通用微处理器、数字信号处理器妥ㄓ眉傻缏雀骼嗉成电路中最常用和最基础的算术运算。透彻而系统地研究整数加法器以及各种算术运算单元中的各项处理技术意义重大。本文以前缀计算的基本概念和图示方法为基础提出前缀计算图的张度、张度空间等一系列相关概念、定义和定理与推论,完善和丰富了前缀计算的理论体系,为本文的后续研究和证明提供理论基础。本文对各种经典加法器的计算原理深入、系统地进行分析和必要的证明,一方面从逻辑功能的角度将加法器分解成“计算各单个位上的进位条件”、“进位链计算”和“根据进位情况计算最终和”三部分计算,另一方面将各种加法器的进位链构成方式统一成四种分块递归扩展组织方式,提出了整数加法器计算和构成的内在统一模型。本文通过对“根据进位情况计算最终和”这一部分进行演化,指出能够以各种不同进位链结构的整数加法器为基础而仅以极少量电路逻辑改变“根据进位情况计算最终和”就实现各种“拓广加法”运算,如双加运算、模加运算和差的绝对值求解。本文提出并分析、证明“模币加”和“模印钡男滤惴ā6杂凇澳”一加”运算,提出了拆环式的新方案,既可以用于孤耄部梢杂糜诙圃牒筒码:对于“模印痹怂悖谋淞舜车幕谒跻宦氲淖鞣ǎ奈;谠胫苯进行计算,不仅改进了计算性能还减少了为了实现计算而进行的编码转换开销。本文将构建的前缀计算理论体系和整数加法器的内在统一模型应用于构造三类前缀计算图:最小深度前缀计算图的规则构造、最小深度前缀计算图的混合结构构造以及任意深度最小延迟前缀计算图的构造。进一步定义一系列概念缂扑阕杂啥取⒖行区间等⑻岢霾⒅っ饕幌盗卸ɡ砗屯坡郏⒁源宋;」乖烨蠼馑惴ú⒍运惴ǖ正确性进行形式证明。本文将前缀计算理论应用于前导零问题。从前缀计算的角度,提出一系列的定义、定理,证明了前导零检测算法本质上都可以归结为前缀计算问题,因而适用递归式求解方法。在此基础之上,给出了前导零的二分递归检测算法,并加以证明;对于前导零的预测方法,通过对加法运算量做“借位留存”减法,将对两个运算量的预测转换
为对,肿址系氖执奶卣骷觳馕侍猓佣芄挥τ枚值莨榍蠼夥关键词:;经过细致分析、通过采用了消除连续的“一闹乇嗦爰际醵岢隽艘恢滞骋位串形式来预测前导零的位数,并设计出一组位串构成形式的递归判别方法和前导零位数的递归推断方法,解决了前人预测方案对有些情况有可能存在误差为奈侍狻本文还进一步将前导零预测的新方法应用于乘法一加法熔合运算单元,提出了加法与舍入处理相结合的双路径处理设计,对前人的设计作了改进,针对不同类型的运算数据采用不同的数据通路进行计算,降低了平均节拍数、.提高了计算效率。
瓾猠琱,..,瑃,,,甧’,,瑆琲,,瑃,瑆..琭,篶籓,甤保瑃,,.,一.—辭
,玪,,,.琣,,瑀;,瓼琣..“一眘琣琣.,。.—,瑃,仃,琣,,
:,琲琹,
插图清单图白罕泶锸絧··的两种不同计算结合过程⋯图白罕泶锸健住的两种不同计算过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图进位链前缀计算图的递归构造:块的并列式扩展——单级补缀方案⋯⋯⋯魏次前缀计算的图示法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图ḿ悠魇疽馔肌图胁ń患臃ㄆ鹘患扑愕那白杭扑阃肌加法器进位计算的前缀计算图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯加法器进位计算前缀计算图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.臃ㄆ鹘患扑闱白杭扑阃肌加法器进位计算前缀计算图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.的前缀计算结构分治构造法:减半式递归构造⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图臃ㄔ怂愕穆呒纸狻图患督惶炯臃ㄆ髟硗肌图患督惶炯臃ㄆ鹘淮ǖ葑罨登榭鍪疽馔肌图患督惶炯臃ㄆ鹘磺白杭扑阃肌图曼彻斯特进位链加法器示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图多级进位跳跃加法器示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图进位选择加法器原理示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图进位链前缀计算图的递归构造:块的并列式扩展的一般形式⋯⋯⋯⋯⋯⋯唤涣床棺杭扑憧榈募钢植煌桨未列全图进位链前缀计算图的递归构造:块的级联式扩展⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图进位链前缀计算图的递归构造;块的减数式扩展⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图进位链网络的功能拓展:复合加法器⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图进位链网络的功能拓展:模币加运算电路⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯“图进位链网络的功能拓展:基于珂位原码的模加怂恪图差的绝对值:基于进位链网络的末级求