СВЕРТКА РЕГУЛЯРНЫХ МАТРИЧНЫХ СТРУКТУР ЗАКАЗНЫХ СБИС МЕТОДОМ МОДЕЛИРОВАНИЯ ОТЖИГА
Abstract
Рассматривается задача топологической оптимизации программируемых логических матриц
методом свертки. Предлагаются алгоритмы многократной и простой сверток регулярных струк-
тур СБИС на основе моделирования отжига, позволяющие находить оптимальное или близкое к нему решение задачи свертки. Приводятся результаты исследования предложенных алгоритмов свертки.
About the Authors
Л. Черемисинова
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
И. Логинова
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Ульман, Дж. Вычислительные аспекты СБИС / Дж. Ульман. – М. : Радио и связь,
2. – 480 с.
3. Hachtel, G.D. An Algorithm for optimal PLA Folding / G.D. Hachtel, A.R. Newton,
4. A. L. Sangiovanni-Vincentelli // IEEE Trans. Computer-Aided Design of Integrated Circuit Syst. – 1982. – Vol. CAD-1, № 2. – P. 63–77.
5. DeMicheli, G.A. Multiple Constrained Folding of Programmable Logic Arrays: Theory and
6. Applications / G.A. DeMicheli, Sangiovanni-Vincentelli // IEEE Trans. Computer-Aided Design. – 1983. – Vol. CAD-2, № 3. – P. 151–167.
7. Macii, E. Graph models for PLA folding problems / E. Macii , T. Wolf // International Journal of Systems Science. – 1996. – Vol. 26, № 7. – P. 1439–1445.
8. Wong, D.F. Simulated Annealing for VLSI Design / D.F. Wong, H.W. Leong, C.L. Liu //
9. Boston : Kluwer Academic Publ. – 1988. – 220 p.
10. Hsu, W.-L. Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs / W.-L. Hsu, T.-H. Ma // SIAM J. Comput. – 1999. – Vol. 28, № 3. – P. 1004–1020.
11. Golumbic, M.C. The complexity of comparability graph recognition and coloring / M.C. Golumbic // Computing. – 1977. – Vol. 18. – P. 199–208.
12. Hashimoto, A. Wire Routing by Optimizing Channel Assignment Within Larger Apertures /
13. A. Hashimoto, J. Stevens // Proc. of 8th Design Automation Workshop, DAC '71. – Atlantic City, NJ, USA. – 1971.
14. Equation of State Calculations by Fast Computer Machines / N. Metropolis [et al.] //
15. J. Chemical Physics. – 1953. – Vol. 21, № 6. – P. 1087–1092.
16. Kirkpatrick, S. Optimization by Simulated Annealing / S. Kirkpatrick, Jr.C.D. Gelatt,
17. M.P. Vecchi // Science. – 1983. – Vol. 220(4598). – P. 671–680.
18. Greening, D.R. Simulated Annealing with Errors / D.R. Greening // Ph.D. dissertation, University OF CA Los Angeles. – 1995 [Electronic resourse]. – Mode of access : http: //
19. dan.greening.org/publications/phd.pdf. – Date of access : 28.03.2004.
20. Van Laarhoven, P.J.M. Simulated Annealing: Theory and Applications /
21. P.J.M. Van Laarhoven, E.H.L. Aarts. – Dordrecht : Reidel, 1987.
22. Ingber, L. Optimization of Trading Physics Models of Markets / L. Ingber, R.P. Mondescu // IEEE Trans. Neural Networks. – 2001. – № 12(4). – P. 776–790.
23. Liu, Chun-Yeh. An Efficient Algorithm for Bipartite PLA Folding / Chun-Yeh Liu, Kewal
24. K. Saluja // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. – 1993. – Vol. 12, №. 12. – P. 1839–1847.
25. Лекции по теории графов / В.А. Емеличев [и др.]. – М. : Наука, 1990. – 384 с.
26. Berkeley PLA test set [Electronic resource]. – Mode of access : http://
27. www1.cs.columbia.edu/ ~cs4861/sis/ espresso-examples/. – Date of access : 03.05.2006.
Review
For citations:
, . Informatics. 2012;(4(36)):108-119. (In Russ.)
Views: 530
Email this article 