Исследование и разработка методов трассировки проводящих покрытий БИС на основе стратегии эволюционного поиска

• Автор: Сергеев, Александр Сергеевич
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Ростов-на-Дону
• Количество страниц: 171 с.

1. Разработка алгоритма формирования сети трасс

1.1. Краткий обзор методов трассировки соединений

1.2. Алгоритм формирования сети трасс

1.3. Оценки сложности и сравнительные характеристики алгоритма ФСТ.

1.4. Выводы

2. Применение алгоритма ФСТ для решения задачи трассировки

элементов БИС

2.1. Алгоритм построения кратчайших связывающих деревьев цепей

2.2. Оценки трудоемкости и основные свойства алгоритма.

2.3. Оптимальное размещение кратчайших связывающих деревьев на КП на основе эволюционной оптимизации клики 1рафа пересечений
цепей
2.4. Минимизация числа внутрисхемных пересечений цепей внутри
канала.
2.5. Выводы
3. Разработка параллельных алгоритмов трассировки на основе
алгоритма ФСТ
3.1. Параллельный алгоритм ФСТ и описание его реализации на МВС
3.2. Организация вычислительного процесса при использовании МВС
3.3. Оценка трудоемкости параллельного алгоритма ФСТ.
3.4. Описание применения паратлельного алгоритма ФСТ для реализации
процесса трассировки.
3.5. Алгоритмы представления поверхностей слоев БИС в памяти МВС
3.6. Выводы.
4. Разработка пакета прикладных программ и результаты
экспериментальной реализации
4.1. Краткое описание основных функциональных характеристик
программы трассировки и структуры пакета прикладных программ .
4.2. Результаты экспериментальной реализации генетического алгоритма и
сравнительные характеристики
4.3. Выводы.
5. Заключение.
Литература


Т они смежны дискрету х, принадлежащему маршруту и существует волновой путь между ними и дискретом 8 они имеют волновую нитку. Таким образом, можно утверждать, что последовательно определенные маршруты и ш содержат по крайней мере единственные дискреты Х И ХЬ такие, ЧТО Х Ш, Х т, Рх РХ, Рх РХ, т. Х , принадлежащего маршруту п смежного дискрета х, такого, что X Ш т. Ш, Рх X 1 целая часть волновой нитки дискрета X на единицу меньше целой части нитки дискрета X означает существование последующего маршрута т,, т. Т до Х дискрет смежен X, принадлежащему маршруту от Т до 8 и существует волновой путь от 8 до X т. X имеет волновую нитку. Отсюда следует, что число маршрутов в сети не может быть меньше числа дискретов КП Х, Х2, . Хк , ДЛЯ которых РХ Рх2 . РХ, т. Действительно, т. Блоксхема алгоритма показана на рис. КП представляется матрицей, обозначаемой М, элементу Му присваивается начальное значение, равное нитке соответствующего дискрета КП. Как следует из схемы, блоки используются для задания начальных значений и преобразования матрицы КП, блоки для определения маршрута, блоки 2 используются для нахождения элемента матрицы, подлежащего блокировке, при его нахождении производится блокировка данного дискрета с последующей передачей управления на блоки для определения подмаршрута, имеющего в качестве начального дискрет, предшествующий блокируемому блоки , если такого дискрета, удовлетворяющего условию блокировки, не существует, то работа алгоритма заканчивается. НАЧАЛО
Г Ввод исходно . Маршрут определн , снятие блокировки
Рис.