Канальная трассировка соединений в БИС (1006300)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Канальная трассировка соединений в БИС.

Общие сведения

Канальная трассировка — проведение соединений (коммутация выводов каждой целя) в канале БИС.

Канал-это область на кристалле БИС прямоугольной формы, на одной или нескольких сторонах которой расположены контакты (выводы логических элементов БИС, принадлежащие цепям), с системой одинаково направленных магистралей.

Магистраль — отрезок прямой (вдоль канала), по которому может проходить соединение. Сечение — аналогичный отрезок прямой поперек канала. По направлению магистралей различают горизонтальные и вертикальные каналы. По числу сторон, на которых имеются контакты, различают различают одно-, двух-, трех- и четырехсторонние каналы. Для проведения соединений на кристалле чаще используют одно двухсторонние каналы.

Ширина ( пропускная способность) канала — это число его магистралей. Загрузка канала — число занятых магистралей.

Алгоритмы трассировки для вертикальных и горизонтальных каналов идентичны, поэтому рассмотрим горизонтальный двухсторонний канал.

Вывод элемента БИС будем изображать точкой на стороне канала с указанием номера электрической цепи, к которому данный вывод принадлежит. Так как существенно относительное расположение выводов в верхней и нижней сторонах канала, поэтому пары выводов с одинаковой абсциссой (координатой по оси ОХ, идущей вдоль канала, например по верхней его стороне) соединены пунктиром

Решение задачи канальной трассировки БИС будем искать в классе цепей простейших конфигураций: р-выводная цепь содержит один горизонтальный и р вертикальных отрезков. На рис. изображен пример канала с четырьмя цепями, каждая из которых представлена одним горизонтальным и двумя вертикальными отрезками.

Отметим, что обычно горизонтальные отрезки всех цепей располагают в первом коммутационном слое, а вертикальные - во втором, т.е. для проведения всех соединений элементов БИС в соответствии с ее логической схемой используется два коммутационных слоя. В месте пересечения вертикальных и горизонтальных отрезков одной цепи, находящихся в разных слоях, имеется межслойный переход. Поэтому вертикальные отрезки цепей, не пересекающие горизонтальные отрезки других цепей, последовательно переводят в первый коммутационный слой.

Любая цепь полностью определяется:

а) горизонтальным отрезком , абсциссами начала и конца которого являются соответственно минимальная и максимальная среди абсцисс всех выводов i данной цепи ;

б) номером п магистрали, на которую этот отрезок назначен (например, на рис. 2 цепь С₃ полностью определяется горизонтальным отрезком Х₃, назначенным на вторую магистраль).

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

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

Если обозначить через номер магистрали, на которую назначается горизонтальный отрезок , цели , то горизонтальные ограничения будут иметь вид: .

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

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

Для описания таких ограничений служит ориентированный граф вертикальных ограничений с уже рассмотренным множеством V вершин и множеством U₂ дуг. Дуга в том случае, если контакт i на верхней стороне канала имеет одинаковую абсциссу с контактом j на нижней стороне канала. Чтобы не было перекрытия вертикальных отрезков цепей, горизонтальный отрезок цели должен быть расположен на магистрали выше, чем горизонтальный отрезок цели (рис. 3.4).

Если , расположен ниже , то вертикальные отрезки будут перекрываться (рис. 3.5). Отсюда следует, что при возрастающей сверху вниз нумерации магистралей и указанном расположении контактов i и j вертикальные ог­раничения будут иметь следующий вид: n_i < n_j.

Графы вертикальных ограничений при вариантах расположения контактов, заданных на рис 3.1 и 3.7, изображены соответственно на рис. 3.6 и 3.8.

Граф вертикальных ограничений необходимо проверить на нали­чие в нем ориентированных циклов, свидетельствующих о нарушении вертикальных ограничений. Так, среди двух графов на рис З.6 и 3.8 последний граф вертикальных ограничений имеет ориентированный цикл из вершин 4, 3, 2.

