Участник:Midmedian/Алгоритм Федуччи-Маттеуса: различия между версиями
Midmedian (обсуждение | вклад) (Добавлено общее описание алгоритма и кусочек математического описания.) |
Midmedian (обсуждение | вклад) (Дополнено математическое описание.) |
||
| Строка 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>-ой ячейкой. | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Версия 19:34, 22 октября 2019
Автор описания: И.А.Бабкин
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 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 Свойства и структура алгоритмов
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]-ой ячейкой.
