В настоящее время одним из самых динамичных направлений в микроэлектронике является проектирование интегральных схем. Этому вопросу уделяется большое внимание, поскольку новые разработки в указанной области открывают широкие возможности для создания устройств с принципиально новыми функциональными возможностями при минимальных затратах труда и материалов. Эти обстоятельства обусловили переход от ручного проектирования к машинному с применением сначала отдельных программ, а затем и крупных САПР, разработка и совершенствование которых продолжается и по сей день.
Несмотря на значительный прогресс в области проектирования ИС, некоторые из направлений требующих развития остаются пока не исследованными, а некоторые – проработанными условно и открытыми для обсуждения по сей день [1]. Среди всех этих вопросов особое место занимают проблемы в проектировании топологии ИС.
Формально, задача разработки топологии ИС сводится к оптимальному, с точки зрения нескольких критериев, размещению на подложке с уже определёнными размерами принудительно связанных между собой элементов микросхемы и может быть отнесена к классу задач выбора из ограниченного, хотя и достаточно широкого, множества вариантов одного, но оптимального по многим критериям. Поскольку многокритериальные задачи не имеют детерминированных решений, на практике выбрана последовательная процедура решения, которая включает в себя ряд этапов. К ним относятся: декомпозиция, т.е. разбиение исходной схемы на блоки, которые называют макроструктурами, или модулями, в соответствии с выбранным критерием (например, по функциональному назначению), планирование кристалла (размещение макроструктур в виде совокупности элементов на подложке), размещение элементов в пределах макроструктур. Далее разработка топологии включает локальную и глобальную трассировку. Локальная трассировка представляет собой прокладку трасс внутри макроструктур, а глобальная — между ними. Процесс проектирования топологии заканчивается процедурой оптимизации/минимизации. На основании созданной топологии разрабатываются шаблоны для последующего производства ИС. Однако, несмотря на глубокую проработку каждой из указанных стадий проектирования, процесс создания топологии не является совершенным.
Рассмотрим некоторые алгоритмы, которые сейчас широко применяются [2] для размещения макроструктур и планирования кристалла. В работе [3] Ша и Даттон ввели представление плоских прямоугольных макроструктур в виде совокупности отрезков линий, ограничивающих некоторую площадь на подложке. Это позволило приближённо отразить геометрию макроструктур. В качестве критерия оптимизации размещения они ввели целевую функцию, представляющую собой сумму квадратов длин проводников, соединяющих макроструктуры, и выполнили оптимизацию, введя условие отсутствия перекрытия макроструктур. Это можно сделать путём введения прямоугольной системы координат и проверки областей, занимаемых макроструктурами, на пересечение. Достоинством этого метода является возможность учёта вращения и зеркального отображения макроструктуры, что заметно облегчает глобальную трассировку. Однако предложенный метод не гарантирует не только получения глобального минимума целевой функции, но даже непересечения макроструктур, поскольку условия неперекрытия основаны на приближённом представлении макроструктур. Помимо этого отсутствует оценка площади, занимаемой соединениями.
Размещение, основанное на декомпозиции с минимальными сечениями, было впервые предложены в работе [4]. Под минимальным сечением понимается такое разбиение площади подложки, при котором достигается наиболее компактное размещение макроструктур. Это оказалось применимыми при проектировании топологии со стандартными ячейками и матрицами. В работе Лаутера [5] была впервые показана эффективность декомпозиции с минимальными сечениями при размещении макроячеек. Основная идея этого метода заключается в группировке тех из макроструктур, которые наиболее тесно связаны, и разделении тех, для которых связи минимальны. Это может быть реализовано на основе разделения с минимальными сечениями, если его применять то в горизонтальном, то в вертикальном направлении. Наиболее существенным в методе является вычисление суммы площадей макроэлементов из двух групп для проверки того, что разность между ними не превысила заданной пороговой величины. Там же Лаутер показал наличие тесной связи между задачей размещения и планирования кристалла при определении структуры его сечения.
Метод Лаутера был применён в несколько обобщённом виде в системе разработки топологии BEAR [2]. Обобщённый метод направлен на максимальное сохранение исходного расположения макроструктур, причём для окончания размещения основным критерием является наилучшее согласование форм ячеек и макроструктур.
Применение понятия структуры сечения при планировании кристалла впервые было предложено Оттентом и Шепеницем [6]. Под структурой сечений здесь понимается планировка кристалла, которую можно получить при последовательном проведении разделения его площади рядом сечений. При этом планировку нужно рассматривать как более общее понятие, под которым понимается результат разделения площади кристалла любым произвольным методом. Однако метод разбиения, как оказалось, ничего существенного для планирования кристалла не даёт, как впрочем, и для размещения на подложке необходимых макроструктур.
Помимо этих методик, широко применяются алгоритмы размещения отдельных элементов ИС на подложке [7]. К ним относятся алгоритмы последовательного размещения, для которых характерно строго последовательное назначение элементов на места коммутационного поля, причём выбор очередного элемента основывается на определении «меры связности» каждого из оставшихся элементов с уже размещёнными. К весьма распространённым относят алгоритмы дихотомического деления, в которых используется метод последовательного разбиения схемы на всё более мелки группы элементов. При этом с одновременно уточняется и некоторым образом корректируется положение каждой вновь образуемой группы. К общим недостаткам этих алгоритмов принято относить их последовательный характер, высокую вычислительную сложность, и неточность оценки числа соединений. Тем не менее, многие программы проектирования топологии основаны на этих алгоритмах. Здесь перечислены далеко не все методы, которые используются при проектировании топологии ИС.
Согласно современной концепции проектирования ИС, после завершения процесса трассировки следует процедура оптимизации/минимизации. Критерий, на основании которого производится этот процесс, как правило, зависит от условий трассировки. Однако ввиду разделения задач размещения и трассировки подобный критерий подобрать очень трудно. Единственным приемлемым критерием в этом смысле является собственно трассировка соединений, как это, например, происходит при ручном проектировании топологии. Однако громадная вычислительная сложность совместного решения задач размещения и трассировки даже для ИС с малым числом элементов заставляет применять при их конструировании эвристические критерии качества размещения [2], и поэтому эвристика играет главную роль в разработке программного обеспечения для проектирования топологии микросхем. Это, прежде всего, различные приближённые оценки тех интегральных параметров трассировки, изменение которых косвенно характеризует условия её проведения при заданном размещении элементов на подложке.
Рассмотрим наиболее широко распространённые частные критерии оптимизации размещения элементов. К ним можно отнести следующие:
— суммарная длина соединений ИС;
— суммарная площадь области реализации её цепей;
— наибольшая длина трассы;
— число трасс, длина которых больше заданной и др.
Помимо указанных критериев встречаются также и весьма экзотические. К ним относится алгоритмы на основе силовых функций [7]. При этом множеству элементов, подлежащих размещению, ставится в соответствие система материальных точек на плоскости, на которые действуют силы притяжения и отталкивания, которые определяются расстоянием между элементами. Тогда за искомое принимается такое расположение элементов на плоскости, при котором система находится в равновесии. Алгоритм, описывающий эту методику, получил некоторое распространение, но его недостатком является неточность решения для большого числа элементов и большой вычислительной сложности. Известны также алгоритмы, основанные на рассмотрении группы элементов, подлежащих размещению на плоскости, в виде механической системы тел. В этом случае критерием оптимального размещения являются нулевые проекции моментов и сил на оси координат.
Наиболее популярным и применяемым для оптимизации размещения элементов является алгоритм Гото. Он не учитывает геометрические размеры элементов, и считает, что выводы каждого элемента совпадают с его геометрическим центром. Смысл метода заключается в следующем. Для каждого элемента, предлагаемого к размещению, определяется совокупность элементов, общее число которых ограничено определённым числом. Каждый следующий элемент выбирается из тех, которые уже размещены на подложке. Далее рассматриваемый элемент включается в эту совокупность, и производится последовательная циклическая перестановка. Она считается успешной и может быть принята, если уменьшает исходное значение целевой функции.
В этом методе вводят понятие медианы элемента. Она определяется как такое положение элемента при его последовательной циклической перестановке, когда значение критерия качества размещения минимально. Применяя такие перестановки последовательно для всех элементов, находят такое их взаимное расположение, при котором целевая функция принимает наименьшее значение во всей области изменения, т.е. когда функция достигает глобального минимума. В качестве целевой функции в принципе могут использоваться любые функции, построенные в соответствии с указанными выше критериями. Однако наиболее часто применяется критерий минимальной суммарной длины соединений. Заметим, что наилучшие результаты в смысле сочетания качества размещения и необходимого машинного времени достигаются при четырёх элементах в группе.
Алгоритм Гото считается одним из самых эффективных алгоритмов оптимизации размещения элементов ИС. Но его возможности во многом ограничены только минимизацией различных оценок суммарной длины соединений схемы, для которых может быть построена сравнительно простая процедура поиска медианы элемента. Другие, более сложные критерии, оказываются трудно реализуемыми в силу большой вычислительной сложности.
К весьма распространённым можно отнести алгоритмы итерационной загруженности сечений, которые, подобно алгоритмам дихотомического деления, обеспечивают условия более оптимального распределения сечений. К общим недостаткам таких алгоритмов относят последовательный характер работы, эвристичность методов выбора и минимизации загруженности очередного сечения монтажного поля. Существуют также алгоритмы равномерного размещения элементов, которые в сочетании с другими позволяют значительно улучшить качество топологии в соответствии с выбранным критерием оптимизации. Однако вычислительные затраты при использовании нескольких алгоритмов при их как последовательной, так и параллельной работе сильно возрастают.
Все эти критерии помимо своих индивидуальных достоинств обладают тем очевидным недостатком, что не соответствуют необходимому условию связи геометрии кристалла с его схемотехникой. Часть из указанных критериев обладают низкой чувствительностью и не всегда полной адекватностью Кроме того, невозможна такая оптимизация топологии ИС, которая проводилась бы сразу по нескольким критериям, потому что крайне сложно учесть в одной целевой функции сразу все критерии, которые были бы необходимы. Критерии часто противоречат друг другу, а использование только одного из них не ведёт к получению оптимального результата с точки зрения параметров топологии.
Огромное число предлагаемых к использованию алгоритмов, как оказалось, не даёт оптимального технического решения проектирования топологии. Известно, что в настоящее время общепринятой практикой является итерационная разработка устройств, при которой на основании испытания опытного образца ведётся усовершенствование разработки. Усовершенствование топологии заключается в выборе такого взаимного расположения элементов схемы и соединений, при котором каждый следующий образец в большей степени удовлетворял бы спецификации на изделие, чем предыдущий. Создание новых опытных образцов связано с изменением их топологии, проектирование которой в приведённых алгоритмах рассматривается как геометрическая задача безотносительно к электрическим параметрам проектируемого изделия. Это приводит к тому, что в созданной топологии невозможно предугадать взаимное влияние элементов и их соединений друг на друга, что в виду субмикронных размеров элементов приводит к значительному отклонению электрических параметров схемы от первоначально запланированных. Это недопустимо в условиях требований к максимальному быстродействию и производительности ИС.
Получается, что на сегодняшний алгоритмы перехода от принципиальной схемы непосредственно к топологии схемы существуют и вполне проработаны, но базируются они на критериях, отдалённых от электроники и более близких к геометрии. Методы определения оптимального расположения элементов и трасс практически отсутствуют, т.е. налицо разрыв между электроникой и геометрией кристалла. Такое положение дел приводит к практической невозможности учёта паразитных параметров схемы и других негативных явлений, а значит, и точного определения параметров элементов, которые будут иметь место в реальном образце ИС.
Поэтому невозможно их рассчитывать и корректировать в процессе разработки, добиваясь оптимальных значений. Под оптимальными здесь понимается такие параметры произведённого образца, при котором данный образец наиболее полно удовлетворяет спецификации. Естественно полагать, что такой образец обладает наилучшей с точки зрения электроники из всех возможных топологий.
Таким образом, оказывается, что в отсутствие какой бы то ни было удовлетворительной теории, учитывающей означенное выше взаимное влияние элементов, процесс разработки новых ИС происходит со значительной затратой средств на создание и испытание промежуточных образцов и приводит как к многократному увеличению общего срока проектирования, так и к сильному удорожанию готовой продукции. И эта проблема требует решения.
Трудность создания теории, описывающей взаимовлияние элементов и трасс ИС, обусловлена следующими факторами. Все составляющие ИС приходится рассматривать как цепи с распределёнными параметрами. В таких линиях напряжение и ток меняются непрерывно от точка к точке, и они обладают распределёнными сопротивлением, ёмкостью и индуктивностью. В этих условиях крайне трудно привычными методами определить взаимовлияние элементов, поскольку для точного определения ёмкостей и др. требуется разделить все составные части проектируемой ИС на очень мелкие участки, что приводит к необходимости рассмотрения огромного количества их пар. Ситуация ещё больше усугубляется, если рассматриваемые элементы ИС относятся к нелинейным.
Но эта задача ввиду своей важности требует решения. Наиболее перспективным в этом отношении является применение численных методов, причём в этой области уже достигнуты некоторые успехи. Численные методы применяются для расчёта времени запаздывания сигналов, определения их искажения при прохождении через участок цепи и для многого другого. Применение строгих аналитических методов здесь в высшей степени самоограничено, поскольку они построены на строгом решении уравнений электростатического поля (уравнений Лапласа или Пуассона). Задача решается только для тривиальных случаев (однородная среда и простейшая форма электродов в виде пластин, ёмкости между двумя шарами или цилиндрами и т. п.). В результате получают некоторую аналитическую формулу, которую можно использовать. В большинстве же случаев рассматриваемая система намного сложнее.
Как правило, для расчёта взаимовлияния элементов ИС строится математическая модель системы на основании дифференциальных уравнений. В настоящее время для их решения широко используются метод конформных изображений (он аналитический), а также метод конечных [8,9] и граничных [10,11] элементов.
Первый из указанных методов относится к методам служебным. Он используется для преобразования областей, в том числе и областей интегрирования дифференциальных уравнений. Он основан на введении функции перехода, которая ставит в соответствие исходной области новую, более «удобную» для исследователя по каким-либо причинам. При этом считается, что исходная область плоская и задана в координатной плоскости комплексных чисел. Здесь используются свойства конформных отображений.
Метод конечных элементов является одним из самых мощных методов, пригодных для анализа и решения самых разнообразных технических и научных задач. Он основан на разбиении всей расчетной области (двумерной или трехмерной) на конечные элементы. Причем чем мельче эти элементы, тем точнее описание процессов и явлений, но тем больше затраты вычислительных ресурсов. Преимущества этого метода перед многими другими обнаруживаются при решении задач математической физики.
Метод конечных элементов является во многом обобщением метода Галёркина и используется для приближённого численного решения линейных дифференциальных уравнений с учётом линейных краевых условий. При этом искомую функцию аппроксимируют линейной комбинацией так называемых финитных функций, в простейшем случае линейных, причём коэффициенты в линейной комбинации рассчитываются вполне определённым методом. В одномерном случае, который встречается наиболее часто, для определения коэффициентов используется система линейных алгебраических уравнений. Заметим, что в этом методе область, в которой ищется решение, всегда является ограниченной.
Метод граничных элементов используется для решения двух- и трехмерных задач. Он может применяться для интегрирования дифференциальных уравнений теплопроводности, диффузии и др. Для этого метода характерна возможность интегрирования по бесконечной области. Собственно метод заключается в разбиении области на ряд ячеек, каждая из которых является, например, треугольником (в плоском случае). При этом граница области, если она гладкая, заменяется на кусочно-линейную или кусочно-плоскую, и граничные условия считаются постоянными на каждом участке внешней границы области. Внутри каждой ячейки искомая функция считается постоянной. Далее проводится интегрирование по всей области с учётом специфики уравнения.
Заметим, что, полагая в рассматриваемом уравнении время параметром, можно рассматривать зависимость интегрируемой функции от времени в данной точке пространства. Это позволяет определять время задержки прохождения сигналов и многие другие характеристики цепей.
Рассмотрим в качестве примера применение методов граничных и конечных элементов к решению дифференциального уравнения теплопроводности (частный случай трёхмерного телеграфного волнового уравнения), которое описывает распространение волн (звуковых, электромагнитных и пр.) в различных средах. Это уравнение имеет вид:
В уравнении (1) искомая функция U(x,y,z,t) описывает распространение волны в пространстве и во времени. Пусть функция U есть, например, потенциал в данной точке области интегрирования Ω, зависящий от времени, а сама область, которую будем считать плоской, представляет собой цепь с распределёнными параметрами. Для её характеристики используем величину k=1/RC, которую можно считать эквивалентной коэффициенту теплопроводности. Уравнение интегрируется при t>0.
Поскольку область считается плоской, то она ограничена плоской кривой, которую обозначим Г. Для получения однозначного решения необходимо задать граничные и начальные условия. Под граничными условиями понимается значение функции U в любой момент времени в точках, лежащих на кривой. Необходимо отметить, что граничные условия могут задаваться и в виде значений производной функции U по направлению, перпендикулярному данной точке на границе Г. Начальные условия задают потенциал в момент времени t=0 в точках, лежащих внутри области Ω. В простейшем случае начальные условия будут нулевыми.
Заметим, что граничные условия могут задаваться и при помощи градиента функции U, вычисленном в направлении, перпендикулярном Г. Как правило, в конкретных инженерных задачах граничные условия задаются одновременно обоими способами.
Если дважды проинтегрировать по частям оператор Лапласа и один раз производную по времени, то из уравнения (1) можно получить следующее:
Здесь функция U* есть фундаментальное решение исходного уравнения (1). Это решение является аналитическим. q* — это функция, которую можно определить как поток через участок границы dГ. Для двухмерного случая они имеют сравнительно простой вид. t определяет конечный момент интегрирования.
Уравнение (2) после незначительных преобразований можно проинтегрировать, используя метод граничных элементов. Для этого кусочно-гладкую (в общем случае) границу аппроксимируем отрезками прямой и полагаем граничные условия неизменными на каждом участке аппроксимации. Область Ω разбивается на ячейки треугольной формы.
При численном решении интегралы заменяются соответствующими суммами, и уравнение (2) решается относительно U для каждого значения времени t. Эти значения перебираются дискретно с необходимым шагом.
В результате для каждого значения времени можно получить значения потенциала в различных точках области.
Метод конечных элементов применяется в основном для интегрирования обыкновенных дифференциальных уравнений. Однако он может применяться и для поиска численного решения уравнений в частных производных. При этом также необходимы начальные и конечные условия. Искомая функция U на каждом участке области интегрирования представляется в виде суммы финитных функций, при этом область заранее разбивается на ячейки. Заметим, что в отличие от метода граничных элементов в пределах ячейки функция U не считается постоянной, а изменяется согласно своей аппроксимации. Несмотря на то, что финитные функции имеют вполне определённый вид и решение сводится к поиску коэффициентов, уже для двухмерного случая возникают серьёзные проблемы с поиском последних. Причина этого заключается в многократном увеличении объёма вычислений, которые надо провести для нахождения этих коэффициентов. Разбиение области интегрирования, как правило, является прямоугольным.
Таким образом, в настоящее время метод граничных элементов является одним из самых перспективных для решения задачи учёта взаимовлияния элементов ИС. Использование его в программных средствах проектирования топологии в сочетании с адекватно построенными моделями учёта паразитных параметров, способно привести к разработке таких критериев оптимизации и размещения, которые обеспечат наиболее оптимальное расположение элементов в смысле соответствия реальной схемы схеме исходной. Такие программные средства могли бы производить автоматическую корректировку рассчитанных параметров принципиальной схемы. Всё это обеспечило бы максимальное соответствие новых образцов их спецификации, и позволило бы устранить итерационный характер разработки топологии.
Для обеспечения осуществления столь далеко идущих планов необходима общая разработка методики учёта взаимовлияния, её физической, математической и расчётной основы. Эти вопросы будут прорабатываться в ближайшее время.
Литература
1. Р.К. Кейвин III, Дж.Л. Хилберт. Проектирование интегральных схем: направления и проблемы. ТИИЭР, 1991, т.78, №2, с.213-235.
2. Э.С. Ку, Т. Оцуки. Последние достижения в проектировании топологии СБИС. ТИИЭР, 1991, т.78, №2, с.6-37.
3. L. Sha, R.W. Dutton, “An analytical algorithm for placement of arbitrarily sized rectangular blocks,” in Proc. 22nd DAC, 1985, pp.284-290.
4. M.A. Breuer, “A class of min-cut placement algorithms,” in Proc.14th , 1977, pp.284-290.
5. U. Lauther, “A min-cut placement algorithm for general cell assemblies based on a graph representation,” in Proc.16th DAC, June 1979, pp.1-10.
6. A.A. Szepieniec, R. Other, “The genealogical approach to the layout problem,” in Proc. 17th DAC, 1980, pp.535-542.
7. Г.Г. Казеннов, Е.В. Сердобинцев. Проектирование топологии матричных БИС. М., «Высшая школа», 1990, с.27-61.
8. В.М. Вержбицкий. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М., «Высшая школа», 2001, с.294-332.
9. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Москва — Санкт-Петербург, «ФИЗМАТИЗД», 2002, С.558-566.
10. П. Бенерджи, Р. Баттерфильд. Метод конечных элементов а прикладных науках. М., «Мир», 1984.
11. К. Бреббия, Ж. Теллес, Л. Вроубел. Методы граничных элементов. М., «Мир», 1987.
Искренне Ваш, Главный научный сотрудник
P.S. Прошу подписываться на мой канал! Считаю, что мой опыт и научные достижения должны стать общедоступными. Только оригинальные статьи, собственные наработки!
P.P.S. Сории за лонгрид. Есть материал, который не поддается логическому разбиению...
