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

Алгоритм канальной трассировки БИС типа вентильных матриц О.А. Шутова Научный руководитель: В.В. Воронова, к.т.н., доиент Казанский государственный технический университет им. А.Н. Туполева Задача трассировки межсоединений БИС типа вентильных матриц включает в себя задачу канальной трассировки, то есть построение соеди­ нений между выводами двух противолежащих рядов блоков. В работе рассматривается реализация метода "стволов и ветвей" для канальной трассировки. Метод вентильных матриц предполагает изготов­ ление подложки, на которой в заранее предусмотренном порядке размеше­ ны базовые ЛС или базовые ячейки. Выполнив межсоединение между ба­ зовыми ячейками, можно получить простые логические вентили. Следова­ тельно. объектом автоматического проектирования топологии блоков и трассировки межсоединений является привязка в каждом изделии логиче­ ских блоков к базовым ячейкам или макроячейкам и определение рисунка между ними. Ограничением этого метода является то, что каждой группе провод­ ников отводится горизонтальная трасса - ствол, поэтому, определив, ка­ кую горизонтальную дорожку следует использовать, задачу трассировки вертикальных проводников - ветвей, можно решить автоматически. Ограничение, не допускающее наложения соседних стволов друг на друга, представлено графом трасс, вершины которого соответствуют груп­ пам соединительных проводников. Ребра графа, инцидентные двум его вершинам, существуют тогда, когда соответствующие стволы не наклады­ ваются, будучи направлены по одной и той же дорожке. Если пренебречь возможностью наложения ветвей, оптимальное распределение можно по­ лучить путем решения задачи раскраски графа. Это задача о минимизации количества цветов, в которые можно окрасить все вершины графа, при на­ личии ограничения, согласно которому две соседние вершины должны иметь различные цвета (горизонтальные дорожки). Ограничение, по которому соединительные проводники не должны накладываться друг на друга, реализуется ориентацией части ветвей графа. Следовательно, в графе с ориентированными ребрами задача распределе­ ния дорожек с учетом ограничений на топологию стволов и ветвей сводит­ ся к задаче нумерации вершин наименьшими целыми числами при услови­ ях; 1. Вершины каждого ребра должны иметь различные номера 2. Начальная точка (вершина) каждого ребра должна иметь больший номер, чем конечная. 113