РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ СБИС С УЧЕТОМ ВРЕМЕННЫХ ЗАДЕРЖЕК
РАСПРОСТРАНЕНИЯ СИГНАЛОВ
В настоящее время разработаны и реализованы в
различных САПР десятки и более алгоритмов размещения элементов на кристалле и
печатной плате [1,2]. В этих алгоритмах обычно в качестве основного критерия
используют такие показатели, как минимум суммарной длины связей, минимум
количества проводников пересекающих линии раздела и равномерность загруз-ки
трассами каналов, учитывающие «трассируемость». Однако при проектиро-вании
топологии высокоскоростных СБИС минимизация максимальной длины (наидлиннейших
связей) соединений является более важным критерием, чем минимизация суммарной
длины соединений (МСД) [3,4]. При использовании критерий МСД обеспечивается
лишь в среднем относительно малая длина соединений, а минимизация длины
наидлиннейших связей достигается лишь в отдельных случаях косвенным образом.
В работе предлагается способ минимизации наидлиннейших связей, основанный на принципе использования потоков сигналов в комбинационных логических схемах (КЛС) и ранжировании элементов. При этом основное внимание уделяется на необходимость сокращения длины наидлиннейшей линий связи, определяющей задержку распространения сигнала по крити-ческому маршруту. В КЛС обычно имеются несколько маршрутов распростра-нения сигналов от точек генерации сигналов-входов КЛС до точек их приема-выходов КЛС, составленные из разного количества последовательно включенных логических элементов. Маршруты в КЛС рассматриваются по направлению, противоположному распространению сигналов, т. е. начиная от выходов КЛС, присоединенных к соответствующим точкам приема (элементам-приемникам) сигналов, которым присваивается нулевой ранг.
Ниже
предлагается способ ранжирования элементов КЛС. При этом предполагается, что в
КЛС отсутствуют обратные связи, образующие контуры, все логические элементы
имеют равные задержки и задержки в линиях связи равны нулю.
Ранжирование элементов КЛС, которое проводится
независимо от их позиций на коммутационном поле кристалла, предполагает
выполнение следующих действий:
– последовательно выбираются маршруты распространения
сигналов в КЛС, начиная от выходов КЛС к ее входам;
– элементам и цепям каждого маршрута присваиваются
ранги, соответствующие его длине, определяемой количеством элементов,
включен-ных последовательно в данном пути распространения сигналов;
– наибольший ранг присваивается элементам самого
длинного (критического) маршрута с максимальной задержкой сигнала N*tз.р.;
– если один и тот же элемент входит в несколько
маршрутов, то его ранг определяется рангом элементов маршрута с наибольшей
длиной (маршрута, для которого N имеет
наибольшее значение).
После
ранжирования производится последовательный выбор элементов по маршрутам и их
размещение на коммутационном поле кристалла. Позиция для размещения выбранного
элемента выбирается в e -
окрестности элемента (из множества элементов данного маршрута), размещённого на
предыдущем шаге. При этом приоритетной является позиция, которая обеспечивает
минимум гипотетической длины проводников, соединяющих эту позицию с точкой
генерации сигнала и позициями на коммутационном поле кристалла, уже занятым с
наибольшими рангами, связанными с размещаемым элементом. Для оценки
гипотетической длины соединительных проводников, т. е. для определения
расстояния между указанными выше позициями на коммутацион-ном поле может быть
использован способ ортогональной метрики.
Структура алгоритма размещения, как и у любого
последовательного алгоритма, определяется правилами выбора очередного элемента
и позиции для его установки. При этом выбор элемента осуществляется независимо
от его позиции и поэтому, выполняется предварительное упорядочение элементов, а
потом уже и собственно размещение в порядке их получения. Выбор элементов каждого маршрута и их размещение
осуществляется в порядке обратном направлению распространения сигналов. При
этом считается, что позиции элементов-источников и элементов-приемников сигналов
на коммутационном поле кристалла уже известны и фиксированы.
В
заключении приводится алгоритм выбора элементов и их размещение на кристалле,
обеспечивающий минимизацию длины соединений по критичес-кому маршруту
распространения сигнала, который предполагает следующий порядок выполнения
операций.
1. Из совокупности элементов маршрута с наибольшей
длиной выбрать элемент хА, связанный с элементом-приемником,
позиция которого на коммутационном поле кристалла задано.
2. Выбрать позицию на кристалле для размещения хА
в e-окрестности элемента-приемника и линии наикратчайшего распространения
сигнала по данному маршруту.
3. Составить список смежных с хА элементов
ХА = {хi / i = 1,n} и упорядочить их по рангам, где n – число
элементов хi, , смежных с хА.
4. Выбрать во множестве ХА среди не размещенных элементов элемент с наибольшим
рангом. Если наибольший ранг среди не размещенных имеет только один элемент хк,
то перейти к п. 6, иначе – к п. 5.
5. Если среди не размещенных элементов наибольший ранг
имеют два или более элементов, например, элементы хк и хq, то выбрать хк, с которым связаны большее число цепей с
наибольшим рангом. Если элементы хк и хq эквиваленты и по этому показателю, то выбор одного из них осуществить в
произвольном порядке.
6. Выбранный элемент хк разместить на коммутационном поле
кристалла в e - окрестности приоритетной позиции.
7. По отображению элемента хк составить
список (множество) цепей U = {uj / j =1, s}, где s – число цепей, инцидентных с входными выводами хк.
8. Упорядочить цепи в списке в соответствии с рангами
элементов, инцидентных к ним и просматривать их последовательно, в порядке
убывания рангов элементов.
9. Если ранги элементов, инцидентных к двум или более
цепям равны, то выбор цепи осуществить в произвольном порядке.
10. Определить для выбранной цепи up элемент хp, который инцидентен к цепи up своим выходным выводом.
11. Если элемент хp окажется уже размещенным или
элементом-источником сигнала, позиция которого на монтажном поле задано, то
перейти к п. 12, иначе – к п. 6.
12.
Проверить, все ли цепи uj, связанные с входными выводами элемента
хк просмотрены.
Если да, то перейти к п. 13, иначе выбрать следующую по списку цепь uк из множества U, т. е. uк ÎU, k ¹ p, p := k и перейти к п. 10.
13. Определить цепь uк, связанную с выходным выводом элемента хк.
14. Из числа элементов, инцидентных своими входными
выводами цепи uк, выбрать элемент хt , который
уже размещен.
15. Проверить смежность хt с
элементами хi множества ЕА, т. е.
наличие его в списке ХА
(хt Î ХА) Если элемент хt отсутствует в списке ХА,
то перейти к п. 10, если хt
принадлежит к множеству ХА,
то перейти к п. 16.
16. Проверить, все ли элементы хi в списке ХА
просмотрены. Если да, то перейти к п. 17, иначе – выбрать следующий по списку
(среди не размещенных элементов) элемент и перейти к п. 6.
17. Перейти к размещению элементов по маршрутам,
сходящимся к следующему элементу-приемнику.
Данный
алгоритм основан на использовании обобщенной модели описания топологии схемы
СБИС [5,6], в которой отображаются все компоненты схемы: элементы,
электрические цепи и связи, степень связности и выводы (контакты) элементов.
Использование обобщенной модели с блочно-иерархической структурой в виде
списков позволяет значительно уменьшить вычислительные затраты, необходимые при
поиске элементов и цепей в процессе упорядочения элементов по их рангам и
выбора элементов для размещения на кристалле.
Предложенный в работе
алгоритм ранжирования и выбора элементов может найти применение при
автоматизированном проектировании топологии высокоскоростных СБИС для получения
начального размещения элементов с последующей оптимизацией на основе алгоритмов
итерационного улучшения. Следует отметить, что предложенный алгоритм
ранжирования может быть использован также при электрическом анализе БИС на
основе однонаправленных моделей, прогнозируемых реакций и релаксаций формы
сигналов, т. е. с учетом однонаправленности распространения сигналов, когда для
каждого фрагмента БИС на произвольном отрезке времени выполняется раздельное
интегрирование.
Список литературы:
1. Норенков И. П. Основы автоматизированного проектирования – М: МГТУ им. Н. Э. Баумана, 2006. – 384 c.
2. Тархов А. Система проектирования печатных плат. PCAD 2004. // Электроника. – M.: 2005. №2. – C. 70-73.
3. Лежебоков А.А. Решение задачи размещения элементов СБИС с учетом временных задержек // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР". – Таганрог: Изд-во ТРТУ, 2006. №8(63). – С. 146-151.
4. Степаненко С.А., Лебедев Б.К. Учет временных ограничений при размещении элементов СБИС // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS’06) и «Интеллектуальные САПР» (CAD-2006). Научное издание в 3-х томах. – М.: Изд-во Физико-математической литературы, 2006, Т.2. – C. 16-21.
5. Джурунтаев Д.З. Модель описания схемного набора данных и автоматзация процееса его подготовки // Вестник КазНТУ. – Алматы: 2006. – №3. – C. 87–92.
6. Джурунтаев Д.З. Об алгоритме и программе разбиения СБИС // Распределенные вы-числительные и коммуникационные сети: Тез. докл. Международной научной кон-ференции, – Mocква, Институт проблем передачи информации РАН, 2007. – C.83-88.
Рассмотрен вопрос размещения элементов СБИС с
учетом временных задержек
распространения сигналов.
Разработаны алгоритмы ранжирования и выбора
элементов и их
размещение на кристалле, обеспечивающие минимизацию
длины соединений по
критическому маршруту распространения сигнала
In that work the algorithm of choice of elements
is offered which can be used for reception
of initial variant of accommodation at minimization of length of
the communication line on
a critical route of distribution
of signals in the combinational logic circuits. The given algorithm is of
interest for the developers high-speed SBIS.