ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ  ПРОЕКТИРОВАНИИ ИНТЕГРАЛЬНЫХ СХЕМ

Демидов Даниил Валентинович

2014 , ТОМ 14, НОМЕР 5 ( сентябрь-октябрь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

УДК 004.312.2, 004.021, 510.649

ИСПОЛЬЗОВАНИЕ РЕЛЯЦИОННОЙ ТЕОРИИ ПРИ ОПТИМАЛЬНОМ ПРОЕКТИРОВАНИИ ИНТЕГРАЛЬНЫХ СХЕМ

Демидов Д.В.

Читать статью полностью

Аннотация

Предложен подход к адаптации реляционной теории для решения задач систем автоматизированного проектирования интегральных схем. Разработан алгоритм оптимального поиска неявных Don't Care (безразличных) значений. Алгоритм описан в терминах адаптированной теории, что позволило получить простое описание алгоритма как для неформального понимания, так и для формального анализа. Предложенный подход позволяет использо- вать позитивный опыт реляционных баз данных по эффективной (в том числе распределенной) реализации операций реляционной алгебры. Проведен сравнительный анализ предложенного алгоритма и классического алгоритма оптимального поиска неявных Don't Care значений. В ходе сравнительного анализа формально доказана корректность предложенного алгоритма. Показано, что предложенный алгоритм, по сравнению с классическим, имеет значительно меньшую асимптотическую сложность в худшем случае. Поиск неявных Don't Care значений в процессе проектирования интегральных схем позволяет повысить такие качества схем, как занимаемая площадь кристалла, энергопотребление, верифицируемость и надежность. Однако классический алгоритм оптимального поиска неявных Don't Care значений не применяется на практике ввиду его чрезмерно высокой вычислительной сложности. Применение алгоритмов субоптимального поиска не позволяет в полной мере реализовать возможности оптимизации интегральных схем. Реализация предложенного в работе алгоритма в системах автоматизированного проектирования интегральных схем целесообразна в силу значительно меньшей вычислительной сложности, потенциально позволяет улучшить соотношение скорости процесса разработки и качества получаемых интегральных схем в аспектах занимаемой площади кристалла, энергопотребления, верифицируемости и надежности. Предложенный подход делает возможным создание распределенной системы автоматизированного проектирования интегральных схем, что позволит повысить доступную системе вычислительную мощность и автоматизировать проектирование более сложных интегральных схем соответственно.

Ключевые слова: САПР, интегральные схемы, оптимизация комбинационных схем, логические сети, частично определенные булевы функции, неявные Don't Care значения, ODC, реляционная теория, реляционная алгебра, естественное соединение.

Список литературы

1. De Micheli G. Synchronous logic synthesis: algorithms for cycle-time minimization // IEEE Transactions

on Computer-Aided Design of Integrated Circuits and Systems. 1991. V. 10. N 1. P. 63–73.

2. Hachtel G.D., Rho J.K., Somenzi F., Jacoby R. Exact and heuristic algorithms for the minimization of incompletely

specified state machines // Proc. of European Conference on Design Automation. Amsterdam,

Netherlands, 1992. P. 184–191.

3. Bogatyrev V.A., Bogatyrev S.V., Golubev I.Yu. Optimization and the process of task distribution between

computer system clusters // Automatic Control and Computer Sciences. 2012. V. 46. N 3. P. 103–111.

4. Sentovich E.M., Singh K.J., Lavagno L., Moon C., Murgai R., Saldanha A., Savoj H., Stephan P.R.,

Brayton R.K., Sangiovanni-Vincentelli A.L. SIS: A System for Sequential Circuit Synthesis. Technical Report

UCB/ERL M92/41, Electronics Research Lab, Univ. of California, Berkeley, 1992.

5. Pederson D.O. The VIS Group. VIS: Verification Interacting with Synthesis, 1995 [Электронный ресурс].

Режим доступа: http://embedded.eecs.berkeley.edu/Respep/Research/vis, свободный. Яз. англ. (дата об-

ращения 04.12.2013).

6. Bartlett K.A., Brayton R.K., Hachtel G.D., Jacoby R.M., Morrison C.R., Rudell R.L., Sangiovanni-

Vincentelli A., Wang A. Multi-level logic minimization using implicit don’t cares // IEEE Transactions on

Computer-Aided Design of Integrated Circuits and Systems. 1988. V. 7. N 6. P. 723–740.

7. Fujiwara H. Logic Testing and Design for Testability. Cambridge: MIT Press, 1985. 304 p.

8. Chang A.C.L., Reed I.S., Beans A.V. Path sensitization, partial boolean difference and automated fault diagnosis

// IEEE Transactions on Computers. 1972. V. C-21. N 2. P. 189–195.

9. Bogatyrev V.A. Exchange of duplicated computing complexes in fault-tolerant systems // Automatic Control

and Computer Sciences. 2011. V. 45. N 5. P. 268–276.

10. Bogatyrev V.A. Fault tolerance of clusters configurations with direct connection of storage devices // Automatic

Control and Computer Sciences. 2011. V. 45. N 6. P. 330–337.

11. Богатырев В.А., Богатырев С.В. Критерии оптимальности многоуровневых отказоустойчивых ком-

пьютерных систем // Научно-технический вестник СПбГУ ИТМО. 2009. № 5 (63). С. 92–97.

12. Богатырев В.А., Богатырев А.В. Функциональная надежность систем реального времени // Научно-

технический вестник информационных технологий, механики и оптики. 2013. № 4 (86). С. 150–151.

13. Muroga S., Kambayashi Y., Lai H.C., Culliney J.N. Transduction method – design of logic networks based

on permissible functions // IEEE Transactions of Computers. 1989. V. 38. N 10. P. 1404–1424.

14. Lin B., Touati H.J., Newton A.R. Don’t care minimization of multi-level sequential logic networks // Proc.

IEEE International Conference on Computer-Aided Design. 1990. P. 414–417.

15. Brayton R.K., Hachtel G., McMullen C., Sangiovanni-Vincentelli A. Logic Minimization Algorithms for

VLSI Synthesis. Kluwer Academic Publishers, 1985. 206 p.

16. Theobald M., Nowick S.M., Wu T. Espresso-HF: a heuristic hazard-free minimizer for two-level logic //

Proceedings - Design Automation Conference. Las Vegas, USA, 1996. P. 71–76.

17. Codd E.F. A relational model of data for large shared data banks // M.D. Computing. 1998. V. 15. N 3.

P. 162–166.

18. Abiteboul S., Hull R., Vianu V. Foundations of Databases. Addison-Wesley, 1995. 685 p.

19. Date C.J., Darwen H. Foundation for Future Database Systems: The Third Manifesto. 2nd ed. Addison-

Wesley, 2000. 608 p.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License