Алгоритм компоновки, учитывающий временные параметры на основе сохранения лучших конусов схемы

Редактирование списка элементов происходит в табличном режиме с трехмерной визуализацией редактируемого элемента в соответствующем окне. Для визуального различения элементов в объеме упаковки им присваивается цветовая последовательность. Полностью реализованы все перечисленные стратегии определения заранее неизвестного объема. Для выбора той или иной стратегии предусмотрены соответствующие пункты системы меню. Сохранять и загружать можно не только наборы элементов, но и готовые решения, что удобно при проведении исследований и сравнительного анализа результатов.

ЛИТЕРАТУРА

1. Бондалетов А.В. Двухмерная упаковка со связями. Части I, II. Известия ТРТУ, №3. Таганрог: изд-во ТРТУ, 1999.

2. Фионова Л.Р. Последовательный алгоритм плотной упаковки элементов. В кн.: Тезисы докл. Респ. науч.-техн. конф. «Автоматизация технического проектирования цифровой аппаратуры». Каунас: КПП, 1981.

3. Тихонов Ю. Программирование трехмерной графики. СПб: БХВ, 1999. 432 с.

УДК 681.3.06

М.В. Рыбальченко, В.М. Глушань АЛГОРИТМ КОМПОНОВКИ, УЧИТЫВАЮЩИЙ ВРЕМЕННЫЕ ПАРАМЕТРЫ НА ОСНОВЕ СОХРАНЕНИЯ ЛУЧШИХ КОНУСОВ СХЕМЫ

Главная особенность рассматриваемого алгоритма, использующего конусные структуры - это возможность помещать критические по времени задержки пути внутрь компонент разбиения с одновременным уменьшением числа компонент. Конусная структура (конус) - множество всех комбинационных элементов схемы, которые могут быть найдены между первичным выходом схемы и ведущими к нему входами [1]. Определим критический путь как наиболее длинный путь между некоторым входом и выходом в конусе исходной неразбитой схемы [2]. Если такой критический путь разрезан в процессе разбиения схемы на компоненты, то возникающие в результате этого паразитные емкости могут привести к чрезмерно большим временным задержкам и, как следствие, низкому быстродействию или неработоспособности спроектированной микросхемы.

Наиболее часто данная проблема возникает при проектировании вентильных матриц, имеющих высокую насыщенность связями, поскольку большое число входов/выходов обуславливает необходимость учёта при компоновке помимо ограничений на размер компонент, также и ограничений на количество их выводов (фак-

). -, , среди которых имеются и критические пути.

Поставим задачу таким образом. Сформировать компоненты разбиения, чтобы для каждой компоненты:

tMAX _____ tMAX

’'РАЗИ _ 0 ,

Size p

Cost p =------ _ max ,

- IO- ’

Известия ТРТУ

Тематический выпуск

Size P < MaxSize , IOP < Max IO ,

MAX t0 -

MAX

схеме; tpA,jK - временная задержка этого пути после разбиения схемы; Costp -

конструктивный критерий разбиения, соответствующий удельному числу внешних связей компоненты; Sizep - размер (число элементов) компоненты разбиения; MaxSize - максимально допустимый размер компоненты разбиения; IOp - число внешних связей компоненты разбиения; Max IO - максимально допустимое число внешних связей компоненты разбиения.

Непосредственный учет критических по времени задержки путей может быть выполнен при использовании ориентированного графа в качестве модели комму.

:

1. .

2. .

3. .

4. Определение стоимости кластеров.

5. Объединение кластеров в компоненты разбиения по наибольшей суммарной стоимости с учетом ограничений.

1

с вершинами на выходах схемы. Тело конуса составляют элементы, имеющие прямую или опосредованную связь с данным выходом, включая соответствующие входы схемы, т.е. учитываются все цепи, сигналы которых влияют на состояние .

Процедуры 2 и 3 предотвращают разрезание критических путей и «сильно» связанных блоков схемы. С учетом количества выходящих из конуса цепей и задержки критического пути, определяется приоритет разреза.

4 ,

объединения полученных блоков в компоненты разбиения, оптимизирующий разбиение с учётом ограничений.

5 , -

рой 4, учитывая явно ограничение на количество элементов в компоненте разбие-

, ( ), задержки в компонентах разбиениях.

Рассмотрим алгоритм разбиения на основе подхода "по лучшему конусу", который максимально сохраняет при разбиении целостность самых лучших по стоимости конусов (эти целые конусы могут не удовлетворять ограничениям на размер , , , -

):

1. .

2. : « » -ем вокруг него всех остальных (при разрезании кластеры формируются из областей конусов, непересекающихся с самым "дорогим").

3. : -

нение кластеров i и j, начиная с кластера, имеющего наибольшую стоимость, с максимизацией стоимости объединённого кластера:

CostM =

1Ou = 1O, +10, +

где Sizei , Sizej - размер i-го и j-го кластеров соответственно, i = 1, к, j = 1, к ; SizeM - размер объединённого кластера;

10 {, 10 j - количество внешних связей i-ro и j^o кластеров соответственно; lOcommon - число общих связей между кластерами i и j;

IOm - ;

при ограничениях: Size M < MaxSize , 1OM < Max 1O .

Объединение кластеров с CostM = 1 производит кластеры CostM>=1, так как размер растет быстрее, чем число входов/выходов.

4. При условии, что никакие больше кластеры не могут быть объединены в компоненту разбиения без нарушения установленных ограничений, осуществляется переход к формированию следующей компоненты в соответствии с п. 3. Если никакие кластеры не могут быть объединены, алгоритм заканчивает ра, . Применимость данного алгоритма обусловлена величиной разветвления на выходах элементов схемы. При малых значениях разветвления, ограничение на число внешних выводов компонент не нарушается при помещении в них целых , . указанные ограничения сразу же могут быть нарушены, что требует другого подхода к разрезанию конусов.

, -

,

,

. -

слеживания образования вторичных критических путей и их минимизации, а также для его применимости к схемам, имеющим большие значения разветвления на вы.

ЛИТЕРАТУРА

1. G. Saucier, D. Brasen, J.P. Hiol. Partitioning with cone structures // Proc. design automation conf., 1993.

2. K.J. Singh, Sangiovanni-Vincentelli. A heuristic algorithm for the fanout problem // Proc. design automation conf., 1990.

УДК 001.8

А.В. Маргелов, А.А. Маргелов ВЫБОР ОСНОВНЫХ ХАРАКТЕРИСТИК ЦЕЛИ МЕТОДОМ АПРИОРНОГО РАНЖИРОВАНИЯ

Одним из методов выбора показателей является метод априорного ранжирования (психологического эксперимента по аналогии с методом априорного ранжирования эксперимента). Метод позволяет произвести математическую обработ-