РАЗМЕЩЕНИЕ ЭЛЕМЕНТОВ СБИС С УЧЕТОМ ВРЕМЕННЫХ ЗАДЕРЖЕК
РАСПРОСТРАНЕНИЯ СИГНАЛОВ
В настоящее время разработаны и реализованы в
различных САПР десятки и более алгоритмов размещения элементов на кристалле и
печатной плате [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.