My processor,无FPU和整数数学的小型16位微控制器仅具有16/16分区和32/16分区,均需要18个周期。目前我正在使用非常缓慢的软件程序(约7,500个周期)来执行64/32分割。有没有办法使用这些分割引擎来计算64/32分割?类似于我已经使用16x16乘法器和加法器来计算32x32乘法?我使用C,但可以使用任何一般的解释如何可以完成...我希望目标< 200个周期(如果它是所有可能的话)。具有32/16位分区的处理器上的64/32位分区
回答
请参阅多词分部的“Hacker's Delight”(第140-145页)。
基本概念(回去Knuth)是基于65536条款来思考你的问题。然后你有一个4位数字和2位数字的划分问题,以2/1数字划分作为一个基元。
C代码是在这里:http://www.hackersdelight.org/hdcodetxt/divmnu.c.txt
我的Knuth(The Art of计算机编程)正在工作,所以直到星期一才能检查它,但这将是我的第一个来源。它有一个关于算术的全部部分。
编辑:你的帖子关于“16/16师和32/16师都需要18个周期。” - dsPIC在汇编中有一个条件减法操作。考虑使用这个作为你的计算基元。
还要注意的是,如果X = XH * 2 + XL和d = DH * 2 + DL,则如果你正在寻找
(Q,R)= X/d,其中X = Q * d + R
其中Q = QH * 2 + QL,R = RH * 2 + RL,然后
XH * 2 + XL = DH * QH * 2 +(DL * QH + DH * QL)* 2 +(DL * QL)+ RH * 2 + RL
这提示(通过查看属于高32位的术语),以使用下面的过程,类似于长除法:
- (QH,R0)= XH /(DH + 1) - > XH = QH *(DH + 1)+ R0 [32/16除法]
- R1 = X - (QH * 2 )* D [需要16 * 32乘,左移16和64位减]
- 计算R1' = R1 - d * 2
- 而R1' > = 0,调整QH向上加1,设定R1 = R1' ,和转到步骤3
- (QL,R2)=(R1 >> 16)/(DH + 1)→R1 = QL *(DH + 1)+ R2 [32/16划分]
- R3 = R1-(QL * D)[需要16 * 32乘法和48位减法]
- 计算R3' = R 3 - d
- 而R3' > = 0,调整QL向上加1,设定R3 = R3' ,和转到步骤7
你的32位商是对(QH,QL),而32位余数是R3。
(这里假定商不超过32位,您需要提前了解大,可以很容易地检查的时间提前。)
我只能建议通过连续的减法并得到结果结果寄存器增量。尝试将64位寄存器拆分为2或4个部分并将其分开分开是一种不可行的方法,因为整数除法引入了错误。
起点是: D.克努特,计算机程序设计2卷,第4.3.1节的艺术,算法d
不过,我想你可能需要优化的算法。
你可能想看看Booth's Algorithm
(http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division)。
你想要的部分大约是页面的1/2。
自从我的VLSI类以来,我还没有看过这个,但是,这可能是你最好的选择,如果可能的话,你可能想在汇编中做到这一点,尽可能优化它,如果你打电话给这个经常。
基本上涉及移位和增加或减少。
- 1. 分区位置
- 2. 同一节点上的分区处理?
- 3. Python - 在位列表分区
- 4. 动态定位分区
- 5. 具有32位操作系统程序兼容性的64位处理器?在64位处理器上的
- 6. 画面处理分区表
- 7. 虚拟处理器和逻辑分区
- 8. 定位分区内的数据
- 9. 区分不同的位掩码
- 10. 返回Pivot位置的分区
- 11. MODx。空分区/管理器
- 12. 带位置的区域上的鼠标位置:绝对区域覆盖区域
- 13. 分区定位泛滥菜单
- 14. 主营儿童分区定位
- 15. WIX安装程序 - 区分64位
- 16. 固定位置填满分区
- 17. 缓冲区位于何处?
- 18. Kafka Connect接收器分区:子分区?
- 19. 分区给定的总的分区和分区数的列表
- 20. Linux分区上的订购文件位置
- 21. OpenNlp不区分大小写的位置查找器
- 22. Emacs中缓冲区的重定位分配器是什么?
- 23. 会话处理 - 如何区分用户
- 24. 如何处理“分区”标签EXTJS
- 25. 如何禁用PLINQ分区/批处理
- 26. Apache Kafka主题分区消息处理
- 27. spring批处理分区性能问题
- 28. Azure存储 - 处理跨分区更新
- 29. 如何区分通信和处理层?
- 30. 表分区清理
是什么语言?在大多数(如果不是全部的话)语言中,double/single与FPU一起工作并且速度非常快......除非我在这里丢失了某些东西 – 2011-01-23 02:12:51
他正在谈论整数除法,而不是浮点除法 – 2011-01-23 02:13:24
我们是否在谈论某些特定语言(C,asm)?该机器是否具有FPU或只能在整数寄存器上运行? – 2011-01-23 02:13:25