8 / 15
Выявление высокоуровневых иерархических структур сверхбольших интегральных схем…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 4
11
линейного упорядочивания. Экспонента Рента для группы
С
может быть полу-
чена как
ln ( ) ln ,
ln | |
C
T C A
C
где
C
A
— среднее число пинов ячейки
С
.
Этот метод описан для нахождения одной ЛСГ в схеме. Если начальное
зерно находится за пределами ЛСГ, то дальнейшие действия не приведут к
нахождению такой группы и на функции не будет минимумов. Для того чтобы
найти ЛСГ, необходимо провести несколько поисков с различными начальными
зернами. Если число поисков будет достаточным, то все ЛСГ будут найдены.
Фаза 3. Улучшение и сокращение ЛСГ.
Кандидат ЛСГ, выращенный из слу-
чайного зерна, может не входить в ЛСГ. Например, если кандидат находится на
границе ЛСГ, то могут быть включены некоторые ячейки, которые группе не при-
надлежат. Для того чтобы этого не происходило, необходимо найти для каждого
кандидата
B
i
, полученного на 2-м этапе, набор других кандидатов
,1 ,2
,
,
, ...,
,
i
i
i l
B B B
используя зерна внутри
B
i
и те же действия, что на этапах 1 и 2. Эти кандидаты
обычно близки, но немного отличаются от
B
i
. Затем к
,1 ,2
,
{ ,
, ... ,
ˆ ˆ
ˆ }
i
i
i l
B B B
применяют
операции объединения и пересечения, похожие на генетический алгоритм. Нако-
нец, кандидат
i
B
c лучшим весом относительно предложенных метрик выбирает-
ся как улучшенный кандидат относительно
B
i
. Эта процедура проводится над все-
ми начальными кандидатами в
B
для получения набора улучшенных кандидатов
,1 ,2
,
{ ,
, ...,
ˆ ˆ
ˆ }.
i
i
i l
B B B
Затем улучшенные кандидаты сравниваются друг с другом. Если
один из кандидатов пересекается с другим и ухудшает вес ЛСГ, то он отсеивается.
Отделенные кандидаты, оставшиеся в конце, являются результирующим набором
ЛСГ предложенного метода.
Следует отметить, что все три фазы, описанные ранее, могут быть выпол-
нены для
m
начальных зерен параллельно. Единственная часть алгоритма, ко-
торую необходимо выполнять последовательно, это сравнение полученных кан-
дидатов в фазе 3.
Эксперимент на реальных данных.
В результате применения полученных
метрик и алгоритмов к фрагменту таблицы соединений СБИС Atmega 328 были
получены минимумы на графике функции ЛСГ, которые соответствовали функ-
циональным элементам схемы (рис. 4,
а
).
Такие минимумы носили локальный характер и затрудняли автоматизацию
принятия решения о принадлежности группы ячеек к функциональному эле-
менту. В результате анализа входных данных реальной таблицы соединений
элементов СБИС было установлено, что сигналы сброса и тактирования, кото-
рые являются общими у большого числа ячеек — членов функциональных
фрагментов, мешают четкому выделению структур по их функции, несмотря на
то, что удовлетворяют всем требованиям предложенных метрик.
Выделить такие «общие» цепи в автоматическом или полуавтоматическом ре-
жимах можно по тому, как число элементов, подключенных к этим цепям, в не-
сколько раз превышает число элементов, подключенных к остальным цепям схемы.
Для того чтобы избавиться от влияния общих цепей на поиск ЛСГ, носящих одну