Вопросы радиоэлектроники. 2019; : 21-25
Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры
https://doi.org/10.21778/2218-5453-2019-8-21-25Аннотация
Рассмотрено решение задачи верификации связности электрических соединений в топологии сверхбольших интегральных схем (СБИС). Эффективное использование вычислительных ресурсов базируется на построении квазилинейных алгоритмов вычислительной (временной и емкостной) сложности. Рассматриваются следующие алгоритмы: заметания плоскости прямой для построения графа электрических соединений; выделения подмножеств связанных вершин в компонентах связности неориентированного графа большой размерности для определения электрически связанных контактов; установления изоморфизма компонентно-полных раскрашенных графов для сравнения восстановленного списка с исходным списком электрических соединений. Предложенное решение имеет временную сложность O(N + N log2 N ) и емкостную сложность O(s + N ), где N – число элементов топологии и s – число контактов в исходной электрической схеме.
Список литературы
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 с.
Issues of radio electronics. 2019; : 21-25
Verification of connectivity of electrical connections in topology of radio electronic equipment products
https://doi.org/10.21778/2218-5453-2019-8-21-25Abstract
The solution of the problem of verifying the connectivity of electrical connections in the VLSI topology is considered. Effective use of computing resources is based on the use of quasi‑linear computational (temporal and capacitive) complexity of algorithms: sweeping the plane of a straight line for constructing a graph of electrical connections; allocation of subsets of connected vertices in the components of the connection of an undirected graph of large dimension for the determination of electrically connected contacts; establish isomorphism of component‑full colored graphs for comparing the restored list with the original list of electrical connections The proposed solution has a time complexity O(N + N log2 N ) and the capacitive complexity O(s + N ), where N is the number of elements in the topology and s is the number of contacts in the source circuit.
References
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. Preparata F., Sheimos M. Vychislitel'naya geometriya: vvedenie. M.: Mir, 1989. 478 s.
4. Kormen T. X., Leizerson Ch. I., Rivest R. L., Shtain K. Algoritmy: postroenie i analiz / 2 e izd. M.: Vil'yams, 2005. 1296 s.
5. Potopakhin V. V. Iskusstvo algoritmizatsii. M.: DMK Press, 2011. 320 s.
6. Brusnikin G. N., Zamorduev S. A. Algoritmy kontrolya topologii matrichnykh BIS na sootvetstvie elektricheskoi skheme // Elektronnaya tekhnika. 1984. № 6. S. 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. Knut D. Iskusstvo programmirovaniya. T. 3. Sortirovka i poisk. M.: Vil'yams, 2007. 824 s.
