快速有符号整数除法算法及其低成本实现

doi:10.3969/j.issn.1000-3428.2015.04.059

计算机工程

快速有符号整数除法算法及其低成本实现

高锦炜,莫鹏飞,杨　军,陈志坚

(浙江大学超大规模集成电路设计研究所,杭州310027)

收稿日期:2014-05-14 出版日期:2015-04-15 发布日期:2015-04-15
作者简介:高锦炜(1989 - ),男,硕士研究生,主研方向:计算机体系结构;莫鹏飞,工程师、硕士;杨　军,博士;陈志坚,讲师。

Alogrithm of Fast Signed Integer Divison and Its Low-cost Implementation

GAO Jinwei,MO Pengfei,YANG Jun,CHEN Zhijian

(Institute of VLSI Design,Zhejiang University,Hangzhou 310027,China)

Received:2014-05-14 Online:2015-04-15 Published:2015-04-15

摘要/Abstract

摘要： 微处理器中完成一条有符号除法指令需要6 个~38 个周期。跳过符号处理直接用补码参与运算,可以节省符号处理的3 个周期,从而提高除法器性能。为此,提出补码不恢复除法,将其运用于整数除法并给出算法证明,研究商的修正问题并给出解决方案。实验结果表明,该除法器在TSMC 130 nm 工艺下的面积为12 687 μm2,完成一条有32 位符号整数除法只需要2 个~34 个周期,相当于仅以多16% 面积的硬件代价提升35% 的有符号除法性能。

关键词: 有符号除法, 整数除法, 补码, 商的修正, 低成本, 除法电路

Abstract: Signed integer division instruction takes 6 ~ 38 cycles to complete in general micro-processors. By using the original operands for division without abs and negation process,3 cycles of latency can be reduced which will effectively improve the division performance of processor. This paper focuses on complement no-restoring division and its application, as well as proof on integer division. This paper does a research in quotient correction and its reasonable solution and also implements the division device. Experimental result shows that the device is only 12 687 μm2 in TSMC 130 nm process and can complete a 32 bit signed integer division in only 2 ~34 cycles,which means a performance improvement of 35% at a cost of only extra 16% area.

Key words: signed division, integer division, complement, quotient correction, low cost, division circuit

中图分类号:

TP301. 6

高锦炜,莫鹏飞,杨军,陈志坚. 快速有符号整数除法算法及其低成本实现[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.04.059.

GAO Jinwei,MO Pengfei,YANG Jun,CHEN Zhijian. Alogrithm of Fast Signed Integer Divison and Its Low-cost Implementation[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.04.059.

参考文献

参考文献 [ 1 ]　Nenadic N M,Mladenovic S B. Fast Division on Fixedpoint DSP Processors Using Newton-Raphson Method[C]/ / Proceedings of International Conference on Computer as a Tool. Washington D. C. ,USA:IEEE Press, 2005:705-708. [ 2 ]　黄叶荪,叶　青,仇玉林. 高速除法器设计及ASIC 实现[J]. 微电子学与计算机,2008,25(2):133-135. [ 3 ]　宣淑巍,李晓江,马成炎. 一种基于循环减法原理除法器的加速方法[J]. 微电子学与计算机,2009,26(12): 12-15. [ 4 ]　Takagi N, Kadowaki S, Takagi K. A Hardware Algorithm for Integer Division[C] / / Proceedings of the 17th IEEE Symposium on Computer Arithmetic. Washington D. C. ,USA:IEEE Press,2005:140-146. [ 5 ]　Bashagha A E, Ibrahim M K. Two ’ s Complement Division Without Using the Set of Full Precision Comparisions [J]. IEE Proceedings of Computers and Digital Techniques,1998,145(1):19-26. [ 6 ]　Shen J P,Lipasyi M H. MIPS32 4KTM Processor Core Family Software User’s Manual[M]. Sunnyvale,USA: MIPS Technologies Inc. ,2002. [ 7 ]　C-Sky. C-Sky CK803 User’s Manual[M]. Hangzhou, China:C-Sky Microsystems,2008. [ 8 ]　Gerwig G,Wetter H, Schwarz E M, et al. The IBM Eserver z990 Floating-point Unit [J]. IBM Journal of Research and Development,2004,48(3/ 4):313-321. [ 9 ]　Koren I. Sequential Algorithms for Multiplication and Division[EB / OL]. (2008-04-16). www. ecs. umass. edu / ece / koren / arith / slides / Part3-seq. ppt. [10]　Wan Xuting,Cai Jianping,Yang Qifan. Remainder Sign Analysis in Fixed-point Division [C] / / Proceedings of International Conference on Computer and Information Technology. Washington D. C. ,USA:IEEE Press,2010: 2143-2147. [11]　Nair P,Kudithipudi D,John E. Design and Implementation of a CMOS Non-restoring Divider[C]/ / Proceedings of IEEE Region 5 Conference. Washington D. C. ,USA:IEEE Press,2006:211-217. [12]　Chinal J P. Some Comments on Postcorrections for Nonrestoring Division [J ]. IEEE Transactions on Computers, 1972,21(12):1385-1394. [13]　Gosling J B, Biakeley C M S. Arithmetic Unit with Integral Division and Square Root [J]. Computers and Digital Techniques,1987,134(1):17-23. 编辑　顾逸斐

[1]	刘念，殷业，叶龙，肖龙，严实. 一种改进的高效RFID加密安全协议[J]. 计算机工程, 2014, 40(7): 87-91.
[2]	牛涛, 沈海斌. 基于分段二次插值的初等函数逼近低成本设计[J]. 计算机工程, 2013, 39(8): 285-287,291.
[3]	潘涛, 左开中, 郭良敏, 罗永龙. 基于异或运算的低成本RFID双向认证协议[J]. 计算机工程, 2012, 38(9): 278-281.
[4]	邵梅, 董荣胜, 孙栋栋, 余兴超. 基于势博弈的多路径网络编码研究[J]. 计算机工程, 2012, 38(14): 66-69.
[5]	范君迪, 李敏波, 陈光雨. 基于代理随机数的低成本RFID安全协议[J]. 计算机工程, 2011, 37(19): 129-132.
[6]	牛红霞, 黄文准, 王永生. 一种改进的组间互补码及其性能分析[J]. 计算机工程, 2011, 37(12): 273-275,278.
[7]	唐敏, 许团辉, 王玉艳. 一种改进的反码加法器设计[J]. 计算机工程, 2011, 37(10): 219-220.
[8]	杨灵, 闫大顺. 基于PUF的低成本RFID系统安全协议[J]. 计算机工程, 2010, 36(15): 148-150,155.
[9]	杜继永, 黄国荣, 程洪炳, 刘华伟. 基于实时操作系统的低成本捷联惯导系统[J]. 计算机工程, 2010, 36(12): 251-252.
[10]	祝胜林;杨波;张明武;胡月明. 基于PRNG的低成本RFID认证协议设计[J]. 计算机工程, 2008, 34(21): 18-19,2.
[11]	赵佳;曾晓洋;韩军;陈俊. 简化的抗零值功耗分析的AES算法及其VLSI实现[J]. 计算机工程, 2007, 33(16): 220-222,.
[12]	陈俊;王晶;曾晓洋;韩军. 低复杂度先进密码算法的VLSI实现[J]. 计算机工程, 2007, 33(04): 143-145.

快速有符号整数除法算法及其低成本实现

Alogrithm of Fast Signed Integer Divison and Its Low-cost Implementation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

Metrics

本文评价

推荐阅读 10