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

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

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

Сделанные выступления 8 июня 2006г. Защита магистерской диссертации октябрь 2005г., декабрь 2006г. Выход статей в Сибирском журнале индустриальной математики, посвященных исследованиям итерационных процессов на графах. 28 ноября 2006г. Выступление с тезисами дипломной работы на семинаре в ИМ СО РАН

Необходимые представления работы декабрь 2006г. Выступление на данном семинаре апрель 2007г. Выступление на МНСК июнь 2007г. Аттестация в НГУ сентябрь 2009г. Защита кандидатской диссертации

Краткая постановка задачи Задан взвешенный граф G = (V, E), подмножество вершин-терминалов S V и вершина-источник s 0 S. Требуется найти такое дерево T, связывающее вершины множества S, чтобы Здесь t i (T) - задержка передачи сигнала (по Эльмору) из источника s 0 в вершину i в дереве T.

Модель Эльмора Дано: T = (V, E) S V Обозначения: P k (T) – путь из 0 в k T i T – поддерево r ij – сопротивление c ij – емкость r 0 – сопротивление в 0 c i – емкость вершины

Описания алгоритмов Алгоритм МАД Шаг 0. Положить начальное дерево T = (s 0, ) и задержку в корне t 0 = 0. Шаг 1. Найти дугу где Положить T = T {i, j} и пересчитать задержки t k : Если вершина j является промежуточной, то положить t j = t i + d ij а задержки t k во все остальные вершины, которые включены в строящееся дерево ранее, оставить без изменения. Если вершина j является терминалом, то отсечь все «висячие» пути дерева и пересчитать задержки в вершины получившегося дерева. Если не все терминалы включены в дерево, то перейти на шаг 1.

Описания алгоритмов Алгоритм ИМАД Алгоритм ИМАД на каждой итерации строит дерево с помощью алгоритма МАД, используя величины реберных задержек, вычисленных по дереву, построенному на предыдущей(их) итерации(ях). Пусть T k – это дерево, полученное на k-ой итерации. Через обозначим задержку сигнала по ребру (i, j) в этом дереве. Иными словами, Тогда на (k+1)-ой итерации к строящемуся дереву будут присоединяться ребра Алгоритм заканчивает работу, когда либо выполнено заданное количество итераций, либо получено ранее построенное дерево.

Пример работы ИМАД Рассмотрим граф с источником 0, терминалами 1, 3 и промежуточной вершиной 2. Рядом с ребрами и вершинами показаны их характеристики c 1 =1 c2=0c2=0 c 3 =1 c 01 =4 c 02 =6 c 12 =3 c 13 =2 c 23 =1 r 01 =2 r 02 =2 r 12 =1 r 23 =3 r 13 =2 r 0 =1

Пример работы ИМАД Начальное дерево пусто. Посчитаем задержки по дугам: d 01 = r 01 (c 01 /2+c 1 ) = 2(4/2+1) = 6, d 02 = 6, d 12 =3.5, d 21 = 2.5, d 13 = d 31 = 4, d 23 =4.5, d 32 = d 01 =6 d 02 =6 d 12 =3,5 d 32 =7,5 d 23 =4,5 d 21 =2,5 d 31 =4 d 13 =4

Пример работы ИМАД На первом шаге можно добавить вершину 1 или 2. Задержки в них равны соответственно: t 1 =r 0 C 0 +r 01 (c 01 /2+C 1 )=1 (4+1)+2 (4/2+1)=11 t 2 =r 0 C 0 +r 02 (c 02 /2+C 2 )=1 (6+0)+2 (6/2+0)=12 Первым присоединяется ребро (0,1)

Пример работы ИМАД Затем добавляются ребра (0,2) и (2,3). Все терминалы включены в дерево, итерация окончена: получено дерево Т 1 Критическая задержка t 3 =

Пример работы ИМАД Пересчитав задержки для дерева Т 1 и проделав аналогичные действия, на следующей итерации получим дерево Т 2 с критической задержкой t 3 =18. Нетрудно убедиться, что дерево Т 3 совпадает с Т 1, поэтому алгоритм останавливается. Второе дерево предпочтительнее

Описания алгоритмов Адаптивный (обучающийся) распределенный алгоритм. Считаем, что для каждого терминала задано множество путей соединения его с другими терминалами. Например, если используются L-образные пути, то между любой парой терминалов существует не более двух путей. Шаг 0. Положить начальное дерево T = (V, ). Шаг 1. Каждый терминал независимо от других терминалов выбирает кратчайший (по времени) путь, связывающие его с корнем s 0 Шаг i+1.Терминалы независимо друг от друга выбирают кратчайшие пути с учетом дерева, построенного на шаге i. Алгоритм останавливается, когда выполнено заданное количество итераций, или получено ранее построенное дерево. В качестве приближенного решения выбирается дерево с наименьшей критической задержкой.

Пример работы распределенного алгоритма Рассмотрим источник 0 и 3 терминала в прямоугольной метрике. Предположим, используются только L-образные соединения. Тогда каждый терминал может быть соединен с источником не более, чем двумя путями

Пример работы распределенного алгоритма На первом шаге терминалы (независимо) выбирают кратчайшие (по времени) пути из источника

Пример работы распределенного алгоритма На втором шаге каждый терминал ищет лучшее соединение с учетом путей, построенных на предыдущем шаге другими терминалами

Пример работы распределенного алгоритма …И так далее

СПАСИБО ЗА ВНИМАНИЕ