Модели и методы глобальной трассировки Кокурина Светлана Евгеньевна E mail: студентка 1 курса магистратуры ММФ Руководитель – А. И. Ерзин – в.н.с. ИМ СО РАН 1 декабря 2006 года Проект «Модели и методы трассировки при проектировании СБИС». Руководители: А. И. Ерзин, В.В. Залюбовский – ИМ СО РАН (НС: 3 студента ММФ: Кокурина С.Е., Комарова А.А., Набока Н.А.; 2 аспиранта ММФ: Алдын-оол Т.А., Тахонов И.И.)

Решаемые задачи Задача проекта в целом: разработка эффективных алгоритмов глобальной маршрутизации на чипе с учетом временных ограничений (модель Эльмора) и ограничений на пропускные способности каналов. Задача проекта в целом: разработка эффективных алгоритмов глобальной маршрутизации на чипе с учетом временных ограничений (модель Эльмора) и ограничений на пропускные способности каналов. Цель исследования: разработка алгоритмов одновременной маршрутизации сетей. Цель исследования: разработка алгоритмов одновременной маршрутизации сетей. Задачи исследования: Задачи исследования: –Построение математических моделей. –Разработка и анализ алгоритмов построения деревьев Штейнера в глобальном графе. –Разработка алгоритмов одновременной маршрутизации совокупности деревьев Штейнера с учетом ресурсных и временных ограничений.

Планы, текущее состояние, проблемы и трудности Этапы Сроки завершения Ожидаемые результаты Текущее состояние и проблемы 1. Изучение методов глобальной маршрутизации 1. Изучение методов глобальной маршрутизации Обзор литературы Сделано 2. Построение математических моделей 2. Построение математических моделей Математические модели Сделано 3. Разработка и анализ алгоритмов 3. Разработка и анализ алгоритмов Построение эффективных алгоритмов В процессе 4. Программная реализация и тестирование алгоритмов 4. Программная реализация и тестирование алгоритмов Программа. Результаты апостериорного анализа алгоритмов. Ожидание 3 Цветовое кодирование: все в порядке, есть основания для особого внимания, требуется решение проблем

Необходимые выступления Основные представления работы: Основные представления работы: –Выступление на семинаре –Защита магистерской диссертации июнь 2008 Дополнительные представления работы: Дополнительные представления работы: –Выступление на МНСК апрель 2007, апрель 2008

Задача Дано: – граф G = (V,E); – граф G = (V,E); – пропускная способность для ребра (максимальное число соединений, которые могут проходить по ребру) – пропускная способность для ребра (максимальное число соединений, которые могут проходить по ребру) – V s V, s =1..S – множества терминалов (сети) – V s V, s =1..S – множества терминалов (сети)Требуется: для каждого V s построить допустимое дерево Штейнера для каждого V s построить допустимое дерево Штейнера

Известные методы Последовательная маршрутизация Последовательная маршрутизация – Алгоритм маршрутизации одной сети – Алгоритм маршрутизации одной сети – Упорядочение сетей – Упорядочение сетей Одновременная маршрутизация Одновременная маршрутизация – Иерархические методы – Иерархические методы – ЦЛП* – ЦЛП* * – релаксируется к дробной постановке с последующим округлением полученного решения, причем даже для релаксированной задачи чаще всего используются эвристики или приближенные комбинаторные алгоритмы

Идея алгоритма 1 этап: Для V s построить множество Q s деревьев Штейнера, допустимых по задержкам 1 этап: Для V s построить множество Q s деревьев Штейнера, допустимых по задержкам 2 этап: Для V s выбрать только одно из допустимых деревьев, минимизируя суммарное (или максимальное) переполнение 2 этап: Для V s выбрать только одно из допустимых деревьев, минимизируя суммарное (или максимальное) переполнение

2 этап ЦЛП ЦЛП Релаксировать, решить градиентным методом Релаксировать, решить градиентным методом Переход к целочисленному решению Переход к целочисленному решению

Пример V 1 = {1,3} V 7 = {4,2} V 2 = {10,3,7,9} V 8 = {10,2,8} V 3 = {6,9} V 9 = {1,8} V 4 = {3,4} V 10 = {2,5} V 5 = {7,1,4,8,10} V 11 = {8,5} V 6 = {9,1} 1 – источник сигнала, 3 – приёмник сигнала

Проекция решения

1 x z

Дерево Штейнера 1) 2) 3) 1) 2) 3) : терминалы, : точки Штейнера.