СОВМЕЩЕННАЯ МОДЕЛЬ ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ И БОЛЬШИХ ИНТЕГРАЛЬНЫХ СХЕМ С ДВУСЛОЙНОЙ КОММУТАЦИЕЙ

Аннотация

The combined model of synthesis of routes in which crossing of the conductors belonging to different chains is allowed is offered. For unambiguous stratification of resultant topology in work the unblocking mechanism which allows to increase sharply efficiency of distributing in comparison with classical wave algorithm is realized.

Полный текст

ВведениеРешающим средством при разработке новой электронной аппаратуры (ЭА) является применение методов машинного проектирования, позволяющих в ко- роткие сроки создавать высоконадежную аппаратуру при сравнительно низких затратах. В качестве перспективной элементной базы современной ЭА исполь- зуются БИС, а в качестве несущих оснований функциональных ячеек в подавля- ющем большинстве случаев применяются двусторонние печатные платы.В последние годы проводятся интенсивные исследования возможности при- менения БИС в аппаратуре двойного назначения для построения различных си- стем управления и контроля космических объектов, атомных энергосистем, ис- следовательских ядерных центров и т.п. Это обусловлено тем, что определенный класс БИС, например комплементарных [1], наиболее выгоден с точки зрения обеспечения минимальной потребляемой мощности, невысокой стоимости, га- баритов и веса, БИС этого класса являются работоспособными в жестких усло- виях воздействия температур, механических нагрузок и различных видов радиа- ционных воздействий.Проведение исследований, проектирование, производство и испытания КМОП БИС двойного назначения невозможно обеспечить без развития средств автома- тизации проектирования. Однако известные отечественные САПР не имеют до- статочно развитых средств для решения данной задачи. Зарубежные программные комплексы, обладающие данными средствами, имеют очень высокую стоимость, а продажа наиболее современных средств не производится, поэтому развитие отечественных средств автоматизации проектирования конструкторско-техно- логического базиса КМОП БИС является актуальной задачей.В перспективе применение плат с двухслойной коммутацией по многим па- раметрам (стоимость, вес, простота изготовления, надежность) в аппаратуре яв-41Вестник РУДН, серия Инженерные исследования, 2016, № 4ляется более предпочтительным [2]. Например, металлизированные переходы в рельефных печатных платах повышают их надежность, причем «эффективный» ресурс магистралей таких плат оказывается на 30…40% выше, чем у плат, выпол- ненных по субтрактивной технологии. Причина заключается в том, что диаметр переходных отверстий в рельефных печатных платах, так же как и диаметр кон- тактных окон КМОП БИС меньше ширины проводника для соответствующей конструкции, что позволяет располагать их в соседних ячейках дискретного ра- бочего поля (ДРП).Наиболее «узким местом» при проектировании печатных плат является имен- но этап трассировки, поскольку при высокой плотности монтажа соединительные проводники должны занимать около 80% от общей площади платы. Таким об- разом, жесткие требования к реализации проводников на КП также как и в слу- чае БИС с двухслойной коммутацией ведут к необходимости разработки новых методов и алгоритмов трассировки.Предлагаемый методАлгоритм трассировки на однослойной модели [3; 4] не нашел широкого рас- пространения в практике автоматизированного конструирования БИС. Это объ- ясняется тем, что даже при наличии достаточного ресурса свободных магистралей этот алгоритм в состоянии полностью развести лишь планарную схему. Подавля- ющее большинство цифровых схем не являются планарными, поэтому для устра- нения конфликтных ситуаций при их разводке прибегают к двухслойному ком- мутационному пространству, причем в качестве второго уровня разводки исполь- зуют либо поликремниевые перемычки [1], либо второй слой металлизации БИС. В данной работе предлагается оригинальная модель ДРП и алгоритм трассиров- ки на ней печатных плат и БИС с двухслойной коммутацией.Предлагаемая совмещенная модель коммутационного пространства представ- ляет собой дискретное рабочее поле (ДРП), которое в ЭВМ представляется дву- мерной таблицей (массивом М) размерностью m × n. Числа m и n определяют ресурс магистралей вдоль координатных осей, разрешенных для проведения про- водников. В таблице ДРП каждая ячейка Sij, расположенная на пересечении ее i-й строки и j-го столбца, содержит восемь поименованных бит (с aij по hij), пред- ставляющих следующую информацию:биты aij и bij представляют сведения об ориентации проводника: aij = 1, если проводник идет по ячейке Sij горизонтально, и bij = 1, если - вертикально;биты cij и dij представляют волновые числа в кодировке Акерса [2];бит eij отмечает ячейки со статусом «приемник цифровой волны»;бит fij программно устанавливается в состояние «1», если в ячейке Sij про-водник меняет направление - фактически этот бит фиксирует наличие контак-та между вертикальным и горизонтальным отрезком;биты gij и hij позволяют ликвидировать неоднозначность при расслоении совмещенной модели, в процессе которого пересекающиеся без контакта прово- дники помещаются в разные слои.Для иллюстрации принципа действия предлагаемого алгоритма отметим ос- новной недостаток классического однослойного волнового алгоритма [3; 4]: в каждый момент он просматривает состояние только одного проводника. По этой42Назаров А.В. Совмещенная модель трассировки печатных плат и больших интегральных схем...причине неизбежно возникает блокирование многих еще не построенных трасс. Для ликвидации взаимного блокирования проводников разрешим их пересечение в модели ДРП в расчете на последующее расслоение.Именно для формализации такого подхода необходимо в каждой ячейке ДРП иметь информацию о направлении проходящих по ней отрезков (биты aij и bij модели каждой ячейки) и о наличии контакта между ними (бит fij).Основная проблема, которую требуется решить при проектировании алгорит- ма трассировки на совмещенной модели (назовем его деблокирующим), - обе- спечение исключительно взаимно ортогонального пересечения отрезков при их построении. Другими словами, необходимо запретить проведение последующе- го отрезка вдоль ранее построенного, поскольку в двухслойном ДРП такое их«слипание» и будет эквивалентом взаимному блокированию трасс, имевшему место в однослойной модели коммутационного пространства. Устранить слипа- ние отрезков проводников можно, если запретить проведение двух отрезков по одним и тем же ячейкам.Принцип, с помощью которого деблокирующая цель будет достигнута, может быть с успехом распространен и на другие версии волновых алгоритмов, поэтому остановимся на нем более подробно.Анализ процедуры построения трасс по классическому волновому алгоритму показывает, что внесение нового маршрута в модель ДРП осуществляется при обратном движении волны (обратная трассировка), однако конфигурация марш- рута полностью определяется состоянием волновых чисел в ячейках ДРП, сфор- мированных на этапе распространения прямой волны. Поэтому если запретить движение прямой волны вдоль ранее построенного отрезка, то «слипания» про- водников на этапе обратной трассировки не возникнет.Чтобы решить поставленную задачу, рассмотрим два возможных варианта до- стижения волной отрезка: волна достигает отрезок в ортогональном к нему на- правлении (рис. 1, а); отрезок достигается волной в коллинеарном к нему на- правлении (рис. 1, б), чтобы исключить из рассмотрения второй вариант, введем в рассмотрение понятие «статус запрета». Будем говорить, что если ячейка ДРП имеет статус запрета, то она считается недоступной для внесения в нее волново- го числа. Ясно, что такая ячейка будет игнорироваться как на этапе при движениипрямой волны, так и на этапе обратной трассировки.а б вРис. 1. Ортогональное (а, в) и коллинеарное (б) касание волной проводника [The orthogonal (а, в) and collinear (б) touch digital wave conductor]43Вестник РУДН, серия Инженерные исследования, 2016, № 4Организовать статус запрета можно, если использовать для его кодирования в ячейке одно «свободное» пока значение волнового числа, равное 3. Действи- тельно, последовательность волновых чисел Акерса (1 - 1 - 2 - 2 - 1 - 1 - и т.д.) требует 2 бита для своей реализации - в нашем случае для их размещения используются биты cij и dij каждой ячейки. При нулевом их состоянии ячейка свободна для внесения волнового числа r. Если cij = 0, а dij = 1, то ρ = 1, наконец, если cij = 1, а dij = 0, то ρ = 2. Ясно, что незадействованным пока состоянием этих бит является: cij = dij =1, при котором ρ = 3, но такого числа в последовательности Акерса нет, поэтому будем его использовать в качестве статуса запрета. К ячейкам, запрещенным для внесения ρ, отнесем также контакты, подлежащие соединению, и ячейки - концы директивных отрезков.Чтобы алгоритмически исключить коллинеарное движение волны по прово- днику, как это показано пунктирной стрелкой на рис. 1, а, построим деблокиру- ющий алгоритм таким образом, чтобы при достижении волной ячейки, занятой проводником, в двух соседних с ней ячейках этого же проводника автоматически формировался «статус запрет» (ρ = 3). Геометрическая интерпретация сказанно- го приведена на рис. 1, б.а б вРис. 2. Пример блокирования цепей цепью B (а) и этапы ее построения (б, в) [Example of blocking chains by chain B (a) and the stages of its creating (б, в)]Продемонстрируем работу деблокирующего алгоритма на примере. Пусть в исходном ДРП, показанном на рис. 2, а, присутствует заранее разведенный про- водник, соединяющий контакты цепи А, и требуется построить проводники, со- единяющие три другие пары контактов цепей В, С и D. Если не применять дебло- кирующий алгоритм, то трасса В вполне может пройти по маршруту, отмеченно- му пунктиром на рис. 2, а. В этом случае контакты остальных цепей будут заблокированы. На рисунке 2, б показано состояние ячеек после построения всех фронтов по деблокирующему алгоритму, а на рис. 2, в - состояние тех же ячеек после выполнения обратной трассировки. Источник волны здесь и далее отмечен черным фоном.На рисунках 3 и 4 показаны аналогичные этапы построения цепей С и D.По окончании синтеза всех трасс совмещенная модель ДРП (рис. 4, б) содер- жит горизонтальные и вертикальные отрезки проводников (биты aij и bij), а также сведения об их контактировании между собой (биты fij). Следующей задачей син- теза трасс является проведение оптимального расслоения совмещенной модели по критерию минимума контактных переходов (окон) между слоями.44Назаров А.В. Совмещенная модель трассировки печатных плат и больших интегральных схем...а бРис. 3. Волновая функция (а) и результат построения цепи С (б) [The wave function (a) and the result of the construction of the chain C (б)]а бРис. 4. Волновая функция (а) и результат построения цепи D (б) [The wave function (a) and the result of the construction of the chain D (б)]а бРис. 5. Базовое (а) и свободное (б) множества отрезков [Basic (a) and free (б) a plurality of segments]ij ijС этой целью все отрезки проводников в ДРП представим двумя множествами. К первому (базовому) отнесем те отрезки, которые пересекаются в ДРП без элек- трического контакта, а ко второму (свободному) - все остальные отрезки. Для текущего примера все базовые отрезки изображены на рис. 5, а, причем ячейки, в которых они пересекаются, выделены темно серым цветом. Формально эти ячейки определяются формулой пересечений вида: a~  b~ , где верхняя тильда означает, что биты aij и bij принадлежат ячейкам, по которым проходят базовые отрезки проводников. Множество отрезков, определенное как свободное, для текущего примера изображено на рис. 5, б.45Вестник РУДН, серия Инженерные исследования, 2016, № 4Собственно расслоение модели проводится в два этапа: на первом отрезки распределяются по слоям, а на втором определяется местоположение контактных переходов (окон).На первом этапе расслоения во избежание короткого замыкания вертикальных и горизонтальных отрезков базового множества часть его, образованная горизон- тальными отрезками помещается в первый слой топологии. Все вертикальные отрезки базового множества переносятся во второй слой. Результат этой операции показан на рис. 6, а. Далее, в первый слой дополнительно переносятся все те от-БАЗрезки свободного множества, которые на множестве MГ MСВобразуют дере-во ортогонального графа, причем оставшиеся отрезки свободного множествапринудительно помещаются во второй слой. Результат этой операции показан на рис. 6, б.а бРис. 6. Предварительное (а) и окончательное (б) расслоение топологии [Preliminary (a) and final (б) bundle topology]ij ij ijЯчейки, в которых необходимо организовать контактные переходы (окна) определяются формулой пересечений вида: a~  b~  f , которая имеет простой физический смысл: переходы (окна) необходимо организовать в местах пересе- чения вертикального и горизонтального отрезков базового множества, если эти отрезки имеют электрический контакт. Геометрически приведенная формула пересечений реализуется наложением рис. 4, б на рис. 6, б, при котором через второе пересечение пройдут лишь две ячейки, отмеченные на рис. 6, б черными квадратиками.