7 / 15
В.И. Кузовлев, Н.А. Иванова
10
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 4
Метод нахождения ЛСГ.
Далее предлагается прямой алгоритм нахождения
ЛСГ, основанный на рассмотренных метриках. Он состоит из трех фаз.
Фаза 1: линейное упорядочение.
Фаза 2: получение начальных кандидатов ЛСГ.
Фаза 3: улучшение и сокращение ЛСГ.
Фазы 2 и 3 могут сочетаться с разными методами линейного упорядочива-
ния [13].
Фаза 1. Линейное упорядочение
инициализирует группу ячеек, зерновая
ячейка которой выбрана случайно. Затем к группе добавляется по одной ячейке.
Кандидатами на добавление в группу являются ячейки, которые не входят в
группу, но соединены с ней напрямую. Среди этих кандидатов выбирается один
с самым большим весом присоединения. Если у ячейки–кандидата
v
i
есть связь,
не ведущая к группе, и у этой связи есть λ(
е
) пинов снаружи группы, то ее вес
будет равен
1 .
( ) 1
e
Чем больше пинов внутри группы, тем больше вес. Связь
между
v
i
и группой определяются как
|
,
0
1 .
( ) 1
e v e e C i
e
Для разрушения свя-
зей в качестве второго критерия используют минимальный разрез.
Таким образом, строятся группы связнных ячеек для получения возможно-
го линейного порядка. По мере последовательного присоединения ячеек, функ-
ция весов будет влиять на увеличение степени связности.
В начале объединения ячеек важно уделять внимание связности
|
,
0
1 ,
( ) 1
e v e e C i
e
а не только минимальному разрезу. Если ячейка–кандидат
находится вне ЛСГ, как правило, у нее меньше связей с соседями, чем у ячейки
внутри ЛСГ. Если использовать минимальный разрез как основной критерий
объединения, скорее всего такая ячейка будет включена в группу. Аналогично,
если ячейка–кандидат находится внутри ЛСГ, как правило, она имеет необхо-
димое число связей с соседними ячейками, а критерий минимального разреза
может исключить ее из ЛСГ. Порядок, по которому ячейки добавляются, задает
линейный порядок. Чем большее предпочтение отдается соединениям, а не раз-
резу, тем плотнее будет группа и тем меньше будет внешних связей, тем больше
к ЛСГ будет добавлено ячеек, которые и должны ей принадлежать.
Фаза 2. Выбор начального кандидата ЛСГ.
Группа ячеек может быть
получена из линейного порядка согласно метрикам. Пусть группа
С
, размера
k
= |
C
|, составлена из первых
k
ячеек линейного порядка, тогда функции
- ( )
GTL SD C
и
- ( )
GTL S C
с учетом
k
будут выглядеть как на рис. 2 и 3. В случае,
если на графике функции присутствует ярко выраженный минимум, соответ-
ствующая группа ячеек будет кандидатом
GTL
«
B
». В процессе вычисления ве-
совой функции
nGTL
необходимо принять значение экспоненты Рента
р
как
среднее значение экспоненты Рента для всех групп, полученных в результате