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

2 Решаемые задачи Задача проекта в целом: Разработка алгоритмов и прототипов программ для решения задач глобальной маршрутизации, возникающих при проектировании СБИС. Цель исследования: Разработка алгоритмов построения надежных сетей. Задачи исследования: - Построение математических моделей. - Разработка и анализ алгоритмов построения надежных подграфов в заданном взвешенном графе.

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

4 Выступления 3-6 апреля 2006: Выступление на КМУ апреля 2006: Выступление на МНСК 7 июня 2006: Защита диплома на тему Оптимизация структур сетей в условиях стоимостных ограничений Статья: Т.А. Алдын-оол. Оптимизация структур сетей в условиях стоимостных ограничений // Труды конференции молодых ученых. ИВМиМГ СО РАН, Новосибирск, 2006, 3-10.

5 Необходимые выступления Основные представления работы: - Выступление на семинаре – Защита кандидатской диссертации – сентябрь 2009 Дополнительные представления работы: - Ежегодная аттестация - Выступление на семинарах и конференциях

6 Откуда возникла проблема Достижения в технологии изготовления СБИС приводят к увеличению плотности упаковки чипа. С ростом числа соединений на чипе и уменьшением их толщины возрастает вероятность короткого замыкания или разрыва. короткое замыкание разрыв короткое замыкание разрыв

7 Задача Дано: - взвешенный граф G =(V, E); - выделенные источник s V и сток t V; - надежность p e 0 (вероятность существования) каждого ребра e E. Требуется: найти подграф S минимального веса, в котором вероятность передачи сигнала из s в t не менее заданной величины P. p1 p2 p3p4p5 p6 p7p8 p9 p10 p11 s t

8 Полиномиально разрешимые случаи В случае, когда требуется найти путь S, задача решается эффективно (за время O(|V||E|)). В случае, когда исходный взвешенный граф G является последовательно-параллельным, задача решается эффективно (за время O(|V||E| 2 )). p1 p2 p3p4p5 p6 p7p8 p9 p10 p11 s t

9 Последовательно-параллельный граф (ппг) можно определить рекурсивно следующим образом. Граф, состоящий из двух вершин s и t, соединенных ребром, является ппг (c источником s и стоком t). Последовательно-параллельный граф Пусть G1 (c источником s1 и стоком t1) и G2 (c источником s2 и стоком t2) два ппг. Тогда следующие графы будут ппг: Gs строится при помощи отождествления t1 c s2. Gp строится при помощи отождествления s1 c s2 и t1 c t2. s t s1 t1 Gs s1 t1 s2 t2 s2 Gp

10 Подзадача s t В случае, когда исходный граф G является решеткой, приближенное решение задачи может быть построено в два этапа. На первом этапе строится некоторый последовательно- параллельный подграф, а на втором – решается исходная задача на ппг. На первом этапе можно построить различные пп подграфы. Очевидно, что их надежности будут разные. Выбираем самый надежный. s t s t s t

11 Спасибо за внимание!