informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-10Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGМНОГОКРАТНАЯ СВЕРТКА РЕГУЛЯРНЫХ СТРУКТУР НА ОСНОВЕ РЕШЕНИЯ ЛОГИЧЕСКИХ УРАВНЕНИЙMULTIPLE FOLDING OF REGULAR STRUCTURES VIA SOLVING LOGIC EQUATIONSЧеремисиноваЛ. Д.CheremisinovaL. D.cld@newman.bas-net.byОбъединенный институт проблем информатики НАН БеларусиBelarus201525092016018089Copyright © Черемисинова Л.Д., 20162016Черемисинова Л.Д.Cheremisinova L.D.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/10

Рассматривается задача минимизации площади регулярных матричных структур заказных СБИС методом многократной свертки. Предлагается метод решения ключевой проблемы многократной свертки – проверки реализуемости множества свертки, который основывается на сведении задачи к решению логического уравнения и проверке выполнимости конъюнктивной нормальной формы.

The problem under consideration is to reduce the area of the layout of regular VLSI structures by means of their multiple folding. The method of solving the key problem of multiple folding, which is implementability checking of the folding set, is suggested. The method is based on the task reduction to solving a logic equation and checking Boolean satisfiability of a conjunctive normal form.

ReferencesУльман, Дж. Вычислительные аспекты СБИС / Дж. Ульман. – М. : Радио и связь, 1990. – 480 с.Ульман, Дж. Вычислительные аспекты СБИС / Дж. Ульман. – М. : Радио и связь, 1990. – 480 с.Бибило, П.Н. Кремниевая компиляция заказных СБИС / П.Н. Бибило. – Минск : Ин-т техн. кибернетики АН Беларуси, 1996. – 268 с.Бибило, П.Н. Кремниевая компиляция заказных СБИС / П.Н. Бибило. – Минск : Ин-т техн. кибернетики АН Беларуси, 1996. – 268 с.Biswas, N.N. Logic design theory / N.N. Biswas. – Prentice-Hall International, 1993. – 306 p.Biswas, N.N. Logic design theory / N.N. Biswas. – Prentice-Hall International, 1993. – 306 p.Hachtel, G.D. An Algorithm for optimal PLA Folding / G.D. Hachtel, A.R. Newton, A.L. Sangiovanni-Vincentelli // IEEE Trans. Computer-Aided Design of Integrated Circuit Syst. – 1982. – Vol. CAD-1, no. 2. – P. 63–77.Hachtel, G.D. An Algorithm for optimal PLA Folding / G.D. Hachtel, A.R. Newton, A.L. Sangiovanni-Vincentelli // IEEE Trans. Computer-Aided Design of Integrated Circuit Syst. – 1982. – Vol. CAD-1, no. 2. – P. 63–77.DeMicheli, G.A. Multiple Constrained Folding of Programmable Logic Arrays: Theory and Applications / G.A. DeMicheli, A.L. Sangiovanni-Vincentelli // IEEE Trans. Computer-Aided Design. – 1983. – Vol. CAD-2, no. 3. – P. 151–167.DeMicheli, G.A. Multiple Constrained Folding of Programmable Logic Arrays: Theory and Applications / G.A. DeMicheli, A.L. Sangiovanni-Vincentelli // IEEE Trans. Computer-Aided Design. – 1983. – Vol. CAD-2, no. 3. – P. 151–167.Черемисинова, Л.Д. Минимизация площади регулярных матричных структур заказных СБИС / Л.Д. Черемисинова // Информатика. – 2004. – № 1. – С. 121–131.Черемисинова, Л.Д. Минимизация площади регулярных матричных структур заказных СБИС / Л.Д. Черемисинова // Информатика. – 2004. – № 1. – С. 121–131.Минимизация площади заказных СБИС на этапе топологического проектирования цифровых схем / Л.Д. Черемисинова [и др.] // Управляющие системы и машины. – 2011. – № 4 (240). – С. 42–50.Минимизация площади заказных СБИС на этапе топологического проектирования цифровых схем / Л.Д. Черемисинова [и др.] // Управляющие системы и машины. – 2011. – № 4 (240). – С. 42–50.Devadas, S. Optimal Layout via Boolean Satisfiability / S. Devadas // Proc. of Intern. Conf. on Computer-Aided Design (ICCAD ’89). – Santa Clara, CA, USA, 1989. – P. 294–297.Devadas, S. Optimal Layout via Boolean Satisfiability / S. Devadas // Proc. of Intern. Conf. on Computer-Aided Design (ICCAD ’89). – Santa Clara, CA, USA, 1989. – P. 294–297.Optimum PLA Folding through Boolean Satisfiability / J.M. Quintana [et al.] // Asian South Pacific Design Automation Conference (ASP DAC’95). – Chiba, Japan, 1995. – P. 289– 293.Optimum PLA Folding through Boolean Satisfiability / J.M. Quintana [et al.] // Asian South Pacific Design Automation Conference (ASP DAC’95). – Chiba, Japan, 1995. – P. 289– 293.Bryant, R.E. Graph-based algorithms for Boolean function manipulation / R.E. Bryant // IEEE Trans. Computers. – 1986. – Vol. C-35, no. 8. – P. 677–691.Bryant, R.E. Graph-based algorithms for Boolean function manipulation / R.E. Bryant // IEEE Trans. Computers. – 1986. – Vol. C-35, no. 8. – P. 677–691.Черемисинова, Л.Д. Свертка регулярных структур на основе решения логических уравнений / Л.Д. Черемисинова // Танаевские чтения : доклады Четвертой Междунар. науч. конф. (29–30 марта 2010, Минск). – Минск : ОИПИ НАН Беларуси, 2010. – C. 129– 134.Черемисинова, Л.Д. Свертка регулярных структур на основе решения логических уравнений / Л.Д. Черемисинова // Танаевские чтения : доклады Четвертой Междунар. науч. конф. (29–30 марта 2010, Минск). – Минск : ОИПИ НАН Беларуси, 2010. – C. 129– 134.Mahajan, Y. Zchaff2004: An Efficient SAT Solver / Y. Mahajan, Z. Fu , S. Malik // Theory and Applications of Satisfiability Testing (2004 SAT Solver Competition and QBF Solver Evaluation (Invited Papers)). – Berlin, Heidelberg : Springer, 2005. – P. 360–375.Mahajan, Y. Zchaff2004: An Efficient SAT Solver / Y. Mahajan, Z. Fu , S. Malik // Theory and Applications of Satisfiability Testing (2004 SAT Solver Competition and QBF Solver Evaluation (Invited Papers)). – Berlin, Heidelberg : Springer, 2005. – P. 360–375.Goldberg, E. BerkMin: A Fast and Robust SAT-Solver / E. Goldberg , Y. Novikov // Design, Automation, and Test in Europe. – Paris, 2002. – P. 142–149.Goldberg, E. BerkMin: A Fast and Robust SAT-Solver / E. Goldberg , Y. Novikov // Design, Automation, and Test in Europe. – Paris, 2002. – P. 142–149.Eén, N., MiniSat / N. Eén, N. Sörensson [Electronic resource]. – Mode of access : http://www.cs.chalmers.se/Cs/Research/FormalMethods/ MiniSat. – Date of access : 09.02.2015.Eén, N., MiniSat / N. Eén, N. Sörensson [Electronic resource]. – Mode of access : http://www.cs.chalmers.se/Cs/Research/FormalMethods/ MiniSat. – Date of access : 09.02.2015.Lecky, I.E. Graph theoretic flgorithms for the PLA folding problem / I.E. Lecky, O.I. Murphy, R.G. Abshe // IEEE Trans. Computer-Aided Design. – 1989. – Vol. 8, no. 9. – P. 1014–1021.Lecky, I.E. Graph theoretic flgorithms for the PLA folding problem / I.E. Lecky, O.I. Murphy, R.G. Abshe // IEEE Trans. Computer-Aided Design. – 1989. – Vol. 8, no. 9. – P. 1014–1021.Cheremisinova, L.D. Some results in optimal PLA folding / L.D. Cheremisinova // Proc. of the Third Intern. Conf. on Computer-Aided Design of Discrete Devices (CAD DD’99). – Minsk UIIP NAS B, 1999. – Vol. 1. – P. 59–64.Cheremisinova, L.D. Some results in optimal PLA folding / L.D. Cheremisinova // Proc. of the Third Intern. Conf. on Computer-Aided Design of Discrete Devices (CAD DD’99). – Minsk UIIP NAS B, 1999. – Vol. 1. – P. 59–64.Cheremisinova, L. SAT-Based Approach to Verification of Logical Descriptions with Functional Indeterminacy / L. Cheremisinova, D. Novikov // 8th Intern. Workchop on Boolean problems. – Freiberg (Sachsen), 2008. – P. 59–66.Cheremisinova, L. SAT-Based Approach to Verification of Logical Descriptions with Functional Indeterminacy / L. Cheremisinova, D. Novikov // 8th Intern. Workchop on Boolean problems. – Freiberg (Sachsen), 2008. – P. 59–66.

The authors declare that there are no conflicts of interest present.