Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

Алгоритм канальной трассировки БИС на стандартных блоках Т В . Федагина Научный руководитель: В.В. Воронова, к.т.н., доцент Казанский государственный технический университет им. А.Н. Туполева Рассматривается модифицированный алгоритм "левого края" для трассировки БИС. Трассировка определяет возможность создания соеди­ нений по программе трассировки, после того как программа размещения расположила все элементы. Сложности при создании соединений возникают при скоплении про­ водников в областях трассировки. При проектировании БИС количество групп соединительных проводников чрезвычайно велико, и поэтому задачу трассировки делят на две части: операции по определению общей структу­ ры каналов без детализации маршрута каждого проводника и операции по определению детальной структуры межсоединений в соответствии с пра­ вилами проектирования в каждом канале. В БИС на стандартных блоках геометрия каждого канала не задаётся заранее. Области трассировки делят на вытянутые прямоугольники и рас­ сматривают их как каналы. Особенностью канальной трассировки является то, что в пределах каналов отсутствуют мешающие трассировки объекты. Целью трассировки соединительных проводников является распределение их маршрутов по соответствующим каналам таким образом, чтобы наибо­ лее эффективно использовать области, отведённые для межсоединений. При трассировке соединений между несколькими точками произво­ дят некоторые предварительные операции: соответствующие проводники разделяют на участки, соединяющие только две точки. Предполагается, что ширина проводников и расстояние между ними определены, а длина и ширина канала определяется по числу необходимых дорожек для трассировки межсоединений. В алгоритме "левого карая" все связи предварительно упорядочивают по начальным значениям абсцисс. Затем последовательно слева направо заполняется каждая дорожка непере­ секающимися соединениями до тех пор, пока все они не будут поставлены в соответствие дорожкам. Затем начинается заполнение дорожек начиная сверху. Ограничения на трассировку (для предотвращения короткого за­ мыкания) моделируется графом ограничений на соединение. Для разрыва цикла офаничений в граф вводится новая вершина, что позволяет провес­ ти расширение одного соединения на два. Можно канал делить на верти­ кальные зоны, каждой из которых задаются свои ограничения, что позво­ ляет лучше упорядочить соединения. 111