автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Временная верификация и оптимизация размещения компонентов предельных по быстродействию ЭВМ

ВВЕДЕНИЕ.

ГЛАВА 1. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ О НАЗНАЧЕНИЯХ.п

Введение.

1.1. Алгоритмы решения задачи о назначениях.

1.1.1. Точный алгоритм решения задачи о назначениях на матрицах общего вида.

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

1.1.3. Приближенный алгоритм решения задачи о назначениях.

1.2. Применение алгоритмов решения задачи о назначениях в САПР электронной аппаратуры.

1.2.1. Назначение интерфейсных сигналов на периферийные элементы интегральных схем и на контакты разъемов многослойных печатных плат.

1.2.2. Проектирование проводных соединений при корпусировании интегральных схем.

1.3. Алгоритм раскраски ребермультиграфа.

1.4. Применение алгоритма раскраски ребер мультиграфа в САПР электронной аппаратуры.

2.1. Задача разбиения.51

2.1.1. Постановка задачи.51

2.1.2. Алгоритм Лина-Кернигана.52

2.1.3. Алгоритм Фидуччиа-Маттеуса.57

2.1.4. Решение задачи разбиения методом моделирования отжига.57

2.1.5. Другие подходы к решению задачи разбиения.60

2.2. Задача размещения.62

2.2.1. Постановка задачи.62

2.2.2. Конструктивные алгоритмы размещения.63

2.2.3. Min-cut алгоритм.66

2.2.4. Другие подходы к решению задачи размещения.70

2.3. Метод локального полного перебора и его применение для оптимизации размещения конструктивных модулей.72

2.3.1. Оптимизация размещения модулей.73

2.3.2. Оптимизация ориентации модулей.77

2.3.3. Экспериментальные результаты.82

2.4. Система проектирования многослойных печатных плат на ПК (САПР ЭРА-ПК)

87

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

Список литера туры.95

ГЛАВА 3. АЛГОРИТМЫ ПОСТРОЕНИЯ И ОЦЕНКИ ДЛИН МИНИМАЛЬНЫХ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ.101

Введение.101

3.1. Минимальные связывающие деревья без дополнительных вершин (деревья Краскала-Прима).103

3.2. Минимальные связывающие деревья с дополнительными вершинами (деревья Штейнера).107

3.2.1. Точные алгоритмы построения деревьев Штейнера в ортогональной метрике 109

3.2.2. Приближенные алгоритмы построения деревьев Штейнера в ортогональной метрике.114 3

3.3. Задача коммивояжера и кратчайшие гамильтоновы цепи.119

3.3.1. Точные алгоритмы решения задачи коммивояжера.120

3.3.2. Приближенный алгоритм решения задачи коммивояжера.129

3.3.3. Экспериментальные результаты.134

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

Список литера туры.146

ГЛАВА 4. ВРЕМЕННАЯ ВЕРИФИКАЦИЯ И ОПТИМИЗАЦИЯ ВРЕМЕННЫХ СООТНОШЕНИЙ СИГНАЛОВ НА ЭТАПЕ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ТОПОЛОГИИ.150

Введение.150

4.1. Основные подходы.150

4.2. Методика анализа временных соотношений.153

4.3. Иерархический анализ задержек.156

4.4. Оптимизация временных соотношений на этапе проектирования топологии .159

4.5. Описание системы ТА К Т.162

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

Список литера туры.167

ЗАКЛЮЧЕНИЕ.-.172

СПИСОК ЛИТЕРА ТУРЫ.174

ПРИЛОЖЕНИЕ. АКТЫ О ВНЕДРЕНИИ.188

Введение

Актуальность работы

Разработка предельных по быстродействию ЭВМ на БИС предъявляет повышенные требования к качеству проектирования, так как с увеличением сложности логических схем требуется все больше времени для поиска и исправления ошибок, которые могут привести к дорогостоящему процессу коррекции проекта. При проектировании предельных по быстродействию ЭВМ особую остроту приобретает проблема минимизации задержек распространения сигналов в линиях связи на этапах размещения и трассировки. Это обусловлено тем, что при субмикронной технологии (0,1-0,18 мкм) и частотах порядка 1 Ггц задержка в линии связи начинает превалировать над задержками срабатывания логических элементов. Важность детального учета и оптимизации временных соотношений на этапе автоматизированного проектирования топологии подтверждает, в частности, опыт разработки ЭВМ CRAY Y-MP и Alpha 21164. Обеспечение требуемого качества проекта достигается детальным моделированием на всех этапах его разработки. Анализ существующих САПР и сложившейся практики проектирования позволяет сделать вывод о том, что моделирование предельных по быстродействию ЭВМ обладает рядом характерных особенностей. Одной из таких особенностей является разделение функций логической и временной верификации. При этом ставится цель максимального ускорения процесса логического моделирования и увеличения предельных размеров моделируемых схем за счет отказа на этом этапе от детального учета временных соотношений сигналов. Временная верификация выполняется путем перебора и вычисления задержек для всех возможных путей распространения сигналов в схеме без детального учета их логических значений. Важность временной верификации подтверждает, например, опыт проектирования группы высокопроизводительных процессоров ЭВМ М-68Х (М-680Н/682Н) фирмы Hitachi, который показал, что временные ошибки составляют около 10% от общего числа ошибок в проекте.

Таким образом, актуальной становится разработка эффективных методов временной верификации и оптимизации расположения конструктивных элементов быстродействующих ЭВМ и реализация на их основе соответствующих средств САПР.

Цель исследования

Целью диссертационной работы являлось создание САПР для анализа и оптимизации временных соотношений сигналов в конструктивных узлах быстродействующих ЭВМ.

В соответствии с этим были определены следующие задачи:

1. Разработка алгоритмического и программного обеспечения для оптимизации расположения компонентов быстродействующих ЭВМ (построение и оценка длин кратчайших связывающих деревьев и цепей, назначение интерфейсных выводов, размещение и выбор ориентации конструктивных модулей, выбор порядка трассировки проводников).

2. Разработка средств взаимодействия системы временной верификации с системой автоматизированного проектирования топологии межсоединений с целью оптимизации задержек в линиях связи;.

3. Разработка алгоритмического и программного обеспечения для иерархического анализа временных соотношений сигналов в графовых моделях сложных логических схем.

Научная новизна работы

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, прежде всего, составляют:

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

2. Алгоритмы оптимизации размещения и ориентации конструктивных элементов ЭВМ методом локального полного перебора.

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

4. Алгоритм взвешенной раскраски ребер мультиграфа.

5. Методика совместного проектирования печатного монтажа в конструктивах смежных уровней.

6. Методика иерархического анализа, верификации и оптимизации временных соотношений сигналов в конструктивных узлах быстродействующих ЭВМ.

Результаты работы, выносимые на заициту:

В процессе проведения исследований автором получены следующие результаты:

1. Теоретически разработан и практически реализован подход к решению задачи оптимизации расположения (размещения и ориентации) конструктивных элементов ЭВМ методом локального полного перебора.

2. Эффективность алгоритмов оптимизации размещения и ориентации подтверждена экспериментальными результатами (в частности, на тест-задаче квадратичного назначения Штейнберга из стандартной библиотеки для задач исследования операций OR-library). Определен класс схем и конструктивов, для которых применение предложенных алгоритмов является наиболее эффективным.

3. На основе предложенных алгоритмов разработано программное обеспечение подсистем размещения САПР многослойных печатных плат КАСПИ-ЭВМ, САПР-Эльбрус и ЭРА-ПК. С использованием разработанного программного обеспечения спроектированы печатные платы ЭВМ 5Э26, 40У6, МВК «Эльбрус-1, -2, -3» (ИТМ и ВТ) и Ml6 (НИИВК).

4. Разработан оптимальный алгоритм решения задачи о назначениях на матрицах специального вида с квадратичной временной сложностью.

5. Разработан приближенный алгоритм решения задачи о назначениях на матрицах общего вида с квадратичной временной сложностью и средней относительной погрешностью около 14%.

6. Разработано алгоритмическое и программное обеспечение для подбора корпусов и разводки проводных соединений между выводами кристалла и контактами корпуса БИС. Разработанное программное обеспечение входит в систему корпусирования БИС «Package Constraints Manager» фирм Avant! и VLSI/Philips.

7. Разработано алгоритмическое и программное обеспечение для назначения интерфейсных сигналов на контакты разъемов вычислительных устройств. Разработанное программное обеспечение входит в систему проектирования сверхбольших многослойных печатных плат ЭРА/ПК на ШМ PC.

8. Разработан алгоритм взвешенной раскраски ребер мультиграфа. На основе алгоритма раскраски разработана и практически реализована в процессе разработки МВК «Эльбрус-2» методика совместного проектирования печатного монтажа в конструктивах смежных уровней.

9. Разработана эффективная параметрическая процедура оценки длин минимальных связывающих деревьев.

10. Разработан алгоритм построения минимальных связывающих цепей и экспериментально доказана его вычислительная эффективность (на тестовых примерах из библиотеки TSPLIB).

11. Алгоритмы построения минимальных связывающих цепей и деревьев реализованы на языке С++ для рабочих станций SUN/HP и входят в состав программного обеспечения экспериментальной версии САПР электронной аппаратуры Compass/Avant! (в подсистему автоматической генерации тестов Test Assistant и трассировщик Pathfinder).

12. Теоретически разработана и практически реализована методика иерархического анализа временных соотношений сигналов в конструктивных узлах быстродействующих ЭВМ на основе метода критических путей.

13. Реализован интерфейс системы временной верификации с подсистемой управляемого задержками размещения и подсистемой трассировки на основе итеративного вычисления коэффициентов приоритета связей

14. Разработана система временной верификации ТАКТ, с помощью которой была выполнена исчерпывающая верификация всех устройств МВК «Эльбрус-3» (ЦП, ПВВ, ЛОП, ООП, ЦУК).

Практическая ценность

Результаты исследований, выполненных по теме диссертации, нашли применение в следующих системах автоматизации проектирования:

1. Подсистемы размещения САПР многослойных печатных плат КАСПИ-ЭВМ, САПР-Эльбрус и ЭРА-ПК, с использованием которых спроектированы печатные платы ЭВМ 5Э26, 40У6, МВК «Эльбрус-1, -2, -3» (ИТМ и ВТ) и Ml6 (НИИВК).

2. Подсистема разводки проводных соединений и автоматического подбора корпусов САПР для корпусирования БИС «Package Constrants Manager (PCM)».

3. Подсистема САПР ЭРА/ПК для назначения интерфейсных сигналов на контакты разъемов вычислительных устройств.

4. Подсистема САПР Compass/Avant! для построения и оценки длин минимальных связывающих цепей и деревьев.

5. Система временной верификации ТАКТ, с помощью которой была выполнена исчерпывающая верификация всех устройств МВК «Эльбрус-3» (ЦП, ПВВ, ЛОП, ООП, ЦУК).

Личный вклад автора

Предложенные в диссертации алгоритмы решения дискретных оптимизационных задач разработаны лично автором. Программное обеспечение в течение ряда лет создавалось коллективом разработчиков (в ИТМ и ВТ, Московском центре СПАРК технологий и ИМВС РАН) при личном участии и под руководством автора и нашло свое применение в нескольких САПР электронной техники: КАСПИ-ЭВМ, САПР-Эльбрус, ЭРА-ПК, Package Constraints Manager (PCM), Compass Design Automation (CDA). Объем программного обеспечения, разработанного лично автором на языках программирования Эль-76, Pascal, Mainsail и С++, составил при этом 5.8 Мбайт (165 тыс. строк).

Апробация

Результаты диссертационной работы докладывались на всесоюзных, российских и международных научных конференциях:

1. О.К.Гущин, В.С.Ирбенек, В.Р.Кравцов, Е.Г.Кречетов. Пакет программ автоматизации конструкторского проектирования многослойных печатных плат высокопроизводительных ЭВМ. Доклад на конференции молодых ученых и специалистов, ЕрНИИММ, Ереван, 1977 г.

2. В.С.Ирбенек, А.В.Жмурин. Анализ временных соотношений сигналов в логических моделях сложных электронных устройств. Доклад на Московской городской конференции молодых ученых и специалистов "Системы автоматизированного проектирования (САПР-85)", Москва, 1985.

3. О.К.Гущин, В.С.Ирбенек, Е.Г.Кречетов, А.С.Калачев. Комплексное проектирование конструктивных модулей суперЭВМ в САПР-Эльбрус. Доклад на I Международной научно-практической конференции "САПР СВТ'89", Ленинград, 17-21 апреля 1989 г.

4. Г.Л.Лакшин, В.С.Ирбенек, В.С.Тихорский. Функционально-логическое моделирование и временная верификация супер-ЭВМ. Доклад на Всесоюзной научно-технической конференции «Проектирование вычислительных средств», Каунас, 6-8 июля 1989 г.

5. V.S.Irbenek, G.L.Lakshin. Organization of logical and functional modeling and temporal verification in CAD for super computers. Report on international scientific conference "New generation computer systems and software", Samarkand, 10-15 September 1990.

6. А.В.Жмурин, В.С.Ирбенек. Опыт разработки САПР ЭРА/ПК. Доклад на научной конференции, посвященной 70-летию академика В.А.Мельникова, Москва, 1999 г.

7. А.В.Жмурин, В.С.Ирбенек. К.В.Келенин, Д.В.Кучеров. Алгоритмическое и программное обеспечение специализированной САПР для корпусирования БИС. Доклад на научной конференции, посвященной 70-летию академика В.А.Мельникова, Москва, 1999 г.

8. В.С.Ирбенек. Алгоритмы построения минимальных связывающих деревьев и их применение в САПР электронной аппаратуры. Доклад на Международной научной конференции XXV Гагаринские чтения. "МАТИ" - Российский государственный технологический университет им. К.Э.Циолковского, М., 6-10 апреля 1999 г.

9. В.С.Ирбенек, А.В.Жмурин, К.В.Келенин. Применение алгоритмов решения задачи о назначениях для проектирования топологии межсоединений. Доклад на российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 333-337.

10. В.Ф.Уткин, В.С.Ирбенек, А.В.Жмурин. Алгоритмическое и программное обеспечение для графического изображения схем, представленных списком соединений. Доклад на российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 338-344.

11. В.С.Ирбенек, А.В.Усенков. Оптимизация размещения конструктивных модулей вычислительных устройств методом локального полного перебора. Доклад на российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 348-356.

12. В.С.Ирбенек, Н.В.Рыженко. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. Доклад на российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 361-366.

Публикации по теме диссертации

Основные результаты диссертации опубликованы в 25-ти печатных работах (из них за период 1999-2000 гг. опубликовано 13 работ) и 4-х отчетах по научно-исследовательской работе ИТМ и ВТ им С. А. Лебедева АН СССР:

1. B.C. Ирбенек, Ю.А. Пронин. Размещение связных систем с большим числом компонентов. -М, ИТМ и ВТ АН СССР, 1973.

2. B.C. Ирбенек, В.А. Кричак. Компоновка интегральных схем. -М., ИТМ и ВТ АН СССР, 1976.

3. Вычислительный комплекс 5Э60. Технический проект. Пояснительная записка. Часть 11. Автоматизация проектирования. -М., ИТМ и ВТ АН СССР (Рукопись), 1976, в соавторстве.

4. О.К.Гущин, В.С.Ирбенек, В.Р. Кравцов, Е.Г.Кречетов. Пакет программ автоматизации конструкторского проектирования многослойных печатных плат высокопроизводительных ЭВМ, -М., Вопросы радиоэлектроники, вып. 12, сер. ЭВТ, 1977.

5. В.А. Ершов, B.C. Ирбенек. Конструкторское проектирование ячеек и панелей МВК «Элъбрус-2». -М., ИТМ и ВТ АН СССР, 1979.

6. В.А. Ершов, B.C. Ирбенек. Двухэтапный алгоритм размещения. -М., ИТМ и ВТ АН СССР, 1980.

7. В.А. Ершов, B.C. Ирбенек. Алгоритм решения задачи назначения на матрицах специального вида. -М.,. ИТМ и ВТ АН СССР, 1981

8. В.А. Ершов, B.C. Ирбенек. Алгоритм раскраски ребер мультиграфа. -М, ИТМ и ВТ АН СССР, 1981.

9. B.C. Ирбенек, В.А. Ершов, Т.М. Трухачева. Методы размещения конструктивных элементов и трассировка проводного монтажа. -М., ИТМ и ВТ АН СССР, 1983.

10. Модульный конвейерный процессор. Эскизный проект. Пояснительная записка. Книга 3. -М., ИТМ и ВТ АН СССР (Рукопись), 1984, в соавторстве.

11. Многопроцессорный вычислительный комплекс «Эльбрус-3». Эскизный проект. Пояснительная записка. Часть 14. Автоматизация проектирования. -М., ИТМ и ВТ АН СССР (Рукопись), 1984, в соавторстве.

12. МВК «Эльбрус-3». Технический проект. Пояснительная записка. Часть 14. Автоматизация проектирования. -М., ИТМ и ВТ АН СССР (Рукопись), 1986, в соавторстве.

13. О.К.Гущин, В.С.Ирбенек, Е.Г.Кречетов, А.С.Калачев. Комплексное проектирование конструктивных модулей суперЭВМ в САПР-Эльбрус. Тезисы доклада на I Международной научно-практической конференции "САПР СВТ'89", Ленинград, 17-21 апреля 1989 г.

14. Г.Л.Лакшин, В.С.Ирбенек, В.С.Тихорский. Функционально-логическое моделирование и временная верификация супер-ЭВМ. Тезисы доклада на Всесоюзной научно-технической конференции "Проектирование вычислительных средств", Каунас, 6-8 июля 1989 г.

15. B.C. Ирбенек. Верификация временных соотношений и оптимизация размещения конструктивных элементов супер-ЭВМ. -М., ИТМ и ВТ АН СССР, 1993.

16. В.С.Ирбенек. Московский центр SPARC-технологий и Compass Design Automation: история и перспективы сотрудничества. Автоматизация проектирования, М., 1997, N 3, с. 3-6.

17. В.С.Ирбенек, К.В.Келенин. Алгоритмы решения задачи о назначениях и их применение. Программные продукты и системы, М., 1999, N 1, с. 20-24.

18. В.С.Ирбенек. Метод локального полного перебора и его применение для оптимизации размещения конструктивных модулей в САПР электронной аппаратуры. Информационные технологии и вычислительные системы, М., 1999, N1, с. 3-17.

19. В.С.Ирбенек. Алгоритмы построения минимальных связывающих деревьев и гсс применение в САПР электронной аппаратуры. В сб. "Высокопроизводительные вычислительные системы и микропроцессоры". Труды института высокопроизводительных вычислительных систем РАН, М., 1999, с. 3-17.

20. В.С.Ирбенек, А.В.Жмурин, К.В.Келенин. Алгоритмы минимизации длин интерфейсных связей в САПР электронной аппаратуры. В сб. "Высокопроизводительные вычислительные системы и микропроцессоры". Труды института высокопроизводительных вычислительных систем РАН, М., 1999, с. 18-30.

21. В.Ф.Уткин, В.С.Ирбенек, А.В.Жмурин. Схем-конструктор алгоритмическое и программное обеспечение для графического изображения схем, представленных списком соединений. В сб. "Высокопроизводительные вычислительные системы и микропроцессоры".

Труды института высокопроизводительных вычислительных систем РАН, М., 1999, с. 31-40.

22. А.В. Жмурин, B.C. Ирбенек. Опыт разработки САПР ЭРА/ПК. Тезисы доклада на научной конференции, посвященной 70-летию академика В.А.Мельникова, -М., 1999 г.

23. А.В.Жмурин, В.С.Ирбенек. К.В.Келенин, Д.В.Кучеров. Алгоритмическое и программное обеспечение специализированной САПР для корпусирования БИС. Тезисы доклада на научной конференции, посвященной 70-летию академика В.А.Мельникова, Москва, 1999 г.

24. В.С.Ирбенек. Алгоритмы построения минимальных связывающих деревьев и га применение в САПР электронной аппаратуры. Тезисы доклада на Международной научной конференции XXV Гагаринские чтения. "МАТИ" -Российский государственный технологический университет им. К.Э.Циолковского, М., 6-10 апреля 1999 г.

25. В.С.Ирбенек, А.В.Жмурин, К.В.Келенин. Применение алгоритмов решения задачи о назначениях для проектирования топологии межсоединений. В сб. докладов российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 333-337.

26. В.Ф.Уткин, В.С.Ирбенек, А.В.Жмурин. Алгоритмическое и программное обеспечение для графического изображения схем, представленных списком соединений. В сб. докладов российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 338-344

27. В.С.Ирбенек, А.В.Усенков. Оптимизация размещения конструктивных модулей вычислительных устройств методом локального полного перебора. В сб. докладов российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики.

Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 348-356.

28. В.С.Ирбенек, Н.В.Рыженко. Применение алгоритмов построения и оценки длин минимальных связывающих деревьев в САПР электронной аппаратуры. В сб. докладов российской научной конференции "Экономические информационные системы на пороге XXI века". Московский государственный университет экономики, статистики и информатики. Институт экономических информационных систем и программирования. М., 19-20 окт. 1999 г., с. 361-366.

29. В.С.Ирбенек. Временная верификация при проектировании предельных по быстродействию ЭВМ. Информационные технологии и вычислительные системы, М., N 1, 2000.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Диссертация содержит 187 страниц текста, 59 рисунков,, 15 таблиц и приложение на 5 листах. Список литературы насчитывает 159 наименований.

Основные результаты, представленные в данном разделе, можно сформулировать следующим образом:

1. Разработан оптимальный алгоритм решения задачи о назначениях на матрицах специального вида с квадратичной временной сложностью.

2. Разработан приближенный алгоритм решения задачи о назначениях на матрицах общего вида с квадратичной временной сложностью и средней относительной погрешностью около 14%.

3. Разработан алгоритм взвешенной реберной раскраски мультиграфа.

4. Разработано алгоритмическое и программное обеспечение для разводки проводных соединений между выводами кристалла и контактами корпуса БИС. Разработанное программное обеспечение входит в систему корпусирования БИС «.Package Constraints Manager» фирмы AvantL

5. Разработано алгоритмическое и программное обеспечение для назначения интерфейсных сигналов на контакты разъемов вычислительных устройств. Разработанное обеспечение входит в систему проектирования сверхбольших многослойных печатных плат ЭРА/ПК на ШМ PC. 6. Разработана и практически реализована в процессе проектирования МВК Эльбрус-2 методика совместного проектирования конструктивов смежных уровней.

Заключение

1. A.J. Hoffman. On greedy algorithms that succeed. London Math Society Lecture Notes Series, 1985, v. 103, pp.97-112.

2. R.M. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher (eds.), Complexity of computer computations, Plenum Press, New York, 1972, pp. 85-103.

3. J.M. Kurtzberg. On approximation methods for assignment problem. J. ACM, 1962, N4, pp. 419-439.

4. O. Ore. The four color problem. Academic Press, New York, 1987.

5. C.E. Shannon. A theorem on coloring the lines of a network J. Math. Phys., 28, 1949, pp. 148-151.

6. E.A. Диниц, M.A. Кронрод. Один алгоритм решения задачи о назначении. ДАН СССР.- 1969, т. 189, N 1. с. 23-25.

7. В.Г. Визинг. Об оценке хроматического класса р-графа. Сб. «Дискретный анализ», Новосибирск, 1964, вып. 3, с. 25-30.

8. А.В. Жмурин, B.C. Ирбенек. Опыт разработки САПР ЭРА/ПК. Тезисы доклада на научной конференции, посвященной 70-летию академика

9. B.А.Мельникова, -М., 1999 г.

10. А.В. Жмурин, B.C. Ирбенек, К.В. Келенин, Д.В. Кучеров. Алгоритмическое и программное обеспечение специализированной САПР для корпусирования БИС. Тезисы доклада на научной конференции, посвященной 70-летию академика В. А.Мельникова, -М., 1999 г.

11. В.А. Ершов, B.C. Ирбенек, Е.Г. Кречетов. Конструкторское проектирование ячеек и панелей МВК «Эльбрус-2». -М ., 1979, (Препринт ИТМ и ВТ им.1. C.А.Лебедева, N 2).

12. Глава 2. Алгоритмы решения задач разбиения и размещения1. Введение

13. В данной главе рассматриваются алгоритмы решения задач разбиения и размещения, играющих ключевую роль при проектировании топологии межсоединений интегральных схем и многослойных печатных плат.21. Задача разбиения

14. Задача разбиения формулируется следующим образом.

15. Вершины графа G(V,E) соответствуют при этом схемным модулям, размер s(v) равен площади, занимаемой модулем v, а вес w(e), e = (vj,vJ), равен числу общих цепей схемных модулей v,. и v.

16. Размер каждого из подмножеств Vt ограничивается сверху величиной Д2>(у)<ДveVi

17. Целевая функция определяется как минимум суммы весов ребер, соединяющих вершины из различных подмножеств1. Cost- ^Гw(e) ,1. Ve=(u,v)&p(u)* p(v)где ребро e-(u,v), a и /?(v) обозначают номера подмножеств вершин и и v.

18. Важным частным случаем общей задачи разбиения на к подмножеств ( к -way partition problem) является задача разбиения графа схемы на два равных по размеру подмножества (two-way partition problem).

19. Рассмотрим алгоритм решения последней задачи, предложенный Лином и Керниганом.21.2. Алгоритм Лина-Кернигана

20. Обозначим далее через Da=Ea- Ia изменение суммарного веса ребер в разрезе при перемещении вершины а из блока А в блок В, а через gab изменение суммарного веса ребер в разрезе при перестановке вершин а и b между собой.

21. Лемма 1. Если два элемента as А и b е В переставляются между собой, изменение суммарного веса ребер в разрезе определяется соотношением:gai=Da+Db-2cab1. Доказательство.

22. Выражение для Еа можно записать следующим образом: Е ~с,+ Vсa ab / j av1. Тогда1. D=E-I=cah+ Yc -/a a a ao / . av aveB.vzb1. Аналогично,1. Db=Eb~Ib =cab+ Y,cbu-huzA,u*a

23. Перемещение вершины а из А в В уменьшает суммарный вес ребер в разрезе на величину1. Тс -I -с h.av а а аЬvsB.v^b

24. Перемещение вершины Ъ из В в А уменьшает суммарный вес ребер в разрезе на величину1. Xcbu-Ib=Db-cab

25. При взаимной перестановке изменение суммарного веса ребер в разрезе равно сумме двух последних выражений и равно8ab=Da+Db-2cab1. Лемма доказана.

26. Перестановка вершин а и Ъ изменяет значения D у связанных с ними вершин. Следующая лемма определяет соотношения для вычисления новых значений D*.

27. Лемма 2. Если два элемента ае А и be В переставляются между собой, то новые значения D* определяются следующими соотношениями1. D;=Dy+2cyb-2cya, УуеВ-{Ь}1. Доказательство.

28. Рассмотрим вершину хе А-{а} (Рис. 1)

29. Так как вершина bпереместилась в блок А, то 1Х увеличилось на схЪ. Аналогично, так как вершина а переместилась в блок В, то 1Х уменьшилось на сха и новое значение1>1х-сш + схЬх х ха хо

30. Аналогичным образом можно показать, что1. Ех = Ех+сха— схЬ

31. Таким образом, новое значение D для х е А-{а} равно D* = Е"-Г = D + 2с -2с „х ^ х X ^ X ха хЬ

32. Аналогично, новое значение D для у е В-{Ь} равно D* = Е*-Г = D +2с . -2су у лу у 1 ^^ уЪ уа

33. Заметим что, если вершина х не связана ни с вершиной а, ни с вершиной Ъ, то сха-схЬ=0 я D*X=DX. Лемма доказана.

34. Gk :. Если не существует такого к, что Gk >0, то пекущее разбиение1невозможно улучшить. В противном случае выбирается к с максимальным значением Gk и осуществляется перестановка {а1}а2,.,ак} с {bl,b2,.,bk}.

35. После этого стираются пометки у всех вершин, и выполняется следующая итерация.

36. Ниже приводится формальное описание данной процедуры.1. Algorithm KLTWPP; Begin

37. Step 1. V = set of 2n elements;

38. Step 5. Find к to maximize the partial sum G= 9i> If G > 0 then

39. Move x = {ab •■•,<!*} to B, and У = {Ьь • ■ to A; Goto Step 2 Else STOP Endlf1. End.

40. Сортировка может быть вьшолнена за время O(nlogn).

41. В результате общее время вьшолнения шага 3 равно 0(п2 logп).

42. Время вьшолнения шага 5 равно 0(п).

43. Таким образом, общая сложность алгоритма Лина-Кернигана равна ()(рп2 log»), где р- число итераций. Эксперименты на больших реальных схемах показали, что р не возрастает с возрастанием п, поэтому общая сложность алгоритма Лина-Кернигана равна 0(п2 logп).

44. В работе 36. предложена модификация классического алгоритма Лина-Кернигана для многоконтактных связей. Другая модель схемы с многоконтактными связями предложена в работе [37] и также позволяет получать отличные результаты.

45. Перечислим сходные черты и принципиальные отличия алгоритма Лина-Кернигана и одной из его модификаций алгоритма Фидуччиа-Маттеуса 12.

46. В алгоритме Лина-Кернигана на очередном шаге рассматриваются перестановки пар вершин, по одной из блока А и блока В, В алгоритме Фидуччиа-Маттеуса на очередном шаге одна вершина переставляется из одного блока в другой.

47. В алгоритме Лина-Кернигана минимизируется суммарный вес ребер графа схемы, соединяющих вершины из разных блоков. В алгоритме Фидуччиа-Маттеуса минимизируется число цепей (ребер гиперграфа, представляющего схему) в разрезе.

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

49. В алгоритме Фидуччиа-Маттеуса используется коэффициентбалансировки, определяемый как г = т^т, где \А\ и \В\ размерыблоков А и В. Разбиение считается сбалансированным при условии, что r*|F|-5max < < г * Г| + 5шах, где =Max[s,\ ieAuB = V.

50. Некоторые вершины могут быть предварительно фиксированы в блоке А или в блоке В.

51. Временная сложность выполнения одной итерации алгоритма Фидуччиа-Маттеуса линейно зависит от длины массива цепей, а количество итераций невелико и не зависит от размера схемы.21.4, Ременце задачи разбиения методом моделирования отжига.

52. Algorithm Simulatedannealing (So, То, а, М, Maxtime); (*Sq is the initial solution *) (*Tq is the initial temperature *) (*alpha is the cooling rate *) {*beta a constant *)

53. Maxtime is the total allowed time for the annealing process*) (*M represents the time until the next parameter update *) begin

54. T = TQ-, S = So; Time = 0; repeat Call Metropolis{S, T, M); Time — Time + M; T = axT; M (3 x M until (Time > MaxTime)', Output Best solution found End. (*ofSimulated-annealing*)

55. Algorithm Metropolis(S, T, M); beginrepeat

56. NewS — neighbour(S)', Ah = (Cost{NewS) Cost(S)); If ((Д/г < 0) or (random < е~лл/Г)) then S = NewS; {accept the solution) M = M- 1 until (M = 0) End. (*of Metropolis*).

57. Определим целевую функцию задачи разбиения

58. При использовании данной целевой функции отсутствуют ограничения на предельные размеры подмножеств А и В, которые определяются автоматически.

59. Рис. 2. Репликация вершин при разбиенииболее критичным, чем стоимость дополнительного оборудования. В работах 18-20,30,33. рассматривается подход, основанный на использовании спектральных методов.

60. В заключение данного раздела рассмотрим еще одно применение алгоритмов разбиения в САПР электронной аппаратура.

61. Для этой цели в КАСПИ-ЭВМ использовалась следующая процедура.

62. Этап размещения играет ключевую роль в обеспечении качества проектирования конструктивных модулей ЭВМ.22.1. Постановка задачи

63. Задача размещения заключается в построении однозначного отображения /множества объектов Е в множество установочных мест Р таким образом, чтобы минимизировать некоторую целевую функцию L = L(f).

64. Ограничения на длины связей и штрафные коэффициенты вычисляются в системе временной верификации и обеспечивают приоритетную минимизацию задержек в линиях связи на критических путях распространения сигналов в схеме.

65. Наряду с суммарной длиной связей в качестве целевой функции используется загрузка горизонтальных и вертикальных сечений схемы.

66. Эвристические алгоритмы размещения можно разбить на две большие группы:конструктивные алгоритмы первоначального размещения;- итеративные алгоритмы оптимизации размещения.

67. Время работы данного алгоритма растет пропорционально кубу размерности задачи.

68. Рассмотрим промежуточный шаг работы другого последовательного алгоритма 55,56,58.

69. Обозначим через Е = {е{), / = 1,2,.,/- множество неразмещенных корпусов, по крайней мере, одной цепью соединенных с уже размещенными.

70. Обозначим далее через P = {pj}, j = 1,2,.т множество свободныхустановочных мест(т>1).

71. Пусть с(/,у)- оценка размещения корпуса е е £ на установочное место

72. Дс(/) с г (0 — C\(i), Ас > Оразность этих минимумов.

73. Определим теперь первую 57,62. и вторую оценочные функции выбора корпуса для размещения на данном шаге1. Ш) = ci(01. Л(0 = Ас(/)

74. Обозначим через Е с Е множество корпусов е{, для которых j = /, (г), то есть, Pj -«лучшее» установочное место.

75. Определим теперь третью оценочную функцию.1. Пусть el е Ej, тогдаз(0= £Дс(*)"М0

76. Пусть далее число конкурентов на место рм (/) (как на «лучшее»), и к2 (/) - число конкурентов на место pj2 (i) (как на «лучшее»).

77. Определим теперь четвертую и пятую оценочные функции

78. Окончательную эвристическую функцию выбора корпуса, размещаемого на данном шаге, определим как линейную комбинацию этих номеров, то есть4=51. F(i) = ^aknfk(i) к=1

79. Нетрудно видеть, что вычислительная сложность вьшолнения одной итерации данного алгоритма равна 0(12т), где /-число неразмещенных корпусов, а т -число свободных посадочных мест. Число итераций при этом равно общему числу неразмещенных корпусов в схеме.

80. Рассмотрим теперь один из самых популярных итеративных алгоритмов размещения алгоритм решения задачи размещения методом последовательных разбиений (min-cut алгоритм).22.3. Min-cut алгоритм

81. Обычно используют одну из трех возможных последовательностей сечений.

82. Рис. 3. Последовательности сечений Формальное описание рекурсивного min-cut алгоритма приведено ниже.

83. Algorithm Мгп—cut(H, n, С); (*H is the layout surface. n is the number of cells to be placed. n0 is the number of cells in a slot. С is the connectivity matrix*). Begin1. (n < no) Then place-cells (К, n, C) Else Begin

84. Hi, K2) cut-surface^)-, (ni^cI)J(n2,c2 partition(n,C); Call Min-cut (N,, щ, ct); Call Min-cut (K2!n2,c2); Endlf; End.

85. Однако следует отметить, что каждая из приведенных последовательностей разбиений обладает одним и тем же существенным недостатком. Дело в том, что в процессе разбиения не учитывается положение интерфейсных выводов для разбиваемой подсхемы.