Fiduccia C.M.и Mattheyses R.M., Линейная по времени эвристика для улучшения разбиений сети, In Proc. 19th ACM/IEEE Design Automation Conference, 175-181, 1982 (перевод).

Линейная по времени эвристика для улучшения разбиений сети
C.M. Fiduccia and R.M. Mattheyses
Центр научного исследования и развития
общей электрики
Schenectady, NY 12301

Перевод: Родригес Залепинос Р. А.

АННОТАЦИЯ

Представлена интерактивная эвристика минимального разреза для разделения сетей, для которой, в худшем случае, время вычислений, затрачиваемое на один проход, растёт линейно вместе с размером сети. На практике, обычно требуется всего лишь очень малое число проходов, что приводит к быстрому аппроксимационному алгоритму для разбиения на минимальные разрезы. Для управления ячейками разных размеров, робота алгоритма продвигается с помощью перемещения одной ячейки за раз между блоками разбиения, сохраняя в это время желаемый баланс, основанный, преимущественнее, на размере блоков, а не на количестве ячеек для каждого блока. Используются эффективные структуры данных, чтобы избежать ненужного поиска лучшей ячейки для перемещения, и для минимизации ненужного обновления ячеек, на которые воздействовало очередное перемещение.

1 ВВЕДЕНИЕ

Для каждой сети (network), состоящей из n ячеек (модулей), соединённых множеством связей (сигналов) (сетей) (nets), задача разбиения на минимальный разрез, состоит в нахождении разбиения множества ячеек на 2 блока А и В таким образом, чтобы количество сетей (nets), у которых ячейки принадлежат обоим блокам, было минимальным. В общем, этот процесс сводится к предмету балансировки состояния, при котором возможны только такие разбиения, блоки которых удовлетворяют определённому пользователем критерию, основанному на размере или степени важности в ограниченности действий.

На данный момент точное решение этой проблемы неопределимо в том смысле, что неизвестно в том смысле, что неизвестно о существовании какого-либо полиномиального алгоритма для её решения. Коль скоро на практике сеть (network) может быть очень большой, практичный алгоритм должен по необходимости использовать для этой цели эвристики, которые демонстрируют почти линейные по времени работы случаи. Этой проблемой занималось некоторое количество учёных [1-5] на протяжении прошлого десятилетия. Мы представляем итеративный алгоритм, у которого, в худшем случае, время работы, затрачиваемое на один проход, растёт линейно с размером сети (network), и который, в типичном случае, сходится на практике за несколько проходов. Это линейное по времени поведение достигнуто посредством перемещения одной ячейки за один раз, из одного блока разбиения в другой, в попытке сократить число сетей (nets), у которых ячейки в обоих блоках. Эта идея была независимо применена на практике Shiraishi и Hirose.Техника, полученная Kernigan и Lin применяется для уменьшения вероятности застрявания процесса минимизации на локальном минимуме. Наша главная забота (contribution) состоит в анализе результатов воздействий, которые оказывают перемещённые ячейки на соседние с ними ячейки и в эффективном использовании [полученных] результатов.

После детального описания (specifying) проблемы разбиения сети, мы обсудим эвристику Kernigan и Lin и представим основную концепцию выбора выгодной ячейки (cellgain), использующаяся для выбора ячейки для перемещения из одного блока разбиения в другой. После этого, исследуются свойства выгод (gain) для конструирования структуры данных, позволяющей эффективно управлять изменением выгод ячеек. Затем мы address (рассказываем, ссылаемся) о проблеме достижения желаемого баланса между размерами двух блоков разбиения в обстановке, которая позволяет иметь ячейкам разные размеры. Затем рассматривается (addressed) проблема определения ячеек, на выгоды которых воздействовал очередной шаг. В обоих случаях показано, что общий объём работы, требуемый за один проход, растёт линейно с размером сети. Мы завершаем (close) [статью] обсуждением VAX-основанной реализации алгоритма приведением результатов и времён выполнения, посчитанных (encountered) при работе программы на нескольких примерах.

2 ПОСТАНОВКА ПРОБЛЕМЫ

