При проектировании БИС проводится предварительная трассировка, s результате которой определяются области, по которым пройдет трасса. Такими областями обычно служат каналы, не занятые элементами, либо отдельные свободные участки. Главная цель предварительной трассировки — равномерное распределение цепей без превышения пропускной способности каналов.
Основным алгоритмом, нашедшим широкое применение для окончательной трассировки соединений, является волновой алгоритм и его модификации.
Известны алгоритмы совместного решения задач .размещения элементов и трассировки монтажных соединений. Метод сечений предназначен для решения этих задач при проектировании регулярных БИС, в которых на коммутационном поле (КП) образуются каналы. Все КП разбивается на горизонтальных и вертикальных сечений, которые делят КП и множество элементов на подмножества. Минимизируется загруженность сечений, под которой подразумевается число цепей, пересекающих линии сечений, путем перестановки элементов из разных сторон сечения. Можно минимизировать загруженность наиболее загруженных сечений; можно установить определенный порядок проведения сечений; можно последовательно делить КП половинными сечениями, каждый раз минимизируя загруженность сечений внутри областей уже меньшего размера; можно провести сначала минимизацию только в вертикальных сечениях, затем только в горизонтальных; можно проводить сечения только в областях, наиболее загруженных соединениями. Для определения наиболее загруженных областей применяется метод минимальных охватывающих прямоугольников (в областях, покрытых наибольшим числом прямоугольников, большая загруженность).
Известен метод трассировки на основе волнового алгоритма по макродискретам масштабной сетки, называемый гибкой трассировкой, в котором положение трассы в макродискрете не фиксируется жестко до прокладки всех трасс, что дает свободу выбора при окончательной трассировке.
Для конструкций с регулярным размещением элементов более эффективна канальная трассировка, так как конструкция уже образует вертикальные и горизонтальные магистрали. Канальная трассировка обычно состоит из двух этапов: предварительной трассировки распределения соединений по каналам с целью равномерной загрузки всех каналов и последующей трассировки внутри каналов.
Широкое применение канальных алгоритмов при проектировании транзисторных и вентильных матричных БИС объясняется не только их .регулярной структурой и наличием горизонтальных и. вертикальных каналов в каждом топологическом слое (транзисторы, логические ячейки с элементарными логическими функциями или макроячейки со сложными логическими функциям» размещаются на базовом матричном кристалле в виде матрицы запрещенных для трассировки областей, каналов межблочной трассировки и поперечных областей максимальных цепей). Важную роль играет то обстоятельство, что при большом числе элементов в конструктивном модуле и .большом числе сигнальных связей между ними канальные алгоритмы оказываются эффективнее .волновых и лучевых алгоритмов.
Ни один из перечисленных алгоритмов трассировки при большой удельной плотности компонентов на кристалле не позволяет получить 100% -ную трассировку межсоединений. Для обеспечения 100%-ной реализации всех соединений в заданном объеме БИС применяется компрессия .
Компрессия топологии (сжатие топологии) БИС — это деформация топологического рисунка спроектированной схемы с целью изменения конфигурации трасс, перемещения основных элементов для достижения 100%-ной реализации всех соединений в заданном объеме БИС. Для этого производится предварительная эскизная трассировка на укрупненном дискретном рабочем поле (ДРП) в предположении, что один дискрет имеет размеры максимального межслойного перехода или размер трассы максимальной ширины. Поэтому при эскизной трассировке принимается, что все трассы имеют одинаковую ширину, все размеры межслойных переходов совпадают с шириной трасс и могут устанавливаться в любом месте изгибов трасс. Эскизный рисунок подвергается компрессии (сжатию) со всех сторон (последовательно вниз, вверх, влево, вправо) к геометрическому центру топологического .рисунка. При каждом направлении делают два шага: сжатие элементов соединений и сокращение длины соединений. Одним из способов проектирования эскиза топологического рисунка БИС является метод стандартных модулей, т. е. использование набора стандартных функциональных ячеек, которые распределяются по линейкам. При этом последовательность решения задач при проектировании следующая:
Процесс построения эскиза итерационный, поэтому применяются быстродействующие алгоритмы компоновки, размещения и трассировки. Обычно заданы размеры кристалла х и следующие ограничения:
; +
где — число линеек; —число ячеек в -й линейке; — высота -го канала; —длина -й линейки; — высота -й ячейки в -й линейке.
Далее результаты эскизной трассировки, выполненной на укрупненном ДРП, переводят на реальное ДРП, которому соответствует реальная мелкая координатная сетка, в которой ширина дискрета равна минимальной ширине трассы либо минимальному допустимому расстоянию между элементами и компонентами. При этом оперируют не ячейками, а элементами и компонентами, так как одновременно производится перетрассировка с щелью минимизации числа межслойных переходов с учетом инвариантности и эквивалентности контактов компонентов м возможности прокладки трасс под компонентами.
В зависимости от имеющегося объема оперативной памяти при компрессии рисунка топологии БИС либо рассматривают все ДРП, либо выделяют окна деформации (ОД), производя последовательную сегментацию ДРП, перемещая ОД с перекрытием через все ДРП. (наиболее удачное перекрытие — на половину ОД).
Все ДРП состоит из дискретов, каждый из которых может быть занят компонентом, трассой, межслойным переходом, запретом, контактом, .границей компонента. Сжатие проводится последовательно просмотром ДРП (вверх, вниз, влево, вправо). Во время сдвига компонента деформируются все подсоединенные к нему и транзитные (проходящие под ним) трассы. Просмотр ОД при деформации начинают с центра ДРП по закону развертываемой спирали. Один проход по всему ДРП составляет одну итерацию. Возможно несколько итераций. Процесс сжатия заканчивается, если при очередной итерации не происходит уменьшения площади рисунка топологии БИС.