автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Спектральные алгоритмы редукции линейных систем управления для задач микроэлектроники

005015097

На правах рукописи

Карасева Ирина Андреевна

СПЕКТРАЛЬНЫЕ АЛГОРИТМЫ РЕДУКЦИИ ЛИНЕЙНЫХ СИСТЕМ УПРАВЛЕНИЯ ДЛЯ ЗАДАЧ МИКРОЭЛЕКТРОНИКИ

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

1 2 МДР Ш1

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2012

005015097

Работа выполнена в Национальном исследовательском центре «Курчатовский институт»

Научный руководитель доктор физико-математических наук,

ведущий научный сотрудник ИВМ РАН, Нечепуренко Юрий Михайлович

Официальные оппоненты доктор физико-математических наук,

доцент кафедры вычислительной математики МГУ, Корнев Андрей Алексеевич

кандидат физико-математических наук, старший научный сотрудник ИВМ РАН, Горейнов Сергей Анатольевич

Ведущая организация Федеральное государственное бюджетное

учреждение науки Вычислительный центр им. А. А. Дородницына Российской академии наук

Защита состоится " заседании диссертационного совета Д 002.045.01 в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики Российской академии наук, расположенном по адресу: 119333, г. Москва, у. Губкина, д.8.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институте вычислительной математики Российской академии наук.

Автореферат разослан " " феб/ЮМ 2012 г.

Мргд 2012 г. в часов на

Ученый секретарь

диссертационного совета

доктор физико-математических наук

Бочаров Г.А.

СПИСОК СОКРАЩЕНИЙ

САПР - система автоматизированного проектирования. RC-схема - схема, содержащая резисторы и конденсаторы. RCL-схема - схема, содержащая резисторы, конденсаторы и индуктивности.

RCLM-схема - схема, содержащая резисторы, конденсаторы и индуктивности с учетом взаимных индуктивностей.

PACT - Pole Analysis via Congruence Transformations, широко используемый спектральный метод редукции RC-схсм, сохраняющий пассивность.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Неидеальность межсоединений в микросхемах оказывает значительное влияние на прохождение сигнала, вызывая задержки, шумы, рассеяние энергии.

Развитие технологии привело к уменьшению размеров конструктивных элементов микросхем, увеличению рабочих частот и увеличению функциональности устройств, а значит и их сложности. С уменьшением размеров возрастает важность учета как емкостных, так и индуктивных влияний фрагментов межсоединений друг на друга. Кроме того, все более важное значение приобретает учет влияния подложки на срабатывание расположенной на ней микросхемы. Таким образом, возрастает важность учета влияния межсоединений и подложки на функционирование схемы.

Электромагнитный анализ, включенный, как этап проектирования, во все современные САПР микроэлектроники, сводит анализ эффектов, вызванных неидеальностью межсоединений, к анализу различных электрических схем.

Методы редукции исходной схеме ставят в соответствие схему с существенно меньшим количеством элементов и, таким образом, позволяют учитывать влияние неидеальности межсоединений за приемлемое время. В прошедшие несколько десятилетий было разработано множество различных алгоритмов редукции как для RC-схем, так и для RCL-схем и RCLM-схем. Однако разработка новых более эффективных алгоритмов продолжает оставаться актуальной задачей.

Редукции позволяют существенно уменьшить размер исходной системы, однако сами редукции достаточно дороги с вычислительной точки зрения. Применение редукции целесообразно, если редуцированная система будет использоваться многократно. К задачам, не требующим многократного решения относиться, в том числе, задача определения времени задержки сигнала. Поэтому разработка новых более эффективных методов быстрого вычисления задержки сигнала является актуальной задачей.

Цель диссертационной работы. Работа посвящена разработке и исследованию спектрального алгоритма редукции для RCLM-схем и метода быстрого вычисления задержки сигнала для RC-схем.

Научная новизна. Исходная система пассивна, т.е. не генерирует энергию, поэтому одним из главных требований к редукции является сохранение пассивности. Спектральный алгоритм редукции, представленный в диссертации, снабжен эффективными средствами сохранения пассивности. Для RC-схем этот метод подобен хорошо известному методу PACT, основанному на преобразованиях конгруэнтности, и может трактоваться как его обобщение. До настоящего времени не существовало спектральных алгоритмов для RLCM-схем, позволяющих сохранять пассивность, для редукции RCL и RCLM схем применялись другие методы, главным образом технология PRIMA, основанная на аппроксимации в подпространствах Крылова.

Предложенный в диссертации алгоритм быстрого вычисления задержки сигнала основан на приближении входного сигнала несколькими первыми функциями JIareppa, а выход системы находится в виде суммы нескольких функций JIareppa и одного из собственных векторов матричного пучка, отвечающего системе (спектральная коррекция решения). Функции JIareppa хорошо приближают многие актуальные сигналы, используемые в микроэлектронике. Однако для вычисления задержки сигнала они используются впервые.

Методы исследования. Для разработки и обоснования алгоритмов в диссертации используются методы матричного анализа.

Практическая значимость. Алгоритмы представленные в данной работе были протестированы на схемах, взятых из промышленных дизайнов. В частности для метода быстрого вычисления задержки сигнала численные эксперименты проводились с использованием

набора состоящего из 35000 тестов. Результаты тестирования показали высокую эффективность обоих алгоритмов и целесообразность их использования в промышленном дизайне микроэлектроники.

Апробация результатов. Основные положения, сформулированные в диссертационной работе, обсуждались на семинарах в ФГБУ науки Институте вычислительной математики РАН, московском отделении Cadence Design Systems, ФГБУ науки Институте проблем проектирования в микроэлектронике, ФГБУ науки Вычислительный центр им. A.A. Дородницына РАН, НИЦ "Курчатовский институт", международной конференции "Matrix Methods and Operator Equations" (г. Москва, 2008 год), школе-конференции молодых ученых конференции "Математические идеи П. JI. Чсбышева и их приложения к современным проблемам естествознания" (г. Обнинск, 2011 год).

