Порядок решения топологических задач и их основное содержание - Проектирование цифровых микросхем и печатных плат

Решение топологических задач начинается с этапа Графо-теоретического описания принципиальной схемы. Один из приемов состоит в том, что радиоэлемент представляется в виде вершины графа. Все как будто бы просто, но здесь есть подводные камни, которые связаны с представлением многовыводных элементов.

Существует большое количество алгоритмов решения топологических задач. Подавляющее большинство из них оперируют матрицами, и оно делятся на два больших класса: Параллельные алгоритмы (в которых преобразования ведутся над графом в целом), и Итерационные (ведутся пошаговые изменения графа). Эти изменения могут быть целенаправленными и случайными с последующими оценками результатов.

Алгоритм последовательного разбиения предполагает разбиение графа на куски с заданным количеством вершин в каждом куске. Алгоритм направлен на реализацию критерия разбиения - минимум числа соединительных ребер. Следовательно, число ребер внутри кусков графа должно быть максимальным. Поэтому в основе алгоритма лежит последовательное формирование кусков графа путем наращивания кусков по принципу связности вершин.

Следующий шаг - решение задачи размещения. Для ее решения используется ряд алгоритмов, среди которых выделяется простотой и эффективностью Параллельный алгоритм обратного размещения. Он может быть использован в ручном варианте решения даже нетривиальных задач размещения.

Для реализации алгоритма задается матрица соединений и матрица расстояний для коммутационного поля. Далее ранжируются вершины по возрастанию их степени:

r(X1) < r(X2) < r(X3) <... < r(XN).

В данном случае индексы 1, 2, 3,..., N обозначают не номера вершин в графе, а их порядок в соответствии с возрастанием степени вершины.

На следующем шаге ранжируются позиции коммутационного поля в порядке убывания их характеристик:

D1 > d2 > d3 >... >dN,

Где DN - центральная позиция.

В данной записи смысл нижних индексов аналогичен отмеченному выше.

В большинстве случаев число вершин задается равным числу позиций коммутационного поля (в любом случае не больше).

Само размещение проводится следующим образом: вершина X1 ставится в позицию D1, вершина X2 в позицию D2 и так далее. Таким образом осуществляется одновременное размещение вершин графа на позициях коммутационного поля.

Существует достаточно много различных алгоритмов трассировки, которые имеют различную эффективность. Одни алгоритмы более приемлемы на начальных этапах трассировки при свободном от трасс коммутационном поле. Другие алгоритмы более эффективны при уже заполненном трассами коммутационном поле. Уяснение сущности алгоритмов трассировки будет рассмотрено на примере базового - волнового алгоритма.

Похожие статьи




Порядок решения топологических задач и их основное содержание - Проектирование цифровых микросхем и печатных плат

Предыдущая | Следующая