АЛГОРИТМ КОМПОНОВКИ

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

В качестве оценки для отбрасывания менее перспективных решений используются средние оценки межузлового критерия для всей сети.

А теперь рассмотрим подробно алгоритм компоновки схем.

Одной из ключевых задач автоматизации конструирования вычислительных систем является задача компоновки. Она имеет множество традиционных и классических постановок.

Обычные её решения основаны либо на точных методах, носящих, как правило, переборный характер, либо на последовательных алгоритмах, которые из-за невысокой точности требуют применения дополнительных улучшающих алгоритмов. [1]

Предлагается алгоритм компоновки, который связан с ограниченным перебором вариантов, но по своей схеме решения приводит к результатам, близким к оптимальным. В отличие от последовательных алгоритмов, которые основаны на принципе поиска локального оптимума, на очередном шаге компоновки, предлагаемый алгоритм базируется на оценочной функции, ведущей к глобальному оптимуму.

Алгоритм ориентирован на компоновку схем, имеющих нерегулярную внутреннюю структуру, для которых задача компоновки обычно формулируется как процедура разбиения исходной схемы на подсхемы при заданных ограничениях и критерии качества.

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

Формальной моделью исходной системы могут быть гиперграфы, двудольные графы. Так как они все могут быть однозначно представлены изоморфными матричными или списочными структурами данных, которые необходимы для их машинного представления, то для рассматриваемой задачи все указанные графовые модели являются идентичными.

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

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

Исходными данными для алгоритма являются: допустимое число компонентов конструктивного узла – m; допустимое число внешних соединений узла – p; матрица инциденций для гиперграфа исходной схемы, отражающая информацию о связанности компонентов схемы; число компонентов исходной схемы – z.

Для реализации алгоритма последовательно вычисляются величины:

где n₁ – начально число узлов оптимальной компоновки.

где l₁ – максимально возможное суммарное число внешних связей между n₁ узлами.

где  – число связей между i и j компонентами исходной схемы, а L – суммарное число связей между всеми компонентами схемы.

,

где  – суммарное число внутренних связей в n₁ узлах.

где  – среднее суммарное число связей между компонентами одного узла.

Величины  и  являются начальными потенциальными оценками компоновки.

Очевидно, что оптимальная компоновка должна удовлетворять условию:

где  – суммарное число связей в узле.

Левую часть выражения (1) можно представить в виде:

В нём первое слагаемое определяет отклонение от потенциальной оценки первого шага компоновки, второе – для второго, и так далее.

Таким образом, выражение (2) задаёт стратегию компоновки и его значение может служить оценкой компоновки. Само выражение (2) может принято в качестве оценочной функции. Необходимо стремиться к такому варианту компоновки, для которого выражение (2) принимает максимальное значение.

На каждом шаге компоновки значения  и  можно уточнять. С учётом этого, оценочную функцию для k-го шага компоновки можно представить в виде:

где k означает номер текущего шага решения.

Значение  можно определить с помощью выражения:

Величины  и  можно определить с помощью выражений

Величина  определяется из выражения:

где  – число компонентов исходной схемы, из которой удалены элементы, скомпонованные на  предшествующих шагах. Введя обозначение , оценочную функцию  для -го шага компоновки можно представить в виде: .

Список литературы:

1. Абрайтис Л.Б., Шейнаускис Р.И., Жилевичус В.А. Автоматизация проектирования ЭВМ. М.сов.радио, 1978. – 31с.
2. Зазеннов Г.Г., Савельев П.В., Ермак В.В. и др. Автоматизация проектирования БИС. Практическое пособие в 6 кн. М., 1990. – 27с.