4 / 15
Выявление высокоуровневых иерархических структур сверхбольших интегральных схем…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 4
7
Объединение
[7] —
это метрика, считающая число внутренних соедине-
ний, которое растет с размером кластера, что плохо подходит для сравнения
двух кластеров, как претендентов на ЛСГ. Кластер, больший по размеру, всегда
будет обладать бóльшим весом и, как следствие, большей способностью к объ-
единению.
Метрики разреза отношения и масштабированного разреза
[8] используют
при расчете веса кластера по формуле
( )
.
| |
T C
C
Поскольку
Т
(
С
) растет намного мед-
леннее, чем размер кластера, то больший кластер будет всегда иметь меньший вес,
что не позволяет такой метрике сравнивать кластеры разных размеров.
В [9] предложено использовать экспоненту Рента для измерения парамет-
ров кластера, при этом вес кластера
С
пропорционален
ln ( ) .
ln | |
T C
C
Несмотря на то,
что это более верно, чем при разрезе отношения, вес кластера по-прежнему мо-
нотонно убывает с его ростом.
В [10] представлена концепция метрики РС (разделение степени). Степень —
среднее число связей, инцидентных каждой вершине в кластере, разделение —
средняя длина самого короткого пути между двумя вершинами. Проход по случай-
ному пути в этом методе помогает получить хорошую глобальную кластеризацию
схемы. Однако недостаток этой метрики в том, что она не рассматривает внешних
соединений кластера. Более того, среднее значение здесь используется для оценки
качества всей кластеризации, а не отдельного кластера.
В [11, 12] приведены несколько сложных метрик: связность, раздельность
граней и слипание, которые могут быть полезны при решении поставленной
задачи. Однако эти метрики не учитывают разный размер кластеров и требуют
значительных временных затрат при вычислении.
В итоге ни одна из рассмотренных методик не сравнивает кластеры разных
размеров, не смещаясь в сторону больших или меньших. Предлагаемая метрика
будет учитывать размер кластера при подсчете коэффициента его связности.
Метрики для ЛСГ.
Такая метрика должна, во-первых, сравнивать кластеры
различных размеров, во-вторых, измерять связность групп ячеек. Начнем с раз-
реза отношения (
RC
) и метрики Рента (Rent) для каждого кластера
С
. Как об-
суждалось ранее:
( )
( )
| |
T C
RC C
C
ln ( )
Rent( )
,
ln | |
T C
C
C
где
Т
(
С
) — число цепей в разрезе, а |
C
| — размер кластера,
— знак пропорци-
ональности. Недостаток обеих метрик в том, что числитель (относящийся к
разрезу) и знаменатель (относящийся к размеру кластера) не масштабируются
относительно друг друга. Однако из правила Рента известно, что
Т
(
С
) должен
расти пропорционально |
C
|
p
, где
p
— экспонента Рента,
p
< 1. Таким образом,
можно задать вес ЛСГ (
GTL
-
S
) как