3 / 15
В.И. Кузовлев, Н.А. Иванова
6
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 4
Существующие метрики кластеризации не позволяют сравнивать группы
ячеек различных размеров. Необходимо так разграничивать структуры, чтобы
компоновщик и трассировщик смогли правильно сформировать топологию
схемы. Такие метрики и алгоритмы позволяют выделять как несколько неболь-
ших ЛСГ, так и одну крупную ЛСГ, включающую в себя более мелкие. Метрики
масштабированы таким образом, что приблизительный коэффициент связ-
ности одного обычного кластера равен единице, а которые меньше обычного,
оцениваются меньшими значениями (например, менее 0,1), что соответствует
ЛСГ.
Далее будет показано, как использовать метрику, чтобы найти набор ЛСГ.
Алгоритм начинает работу со случайно выбранного зерна и разрастается в ЛСГ
путем итеративного добавления ячеек. Для одновременного разрастания не-
скольких зерен и исключения тех кандидатов, которые не подходят или накла-
дываются друг на друга, используется распараллеливание потоков. Результатом
является независимый набор обнаруженных ЛСГ.
Существующие решения.
Логически связанная группа, как и кластер, яв-
ляется фрагментом схемы логических ячеек, поэтому складывается впечатле-
ние, что к ЛСГ можно применить традиционные кластерные метрики. Однако
существуют некоторые явные различия в формулировках проблемы поиска
сильно связнных логических структур и проблемы кластеризации ячеек.
1. Общепринятая кластеризация приводит к снижению размеров площади
размещения. Такие кластеры, как правило, малы (от двух до десяти ячеек) для
того, чтобы не потерять много данных при решении задачи уменьшения места
расстановки. Кластеризация такого типа имеет локальную природу [6]. Однако
функциональные элементы являются большими особыми логическими струк-
турами, состоящими из сотен и тысяч ячеек, что требует более глобального
подхода, учитывающего как внешние, так и внутренние связи групп.
2. При обычной кластеризации необходимо, чтобы каждая ячейка принад-
лежала кластеру, которые составляют всю схему СБИС. При выделении ЛСГ,
напротив, рассматриваются особые подгруппы ячеек, которые будут разме-
щаться другим приоритетным способом.
Пусть входная электрическая принципиальная схема СБИС будет гипергра-
фом
G
= (
V
,
E
), где
V
(вершины графа) — это набор ячеек, а
E
(ребра графа) —
набор связей таких, что каждая
e
E
соединена с подмножеством
V
. Результатом
кластеризации является набор отдельных подмножеств ячеек
С
1
,
С
2
, …,
С
к
V
таких, что
V
=
С
1
С
2
, …,
С
к
. Пусть дан кластер
С
, тогда разрез графа
определяется как размер множества
0& (
)
0 .
T C e E C e
V C e
│
Метрики кластеризации
могут получать разрез графа двумя различными
способами, но в основном разрез не зависит от размера кластера. Это более
уместно при делении или размещении сверху вниз, где размеры областей огра-
ничены.