Следуя Shweikert и Kernigan, мы представляем сеть (network) как множество из С ячеек (модулей) cell(1), ... , cell(C), соединённых N сетями (сигналами) (nets) net(1), ... , net(N). Коль скоро разбиение concerned, без потери общности мы можем сделать перечисленные ниже предположения о том, что есть сеть (network). Мы считаем, что сеть (net) определена как множество, состоящее, по крайней мере, из двух ячеек (cells) в одной сети (net). Число ячеек в сети(i) (net(i)) будем обозначать как n(i). Любые две ячейки, разделяющие, как минимум, одну сеть (net), называются соседями. Считается, что каждая ячейка имеет размер s(i) и количество контактов (pins) p(i), определяющее к скольким сетям (nets) принадлежит эта ячейка. Эти предположения легко устанавливаются процедурой (routine) ввода, устанавливающей этот порядок. Считается, что на входе сети (nets) подаются сразу, в любом порядке; каждая сеть (net) подаётся полностью перед тем, как начинает подаваться следующая сеть (net).

Т.к. (since) одна единица в контакте для одной и только одной сети (net), то общее число контактов p(1) + ... + p(C), называемое P, может быть принято за "размер" сети (network). Ясно (clear), что ни С, ни N не послужит для этой цели, т.к. ни число контактов р(i) для ячейки, ни количество ячеек на сеть n(i) не является ограниченным. В любом случае, и С и N ограничены как O(P).

Следующая процедура ввода будет работать с реальными сетями (networks), чьи сети (nets) часто подаются как списки пар (ячейка, контакт), что нарушает некоторые вышеперечисленные предположения касательно того, что составляет сеть (net). Сети (nets) последовательно пронумерованы 1, 2, ..., N в той последовательности, которой они подаются (encountered) во входном потоке. Предполагается, что ячейки идентифицируются целыми числами в диапазоне 1, 2, ..., С. Основная (principal) функция, выполняемая процедурой - конструирования двух структур данных из последовательности сетей (nets), подаваемых на входе. Первая структура - массив CELL, который для каждой ячейки содержит связный список сетей (nets), содержащих эту ячейку. Вторая структура - массив NET, содержащий для каждой сети (net) связный список ячеек в этой сети (net). В обоих случаях каждый создаваемый связный список рассматривается (regarded) как множество без дубликатов и без указания порядка для элементов. Каждая запись (record) в каждом из этих массивов содержит также несколько дополнительных полей, использующихся алгоритмом для выполнения своего назначения.

/* Процедура ввода списка сетей (net-list) */
ДЛЯ каждой сети (net)  n = 1 ... N  do
    ДЛЯ каждой (ячейка, контакт) пары (i, j) 
        в сети   n  do
        /*сохранение(maintain) свойства множества */
        ЕСЛИ  сеть  n  не  в начале списка сетей  (net-list) для ячейки  i
        ТО    вставить ячейку i в список ячеек (cell-list) cети  n  
                 и вставить сеть (net) n  в список  сетей (net-list) ячейки  i. 
     КЦ ДЛЯ
КЦ ДЛЯ

Следует также удалять сети (nets) только с одной ячейкой и ячейки, которые не содержаться ни в одной из поданных сетей (nets). Ясно, что для выполнения вышеуказанной работы, достаточно (suffice) времени O(P), при условии (provided), что количество пар (ячейка, контакт) во входном потоке есть O(P).

