一个超级难的简单计算题

只看该作者 · 2012-3-11 15:56

3个正整数，A为12bit，B和C为10bit，且B<C，C>255
问题是：计算A*B/C的商和余数，无论用什么芯片，时间最短能达到多少？
如果把A,B,C扩展到16bit，又如何？
苦想了一个多月，仍然没有找到一个很好的解决办法，目前只做到了30ns

1万 · 2012-3-11 16:03

如果把A,B,C扩展到16bit，又如何？若用16位的片子已经是16位的了，不用扩！

30ns 这个已经很快了，5MIPS单片机单周期200ns，ST的M4据说最快为168MIPS,单周期也要6ns。
你用什么芯片运算的啊？ DSP ?

加快速度：提升主频，或超频计算！！

只看该作者 · 2012-3-11 16:05

我用FPGA整的，ARM能做单周期除法？

1万 · 2012-3-11 16:17

多少主频都没说，30ns怎么做参考？

1万 · 2012-3-11 19:44

我用FPGA整的，ARM能做单周期除法？
drentsi 发表于 2012-3-11 16:05

我可没说这个，我只是例了一下单片机的周期时间，具体要看芯片了！
我的意思是30ns已经很快了！

只看该作者 · 2012-3-11 21:20

FPGA做的，目前最快能做到9个clock，跑333MHz，总延时为30ns
整个数据处理环路为12个clock，延时为40ns，且无法解开环路，无法通过并行化来提升性能。
瓶颈就在这个乘除法，每减少一个clock，都是十分有意义的

1万 · 2012-3-11 22:28

http://www.docin.com/p-200198263.html
号称2周期

只看该作者 · 2012-3-12 07:53

http://www.docin.com/p-200198263.html
号称2周期
zjp8683463 发表于 2012-3-11 22:28

噢，这个值得好好看看！

1万 · 2012-3-12 12:48

这个NB ! ! !

2周期 ! ! !

只看该作者 · 2012-3-12 13:45

??????????????/

只看该作者 · 2012-3-12 14:06

http://www.docin.com/p-200198263.html
号称2周期
zjp8683463 发表于 2012-3-11 22:28

我只懂verilog，看不懂vhdl。不过我仍然保持我的怀疑：
1）作者的vhdl算法实现跟他**开头的文字描述，看上去不一致；文字描述了依赖于时钟的移位操作，既然是这样我认为不可能在两个cycle内就得到除法结果。
2）即便他能在两个两个cycle内得出结果，但在同样的硬件性能下，他的imeplement后的结果只能run到10Mhz，那与用10个cycle得到结果，但能run到200MHz的实现方法相比，那还不如后者了呢

所以，最快的就是用FPGA内部的硬件乘法器（cpu，单片机里都有）实现。但我还是不相信楼主用了9个周期，我觉得不会这么慢，等我有时间，我试试。

只看该作者 · 2012-3-12 15:15

学习

1万 · 2012-3-12 15:23

最快的就是用FPGA内部的硬件乘法器,但我还是不相信楼主用了9个周期

是否LZ为了提高速度内插了寄存器？
LZ能再详细说一下用什么器件、加了哪些时序约束就好了。

只看该作者 · 2012-3-12 19:08

只看该作者 · 2012-3-12 19:23

上图是一个月来尝试的各种计算方式。
各种除法器流水线级数各不相同，工作频率也不相同，但总的运算时间却很难突破。
其中有单周期除法，100ns
High-Radix,50ns
xilinx生成的除法器，150ns
查表试商法等等
目前做到最快的有三种方式：
1.先计算A*B，1clk，再经查表试商8clk，总共9clk，工作到333MHz，延时30ns
2.先计算A*B，1clk，再经查表试商5clk，总共6clk，工作到200MHz，延时还是30ns
3.计算M=A*B,同时查表求D=2^S/C,1clk;计算N=M*D,1clk;商Q=N/2^S,直接移位，计算R=Q*C-M,1clk;比较R与C，修正Q,1clk;总共4clk,跑到166MHz，延时24ns;很难提高速度;插入合适的寄存器后,能跑到200MHz,但是需要6clk,延时还是30ns

只看该作者 · 2012-3-12 22:44

我大概试了下，确实很难突破。
fpga实现除法是基于组合逻辑，这样的话，光靠eda工具产生除法电路，应该是做不到了，人能干预的仅仅是时序约束部分。

1万 · 2012-3-13 05:10

我只懂verilog，看不懂vhdl。不过我仍然保持我的怀疑：
1）作者的vhdl算法实现跟他**开头的文字描述，看上去不一致；文字描述了依赖于时钟的移位操作，既然是这样我认为不可能在两个cycle内就得到除法结果。
2） ...
GavinZ 发表于 2012-3-12 14:06

多个移位操作是可以一个时钟内完成的。至少乘法器是可以单时钟内完成。

1万 · 2012-3-15 17:47

多个移位操作是可以一个时钟内完成的。至少乘法器是可以单时钟内完成。
李冬发发表于 2012-3-13 05:10

围观冬发哥！！

只看该作者 · 2012-3-16 13:59

那一篇号称只用2周期做除法运算的**不是NB，是SB！

专栏首页

一个超级难的简单计算题

相关下载

相关帖子

无冕之王奖章

沉静之湖泊

十世金身

技术导师奖章

核心会员奖章

坚毅之洋流

技术奇才奖章

突出贡献奖章

伴坛终老

七世轮回

技术高手奖章

技术领袖奖章

社区建设奖章

湍急之河流