Исследование и разработка метода планировки цепей СБИС с равномерным заполнением области трассировки

Содержание
Введение
Глава 1. Обзор алгоритмов и методов планировки цепей
1.1. Этапы решения задачи трассировки.
1.2. Модели представления коммутационного пространства
1.3. Методы планировки цепей
1.3.1. Алгоритмы лабиринтной трассировки
1.3.2. Алгоритмы трассировки многотерминальных цепей
1.3.3. Методы оптимизации множества цепей.
1.4. Алгоритмы планировки цепей с конкурса БРР .
1.5. Выводы.
Глава 2. Алгоритм построения множества деревьев Штейнера
2.1. Необходимость разработки нового алгоритма для построения деревьев Штейнера.
2.2. Постановка задачи построения семейства деревьев Штейнера.
2.3. Алгоритм построения семейства деревьев Штейнера
2.3.1. Алгоритм построения семейства остовных деревьев
2.3.2. Алгоритм преобразования остовных деревьев к деревьям Штейнера с ортогональными ребрами.
2. 4. Фильтрация семейства деревьев.
2.4.1. Оценка близости двух деревьев
2.4.2. Фильтрация семейства деревьев Штейнера.
2.5. Выводы.
Глава 3. Метод планировки цепей с использованием семейств деревьев Штейнера
3.1. Постановка задачи
3.1. Выбор деревьев для равномерного заполнения области трассировки
3.2. Алгоритм оптимизации с использованием семейства деревьев Штейнера.
3.2.1. Целевая функция для оценки распределения загруженности области трассировки
3.2.2. Алгоритм выбора деревьев из семейства
3.3. Демонстрация работы алгоритма выбора деревьев Штейнера.
3.5. Выводы.
Глава 4. Программная реализация метода планировки цепей и результаты тестирования
4.1. Программная реализация метода планировки цепей
4.1.1. Программная реализация алгоритма генерации семейства деревьев Штейнера
4.1.2. Программная реализация алгоритма выбора деревьев Штейнера
4.2. Исследование реализации алгоритмов
4.2.1. Результаты тестирования быстродействия
4.2.2. Результаты тестирования эффективности предложенных алгоритмов.
4.4. Выводы.
Заключение
Список литературы