Student Projects

VE/VM450

Effective Rewriting Strategy for Digital Circuit Optimization

Instructors: Prof. Weikang Qian, Prof. Chong han
Team Members: Yifan Cao, Xingyun Mao, Hanyu Wang, Yujie Chen, Zhiyu Chen

Project Video

Team Members

Team Members:

Yifan Cao, Xingyun Mao, Hanyu Wang, Yujie Chen, Zhiyu Chen

Instructors:

Prof. Weikang Qian, Prof. Chong han

Project Description

Problem

For some digital circuits, it is possible to find circuits with less gates but with the same Boolean function. This kind of area optimization is desired because smaller area will lower the power consumption. Given the modern very large scale integrated circuits (VLSI) like Fig. 1, computer aided tools are needed for such optimization. This project aims at designing an effective algorithm to achieve area optimization, and also building a user-friendly graphical user interface for the algorithm.

Fig. 1 Circuit diagram of Intel i7 CPU [1]

Concept Generation

The project consists of an optimizer and a Graphical User Interface (GUI). The optimizer implements digital circuit optimization through a rewriting algorithm based on Simulated Annealing, which enables the circuits to be optimized close to the global area minimum. The GUI visualizes the process of the optimization through easy operations on the monitor, gird, shell, and buttons.

Fig. 2 Concept Diagram

Design Description

We improve the current rewriting strategy by utilizing the Simulated Annealing method. From the local optimum, our algorithm applies rewrite, refactor and resubstitution on the circuit that accept negative changes with a certain probability and then have positive changes to try not be stuck at the local. We also build a GUI with pygame that contains gate selection buttons, a node grid, an information board showing the current circuit area, run and clear buttons and a shell. Most operations can be managed with mouse clicks, including placing nodes and drawing connections. We can use the mouse wheel to zoom in and out the grid.

Fig. 3 The Graphical User Interface

Implementation and Results

GUI Implementation is shown in Fig. 3，and the figure of circuit area over rewriting iteration is shown in Fig. 4. The methods with SA have relatively small area.

Fig. 4 Area reduction of SA methods

Validation

Validation Process:
For the effect of area reduction, compare the results of our program with that from original tool ABC. For run time, a timer in C++ can be used to measure it. For fraction of suitable circuits, we process a large amount sample circuits on our program and detect whether there are any bugs.
Some other specifications can also be verified using easy experiments.
Validation Results:
According to validation part, most specifications can be met.
√ Fraction of circuit’s function not changed = 100 %
√ Fraction of area reduced >= 15%
√ Fraction of suitable circuits=100%
√ Runtime <= 600s
√ Number of command lines/clicks <=3
√ Correctness of visualized circuits
• Storage usage <= 30 MBytes
√ means verified and · means to be determined.

Fig. 5 The reduced circuit area

Conclusion

Based on local rewriting operations changing some cuts of a digital circuit, the Simulated Annealing method can be applied to make the circuit area closer to the global minimum. Also, it is helpful to build a GUI which is easy to operate and can visualize the optimization process.

Acknowledgement

Prof. Weikang Qian, Prof. Chong Han from UM-SJTU Joint Institute

Reference

[1]http://computerscience.chemeketa.edu/cs160Reader/_images/coreI7.jpg

UM-SJTU JOINT INSTITUTE