В разбиении ячеек на два блока А и В, сеть (net) называется разрезанной (cut), если хотя бы одна ячейка из этой сети (net) содержится в каждом блоке и неразрезанной (uncut) иначе. Будем называть это состоянием разрезанности (cutstate) сети (net). Это состояние может быть deduced из сетевого (net's) распределения (distribution) - количества ячеек, содержащихся в блоках А и В соответственно (respectively).

Множество разреза (cutset) разбиения определяется как множество всех разрезанных сетей. И, наконец, размер (size) |X|, блока ячеек Ч определяется как сумма размеров s(i) составляющих его ячеек.

Для заданной доли (отношения) 0 < r < 1 мы желаем разбить сеть на 2 блока А и В таким образом, чтобы |A| / (|A| + |B|) ? r, и чтобы при этом минимизировать мощность (cardinality) полученного в результате множества разрезов. Отношение r предназначено (intended) только для того, чтобы установить (capture) критерий баланса конечного разбиения, полученного алгоритмом. Не следует считать, что каждое перемещение должно сохранять баланс (хотя это, конечно, не исключено), ни то, что в частности, исходное разбиение должно быть сбалансированным. Позже мы обсудим этот момент (point) более подробно. Помимо задания отношения r и начального разбиения (А либо В может быть пустым), пользователю разрешается обозначать (designate) некоторые ячейки как "фиксированные" в одном из двух (either) блоков А или В разбиения. Это позволяет использовать алгоритм для дальнейшего улучшения (refine) блоков, созданных предыдущими разбиениями.

3 ОСНОВНАЯ ИДЕЯ

Для данного разбиения ячеек (А, В) главной идеей алгоритма является перемещение одной ячейки за раз из одного блока разбиения в другой в попытке минимизировать множество разрезов конечного разбиения. Ячейка, которую нужно переместить, называется базовой ячейкой (base cell). Она выбирается на основании критерия баланса и по влиянию на размер текущего множества разрезов. Определим выгоду (gain) g(i) ячейки (i), как число сигналов, на которые уменьшиться множество разрезов при перемещении ячейки (i) из текущего блока в комплиментарный. Заметим, что выгода ячейки может быть отрицательна. На самом деле, g(i) должна быть целым числом в диапазоне от -p(i) до +p(i). Также ясно, что во время каждого перемещения нам надо держать в уме критерий баланса, для предотвращения миграции всех ячеек в один блок разбиения. Несомненно, что разбиение, для которого баланс проигнорирован, будет наилучшим. Таким образом, критерий баланса используется для выбора блока, из которого будет перемещена ячейка с наивысшей выгодой. Часто будет иметь место случай, при котором выгода выбранной ячейки будет неположительной. В таком случае, мы всё-таки переместим ячейку в ожидании того, что перемещение позволит алгоритму "выбраться из локального минимума". После того, как сделаны все перемещения, лучшее разбиение, вычисленное за время прохода, берётся как выход этого прохода. Эта техника минимизации подаётся согласно Kernigan и Lin.

Чтобы предотвратить процесс перемещения ячеек от "thrashing", или вхождения в бесконечный цикл, каждая базовая ячейка немедленно "блокируется" в своём новом блоке до конца этого прохода. Т.о. только свободным ячейкам в действительности разрешено делать одно перемещение в течении некоторого прохода до тех пор, пока все ячейки не будут заблокированы либо критерий баланса воспрепятствует (prevents) последующим перемещениям. Затем возвращается лучшее разбиение, полученное в течении прохода. Затем могут совершаться дополнительные проходы до тех пор, когда в дальнейшем они не будут давать улучшений. Обычно на практике это происходит быстро, за несколько шагов, что приводит к почти линейному алгоритму; однако мы ничего не утверждаем (claim) о числе проходов, необходимых (require) в худшем случае, за исключением обращения вашего внимания на очевидный факт, что возможно только O(n) проходов, т.к. (since) множество разрезов (cutset) ограничено числом сигналов.

Объём работы (bulk), необходимый для осуществления перемещения, состоит в выборе базовой ячейки, её перемещении, и затем согласования (adjusting) выгод её свободных соседей. Если это не будет делаться аккуратно, то для каждой ячейки будет пересчитываться её выгода каждый раз при перемещении одной из её соседок. В этом точно нет необходимости. Наивный (naive) подход приведёт к алгоритму, выполняющему (n(i))2+ ... +(n(i))2 = O(p2) вычислений выгоды за проход. Это вытекает (stems) из того факта, что отношение соседства induced сигналом, содержащим n ячеек, является полным графом с O(n2) рёбрами. Т.к. однократное вычисление выгоды для ячейки с p(i) pins занимает O(p(i)) времени (work), этот подход к поддержанию выгод ячеек займёт более чем O(P2) времени. Это довольно (particularly), даже если существует [лишь] один большой сигнал.

Мы решаем первую проблему (выбора базовой ячейки) с наибольшей выгодой в этом блоке) использованием структуры данных, которая быстро возвращает ячейку с наибольшей выгодой и позволяющую перевнести в неё перевычисленную выгоду ячейки за константное время. Мы рассматриваем (consider) решение этой проблемы в следующей секции, где мы обсуждаем понятие (notion) выгоды ячейки.

