Алговики - Вклад [ru]

Участник:Midmedian/Алгоритм Федуччи-Маттеуса

2019-10-22T17:13:56Z

Midmedian: Дополнено математическое описание.

Автор описания: [[Участник:Midmedian|И.А.Бабкин]]

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

=== Общее описание алгоритма ===
'''Алгоритм Федуччи-Маттеуса (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>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 < 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> шагов и возвращаемся на первый шаг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==

Участник:Midmedian/Алгоритм Федуччи-Маттеуса

2019-10-22T16:34:49Z

Midmedian: Дополнено математическое описание.

Участник:Midmedian/Алгоритм Федуччи-Маттеуса

2019-10-22T15:46:06Z

Midmedian: Добавлено общее описание алгоритма и кусочек математического описания.

Участник:Midmedian/Алгоритм Федуччи-Маттеуса

2019-10-19T12:10:31Z

Midmedian: Новая страница: «Автор описания: И.А.Бабкин == Свойства и структура алгоритмов == === Общее…»

Автор описания: [[Участник:Midmedian|И.А.Бабкин]]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

== Литература ==