基于散列表的加法器重写优化算法

Hash Table Based Adder Rewriting Optimization Algorithm

摘要: 在大规模算术集成电路设计领域中，乘法器电路的验证是一重大难题。当前主流的方法是Gröbner基法。在此基础上，研究者们提出了加法器重写等优化方法，但重写过程依赖进位变量且需遍历全部变量，导致验证效率降低。为此，本文利用散列表对该方法进行优化，使用散列表存储所有和位输出变量，遍历表中元素进行扩充，再结合加法器的结构特性去识别加法器，从而不再依赖进位变量并且减少了需要遍历的变量数目。由实验结果可知，优化算法提高了Gröbner基的生成效率，也提高了乘法器的验证效率。

Abstract: In the field of very large scale integration design, the verification of multiplier circuits is a major problem. The current mainstream method is the Gröbner basic method. On this basis, researchers have proposed optimization methods such as adder rewriting, but the rewriting process relies on carrying variables and needs to traverse all variables, resulting in reduced verification efficiency. For this reason, this paper optimizes the method by using a hash table, uses a hash table to store all the sum bit output variables, expands the elements in the traversal table, and then identifies the adder by combining the structural characteristics of the adder, so that it no longer depends on car-rying variables and reduces the number of variables that need to be traversed. The experimental results show that the optimization algorithm improves the generation efficiency of Gröbner basis and the verification efficiency of multipliers.