Существует два способа устранения ориентированного цикла. Первый из них состоит в решении задачи трассировки в классе расширенных конфигураций, когда цепь представляется двумя горизонтальными отрезками (например, цепь 4 на ряс. 3.9 — отрезками 4' и 4 " ) и по крайней мере, тремя вертикальными. Для устранения цикла берут любую цепь, горизонтальный от­резок которой входит в этот цикл (обычно цепь с горизонтальным отрезком наибольшей длины), и эту цепь представляют двумя гори­зонтальными отрезками, причем конец перво­го из них и начало второго имеют одинаковую абсциссу. Данная абсцисса выбирается (в ме­сте возможного расположения контактов, так как существует минимальное расстояние меж­ду ними) такой, чтобы на одной (или даже двух) стороне канала отсутствовал контакт.

Например, на рис. 3.9 на нижней стороне ка­нала отсутствует контакт между выводами 3 и 2 (на верхней стороне канала ту же абсциссу имеет контакт 1), поэтому именно эту абсциссу имеют конец горизонтального отрезка 4' и начало отрезка 4 " цепи 4.

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

Так, вместо изображенного на рис.3.8 графа вертикальных ограни­чений с ориентированным циклом при расположении контактов, при­веденном на рис.3.7, после устранения цикла получаем граф вертикальных ограничений, представленный на рис.3.10. В этом графе вместо вершины 4 появляются две вершины 4' и 4 " и три новые дуги: от 4' к 4", от 1 к 4' и 4", а также две прежние дуги от 4 к 3 и от 2 к 4 заменяются на дуги от 4' к 3 и от 2 к 4". Заметим, что две дуге от 1 к 4' и 4 " появляются, так как в заданном расположении контактов на рис.3.7 отсутствует контакт на нижней стороне канала между контактами 3 и 2 под контактом 1. Если бы отсутствовал контакты на верхней стороне канала, например, там, где на рисЗ.7 изображен контакт 1, который бы переместился на нижнюю сторону канала между контактами 3 и 2, то граф вертикальных ограничений имел бы вид, приведенный на рисЗ.11, где две дуги в отличие от графа рис.3.10 направлены в другую сторону: от4'к1иот 4"к1.

Второй способ устранения ориентированного цикла в графе вер­тикальных ограничений состоит в том, что меняются местами два контакта (что приводит к переразмещению соответствующих логических элементов), один из которых принадлежит цепи с горизонтальным отрезком из цикла наибольшей длины, а вторым является такой контакт, напротив которого на противоположной стороне канала отсутствует контакт. Например, для заданного на рис.3.7 расположения контактов при втором способе устранения цикла следует поменять местами контакты 4 и 1 на верхней стороне канала, так как горизон­тальный отрезок цепи 4 имеет наибольшую длину, а напротив кон­такта 1 (см. рис.3.7) на нижней стороне канала между 3 и 2 отсутствует контакт. Тогда получим расположение контактов и гори­зонтальных отрезков без привязки их к магистралям, изображенное на рис.3.1, граф горизонтальных ограничений (рис.3.3) и граф верти­кальных ограничений (рис.3.6) без ориентированного цикла.

После устранения ориентированных циклов в графе вертикальных ограничений для осуществления трассировки строится обобщенный граф ограничений Z=(V, U), где V— уже рассмотренное множество вершин, U — множество звеньев (ребер и дуг). Звеньям соответствуют ребра из графа горизонтальных отрез­ков и дуги из графа вертикальных ограничений. Если две вершины соединены одновременно и дугой и ребром, то в графе Z оставляют только дугу. Так, для расположения контактов на рис.3.7 при первом способе устранения цикла по графам горизонтальных ограничений на рис3.12 и вертикальных ограничений на рис3.10 получаем обобщенный граф на pиc3.13, а при втором способе устранения циклов по графам на рис.3.3 я 3.6 получаем обобщенный граф на рис.3.14.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)