Experimental Comparison of Logic Circuit Synthesis Methods
Maxim Dmitrievich VERSHKOV,
Alexey Aleksandrovich Yagzhov,
Nikita Sergeevitch ROMANOV,
Anna Alekseevna FEDOTOVA,
Egor Pavlovich ZNATNOV https://doi.org/10.15514/ISPRAS-2024-36(4)-10
Abstract
This paper presents the results of an experimental comparison of methods for the synthesis of combinational logic circuits that implement specified Boolean functions. The following methods were considered: the method of Akers, bi-decomposition, the methods of cascades, Minato-Morreale, Reed-Muller and DSD-decomposition. The comparison was based on an estimate of power, delay and area of synthesized logic circuits. The evaluation was carried out without the process of technology mapping of the circuits. These parameters were chosen because they are the main criteria for technology-independent optimization, where these methods are widely used. Boolean functions with the number of arguments from 4 to 10 were used as input data. They were generated on the basis of information on the frequency of occurrence of various NPN-equivalence classes of Boolean functions of 4 variables. As a result of the study, it was found that the Minato-Morreale method is the most universal in solving technology-independent optimization problems and can be used for different criteria.
About the Authors
Maxim Dmitrievich VERSHKOV
Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics.
Russian Federation
Russian Federation
5th year student of the A.N. Tikhonov Moscow Institute of Electronics and Mathematics of the National Research University Higher School of Economics. Research interests: optimization of digital VLSI.
Alexey Aleksandrovich Yagzhov
Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics.
Russian Federation
Russian Federation
4th year student of the A.N. Tikhonov Moscow Institute of Electronics and Mathematics of the National Research University Higher School of Economics. Research interests: optimization of digital VLSI.
Nikita Sergeevitch ROMANOV
Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics.
Russian Federation
Russian Federation
5th year student of the A.N. Tikhonov Moscow Institute of Electronics and Mathematics of the National Research University Higher School of Economics. Research interests: optimization of digital VLSI.
Anna Alekseevna FEDOTOVA
Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics.
Russian Federation
Russian Federation
3th year student of the Faculty of Computer Science of the National Research University Higher School of Economics. Research interests: optimization of digital VLSI.
Egor Pavlovich ZNATNOV
Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics.
Russian Federation
Russian Federation
3th year student of the Faculty of Computer Science of the National Research University Higher School of Economics. Research interests: optimization of digital VLSI.LSI.
References
1. Riener H., Mishchenko A., Soeken M. Exact DAG-aware rewriting. In Proc. of Design, Automation and Test in Europe Conference and Exhibition, 2020, pp. 732–737.
2. Ammes G., Lau W., Ribas R. P. (2018) Comparative analysis of different Boolean function synthesis Methods. In Proc. of Microelectronics Students Forum. Available at: https://sbmicro.org.br/eventos/sforum/volume-18, accessed 01.07.2024.
3. McCluskey E. J. Minimization of Boolean functions. The Bell System Technical Journal, vol. 35, no. 6, 1956, pp. 1417–1444.
4. Choudhury M., Mohanram, K. Bi-decomposition of large Boolean functions using blocking edge graphs. In Proc. of the International Conference on Computer-Aided Design, 2010, pp. 586–591.
5. Wu D., Zhu J. FBDD: A folded logic synthesis system. In Proc. of International Conference on ASIC, 2005, pp. 746–751.
6. Singh E. M. S. K. J., Murgai L. L. C. M. R., Sangiovanni-Vincentelli R. K. B. A. SIS: A system for sequential circuit synthesis. University of California, Berkeley, vol. 94720, 1992, p. 4.
7. ABC. Available at: https://github.com/berkeley-abc/abc, accessed 01.07.2024.
8. Yang S. Logic synthesis and optimization benchmarks user guide: version 3.0. Research Triangle Park, NC, USA: Microelectronics Center of North Carolina (MCNC), 1991, pp. 502-508.
9. Brglez F., Bryan D., Kozminski K. Combinational Profiles of Sequential Benchmark Circuits. In Proc. of the International Symposium of Circuits and Systems, 1989, pp. 1929–1934.
10. Albrecht. C. IWLS 2005 Benchmarks. 2005. Available at: http://iwls.org/iwls2005/benchmarks.html, accessed 01.07.2024.
11. Sasao T., Butler J. T. Worst and best irredundant sum-of-products expressions. IEEE Transactions on Computers, vol. 50, no. 9, 2001, pp. 935–948.
12. Minato S. Fast generation of prime-irredundant covers from binary decision diagrams. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E76-A, no. 6, 1993, pp. 967-973.
13. Akers B. Synthesis of combinational logic using three-input majority gates. In Proc. of 3rd Annual Symposium on Switching Circuit Theory and Logical Design, 1962, pp. 149–157.
14. Pottosin Y. V. Synthesis of combinational circuits by means of bi-decomposition of Boolean functions. Informatics, vol. 19, no. 1, 2022, pp. 7–18.
15. Povarov G. N. A method for synthesis of computing and controlling contact circuits. Automatika i Telemekhanika, vol. 18, no. 2, 1957, pp. 145–162 (in Russian).
16. Harking B. Efficient algorithm for canonical Reed-Muller expansions of Boolean functions. IEE Proceedings E (Computers and Digital Techniques), vol. 137, no. 5, 1990, pp. 366–370.
17. Bertacco V. Scalable Hardware Verification with Symbolic Simulation. Springer Science & Business Media, 2006.
18. Shannon C. E. The synthesis of two-terminal switching circuits. The Bell System Technical Journal, vol. 28, no. 1, 1949, pp. 59–98.
19. Zhegalkin I. I. On the technique of calculating propositions in symbolic logic. Matematicheskii Sbornik, vol. 34, no. 1, 1927, pp. 9-28 (in Russian and French).
20. kitty. Available at: https://github.com/msoeken/kitty, accessed 01.07.2024.
21. STACCATO. Available at: https://web.eecs.umich.edu/staccato/, accessed 01.07.2024.
22. OpenABC-D. Available at: https://github.com/NYU-MLDA/OpenABC, accessed 01.07.2024.
23. Lee S.-Y., Riener H., De Micheli G. Logic resynthesis of majoritybased circuits by top-down decomposition. In Proc. of 24th International Symposium on Design and Diagnostics of Electronic Circuits & Systems, 2021, pp. 105–110.
Review
For citations:
VERSHKOV M.D., Yagzhov A.A., ROMANOV N.S., FEDOTOVA A.A., ZNATNOV E.P. Experimental Comparison of Logic Circuit Synthesis Methods. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2024;36(4):133-142. https://doi.org/10.15514/ISPRAS-2024-36(4)-10
Email this article 