Участник: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>N</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> шагов и возвращаемся на первый шаг.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

Текущая версия на 20:13, 22 октября 2019

Автор описания: И.А.Бабкин

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Федуччи-Маттеуса (FM-алгоритм)[1] является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) с минимальным количеством разрезанных сетей (гиперрёбер) за линейной время.

1.2 Математическое описание алгоритма

Пусть дан гиперграф [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]B[/math] определим, как

[math]|B|=\sum\limits_{i=1}^{|N|} n(i)=\sum\limits_{i=1}^{|C|} s(i)[/math].

Задача заключается в разделении [math]P[/math] на непересекающиеся блоки [math]A[/math] и [math]B[/math] размерами [math]|A|[/math] и [math]|B|[/math] соответственно так, чтобы выполнялось условие

[math]\frac{|A|}{|A|+|B|} \cong r[/math],

где [math]r[/math] - коэффициент разделения ([math]0 \lt r \lt 1[/math]).

Прирост [math]i[/math]-ой ячейки, находящейся в некотором блоке [math]B[/math], определим, как

[math]\Delta g(i)=FS(i)-TE(i)[/math][2],

где [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 \lt n \lt i[/math]) для максимизации [math]G_n[/math]. Если [math]G_n \gt 0[/math], то переходим на следующий шаг, иначе заканчиваем алгоритм.

6. Выполняем полученный проход из [math]n[/math] шагов и возвращаемся на первый шаг.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. Fiduccia C. M., Mattheyses R. M. A linear-time heuristic for improving network partitions //19th Design Automation Conference. – IEEE, 1982. – С. 175-181.
  2. Kahng A. B. et al. VLSI physical design: from graph partitioning to timing closure. – Springer Science & Business Media, 2011.