快速启发式ESOP电路面积优化算法

Fast Heuristic Area Optimization Algorithm for ESOP Circuits

针对积之异或和(ESOP)电路面积优化的时间效率问题,提出一种快速的启发式算法.该算法使用多输出立方体表示乘积项,首先由基于伪Kronecker判决图的方法得到初始ESOP覆盖,然后使用启发式局部极性转换与局部变换交替迭代的方式进行面积优化.为提高算法效率,启发式局部极性转换仅尝试改变立方体中单个变量的极性,并且仅接受对减少电路面积有帮助的极性转换,该转换有助于使优化过程跳出局部极小;局部变换则通过对ESOP覆盖中距离为1或2的立方体进行变形来减少电路面积,该变换有助于算法的收敛.实验结果表明,文中算法能够适用于具有较多输入变量的多输出电路;与MPRM电路相比,ESOP电路能够降低电路面积开销;与其他ESOP电路优化算法相比,该算法能够显著改善面积优化的时间效率.

A fast heuristic algorithm is proposed to reduce the time consumed by area optimization of exclu-sive-or sum-of-product (ESOP) circuits. The proposed algorithm uses multi-output cubes to represent prod-uct terms, it first obtains an initial ESOP cover by using pseudo Kronecker decision diagram based approach, and then iteratively applies heuristic local polarity conversion and local transformation to optimize ESOP. In order to improve the algorithm efficiency, heuristic local polarity conversion only attempts to change the polarity of one variable in cubes, and only accepts the changes that can reduce the area, it helps the algo-rithm to escape from local minima. Local transformation reduces the area by reshaping cubes with distance of one or two, and helps the algorithm to converge. Experimental results show that, the proposed algorithm can be applied to multi-output circuits with very large number of input variables. In comparison with MPRM circuits, ESOP circuits can reduce the area overhead. In comparison with other area optimization algorithms for ESOP circuits, the proposed algorithm can significantly improve the time efficiency.