Вторая проблема (обновление выгод соседок базовой ячейки) намного интересней. Наивный алгоритм заключается в пересчёте выгоды каждой свободной ячейки в каждом сигнале базовой ячейки. Мы избегаем такого потребления (consuming) времени pitfalls показывая, что сигнал (i) никогда не accounts для более чем 2n(i) перевычислений выгоды за время одного полного прохода. Более того, мы показываем, что каждое перевычисление выгоды может быть заменено соответствующей последовательностью простых инкременирования / декременирования выгоды, которые могут выполнятся за константное время. Эти решения двух проблем сокращают общую работу, необходимую для выполнения одного прохода, до O(P) в худшем случае.

4 ПРОИЗВОДИТЕЛЬНОСТЬ И ПРИЛОЖЕНИЯ

Алгоритм реализован на языке С и работает на VAX 11/780. Его производительность была вычислена использованием его для разбиения нескольких случайно-логичных многоячеечных конструкций. Ниже перечислены четыре примера. В среднем, чип имел 267 ячеек, 245 сетей (nets) и 2650 контактов. На этих чипах алгоритм типично делает около 900 перемещений за процессорную секунду. Это, конечно же, будет зависеть от среднего количества контактов на ячейку и размеров сетей (nets). Фактор, при котором алгоритм будет работать лучше наивного алгоритма, будет зависит от размера сети (network) и, особенно, от размера наибольшей сети (net). Новый алгоритм лучше, особенно когда сеть (network) содержит даже одну большую сеть (net).

	CELLS	NETS	PINS	PASSES	TIME
Chip 1	306	300	857	3	1.63
Chip 2	296	238	672	2	.98
Chip 3	214	222	550	5	1.91
Chip 4	255	221	571	5	2.09

Таблица 4 − Производительность программы

В таблице 4: Chip - чип, Cells - число ячеек, Nets - число сигналов, Pins - контактов, Passes - количество проходов, Time - время работы.

Как инструмент размещения ячеек в полиячеечном окружении, алгоритм применяется двумя довольно примечательными способами. Первый - это очевидное приложение для разбиения ячеек по каналам. Мы называем это межканальное размещение. Его цель - сократить количество необходимых межканальных связей. Второе приложение - инструмент для внутриканального размещения. Здесь целью является сократить давление в канале и длину проводов. Это делается рекурсивно, чтобы сперва определить, в какой половине канала должна быть размещена ячейка, потом в какой четверти, и т.д. Мы чувствуем, что это новый подход для внутриканального размещения.

БЛАГОДАРНОСТИ

Авторы хотят поблагодарить Боба Дерроу, реализовавшего алгоритм на VAX. Без обратной связи, которую мы получили от этих реализаций, трудно было бы оценить эвристическое решение. Также благодарим Фила Льюиса и Рона Ривеста за их предложения.

СПИСОК ЛИТЕРАТУРЫ

1. M. A. Breuer, "Min-Cut Placement", J. of Design and Fault-Tolerant Computing, Vol. I, number 4, Oct. 1977, pp. 343-362.
2. M. A. Breuer, "A Class of Min-Cut Placement Algorithm", Proc. 14th Design Automation Conference, New Orleans, 1977, pp. 284-290.
3. B. W. Kernigan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", Bell System Technical Journal, Vol. 49, Feb. 1970, pp. 291-307.
4. D. G. Schweikert and B. W. Kernigan, "A Proper Model for the Partitioning of Electrical Circuits", Proc. 9th Design Automation Workshop, Dallas, June 1979, pp. 57-62.
5. H. Shiraishi and F. Hirose, "Efficient Placement and Routing for Masterslice LSI", Proc. 17th Design Automation Conference, Minneapolis, June 1980, pp. 458-464.