Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры

Аннотация

Рассмотрено решение задачи верификации связности электрических соединений в топологии сверхбольших интегральных схем (СБИС). Эффективное использование вычислительных ресурсов базируется на построении квазилинейных алгоритмов вычислительной (временной и емкостной) сложности. Рассматриваются следующие алгоритмы: заметания плоскости прямой для построения графа электрических соединений; выделения подмножеств связанных вершин в компонентах связности неориентированного графа большой размерности для определения электрически связанных контактов; установления изоморфизма компонентно-полных раскрашенных графов для сравнения восстановленного списка с исходным списком электрических соединений. Предложенное решение имеет временную сложность O(N + N log2 N ) и емкостную сложность O(s + N ), где N – число элементов топологии и s – число контактов в исходной электрической схеме.