Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры
Аннотация
Рассмотрено решение задачи верификации связности электрических соединений в топологии сверхбольших интегральных схем (СБИС). Эффективное использование вычислительных ресурсов базируется на построении квазилинейных алгоритмов вычислительной (временной и емкостной) сложности. Рассматриваются следующие алгоритмы: заметания плоскости прямой для построения графа электрических соединений; выделения подмножеств связанных вершин в компонентах связности неориентированного графа большой размерности для определения электрически связанных контактов; установления изоморфизма компонентно-полных раскрашенных графов для сравнения восстановленного списка с исходным списком электрических соединений. Предложенное решение имеет временную сложность O(N + N log2 N ) и емкостную сложность O(s + N ), где N – число элементов топологии и s – число контактов в исходной электрической схеме.
Об авторе
Г. Н. БрусникинРоссия
Брусникин Геннадий Николаевич, кандидат технических наук, старший научный сотрудник, доцент
124498, Москва, Зеленоград, пл. Шокина, д. 1
Список литературы
1. Sharathkumar R., Maheshwari P., Gupta P. A practical algorithm for connectivity extraction for very large VLSI layouts. Conference Proceedings: 49th IEEE International Midwest Symposium on Circuits and Systems, San Juan, 2006.
2. Bentley J. L., Ottmann T. A. Algorithms for reporting and counting geometric intersections // IEEE Transactions on Computers. 1979. C 28 (9). P. 643–647.
3. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989. 478 с.
4. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ / 2 е изд. М.: Вильямс, 2005. 1296 с.
5. Потопахин В. В. Искусство алгоритмизации. М.: ДМК Пресс, 2011. 320 с.
6. Брусникин Г. Н., Замордуев С. А. Алгоритмы контроля топологии матричных БИС на соответствие электрической схеме // Электронная техника. 1984. № 6. С. 34–36.
7. Brusnikin G. N., Loshakov V. N. Methods and algorithms for hierarchical layout synthesis of VLSI circuits. Proceedings of a joint Symposium Information processing and Software Systems Design Automation, 1990. P. 348–353.
8. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. М.: Вильямс, 2007. 824 с.
Для цитирования:
Брусникин Г.Н. Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры. Вопросы радиоэлектроники. 2019;(8):21-25. https://doi.org/10.21778/2218-5453-2019-8-21-25
For citation:
Brusnikin G.N. Verification of connectivity of electrical connections in topology of radio electronic equipment products. Issues of radio electronics. 2019;(8):21-25. (In Russ.) https://doi.org/10.21778/2218-5453-2019-8-21-25