1. Структура ТМ.
В лэйауте (англ. layout - детальное геометрическое описание всех слоев кристалла) транзисторных матриц все p-транзисторы располагаются в верхней половине матрицы, а все n-транзисторы - в нижней. Транзисторные матрицы имеют регулярную структуру, которую составляют взаимопересекающиеся столбцы и строки. В столбцах матрицы равномерно расположены полосы поликремния, образующие взаимосвязанные затворы транзисторов. По другим полюсам транзисторы соединяются друг с другом сегментами металлических линий, которые размещаются в строках матрицы. Иногда, для того чтобы соединить сток и исток транзисторов, находящихся в различных строках, вводят короткие вертикальные диффузионные связи. В дальнейшем ТМ будет представляться абстрактным лэйаутом.
Абстрактный лэйаут - схематический рисунок будущего кристалла, где прямоугольники обозначают транзисторы, вертикальные линии - поликремниевые столбцы, горизонтальные - линии металла, штриховые - диффузионные связи, точки - места контактов, стрелки - места подключения транзисторов к линиям Gnd и Vdd. При переходе к послойной топологии стрелки должны быть заменены полосками в диффузионном слое, по которому осуществляются соединения между строками ТМ. Очевидно, что подведению вертикальных связей к линиям Gnd, Vdd могут препятствоватьтранзисторы, расположенные в других строках транзисторной матрицы, либо расположенные в тех же столбцах диффузионные связи между строками (горизонтальные линии металла не являются препятствием). В следствие этого приходится размещать несколько линий Gnd в n-части ТМ и несколько линий Vdd в p-части ТМ. Возникает задача минимизации числа этих линий. Будем рассматривать ее только для n-части ТМ, задача минимизации числа линий Vdd для p-части ТМ решается аналогичным образом.
Пример абстрактного лэйаута для КМОП-схемы (рис. 1.а.) показан на рис. 1.б.
2. Формализация задачи.
Пусть транзисторная матрица размером n на m задана абстрактным лэйаутом. Представим последний троичной матрицей S размером n на 2m, поставим ее строки в соответствие строкам ТМ, а пары соседних столбцов - столбцам ТМ. Таким образом, каждый элемент матрицы S представляет некоторую позицию лэйаута и получает значение 1, если там стоит стрелка, значение 0 - если там не показан ни транзистор, ни диффузионная связь, и значение * - в остальных случаях. Легко видеть, что значение * свидетельствует о невозможности проведения через данную точку диффузионной связи от стока некоторого транзистора к линии Gnd.
Например, для абстрактного лэйаута ТМ (рис. 1.б.) матрица S имеет вид:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
S1 * 1 0 0 * * * * 0 0 0 0 * *
S2 1 * 1 * * * 0 0 1 * 0 0 0 *
S = S3 1 * * 1 0 0 0 0 0 0 0 0 * 1
S4 0 0 0 0 1 * 0 0 0 0 0 0 * *
S5 1 * * * 0 0 * 1 0 0 0 0 0 *