Трассировка межсоединений элементов СБИС, на основе построения кратчайших покрывающих деревьев, с использованием первого алгоритма Штейнера

СОДЕРЖАНИЕ

Введение. 3

1. Содержательная постановка задачи трассировки межсоединений элементов сбис 4

2. Математическая постановка задачи трассировки межсоединений элементов сбис, на основе построения кратчайших покрывающих деревьев. 7

3. Описания первого алгоритма штейнера решения задачи трассировки межсоединений элементов сбис, на основе построения кратчайших деревьев. 9

4. Решение задачи трассировки межсоединений элементов сбис, на основе построения кратчайших деревьев на контрольном примере. 12

5. Описание программы для решения задачи трассировки межсоединений элементов сбис, на основе первого алгоритма штейнера. 18

6. Оценка временной сложности первого алгоритма штейнера для решения задачи трассировки межсоединений элементов сбис, на основе построения кратчайших покрывающих деревьев. 23

Заключение. 28

Список источников. 29

Приложение 1. Листинг программы.. 30

Приложение 2. Экранные формы программы.. 62

ВВЕДЕНИЕ

Современные СБИС и печатные платы содержат миллионы элементов и миллиарды межсоединений, поэтому ручная трассировка становится практически невыполнимой и требует использования специализированных алгоритмов и САПР. Эффективность этапа трассировки напрямую влияет на электрические характеристики устройства, его надёжность и себестоимость, так как длина и топология проводников определяют задержки сигналов, уровни помех и плотность компоновки.

Задача автоматической трассировки межсоединений традиционно формулируется на языке теории графов: область платы представляется графом или решёткой, контакты моделируются терминальными вершинами, а проводники — рёбрами с весами, соответствующими геометрической длине или задержке. В этом контексте построение оптимальной топологии соединений сводится к задаче построения минимального дерева Штейнера, позволяющего соединить заданное множество вершин с минимальной суммарной длиной за счёт введения дополнительных (штейнеровских) точек. Такой подход широко используется в глобальной трассировке и оценке длины межсоединений при проектировании печатных плат.

Несмотря на то что задача минимального (в частности, ортогонального) дерева Штейнера является NP‑трудной[1], на практике применяются эвристические и приближённые алгоритмы, обеспечивающие приемлемое качество решений за полиномиальное время. Разработка и исследование таких алгоритмов, адаптированных к сеточной модели коммутационного поля и технологическим ограничениям (запретные зоны), представляет значительный интерес для повышения степени автоматизации трассировки.

Целью данной работы является разработка и программная реализация алгоритма построения дерева Штейнера в манхэттенской метрике для задачи трассировки межсоединений на печатной плате, а также анализ его вычислительной эффективности на основе пооперационного разложения и оценок асимптотической временной сложности. Реализованный программный комплекс должен обеспечивать визуальное задание исходных данных, построение маршрутов с учётом ограничений и наглядное представление полученной топологии в текстовой и графической формах.