Публикации. Основные результаты диссертации изложены в четырех печатных работах, две из которых опубликованы в журналах, рекомендованых ВАК.

Личный вклад автора. В работах [1,3], написанных в соавторстве, личный вклад автора в равных долях с соавторами.

Структура и объём диссертации. Диссертация состоит из введения, двух глав, заключения и списка литературы, состоящего из 51 наименований. Общий объем составляет 107 страниц, в том числе 23 таблицы и 10 рисунков.

Благодарности. Диссертант выражает особую благодарность своему научному руководителю Юрию Михайловичу Нечепуренко за постоянную помощь и ценные советы в работе над диссертацией. Автор выражает искреннюю благодарность ныне ушедшей из жизни Алене Станиславовне Потягаловой, вместе с которой была начата работа над методом быстрого вычисления задержки сигнала.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, сформулирована цель и указана практическая значимость и научная новизна работы.

В первой главе предлагается и обосновывается алгоритм спектральной редукции для RCLM схем, позволяющий сохранить пассивность. Такие схемы моделируются системами дифференциальных и

алгебраических уравнений следующего вида:

Е^ + Ах = Ви, у = Втх. (1)

Здесь и означает покомпонентный вектор напряжений в портах схемы (вход системы), у - покомпонентный вектор токов, втекающих через порты из внешней схемы (выход), ах- п-компонентный вектор внутренних переменных (вектор состояния); А и Е - квадратные вещественные матрицы порядка п, а В - прямоугольную матрицу размера пхщ, имеющие следующую блочную структуру:

Ей Еп 0 0] [0"

Е\2 Е22 о О О О О Езз 0 ' 0 ' О 0 0 0 ] [/,»,_

где Лу и Еу - матрицы размеров щ х и щ + щ + щ + щ = п, а через /т здесь и далее обозначена единичная матрица порядка тп.

Рассматриваемая система отвечает пассивной, т.е. не генерирующей энергию схеме. Поэтому суммарная энергия, поступившая в систему извне в любой момент времени т > О, неотрицательная. Иначе говоря, для любой достаточно гладкой функции и

т

£(т) = /(и(*),у(*))Л> 0, т > 0.

о

Справедливость этого гарантируют следующие свойства матриц А и Е:

А + Ат > 0, Е = Ет > 0, которыми на практике они обладают.

Если существуют преобразования Лапласа управления й(в) и состояния х(й) системы (1), то они связаны равенством (А+вЕ)х = Вй. Если, кроме того, матричный пучок А + вЕ - регулярный, то у(з) = где

С{8) = Вт{А + зЕ)~1В. Функцию С(й) называют передаточной функцией системы (1).

Алгоритм состоит из трех этапов: предварительных преобразований, блочной диагонализации на основе сбалансированной дихотомии и непосредственно редукции.

Аи А\2 ¿13 -Лч

А\2 А2 2 ¿23 0

Лзз 0

0 0 0

На первом этапе используя преобразования конгруэнтности, исходная система приводится к эквивалентной системе с новыми матрицами А и Е следующего вида

(2)

' Ап V Ей 0 о'

А = ЗУТ 0 , Е = 0 ■^Пз + Пз 0

0 0 0 0 0

где

Л22 А23

^23

-Дя ^33

У=\А1г А13\, J =

О -/,

"3

Блоки матриц Ау и Е^ отличаются от исходных. Размер системы может, вообще говоря, уменьшится. Полученная система пассивна, а конечный спектр пучка А + вЕ остается неизменным.

На втором этапе выполняется блочная диагонализация. Система полученная после предварительных преобразований приводится к новой системе с теми же матрицами Е и В, но новой матрицей А вида

А'-

Ац V: ЛУ? Я

К

я,

(3)

где

А?22 А323 -А% А{

зз

, Ц = I А{2 А{з

4

о

о

(4)

блоки А\к являются симметричными неотрицательно определенными

матрицами и каждый блок с индексами Ы имеет размерность пк хп],

р

п{=Щ, £ п{ =пк, к = 2,3. ¿=1

Для новой системы достаточное условие пассивности можно записать как

Н =

Ап ... Ар12 А1Т А1

^12 ^22

>0, А13>0, j = l,...,p, Еп>0.

Условие Н > 0 означает, в частности, что все подматрицы А22 > 0. Определим для каждой такой подматрицы матрицы А^, А/2 следующим образом. Если А22 невырожденная, то А$2 = А22, А{2 = А{2. В противном случае А22 - это квадратная невырожденная матрица, входящая в некоторое произвольное (например, спектральное) разложение вида А22 = Pj diag{A<i2,0)Pj' с ортогональной матрицей Pj, а [Ai2) ^12] = AnPj, гДе число столбцов матрицы совпадает с порядком матрицы А22. Справедлива следующая лемма.

Лемма 1. Пусть матрицы А^2 пулевые для всех тех j, при которых матрица А22 вырожденная. Тогда Н > 0 в том, и только том случав, если

д = £ д,- > О,

j=О

где

А0 = A1U Aj = -Xi2{Xi2rlAg.

Лемма 1 обосновывает следующее достаточное условие пассивности.

Критерий пассивности 1. Система (1) пассивна, если AJ33 > 0 (j = 1, ...,р), Ец > 0 и выполнены условия леммы 1.

Однако на практике, часто оказываются выполненными более жесткие условия.

Критерий пассивности 2. Система (1) пассивна, если

А{2 > 0, А{з > 0, j = 1, ...,£>; Д = £ Aj > 0, Еп > 0,

3=0

где

До - An, Aj = -А{2(А{2у1А%.

Мы будем приводить матрицу А, полученную после предварительных преобразований, к виду (3) преобразованиями подобия, последовательно шаг за шагом увеличивая число блоков р на единицу. Первый шаг состоит в умножении второй блочной строки матрицы А в (2) слева на У-1 и второго блочного столбца справа на Y, где Y -невырожденная матрица порядка т = п2 + пз такая, что

1 _ ' Jx 0 ' YTJ, Y^FY = >1 0 ' ' Li 0

J- —

0 J2 0 f2 ' J .0 .

а матрицы Р^ удовлетворяют равенству (ЗР)Т — FJ, (^Р)т = РЗ^, и их спектры являются непересекающимися взаимно дополнительными самосопряженными подмножествами спектра матрицы F.

Затем аналогичному преобразованию, которое в [1,3] было названо сбалансированной дихотомией, подвергаются вторые либо третьи блочные строки и столбцы полученной матрицы. И так далее. Поскольку каждый шаг является преобразованием подобия исходной матрицы А, и не является, вообще говоря, преобразованием конгруэнтности, матрица (3) при р > 2 может не удовлетворять достаточному условию пассивности А + Ат > 0. Однако критерий пассивности 1 либо 2, позволяет эффективно следить за выполнением этого условия после каждой дихотомии.

Кроме того, поскольку У~1 = (УТУ)~1УТ, в качестве меры отклонения очередного преобразования подобия от преобразования конгруэнтности можно рассматривать величину и = сопс^^У). Сбалансированная дихотомия включает в себя выбор для заданной матрицы Р такой матрицы У, что бы величина и не превосходила заданной величины. Существование этой матрицы обосновывают следующие две леммы.

Лемма 2. Пусть Р и 3 - вещественные квадратные матрицы порядка т такие, что

<51 - вещественная т X т\ матрица, столбцы которой образуют ор-тонормированный базис в инвариантном подпространстве матрицы Р, отвечающем некоторому изолированному самосопряженному подмноэ/сесгпву Х(Р) 1 ее спектра Х(Р), и фг ~~ вещественная гп х т2 (тег = т—т\) матрица, дополняющая до ортогональной квадратной. Тогда матрица = [фь */<Зг] ~ невырожденная и справедливы следующие равенства:

о

о '

{С%ЛЭгШЛ21) + = /т„

{ОрЯхШ^г) + {Я1Щг)2 = 1тг

JFZ =

о

о

гтзг =

Пусть, в условиях леммы 2 О^ЗС^^ = и^И^З^Щ есть спектральное разложение матрицы (д^ЗСд], где О] - положительная диагональная матрица модулей собственных значений этой матрицы, или, что тоже самое, ее сингулярных чисел, и) - вещественная ортогональная матрица, а «/, - диагональная матрица состоящая из ±1, т.е. знаков собственных значений. Отметим, что суммарное количество 1 (—1) в матрицах 3\ и 3% равно количеству 1 (—1) в матрице 3. Рассмотрим матрицу

У = [УЬУ2], У1 = $1[/1£Г1/2, ^^¡/г^2 (6)

В диссертации показывается, что эта матрица удовлетворяет (5), а для полученных и ^ справедливо [3]Р)Т = FJj.

Лемма 3. Минимальные диагональные элементы матриц и £>2 равны меэ/сду собой и не превосходят единицу, а для матрицы У справедливо следующее неравенство

V = сопЛ2{УТУ) < V* = ЗтЫ (1 - - ,

где с1тт - величина этих минимальных диагональных элементов.

В диссертации показано, как выбрать для заданных матриц F и 3 описанные в лемме 2 матрицы <31 и оценить величину и через минимальное сингулярное число матрицы С^ЗС^х либо С^ЗС}?. и, если эта величина нас устраивает, выполнить сбалансированную дихотомию.

Третьем этапом являться редукция. Редукция производиться на основе редукции передаточной функции. Передаточная функция полученной системы, т.е. системы (1), с матрицей Е вида (2) и матрицей А вида (3), представима в виде

<?(*) = £ ад, (7)

■7=0

где

С?о(в) = Ли + вЕи, ад = + в^Г'З^Т.

Лемма 4. Для слагаемых передаточной функции (7) справедливы следующие представления: Gj(s) = + йС^^) = б^о + яС^ю +

Близость редуцированной системы к исходной оценивается непосредственно по формуле

тах||С(ш) - ¿"(и^Нг/НС^Нг, и = шк, к = 1, для заданного набора контрольных частот

О < Ш1 < ... < и>я = ютах.

Используются следующие варианты редукции:

a) слагаемое в ¿(в) отбрасывается полностью,

b) сохраняется нулевой момент

c) сохраняются два первых момента, т.е. б^о + sGjw■ Соответствующая редуцированная система получается из исходной отбрасыванием 3 + 1-х блочных строк и столбцов матриц Аи Е п ] + 1-й блочной строки матрицы В. При сохранении нулевого момента, помимо этого меняется матрица Ац\ Л"™ = Лц + а при сохранении еще и первого момента меняется также и матрица Ец\ Е'^™ = Еп + Для того, чтобы редуцированная система продолжала удовлетворять критерию пассивности 1 либо 2 надо, что бы Дпеш > О, где Апег" = Д — Д| в случае полного отбрасывания слагаемого Gj{s) и Апеу} = А - А] + в случае сохранения нулевого момента. Кроме того, при сохранении первого момента необходимо убедиться, что

> 0.

После редукции для уменьшения числа ненулевых элементов можно выполнить блочную диагонализацию (уже не обращая внимание на критерий пассивности) тех блоков, которые не удалось разбить с сохранением выполнения критерия пассивности.

Предложенный алгоритм был протестирован на ИСЬ и ИСЬМ схемах из промышленного дизайна. Порядок матриц от 41 до 142. Результаты экспериментов представлены в таблицах. В таблице 1 представлено количество резисторов (II), конденсаторов (С), индуктивно-стей (Ь), взаимных индуктивности! (М), размеры исходных (щ) и редуцированных матриц (пг), а также отношение размера редуцированных матриц к исходным.

Тест И С 1 М щ пг пг/щ

1 32 15 13 - 41 6 0.15

2 141 48 46 - 142 12 0.08

3 95 48 46 - 142 15 0.10

4 500 1070 41 610 141 9 0.06

Таблица 2 для каждого теста показывает качество редукции. А именно количество ненулевых элементов исходных матриц (ЛГ,-), количество ненулевых элементов редуцированных матриц (АГг), а так же отношение количества ненулевых элементов исходных матриц к ненулевым элементам редуцированных матриц. Кроме того в 5-й колонке представлена погрешность редукции.

Таблица 2. Качество редукции

Тест К лда Погрешность редукции

1 142 ю о 0.18 0.042

2 517 56 0.1 0.069

3 420 57 0.14 0.068

4 4677 54 0.01 0.047

Из таблицы 1 видно, что предложенный алгоритм редукции позволяет существенно уменьшить размер системы и, как показано в таблице 2, при этом количество ненулевых элементов значительно сокращается. Отдельно стоит выделить И-СЬМ-схсму, которая имеет намного больше ненулевых элементов. Поэтому отношение количества ненулевых элементов исходных матриц к ненулевым элементам редуцированных матриц значительно меньше, и равно 0.01, в то время как для ЯСЬ-схем, представленных в таблицах, эта цифра варьируется от 0.1 до 0.18.

Во второй главе предлагается метод быстрого вычисления задержки сигнала. Рассматриваются КС-схемы с П1-м портовым узлом и П2-я внутренними узлами, из которых только один является выходом. Моделирование таких ИС-схем на основе законов Ома и Кирхгофа приводит к линейной системе обыкновенных дифференциальных и алгебраических уравнений следующего вида:

Е— + Ах = Вщп, иои1 = Сх, (8)

с начальным условием

х2(0) = 0, (9)

где х = (х{, Х3 )т - п-компонентный вектор, х'1 = щп, х2 ~ п2-компонентный вектор напряжений во внутренних узлах, хз - щ-ком-понентный вектор токов, вытекающих из портовых узлов, и п = 2п\ + п2. Задержка определяется как разность времени, за которое напряжение, поданное на вход, достигает определенного значения, и времени, за которое напряжение на выходе достигает того же значения. Таким образом, для приближенного вычисления задержки сигнала для заданного входного сигнала щп(1), необходимо найти приближенное значение ит1(Ь) при í > Ттах, где Ттах некоторое заданное время.

На первом этапе ищем решение, удовлетворяющее только (8). Для этого мы приближаем щп несколькими функциями Лагерра:

к-1

« щп({) = ]Г а;^(г), !=0

где

__«оо р^ (р

я® = ^2ре-р1и(2рЬ), а,- = /о и^фоЙ, =

Здесь - г-я функция Лагерра, ¿¿(£) - полином Лагерра г-й степени, щ - вектор коэффициентов. Затем ищем приближение вектора х в следующем виде:

4=0

где с* некоторые неизвестные векторы коэффициентов. Таким образом, вычисление = Сх сводится к вычислению векторов с,. Для того чтобы вычислить Сг подставляем щп, х и йх/сИ в (8) и приравниваем слагаемые при одинаковых функциях Лагерра. Для вычисления производной функции Лагерра используем следующие равенства:

= ЩШ = ^рРт + 2р±у[ч(1), i> 1,

где Щ - числовые коэффициенты, которые можно найти, используя явный вид функций Лагсрра. Это приводит к системе линейных алгебраических уравнений:

(А-рЕ 2рЬ\Е ... 2рЬ\-_\Е 2РЬкк1\Е \ ( с0 \ ( Ва0 \

О А-рЕ ... 2рЬкк1\Е 2рЪкк-_\Е

\

О 0 ... О А — рЕ у \ Ск-1 / \Вак^)

со С1

Всц

Найденное приближенное решение удовлетворяет (8), но, вообще говоря, не удовлетворяет начальному условию (9).

На втором этапе выполняется спектральная коррекция решения. К полученному решению добавляется решение однородной системы уравнений

Е^ + Ах = О М

с начальным условием ^(О) = —£2(0). Известно, что решение этой системы можно представить в виде суммы решений вида

где А; - конечное собственное значение пучка ХЕ+А, - собственный вектор, отвечающий этому собственному значению, а с^ - числовой коэффициент.

Как показывают численные эксперименты, для хорошего приближения иои1 достаточно потребовать, что бы {¿^(0) = 0. Для этого достаточно использовать только одно из решений, отвечающее минимальному собственному значению А,пг,г пучка АЕ + А. Добавляя это решение, к полученному ранее приближенному решению, получим:

х{1) и х{г) = £ +

1=0

где

г=0

Предложенный метод был использован для быстрого вычисления задержки сигнала для частного случая, когда на один из портов подавалось напряжение, которое растет линейно от 0 до 1 вольта за время Т и далее не меняется.

Для быстрого вычисления задержки, щп приближался двумя функциями Лагсрра.

Приближение выходного сигнала двумя функциями Лагерра не позволяет гарантировать хорошее приближение задержки сигнала для всех схем. Однако были предложены критерии, позволяющие определить, будет ли гарантированно хорошее приближение для каждой из схем:

Критерий 1: в < Г/,, где 5' обратная величина максимального собственного значения Хтах пучка А + XЕ, взятая с противоположным знаком, Т.е. 5 = 1/^тах-

Критерий 2: ЯСы < 7/„ величина ЯСш = (£Я*)(£С;), равная произведению суммы всех сопротивлений резисторов на сумму емкостей всех конденсаторов схемы.

Здесь Тд задается пользователем. Схемы, удовлетворяющие критерию 1 или критерию 2, отвечают схемам с небольшой задержкой сигнала.

Для сигналов, которые достигают 1 вольта за время Т = 100, 200 и 400 пикосекунд были проведены численные эксперименты при помощи набора, состоящего из 35000 схем из промышленных дизайнов. Из этого набора выбирались схемы для дальнейшего исследования при помощи одного из двух описанных выше критериев. Если схема удовлетворяла выбранному критерию, то для него вычислялось ыои(, приближенное и точное время задержки и погрешность. В противном случае схема отбрасывалась.

Был проведен ряд численных экспериментов с использованием я-критерия. В таблице 3 показано количество схем, удовлетворявших условию в < Тд, максимальная точная задержка сигнала максимальная и средняя погрешности, а так же дисперсия, которая вычислялась по формуле

где £ - среднее значение погрешности, а гц - количество отобранных схем.

Также был проведен ряд численных экспериментов с использованием ЯС(0{-критерия. Результаты представлены в таблице 4, где в третьем столбце указано количество схем, удовлетворяющих условию

П х 1011 отобранных максимальная средняя

Т схем гртах 1<1е1 погрешность погрешность дисперсия

100 2 23572 27 2 0.0611 0.0593

200 2 23572 27 1 0.0302 0.0293

400 2 23572 27 1 0.0080 0.0079

100 1 18416 14 1 0.0252 0.0246

200 1 18416 13 1 0.0137 0.0135

400 1 18416 14 1 0.0050 0.0050

ИСш <т,,

Таблица 4. Результаты использования критерия 2

отобранных максимальная средняя

т П х 1011 схем '-ртах погрешность погрешность дисперсия

100 10 21769 53 2 0.0446 0.0428

200 10 21769 57 4 0.0309 0.0328

400 10 21769 57 1 0.0092 0.0091

100 7 19375 41 1 0.0287 0.0639

200 7 19375 43 1 0.0199 0.0288

400 7 19375 42 1 0.0078 0.0078

100 5 17137 29 1 0.0239 0.0233

200 5 17137 29 1 0.0172 0.0169

400 5 17137 29 1 0.0061 0.0060

Как видно из таблиц 3 и 4, оба критерия дают хорошие результаты, однако комбинация этих двух критериев позволяет добиться увеличения количества отобранных схем, т.е. тех, для которых возможно успешное применение предложенного метода. Критерий 3: б < Тд, или ДС^ < Т/,2.

В таблице 5 представлены результаты для схем, удовлетворяющих в < 1 х Ю-11 или ЯСш < 7 х Ю-11. Количество отобранных схем увеличилось до 20903. В то же время, использование первого критерия позволяло отобрать лишь 18416, а второго - 19375 схем.

Таблица 5. Результаты применения критерия 3

отобранных Тчпах 1<1е1 максимальная средняя

Т схем погрешность погрешность дисперсия

100 20903 41 1 0.0303 0.0204

200 20903 43 1 0.0197 0.0193

400 20903 42 1 0.0079 0.0079

Таким образом, предложенный алгоритм позволяет быстро обработать около 59% тестов из представленного набора. Для остальных

схем можно использовать другие методы. В результате общее время обработки всего набора уменьшается.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Впервые предложен и реализован алгоритм спектральной редукции для RCLM-схем, позволяющий сохранить пассивность. Выполнены численные эксперименты с тестами из промышленных дизайнов, показавшие его высокую эффективность.

2. Обоснованы преобразования, используемые в этом алгоритме. Доказано сохранение пассивности.

3. Предложен метод быстрого вычисления задержки сигнала в RC-схемах на основе приближения входного и выходного сигналов функциями Лагерра и спектральной коррекции решения. Выполнены численные эксперименты с 35000 тестами из промышленных дизайнов, показавшие его высокую эффективность.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в научных изданиях рекомендованных ВАК РФ:

1. I.A. Karaseva, Yu.M. Nechepurenko, A.S. Potyagalova. Spectral reduction for control systems modeling passive integrated circuits // Comp. Maths. Math. Phys.. 2008. V.48, N.5. P.746-762.

2. I.A. Karaseva. Fast calculation of signal delay in RC-circuits based on Laguerre functions // Russ. J. Numer. Anal. Mach. Modeling. 2011. V.26, N.3. P.295-301.

Статьи в материалах конференций:

3. Yu.M. Nechepurenko, A.S. Potyagalova, I.A. Karaseva. Spectral model order reduction preserving passivity for large multiport RCLM networks //in Matrix methods: theory, algorithms, applications / Ed by Vadim Olshevsky and Eugene Tyrtyshnikov. New Jersey. London: World Scientific Publishing. 2010. P.533-538.

4. И.А. Карасева. Быстрое вычисление задержки сигнала в RC-схемах на основе функций Лагерра // V Международная конференция "Математические идеи П.Л.Чсбышева и их приложение к современным проблемам естествознания". Научная школа-конференция молодых исследователей: Тез. докладов / Под общей ред. В.А. Галкина. Обнинск: ИАТЭ НИЯУ МИФИ. 2011. С.21-22.

Заказ № 68-П/02/2012 Подписано в печать 13.02.2012 Тираж 100 экз. Усл. п.л.0,7

ООО "Цифровичок", тел. (495) 649-83-30 \С'} www.cfr.ru ; e-mail:info@cfr.ru

61 12-1/659

Национальный Исследовательский Центр "Курчатовский институт"

На правах рукописи

Карасева Ирина Андреевна

СПЕКТРАЛЬНЫЕ АЛГОРИТМЫ РЕДУКЦИИ ЛИНЕЙНЫХ СИСТЕМ УПРАВЛЕНИЯ ДЛЯ ЗАДАЧ МИКРОЭЛЕКТРОНИКИ

05.13.18 - Математическое моделирование, численные методы и

комплексы программ

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук Нечепуренко Ю. М.

Москва 2012

Оглавление

Введение 4

Глава 1. Алгоритм спектральной редукции 12

1.1 Постановка задачи................................................12

1.2 Предварительные преобразования..............................18

1.3 Блочная диагонализация........................................26

1.4 Сбалансированная дихотомия....................................33

1.5 Редукция..........................................................39

1.6 Численные эксперименты........................................41

1.7 Анализ результатов ..............................................70

1.8 Выводы............................................................72

Глава 2. Метод быстрого вычисления задержки сигнала 74

2.1 Постановка задачи................................................74

2.2 Приближение выходного сигнала функциями Лагерра .... 79

2.3 Спектральная коррекция решения..............................82

2.4 Быстрое вычисление задержки сигнала........................84

2.5 Численные эксперименты........................................89

2.6 Выводы............................................................98

Заключение 99

Литература 101

Введение

Актуальность работы. Неидеальность межсоединений в микросхемах оказывает значительное влияние на прохождение сигнала, вызывая задержки, шумы, рассеяние энергии.

Развитие технологии привело к уменьшению размеров конструктивных элементов микросхем, увеличению рабочих частот и увеличению функциональности устройств, а значит и их сложности. С уменьшением размеров возрастает важность учета как емкостных, так и индуктивных влияний фрагментов межсоединений друг на друга. Кроме того все более важное значение приобретает учет влияния подложки на срабатывание расположенной на ней микросхемы. Таким образом возрастает важность учета влияния межсоединений и подложки на функционирование схемы.

Электромагнитный анализ, включенный, как этап проектирования, во все современные САПР микроэлектроники, сводит анализ эффектов, вызванных неидеальностью межсоединений, к анализу различных электрических схем.

Методы редукции ставят в соответствии исходной схеме схему с существенно меньшим количеством элементов, и таким образом, позволяют учитывать влияние неидеальности межсоединений за приемлемое время. В прошедшие несколько десятилетий было разработано множество различных алгоритмов редукции как для ЫС-схем, так и для ЯСЬ-схем и ЫСЬМ-схем.

Среди этих методов можно выделить несколько групп. Методы основанные на приближениях Паде, к таким методом относятся алгоритмы AWE /41, 42/, PVL /9, 10/ и его многопортовая версия MPVL /11/, а также SyPVL /12/ и его многопортовая версия SyMPVL /13, 14, 15/. Методы последовательного исключения узлов, самый известный метод TICER /8/. Проекционные методы с использованием подпространств Крылова /19, 20, 21/, среди которых наиболее известным является алгоритм PRIMA /16, 17, 18/. Спектральные методы, наиболее известный PACT /22, 23/. Методы сбалансированного усечения и другие /48, 49, 50/.

Однако разработка новых более эффективных алгоритмов продолжает оставаться актуальной задачей.

Редукции позволяют существенно уменьшить размер исходной системы, однако сами редукции достаточно дороги с вычислительной точки зрения. Применение редукции целесообразно, если редуцированная система будет использоваться многократно. К задачам не требующим многократного решения, относиться в том числе, задача определения времени задержки сигнала /44/. Поэтому разработка новых более эффективных методов быстрого вычисления задержки сигнала является актуальной задачей.

Цель диссертационной работы. Работа посвящена разработке и исследованию спектрального алгоритма редукции для RCLM-схем и метода быстрого вычисления задержки сигнала для RC-схем.

Научная новизна. Исходная система пассивна, т.е. не генерирует энергию, поэтому одним из главных требований к редукции является сохранение пассивности. Спектральный алгоритм редукции, представленный в первой главе /1, 2/, снабжен эффективными средствами сохранения

пассивности. Для RC-схем этот метод подобен хорошо известному методу PACT /22/, основанному на преобразованиях конгруэнтности, и может трактоваться как его обобщение. До настоящего времени не существовало спектральных алгоритмов для RLCM-схем, позволяющих сохранять пассивность. Для редукции RCL и RCLM схем применялись другие методы(/48, 49, 50/), главным образом технология PRIMA, основанная на аппроксимации в подпространствах Крылова.

Предложенный во второй главе алгоритм быстрого вычисления задержки сигнала основан на приближении входного сигнала несколькими первыми функциями Лагерра, а выход системы находится в виде суммы нескольких функций Лагерра и одного из собственных векторов^матричного пучка, отвечающего системе (спектральная коррекция решения) /3, 4/. Функции Лагерра хорошо приближают многие актуальные сигналы, используемые в микроэлектронике. Однако для вычисления задержки сигнала они используются впервые.

Методы исследования. Для разработки и обоснования алгоритмов в диссертации используются методы матричного анализа.

Практическая значимость. Алгоритмы представленные в данной работе были протестированы на схемах взятых из промышленных дизайнов. В частности для метода быстрого вычисления задержки сигнала численные эксперименты проводились с использованием набора состоящего из 35000 тестов. Результаты тестирования показали высокую эффективность обоих алгоритмов и целесообразность их использования в промышленном дизайне микроэлектроники.

Апробация результатов. Основные положения, сформулирован-

ные в диссертационной работе, обсуждались на семинарах в ФГБУ науки Институте вычислительной математики РАН, московском отделении Cadence Design Systems, ФГБУ науки Институте проблем проектирования в микроэлектронике, ФГБУ науки Вычислительный центр им. A.A. Дородницына РАН, НИЦ "Курчатовский институт", международной конференции " Matrix Methods and Operator Equations" (г. Москва, 2008 год), школе-конференции молодых ученых конференции "Математические идеи П. Л. Чебышева и их приложения к современным проблемам естествознания" (г. Обнинск, 2011 год).

Публикации. Основные результаты диссертации изложены в четырех печатных работах, две из которых опубликованы в журналах, рекомен-дованых ВАК.

Личный вклад автора. В работах [1,3], написанных в соавторстве, личный вклад автора в равных долях с соавторами.

Структура и объём диссертации. Диссертация состоит из введения, двух глав, заключения и списка литературы, состоящего из 51 наименований. Общий объем составляет 107 страниц, в том числе 23 таблицы и 10 рисунков.

В первой главе предлагается и обосновывается алгоритм спектральной редукции для RCLM схем, позволяющий сохранить пассивность. Такие схемы моделируются системами дифференциальных и алгебраических уравнений. Алгоритм состоит из трех частей: предварительных преобразований, блочной диагонализации на основе сбалансированной дихотомии и непосредственно редукции.

На первом этапе используя преобразования конгруэнтности, исход-

ная система приводится к эквивалентной системе с новыми матрицами, обладающими определенными свойствами. Размер системы может, вообще говоря, уменьшится. Полученная система остается пассивной.

На втором этапе выполняется блочная диагонализация. Блочная диагонализация проводится итеративно. На первом шаге полученные после предварительных преобразований матрицы системы подвергаются преобразованию, которое разбивает их главные подматрицы на два блока. Это преобразование было названо сбалансированной дихотомией. Затем полученные после первого шага матрицы подвергается аналогичному преобразованию, которое разбивает один из двух полученных после первого шага блоков на два. В результате получается матрицы с тремя блоками на главной диагонали. Таким образом, на каждом шаге количество блоков увеличивается на единицу. После таких преобразования система, вообще говоря, может оказаться не пассивной, однако этот этап включает в себя критерии, которые позволяют проверять сохранение пассивности на каждом шаге. Сформулированы и доказаны леммы, которые показывают существование преобразований, используемых в этом алгоритме, и сохранение пассивности.

Третьим этапом являться редукция. Редукция производиться на основе редукции передаточной функции. Редуцированная система получается из исходной отбрасыванием соответствующих блочных строк и столбцов матриц. Близость редуцированной системы к исходной оценивается в терминах близости передаточных функций.

Были проведены численные эксперименты на ИСЬ и ЖХМ-схемах из промышленного дизайна. Численные эксперименты показали высокую

эффективность используемого алгоритма. Предложенный алгоритм спектральной редукции позволяет существенно уменьшить размер системы, при этом количество ненулевых элементов значительно сокращается.

Во второй главе рассматривается метод быстрого вычисления задержки сигнала для ЫС-схем. Моделирование ИС-схем на основе законов Ома и Кирхгофа приводит к линейной системе обыкновенных дифференциальных и алгебраических уравнений. Задержка определяется как разность времени, за которое напряжение, поданное на вход, достигает определенного значения, и времени, за которое напряжение на выходе достигает того же значения. Таким образом для приближенного вычисления задержки сигнала для заданного входного сигнала, необходимо найти приближенное значение выходного. Рассматривалась задача с одним выходом.

На первом этапе приближаем входной сигнал несколькими функциями Лагерра и представляем выходной в том же виде, с неизвестными коэффициентами при функциях Лагерра. Таким образом, вычисление искомого выходного сигнала системы сводится к вычислению этих коэффициентов. Показано, что для нахождения этих коэффициентов требуется решить линейную систему уравнений.

На втором этапе выполняется спектральная коррекция решения. К полученному решению добавляется одно из решений однородной системы уравнений с некоторым неизвестным коэффициентом, который находиться из условия, что выходной сигнал в нулевой момент времени равен нулю. Численные эксперименты показали, что выполнение спектральной коррекции позволяет существенным образом увеличить точность приближения.

Предложенный метод был использован для быстрого вычисления за-

держки сигнала для частного случая, когда на один из портов подавалось напряжение, которое растет линейно от 0 до 1 вольта за время Т и далее не меняется. При этом, для приближения входного и выходного сигналов используются всего две функции Лагерра. Такой способ не может гарантировать хорошее приближение для всех схем, однако предлагаются простые критерии, позволяющие определить, будет ли гарантированно достаточно хорошее приближение для каждой рассматриваемой схемы.

Для сигналов которые достигают 1 вольта за время Т — 100, 200 и 400 пикосекунд были проведены численные эксперименты при помощи набора, состоящего из 35000 схем из промышленных дизайнов. Из этого набора выбирались схемы для дальнейшего исследования при помощи одного из критериев. Если схема удовлетворяла выбранному критерию, то для него вычислялось выходной сигнал, приближенное и точное время задержки и погрешность. В противном случае схема отбрасывался. Численные эксперименты показали эффективность представленного метода. Алгоритм позволяет быстро обработать примерно 59% схем из представленного набора.

Основные результаты и выводы.

1. Впервые предложен и реализован алгоритм спектральной редукции для ЖХМ-схем, позволяющий сохранить пассивность. Выполнены численные эксперименты с тестами из промышленных дизайнов, показавшие его высокую эффективность.

2. Обоснованы преобразования, используемые в этом алгоритме. Доказано сохранение пассивности.

3. Предложен метод быстрого вычисления задержки сигнала в КС-схемах на основе приближения входного и выходного сигналов функциями Лагер-

ра и спектральной коррекции решения. Выполнены численные эксперименты с 35000 тестами из промышленных дизайнов, показавшие его высокую эффективность.

Благодарности. Диссертант выражает особую благодарность своему научному руководителю Юрию Михайловичу Нечепуренко за постоянную помощь и ценные советы в работе над диссертацией. Автор выражает искреннюю благодарность ныне ушедшей из жизни Алене Станиславовне Потягаловой, вместе с которой была начата работа над методом быстрого вычисления задержки сигнала.

Глава 1. Алгоритм спектральной редукции

1.1. Постановка задачи

Рассмотрим линейную систему управления вида

Е^ + Ах = Ви, у = Втх, <И

(1.1.1)

возникающую при моделировании пассивных частей интегральных схем /27/, содержащих резисторы (Я - элементы), конденсаторы (С - элементы), индуктивности (Ь - элементы) и взаимные индуктивности (М - элементы). Здесь и означает покомпонентный вектор управления (вход системы), у -покомпонентный вектор наблюдения (выход), а х - п-компонентный вектор внутренних переменных (вектор состояния); А и Е - квадратные вещественные матрицы порядка п, а В - прямоугольная матрица размера п х П1, имеющие следующую блочную структуру:

А =

Е =

Ап А12 А13

Ау2 А22 А23

-Л-13 ~АТ1Ъ Л33

I

п 1

О

о

ЕЦ Е\ 2 0 0 0

Е12 Е22 0 0 , в = 0

0 0 Е33 0 0

0 0 0 0 1пг

-I

п 1

о о о

(1.1.2)

где Ац и Ец - матрицы размеров щ х п^ и щ + п2 + щ + щ = п, а через 1т здесь и далее обозначена единичная матрица порядка т.

Будем предполагать, что блоки матриц А и Е обладают следующими свойствами:

а) Матрицы

Ли л12 , Л33, Е п Е\2

_ ^12 А22 _ Е12 е22

- симметричные неотрицательно определенные, а матрица Е33 - симметричная положительно определенная. Ь) Пучок

А22 + эЕ22

(1.1.3)

^23

А1ъ Лзз + зЕ33

- регулярный, т.е. существует такое число «о, что матрица .й(зо) - невырождена, а его конечные собственные значения, т.е. корни уравнения с^ Щв) = О, лежат строго в левой полуплоскости.

с) Пучок А22 + ¿>.£/22 - регулярный.

(1) Уравнение Е^+ЗЕъч = 0 разрешимо относительно щхп2 матрицы

5.

Отметим, что выполнения этих условий на практике всегда можно добиться известными преобразованиями рассматриваемой схемы /18/.

В соответствии с разбиением на блоки матриц А и Е будем представлять вектор х следующим образом: х = (х^, х2 , , х^)т, где х* - покомпонентный вектор при г = 1,2,3 и покомпонентный вектор при г = 4. Отметим, что х\ = и и является вектором напряжений в портах схемы, х2

- вектор напряжений во внутренних узлах, Х3 - вектор токов, текущих по

ребру, содержащему индуктивность, а у = х^ - вектор токов, втекающих через порты из внешней схемы. Если схема состоит только из резисторов и конденсаторов, то щ = 0, т.е. в векторе состояния системы (1.1.1), (1.1.2) отсутствует подвектор а в матрицах отсутствуют все блоки, имеющие индекс 3, такие схемы называют КС схемами.

Рассматриваемая система отвечает пассивной /40, 32/, т.е. не генерирующей энергию, схеме. Поэтому суммарная энергия, поступившая в систему извне в любой момент времени т > 0, неотрицательная. Иначе говоря, для любой достаточно гладкой функции и

т

£{т) = ¡(и{1),у(1))М> 0, т > 0. (1.1.4)

о

Справедливость (1.1.4) гарантируют следующие свойства матриц А и Е:

А + Ат > 0, Е = Ет > 0, (1.1.5)

вытекающие из указанного выше свойства (а) их блоков. Действительно, учитывая симметричность матрицы Е, имеем:

/ (Цх \

(и, у) = (и, Втх) = (Ви, х) = + Ах, х) =

К{Е%Х) + {%ЕХ)) + 12({АХ'Х) + ^АТх^ШЕ%х)+(ЕхШ+т

^((Ах,х) + (Атх,х)) = ^(Ех,х) + (^Л+2Л х, ^ •

Поэтому из неотрицательной определенности матриц Е н А-\- Ат следует (1.1.4). Таким образом, для любой системы вида (1.1.1) с матрицами А и Е, удовлетворяющими (1.1.5), справедливо неравенство (1.1.4).

Если существуют преобразования Лапласа управления й(з) и состояния системы (1.1.1), то они связаны равенством (А+вЕ)х = Вй. Если, кроме того, матричный пучок А + бЕ - регулярный, то у (в) = (^(5)^(5), где

ОД = Вт(А + зЕ)~1В.

Отметим, что det(Л + вЕ) = det Поэтому свойство (Ь) эквивалентно регулярности пучка А + вЕ и отсутствию у него конечных собственных значений с неотрицательной вещественной частью.

Функцию называют передаточной функцией системы (1.1.1).

Для нее справедлива следующая формула:

А\2 + зЩ2

в{з) = Лц + зЕи - [Л12 + зЕ12, АцЩз)-1

-Ат

(1.1.6)

Действительно систему уравнений (А 4- зЕ)х — Вй, учитывая блочную структуру (1.1.2) можно переписать следующим образом

(Ли + + ([Л12, Л13] + З[Е12, 0])

%2 Хз

— ¿4 = 0,

/ ^12 Е12 \ УЯ х2

Х\ -

\ 0 ) £ъ

= 0, ¿4 = у; х\ = й

Из второго уравнения видно

Х2 Ат12 + зЕ{2

Хз

Исключая вектор [х2, из первого уравнения и учитывая, что х\ =

и

получаем

/

(Лц + зЕц) + [¿12 + эЕ12, -А13] Д-1

V

нетрудно видеть, что передаточная функция такой системы будет функция (1.1.6). В частности, если щ = 0, то Щв) = А22 + зЕ22 и

д(з) = Ап + зЕп - (А12 + зЕ12)(А22 + зЕ22)-\А12 + зЕ12)т. (1.1.7)

В этой главе предлагается спектральный метод редукции