Участник:Midmedian/Алгоритм Федуччи-Маттеуса: различия между версиями
Midmedian (обсуждение | вклад) Добавлено общее описание алгоритма и кусочек математического описания. |
Midmedian (обсуждение | вклад) Дополнено математическое описание. |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 5: | Строка 5: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Федуччи-Маттеуса (FM-алгоритм)'''<ref>Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.</ref> является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) за линейной время. | '''Алгоритм Федуччи-Маттеуса (FM-алгоритм)'''<ref>Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.</ref> является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) с минимальным количеством разрезанных сетей (гиперрёбер) за линейной время. | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Пусть дан гиперграф <math>P=(C,N)</math>, где <math>C</math> - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей | Пусть дан гиперграф <math>P=(C,N)</math>, где <math>C</math> - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей <math>N</math>. Гарантируется, что гиперграф состоит как минимум из двух ячеек и что каждая из ячеек содержится хотя бы в одной из сетей. | ||
''Количество ячеек'' в <math>i</math>-ой сети обозначим как <math>n(i)</math>, а ''размер'' <math>j</math>-ой ячейки (количество сетей, в которые входит ячейка) за <math>s(j)</math>. | ''Количество ячеек'' в <math>i</math>-ой сети обозначим как <math>n(i)</math>, а ''размер'' <math>j</math>-ой ячейки (количество сетей, в которые входит ячейка) за <math>s(j)</math>. | ||
| Строка 21: | Строка 21: | ||
где <math>r</math> - ''коэффициент разделения'' (<math>0 < r < 1</math>). | где <math>r</math> - ''коэффициент разделения'' (<math>0 < r < 1</math>). | ||
''Прирост'' <math>i</math>-ой ячейки, находящейся в некотором блоке <math>B</math>, определим, как | |||
:<math>\Delta g(i)=FS(i)-TE(i)</math><ref>Kahng A. B. et al. VLSI physical design: from graph partitioning to timing closure. – Springer Science & Business Media, 2011.</ref>, | |||
где <math>FS(i)</math> - количество разрезанных сетей, связанных только с <math>i</math>-ой ячейкой (и никакой другой из блока <math>B</math>), а <math>TE(i)</math> - количество неразрезанных сетей, связанных с <math>i</math>-ой ячейкой. | |||
''Максимальный положительный прирост'' <math>G_n</math> определим, как максимальную сумму приростов ячеек за префикс прохода, состоящего из <math>n</math> шагов: | |||
:<math>G_n=\sum\limits_{i=1}^{n} \Delta g_i</math>. | |||
Ячейка называется ''базовой'', если среди всех ячеек блока она обладает наибольшим приростом. | |||
Теперь можно перейти к непосредственному описанию FM-алгоритма. На вход подаётся пара блоков: | |||
1. Вычисляем приросты всех ячеек. <math>i=1.</math> | |||
2. Среди возможных незафиксированных базовых ячеек выбираем ту, при перемещении которой соблюдается критерий алгоритма. Перемещаем её. | |||
3. Фиксируем выбранную базовую ячейку. Перевычисляем приросты всех незафиксированных ячеек, связанных с выбранной разрезанной сетью. | |||
4. Если все ячейки зафиксированы, то переходим на следующий шаг. Иначе, <math>i:=i+1</math>, возвращаемся на второй шаг. | |||
5. Определяем наилучший префикс ячеек <math>c_1, \dots, c_n</math> (<math>1 < n < i</math>) для максимизации <math>G_n</math>. Если <math>G_n > 0</math>, то переходим на следующий шаг, иначе заканчиваем алгоритм. | |||
6. Выполняем полученный проход из <math>n</math> шагов и возвращаемся на первый шаг. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Текущая версия от 17:13, 22 октября 2019
Автор описания: И.А.Бабкин
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Федуччи-Маттеуса (FM-алгоритм)[1] является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) с минимальным количеством разрезанных сетей (гиперрёбер) за линейной время.
Математическое описание алгоритма
Пусть дан гиперграф [math]\displaystyle{ P=(C,N) }[/math], где [math]\displaystyle{ C }[/math] - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей [math]\displaystyle{ N }[/math]. Гарантируется, что гиперграф состоит как минимум из двух ячеек и что каждая из ячеек содержится хотя бы в одной из сетей.
Количество ячеек в [math]\displaystyle{ i }[/math]-ой сети обозначим как [math]\displaystyle{ n(i) }[/math], а размер [math]\displaystyle{ j }[/math]-ой ячейки (количество сетей, в которые входит ячейка) за [math]\displaystyle{ s(j) }[/math].
Размер блока [math]\displaystyle{ B }[/math] определим, как
- [math]\displaystyle{ |B|=\sum\limits_{i=1}^{|N|} n(i)=\sum\limits_{i=1}^{|C|} s(i) }[/math].
Задача заключается в разделении [math]\displaystyle{ P }[/math] на непересекающиеся блоки [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] размерами [math]\displaystyle{ |A| }[/math] и [math]\displaystyle{ |B| }[/math] соответственно так, чтобы выполнялось условие
- [math]\displaystyle{ \frac{|A|}{|A|+|B|} \cong r }[/math],
где [math]\displaystyle{ r }[/math] - коэффициент разделения ([math]\displaystyle{ 0 \lt r \lt 1 }[/math]).
Прирост [math]\displaystyle{ i }[/math]-ой ячейки, находящейся в некотором блоке [math]\displaystyle{ B }[/math], определим, как
- [math]\displaystyle{ \Delta g(i)=FS(i)-TE(i) }[/math][2],
где [math]\displaystyle{ FS(i) }[/math] - количество разрезанных сетей, связанных только с [math]\displaystyle{ i }[/math]-ой ячейкой (и никакой другой из блока [math]\displaystyle{ B }[/math]), а [math]\displaystyle{ TE(i) }[/math] - количество неразрезанных сетей, связанных с [math]\displaystyle{ i }[/math]-ой ячейкой.
Максимальный положительный прирост [math]\displaystyle{ G_n }[/math] определим, как максимальную сумму приростов ячеек за префикс прохода, состоящего из [math]\displaystyle{ n }[/math] шагов:
- [math]\displaystyle{ G_n=\sum\limits_{i=1}^{n} \Delta g_i }[/math].
Ячейка называется базовой, если среди всех ячеек блока она обладает наибольшим приростом.
Теперь можно перейти к непосредственному описанию FM-алгоритма. На вход подаётся пара блоков:
1. Вычисляем приросты всех ячеек. [math]\displaystyle{ i=1. }[/math]
2. Среди возможных незафиксированных базовых ячеек выбираем ту, при перемещении которой соблюдается критерий алгоритма. Перемещаем её.
3. Фиксируем выбранную базовую ячейку. Перевычисляем приросты всех незафиксированных ячеек, связанных с выбранной разрезанной сетью.
4. Если все ячейки зафиксированы, то переходим на следующий шаг. Иначе, [math]\displaystyle{ i:=i+1 }[/math], возвращаемся на второй шаг.
5. Определяем наилучший префикс ячеек [math]\displaystyle{ c_1, \dots, c_n }[/math] ([math]\displaystyle{ 1 \lt n \lt i }[/math]) для максимизации [math]\displaystyle{ G_n }[/math]. Если [math]\displaystyle{ G_n \gt 0 }[/math], то переходим на следующий шаг, иначе заканчиваем алгоритм.
6. Выполняем полученный проход из [math]\displaystyle{ n }[/math] шагов и возвращаемся на первый шаг.