Полупроводниковые микросхемы. Многокристальная и однокристальная микросхема. Гибридно-плёночные микросхемы, страница 13

Размещение разногабаритных элементов.

Различают размещение элементов кратных размеров и некратных (разногабаритных). В первом случае может находиться несколько элементов или наборов – один элемент занимает несколько позиций. Во втором случае: - гораздо сложнее - сходна с задачей раскройки материала на максимальное количество изделий, только необходимо разместить все элементы. Сложение с существенно разными размерами – задача разрезания. Дихотомия (разрезание пополам) Затем, множество элементов делим на два подмножества элементов. Например, с помощью алгоритма компоновки. S(E₁), S(E₂) – площади, занимаемые элементами двух множеств на подложке. S(E₁) + S(E₂) =S = L_xL_y/ | S(E₁) - S(E₂) | ≤ E (заданный параметр)

Далее берем Е₁ и делим его и так далее до тех пор, пока каждая площадь, то есть группа не будет не будет состоять из одного элемента.

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

- разрешено Х проводников или нет

- возможен переход со слоя на слой или нет

- количество слоев для трассировки

- под каким углом можно проводить соединение

- допустимая ширина проводок и расстояние между ними

- максимальная длина проводников, идущих параллельно в соседних позициях и так далее…

алгоритмы трассировки зависят от  конструктивно-технологической базы и от технологии изготовления.

 Задача трассировки обычно делится на подзадачи:

Построение списка соединений. Сводится к построению минимального связывающего дерева. Эта задача имеет полиномиальный алгоритм (а. Грима, а. Краскала ). Алгоритм – точный результат за полиномиальное время.

Алгоритм Прима: Для произвольной вершины xi – ищется ближайшая xj и они соединяются. Из всех неподсоединенных вершин выбирается ближайшая к паре и подсоединяется .

Алгоритм Краскала: Все пары элементов упорядочиваются по неубыванию. Просмотр слева направо. В дерево включается каждое ребро, не образующее цикл с уже вошедшими ребрами. 2) ГДЕ? Цель: выявление конфликтов между проводниками и их расслоение . Расслоение можно производить до, во время и после трассировки. Вершины – это проводники, а ребра – если есть пересечения, далее раскрашивается. Сколько красок, - столько слоев. 3) КОГДА? Определение порядка проведения соединений (определение порядка трассировки). Порядок проведения влияет на качество. Метод прямоугольников: для каждой цепи строится минимальный охватывающий прямоугольник. Подсчитывается количество контактов чужих цепей, попавших в прямоугольник данной цепи. Цепи упорядочиваются в порядке неубывания. Полученный порядок и есть порядок соединений.

4) КАК? Алгоритм трассировки (алгоритм организации проводников). Является основным и трудоемким этапом, обеспечивающим эффективность и качество в целом. Делится на: волновой, лучевой, канальный.

16. Этапы компоновки, размещения элементов и трассировки межсоединений (продолжение)

Волновой алгоритм трассировки и его модификации. Входит во все САПР. Коммутационное поле делится на дискреты. Величина дискрета определяется минимальной шириной проводника и минимальной длиной между ними. В одном дискрете может проходить только один проводник – дискретное рабочее поле (ДРП) 2 этапа: а) распространение волны. Моделировать распространение волны по свободным дискретам ДРП. Ф – фронт – множество дискрет, которые входят в окрестность источника.  Распределение волны до тех пор, пока очередной фронт не достигнет приемника или в очередной фронт не удается включить ни одной новой ячейки. По мере распределения волны ячейки i-го фронта засекаются. Если соединение существует, то: б) проведение трассы. Пройденные ячейки составляют исходный путь. Пусть критерий СДС (суммарная длина соединений). Пример: