从一个小案例学IC设计的算法优化

IT圈老男孩1 · 发表于 2023-2-22 09:28

今天讲一个很简单的IC设计算法优化案例，希望大家能够从中找到芯片设计优化的一些方法。案例取自本人工作开发的一点小经历，省去背景和细节，单独拎出一个局部讲一下。

题目是这样的：有一个4bit宽的整数，要求实现其乘以0.675之后的下取整。

怎么用verilog实现呢？
看到这个题，你当然不能直接写: assign output = input *0.675;
因为被乘数是个小数。如果被乘数是整数的话，这么写“*”倒也可以，只不过最后会用乘法器来实现，浪费面积而已。

最简单的办法就是用查找表：
0 * 0.675，得到0，下取整得到0；
1 * 0.675，得到0.675，下取整得到0；
2* 0.675，得到1.35，下取整得到1；
3* 0.675，得到2.025，下取整得到2；
............
15*0.675，得到10.125，下取整得到10；

高级一点的办法是把0.675转换成分数。
0.675=27/40;
先乘以27，再除以40；
乘以27很简单，可以拆成乘以（16+8+2+1），采用左移累加来实现。但是分母是40，没法通过右移来实现除法。除非分母是32或者64。

下面就是我的优化步骤：
（1）对于分数乘法，我们希望分母是2的指数，分子无所谓，这样就可以用简单的移位实现分数乘法；
（2）0.675如果采用64为分母，最接近的分数是：43/64；
（3）0.675用43/64代替，误差为0.27%，误差非常小，可以忽略不计；
（4）经验证，4bit整数乘以0.675做下取整，跟乘以43/64做下取整，得到的结果是一模一样的（有兴趣可以自己验证下）；
（5）将原题目等价成：4bit整数乘以43/64，然后做下取整；
（6）将43/64改写成（32+8+2+1）/64；
所以：output =( (input<<5) + (input<<3) + (input <<1) + input ) >>6;
从而避免了采用查找表来实现所需算法。

当然本例中，这么做是不是一定更加节省面积，其实还不好说。因为新算法用了3个加法器，查找表只有16个取值，新算法未必比查找表更节省。
但是假设输入位宽变宽为10bit，那么输入会有1024个取值，查找表的开销将会十分庞大，采用移位计算就会更有优势。

欢迎大家关注我的微信公众号：半导学社。

franciscochonge · 发表于 2023-2-22 09:30

【当然本例中，这么做是不是一定更加节省面积，其实还不好说。因为新算法用了3个加法器，查找表只有16个取值，新算法未必比查找表更节省。
但是假设输入位宽变宽为10bit，那么输入会有1024个取值，查找表的开销将会十分庞大，采用移位计算就会更有优势。】看文章都不看全么……

jquave · 发表于 2023-2-22 09:39

这个优化方向和写C很类似，哈哈

redhat9i · 发表于 2023-2-22 09:49

妙哉，妙哉。学习了一个

super1 · 发表于 2023-2-22 09:55

又是左移又是右移的，还要用加，还有误差，一共四bit输入，最多16种可能，做个查找表不更直观，误差0，都不用验算，省资源面积，timing肯定也更好

JoshWindsor · 发表于 2023-2-22 09:59

*11/16 就可以了，2个加法器。

KaaPexei · 发表于 2023-2-22 09:59

没有误差的，左移右移也不占资源的。

Arzie100 · 发表于 2023-2-22 10:08

误差大于千分之一，如果输入10bit的话43/64就不够用了。

unityloverz · 发表于 2023-2-22 10:13

对，10bit的话也要增大分母，256，512,1024等的分母说不定可以

TheLudGamer · 发表于 2023-2-22 10:13

我觉得你引用的这段话是作者看到我评论再加的

		自动登录	找回密码
密码			立即注册