Экспериментальное сравнение методов синтеза логических схем
Максим Дмитриевич ВЕРШКОВ,
Алексей Александрович ЯГЖОВ,
Никита Сергеевич РОМАНОВ,
Анна Алексеевна ФЕДОТОВА,
Егор Павлович ЗНАТНОВ https://doi.org/10.15514/ISPRAS-2024-36(4)-10
Аннотация
В работе описаны результаты экспериментального сравнения методов синтеза комбинационных логических схем, реализующих заданные булевы функции. Рассмотрены следующие методы: Акерса, би-декомпозиции, каскадов, Минато-Морреале, Рида-Маллера и DSD-разложения. Сравнение основывалось на оценке энергопотребления, задержки и площади синтезируемых логических схем. Оценка осуществлялась без процесса технологического отображения схем. Выбор данных параметров обусловлен тем, что они являются основными критериями технологически независимой оптимизации, в которой данные методы находят широкое применение. В качестве исходных данных использовались булевы функции с числом аргументов от 4 до 10, которые были сгенерированы на основе информации о частоте встречаемости различных NPN-классов эквивалентности булевых функций от 4 переменных. В результате исследования было установлено, что метод Минато-Морреале является наиболее универсальным при решении задач технологически независимой оптимизации и может быть использован для различных критериев.
Об авторах
Максим Дмитриевич ВЕРШКОВ
Институт системного программирования РАН,
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Cтудент 5-го курса Московского института электроники и математики им. А.Н. Тихонова Национального исследовательского университета «Высшая школа экономики». Сфера научных интересов: оптимизация цифровых СБИС.
Алексей Александрович ЯГЖОВ
Институт системного программирования РАН,
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Cтудент 4-го курса Московского института электроники и математики им. А.Н. Тихонова Национального исследовательского университета «Высшая школа экономики». Сфера научных интересов: оптимизация цифровых СБИС.
Никита Сергеевич РОМАНОВ
Институт системного программирования РАН,
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Cтудент 5-го курса Московского института электроники и математики им. А.Н. Тихонова Национального исследовательского университета «Высшая школа экономики». Сфера научных интересов: оптимизация цифровых СБИС.
Анна Алексеевна ФЕДОТОВА
Институт системного программирования РАН,
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Cтудентка 3 курса Факультета компьютерных наук Национального исследовательского университета «Высшая школа экономики». Сфера научных интересов: оптимизация цифровых СБИС.
Егор Павлович ЗНАТНОВ
Институт системного программирования РАН,
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Cтудент 3 курса Факультета компьютерных наук Национального исследовательского университета «Высшая школа экономики». Сфера научных интересов: оптимизация цифровых СБИС.
Список литературы
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.
Рецензия
Для цитирования:
ВЕРШКОВ М.Д., ЯГЖОВ А.А., РОМАНОВ Н.С., ФЕДОТОВА А.А., ЗНАТНОВ Е.П. Экспериментальное сравнение методов синтеза логических схем. Труды Института системного программирования РАН. 2024;36(4):133-142. https://doi.org/10.15514/ISPRAS-2024-36(4)-10
For citation:
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
Послать статью по эл. почте 