MULTIPLE FOLDING OF REGULAR STRUCTURES VIA SOLVING LOGIC EQUATIONS
Abstract
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
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.
Review
For citations:
Cheremisinova L.D. MULTIPLE FOLDING OF REGULAR STRUCTURES VIA SOLVING LOGIC EQUATIONS. Informatics. 2015;(1):80-89. (In Russ.)
Views: 928
Email this article 