close

Вход

Забыли?

вход по аккаунту

?

10315.On circuit partitioning for physical design of CMOS standard cells

код для вставкиСкачать
Материалы Международной конференции
Интеллектуальные САПР”
“
метод–пересечение каждого с каждым, с последующим выполнением операции
поглощения кубов. Другой метод – пересечение с ограничениями. В соответствии
с единым форматом схемы ФЕ = Ф( X, Z, Y, Y’ ), где Х - независимые входы схемы, Y- сигналы обратной связи, определяющие исходное состояние схемы, Y’сигналы обратной связи, определяющие последующее состояние схемы, и Z – выходные или внутренние значения комбинационных элементов (подсхем) схемы.
Ограничения можно задавать как для любого поля вектора ФЕ, так и для любого
сочетания полей и ограничений.
Введем ограничения на пересечения по полю Y, что соответствует построению графа переходов в прямом направлении. Положив начальные значения
Y0=(ххх…х), вычисляем исходное состояние ФЛС. Полученное значение Y0’ автоматически вносится в вектор ограничений az в поле Y и в дальнейшем Y0 является
ограничением на выбор очередных кубов из покрытия C(f), т.е., если ci∩az=∅, то
данный куб из перебора исключается, если ci ∩az≠∅, то куб ci участвует в операции пересечения и полученное решение Yk’ вносится в поле Y вектора ограничений.
Построенный граф переходов ФЛС позволяет формализовать моделирование,
верификацию и построение различных испытательных последовательностей путем
направленного перебора по вершинам и дугам графа. Формализация ограничения в
виде функции запрета задается в виде специального предиката.
УДК 681.3
Andrei Zinchenko and Alexander Marchenko
ON CIRCUIT PARTITIONING FOR PHYSICAL DESIGN OF CMOS
STANDARD CELLS
As circuit size of CMOS standard cells is constantly growing and nowadays reaches
hundreds of transistors, the hierarchical top-down techniques may be successfully applied
for automatic layout synthesis of such cells. Therefore the circuit partitioning becomes an
important task of an automated layout synthesis flow for standard cells.
Circuit partitioning itself is the well known task and there are lots of data representation models and algorithms applied on them to achieve better circuit partitioning results
. A hypergraph-based circuit representation model seems to be the most widely used for
such task. The mapping of circuit to hypergraph is usually straightforward - each net is
represented as hyperedge and components are represented as vertices. There are several
K-way partitioning algorithms and heuristics capable to produce good hypergraph partitioning results for given K ,. There are some software packages combining the best
known approaches and producing very good hypergraph partitioning results. The hMeTiS package is one of them .
Unfortunately the hypergraph K-way partitioning task does not completely reflect
the nature of mentioned circuit partitioning problem since it uses only data about circuit
topology. Many layout specific properties and constraints which are very important for
standard cell layout design can not directly fit into that model. In these conditions even
optimal hypergraph partitioning may happen to be useless for specified task.
We propose the heuristic on mapping the circuit to a hypergraph in such way that
any reasonably good K-way partitioning of that would lead to acceptable physical hierarchy of the circuit thus anticipating successful hierarchical layout design of the stan-
199
Известия ТРТУ
Тематический выпуск
dard cell. The essence of our approach is to represent each circuit net as a set of hyperedges with different weights instead of one weighted hyperedge. Some important properties of proposed technique are:
♦
It reflects some CMOS-specific functional peculiarities which make partitioning
reasonable from functional point of view;
♦
It can incorporate the cell layout-specific assumptions and constraints to simplify
further placement and routing tasks;
♦
It can be easily modified for regular graph-based partitioning techniques;
The implementation of proposed technique with use of hMeTiS package for hypergraph partitioning shows effectiveness of our heuristic when compared with straightforward circuit-as- hypergraph partitioning by the same algorithms.
LITERATURE
1. C.J.Alpert and A.B.Kahng, “Recent Directions in Netlist Partitioning: A Survey”, Integration,
the VLSI Journal, 19(1-2):1-81, 1995.
2. G.Karypis and V.Kumar, “Multilevel k-way hypergraph partitioning’, in Proc. IEEE-ACM
Design Automation Conf., 1999, pp.343–348.
3. G.Karypis and V.Kumar, “hMeTiS: A Hypergraph Partitioning Package. Version 1.5.3”, Univ.
of Minnesota, Dept. of Computer Science and Engineering, Minneapolis, MN 55455;
http://www.cs.umn.edu/~karypis.
УДК 681.3
А.С. Плеханов
ВЫБОР СЛОЯ ДЛЯ СЕГМЕНТОВ ПРОВОДНИКОВ ПРИ ОПТИМИЗАЦИИ
ТОПОЛОГИИ БИБЛИОТЕЧНЫХ ЭЛЕМЕНТОВ
В современных технологиях для создания межсоединений в интегральных
схемах используют два и более трассировочных слоя. В процессе создания межсоединений необходимо учитывать различные требования: минимизацию числа переходов, оптимизацию количества проводников в каждом слое, уменьшение задержек распространения сигналов и другие. Поэтому после этапа трассировки схемы проводят оптимизацию топологии с учетом перечисленных требований.
Известен [1] эффективный метод такой оптимизации. Однако, библиотечные
элементы предъявляют дополнительные требования к оптимизации их топологии,
такие, как минимизация критического пути и локальной плотности канала.
Автором разработан метод, который учитывает указанные выше требования
при создании топологии библиотечных элементов. Он заключается в модификации
графа конфликтов-связности следующим образом:
1. Вершинам графа, соответствующим сегментам проводников, добавляется
вес, зависящий от присвоенного слоя сегменту. Вес зависит от минимальной ширины проводника в слое, минимального расстояния между проводниками, задержки распространения сигнала и т.п.
2. В графе дополнительно создаются ребра между двумя вершинами, соответствующими каждой паре соседних сегментов. Если оба сегмента пары лежат в одном слое, то ребру присваивают не нулевой вес.
Процесс оптимизации заключается в выборе слоя для каждого сегмента, при
котором суммарный вес всех вершин и ребер графа минимален.
Предложенный метод позволил сократить площадь топологии библиотечных
элементов.
200
Документ
Категория
Без категории
Просмотров
1
Размер файла
67 Кб
Теги
physical, cmos, design, partitioning, circuits, standart, cells, 10315
1/--страниц
Пожаловаться на содержимое документа