МНОГОКРАТНАЯ СВЕРТКА РЕГУЛЯРНЫХ СТРУКТУР НА ОСНОВЕ РЕШЕНИЯ ЛОГИЧЕСКИХ УРАВНЕНИЙ
Аннотация
Рассматривается задача минимизации площади регулярных матричных структур заказных СБИС методом многократной свертки. Предлагается метод решения ключевой проблемы многократной свертки – проверки реализуемости множества свертки, который основывается на сведении задачи к решению логического уравнения и проверке выполнимости конъюнктивной нормальной формы.
Список литературы
1. Ульман, Дж. Вычислительные аспекты СБИС / Дж. Ульман. – М. : Радио и связь, 1990. – 480 с.
2. Бибило, П.Н. Кремниевая компиляция заказных СБИС / П.Н. Бибило. – Минск : Ин-т техн. кибернетики АН Беларуси, 1996. – 268 с.
3. Biswas, N.N. Logic design theory / N.N. Biswas. – Prentice-Hall International, 1993. – 306 p.
4. 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.
5. 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.
6. Черемисинова, Л.Д. Минимизация площади регулярных матричных структур заказных СБИС / Л.Д. Черемисинова // Информатика. – 2004. – № 1. – С. 121–131.
7. Минимизация площади заказных СБИС на этапе топологического проектирования цифровых схем / Л.Д. Черемисинова [и др.] // Управляющие системы и машины. – 2011. – № 4 (240). – С. 42–50.
8. 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.
9. 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.
10. 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.
11. Черемисинова, Л.Д. Свертка регулярных структур на основе решения логических уравнений / Л.Д. Черемисинова // Танаевские чтения : доклады Четвертой Междунар. науч. конф. (29–30 марта 2010, Минск). – Минск : ОИПИ НАН Беларуси, 2010. – C. 129– 134.
12. 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.
13. Goldberg, E. BerkMin: A Fast and Robust SAT-Solver / E. Goldberg , Y. Novikov // Design, Automation, and Test in Europe. – Paris, 2002. – P. 142–149.
14. 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.
15. 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.
16. 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.
17. 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.
Рецензия
Для цитирования:
Черемисинова Л.Д. МНОГОКРАТНАЯ СВЕРТКА РЕГУЛЯРНЫХ СТРУКТУР НА ОСНОВЕ РЕШЕНИЯ ЛОГИЧЕСКИХ УРАВНЕНИЙ. Информатика. 2015;(1):80-89.
For citation:
Cheremisinova L.D. MULTIPLE FOLDING OF REGULAR STRUCTURES VIA SOLVING LOGIC EQUATIONS. Informatics. 2015;(1):80-89. (In Russ.)
Просмотров: 927
Послать статью по эл. почте 