Многоуровневое обобщение класса релаксационных алгоритмов для анализа электрических цепей тема диссертации и автореферата по ВАК РФ 05.13.16, доктор технических наук Дмитриев-Здоров, Владимир Борисович

• Дмитриев-Здоров, Владимир Борисович
• доктор технических наук
• 1998

Оглавление диссертации доктор технических наук Дмитриев-Здоров, Владимир Борисович

СОДЕРЖАНИЕ

1. Введение

2. Релаксационные методы анализа электрических цепей и систем. Общее состояние вопроса и постановка задач исследования

2.1. "Классическая" структура алгоритмов анализа цепей и пути ее модернизации

2.2. Методы релаксации на этапе решения систем линейных и нелинейных алгебраических уравнений

2.3. Методы релаксации для решения систем дифференциальных уравнений цепи

2.4. Способы ускорения сходимости релаксационных алгоритмов и постановка задач исследования

3. Построение многоуровневого итерационного алгоритма

и У «_» о

для решения системы линеиных алгебраических уравнении цепей и систем

3.1. Многоуровневое обобщение базового итерационного алгоритма

3.2. Многоуровневый итерационный алгоритм с демпфированием

3.3. Каноническая структура многоуровневого итерационного алгоритма и его схемная интерпретация

3.4. Многоуровневый итерационный алгоритм для систем, содержащих "черные ящики"

3.5. Выводы

4. Особенности реализации многоуровневых итерационных алгоритмов

4.1. Учет ограниченности числа внутренних итераций МИ А

4.2. Оптимизация параметров МИ А

4.3. "Смещенные" и "несмещенные" итерации МИА

4.4. Выводы

5. Многоуровневые итерационные алгоритмы для анализа статических режимов нелинейных цепей

5.1. Каноническая структура нелинейного варианта МИА

5.2. Сходимость МИА при решении систем нелинейных алгебраических уравнений

5.3. Примеры использования МИА для анализа нелинейных цепей

5.4. Выводы

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

6.1. Каноническая форма многоуровневого метода РФ С

6.2. Сходимость многоуровневого обобщения метода РФС

6.3. Примеры использования МРФС для анализа динамических процессов в цепи

6.4. Выводы

7. Пути улучшения характеристик базового итерационного алгоритма

7.1. Разделение "быстрых" и "медленных" движений

7.2. Модифицированные методы сшивания подсистем

7.3. Обобщенный метод сшивания с адаптацией модели

7.4. Выводы

8. Применение МИА в задачах анализа электрических цепей и систем

8.1. Расширение класса методов структурной декомпозиции при использовании многоуровневых итерационных алгоритмов

8.2. Моделирование смешанных систем с помощью МИА

8.3. Применение МИА для решения уравнений в системе смешанного приборно-схемотехнического моделирования двумерных полупроводниковых структур

8.4. Выводы

9. Заключение

Литература

Введение диссертации (часть автореферата) на тему «Многоуровневое обобщение класса релаксационных алгоритмов для анализа электрических цепей»

1. ВВЕДЕНИЕ

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

Увеличение степени интеграции до 105 АО6 транзисторов на кристалле выдвигает качественно новые требования к алгоритмам и программным средствам, используемым для синтеза и верификации проектных вариантов БИС. В настоящее время для моделирования процессов в БИС с целью их верификации используются несколько различных по характеру процедур. При классификации обычно выделяют программы алгоритмического или функционального моделирования, моделирования на уровне регистров, временного (timing), схемного (circuit), а также компонентного (device) моделирования [1-4]. В последнее десятилетие как у нас в стране, так и за рубежом был разработан ряд программ смешанного моделирования, сочетающих в себе возможности нескольких названных процедур [5-7].

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

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

Схемное моделирование является не только наиболее надежной, но и самой трудоемкой и дорогостоящей процедурой. Для проведения схемного моделирования фирмы - разработчики БИС ежегодно тратят несколько тысяч часов компьютерного времени, а на работы по совершенствованию соответствующего программного обеспечения выделяется несколько миллионов долларов [8]. Необходимость в быстром и надежном электрическом анализе сложных систем возникает и в электроэнергетике, где требуется проводить в реальном времени моделирование кратковременной нестабильности, возникающей при коммутациях в энергосистеме. Так, система Midwestern US662 описывается совокупностью 96 тыс. дифференциально-алгебраических уравнений, которые необходимо решить на 100- 200 шагах временной сетки за 1- 10 с реального времени [9]

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

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

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

В течение двух последних десятилетий сформировался "классический" набор процедур, на котором базируется алгоритмическое обеспечение программ схемного моделирования. Он включает в себя неявные жестко-устойчивые методы алгебраизации ОДУ, ньютоновские итерации для решения нелинейных алгебраических уравнений и "прямые" методы гауссовского типа для решения систем линейных уравнений. Программы подобного типа

позволяют проводить моделирование цепей, описываемых системами, насчитывающими до 102 -105 уравнений [1-3, 11, 12], что не обеспечивает насущных потребностей при решении задач автоматизации и выполнении исследовательских работ. Несмотря на многочисленные и в целом небезуспешные попытки модернизации алгоритмического обеспечения, в рамках приведенной структуры к настоящему времени не удалось существенно расширить возможности программ автоматизированного анализа цепей, сделать их достаточно эффективными при моделировании БИС.

Надежда на существенный прогресс в области схемного моделирования БИС возникла в начале 80-х годов с появлением программ, базирующихся на методах релаксации, позволяющих реализовать структурную декомпозицию анализируемой цепи [13- 15]. По сравнению со своими предшественниками программы этого типа позволили в 10-100 раз сократить затраты процессорного времени при обработке систем, насчитывающих до нескольких сотен уравнений, довести размерность анализируемых систем до нескольких десятков тысяч уравнений. Кроме того, структурная декомпозиция модели дает возможность проводить независимую (последовательную или параллельную) обработку отдельных фрагментов, что открывает дополнительные возможности для реализации релаксационных методов на многопроцессорных системах [16- 19].

Основным недостатком, сдерживающим широкое^ применение релаксационных методов, является их медленная сходимость, а также ограниченность класса цепей, в котором выполняются условия такой сходимости. Попытки решения крайне актуальной задачи улучшения сходимости релаксационных методов в известных работах, например [17, 19- 24], сводятся к выбору оптимальной стратегии разбиения

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

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

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

Совокупность результатов, полученных при достижении поставленной цели и решении соответствующих задач, можно охарактеризовать как новое крупное достижение в развитии

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

На защиту выносятся:

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

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

3. Методики выбора параметров разработанных моделей и алгоритмов, оптимизирующие скорость их сходимости.

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

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

Научная новизна работы заключается в следующем:

1. Построен новый класс многоуровневых релаксационных методов анализа, включающих как частный случай линейные итерационные алгоритмы Зейделя, Якоби, последовательной верхней релаксации (ПВР) и соответствующее ему многоуровневое обобщение релаксационной модели исследуемого объекта. Разработанный класс

М 1111

моделей и алгоритмов применим к системам, содержащим закрытые блоки или "черные ящики".

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

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

3. Сформулированы многоуровневые итерационные алгоритмы (МИА) для анализа нелинейных динамических цепей, описываемых системами нелинейных алгебраических и дифференциальных уравнений, а также построены схемные модели рассмотренных алгоритмов.

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

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

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

Практическая ценность работы.

1. Разработан новый класс релаксационных моделей и алгоритмов, характеризующихся при прочих равных условиях линейной зависимостью затрат от размерности модели при анализе сложных систем. Ускорение достигается как по числу обращений к вычислительным моделям (числу итераций), так и по суммарным затратам времени ЭВМ.

2. Ускорение сходимости при использовании разработанных алгоритмов достигается и при анализе систем, содержащих "черные ящики", то есть фрагменты, внутренняя структура которых неизвестна.

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

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

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

в программе ИСТОК-2Д позволило в 3-8 раз ускорить анализ полупроводниковых структур. Перспективным является использование предложенных подходов для решения задач в других областях техники, требующих быстрого и эффективного анализа сложных систем.

Теоретические и практические результаты диссертационной работы вошли как составная часть в Госбюджетные НИР N3.22.008 "Методы моделирования и автоматизированного анализа радиоэлектронных цепей" и N 11151 "Разработать и исследовать адаптивные модели сложных электронных цепей и пространственно-временных сигналов с целью повышения точности и быстродействия работы САПР радиоэлектронных устройств и эффективности радиотехнических систем", хоздоговорные НИР NN 111118, 111125, 111131, в контракт N 24176821/95 "Моделирование смешанных систем", выполнявшийся по заказу Национального исследовательского центра ФРГ по вычислительной технике и информационным технологиям, а также в контракт 840/02069131/96001 "Виртуальная моделирующая установка, основанная на РЕВВ корабельной энергетической системы", выполняемый в настоящее время по заказу университета Южной Каролины (США) .

С помощью предложенных методов и алгоритмов в Национальном исследовательском центре ФРГ проведено моделирование ряда электро-акустических и электромеханических систем, в том же центре разработанные в диссертации алгоритмы используются в системе интеллектуальной поддержки пользователей программы SPICE3. Кроме того, многоуровневые итерационные алгоритмы внедрены в программу приборно-схемотехнического моделирования ИСТОК-2Д,

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

Основные результаты диссертационной работы неоднократно докладывались на научно-технических семинарах кафедры ТОР ТРТУ, научно-технических конференциях университета (1985-1994 гг.), всесоюзных, республиканских и международных конференциях и школах семинарах, в том числе: "Проблемы автоматизированного моделирования в электронике", Киев, 1983-1991 гг.; "Теоретическая электротехника, электроника и моделирование", Шацк- Карпаты, 1987, 1989; Всесоюзная конференция по теоретической электротехнике, Ташкент, 1987; "Численные методы и средства проектирования и испытания элементов РЭА", Таллин, 1987, 1989, 1991; "Методы автоматизированного проектирования электронно-вычислительной аппаратуры и СБИС", Черновцы, 1988; "Математическое и машинное моделирование в микроэлектронике", Паланга, 1988, 1989; "Новые информационные технологии в науке, образовании и бизнесе", Гурзуф, 1992-1994 гг.; Международный семинар "Нелинейные цепи и системы", Москва, 1992; 3-й Международный семинар по автоматизации проектирования, Москва, 1993; Международный симпозиум по нелинейной теории и ее приложениям, Гаваи, США, 1993; Европейская конференция по автоматизации проектирования, Гренобль, Франция, 1994, Брайтон, Великобритания, 1995, Женева, Швейцария, 1996; семинар "Параллельные вычисления", университет г. Кельна, Германия, 1995; Международная конференция по электронным цепям и системам,

Братислава, Словакия, 1997; 9-й Европейский симпозиум по моделированию, Пассау, Германия, 1997.

Результаты, полученные автором, опубликованы в 54 научных статьях и материалах республиканских, всесоюзных и международных конференций, а. также в монографии, изданной Олденбург-Ферлаг (Мюнхен, Вена) в 1997 г.

Структура диссертационной работы.

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

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

В третьей главе рассмотрены многоуровневые итерационные алгоритмы (МИА) для решения систем линейных алгебраических уравнений, даны оценки областей их сходимости, сформулирована версия алгоритма для систем, содержащих блоки, внутренние переменные которых недоступны.

В четвертой главе рассмотрены практические аспекты применения МИА для анализа линейных систем. Рассмотрены свойства алгоритмов при ограничении числа внутренних итераций, а также при наличии в системе кратных собственных значений.

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

В шестой главе построено многоуровневое обобщение метода релаксации формы сигнала. Исследованы свойства сходимости алгоритмов при анализе динамических систем.

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

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

2. РЕЛАКСАЦИОННЫЕ МЕТОДЫ АНАЛИЗА ЭЛЕКТРИЧЕСКИХ ЦЕПЕЙ И СИСТЕМ. ОБЩЕЕ СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

2.1 "Классическая" структура алгоритмов анализа цепей и пути ее модернизации

2.1.1. Математические и алгоритмические основы большинства используемых в настоящее время программ схемного моделирования были заложены в начале и середине 70-х годов в работах отечественных и зарубежных ученых, в первую очередь, Алексенко А.Г., Анисимова В.И., Анисимова Б.В., Архангельского А.Я., Баталова Б.В., Бахова В.А., Белова Б.И., Белякова Ю.Н., Бененсона З.М., Бондаренко В.М., Бубенникова А.Н., Власова А.И., Глориозова Е.А., Глушкова В.М., Данилова Л.В., Деньдобренко Б.Н., Егорова Ю.Б., Зворыкина Л.Н., Зуева Б.И., Ильина В.Н., Калниболотского Ю.М., Когана В.Л., Королева Ю.В., Маничева В.Б., Мозгового Г.П., Норенкова И.П., Петренко А.И., Петросянца К.О., Попова В.П., Ракитского Ю.В., Русакова С.Г., Сигорского В.П., Синицкого Л.А., Ссорина В.Г., Тимченко А.П., Трохименко Я.К., Флексер Л.А., Чахмахсазян Е.А., Abbas I.K., Balabanian N., Bickart T., Brajden С., Branin F., Brayton R., Calaban D., Chua L., Dertouzos M., Desoer C., Director S., Ebers J., Fletcher R., Gear C., Gummel H., Gustavson F., Hachtel G., Herskowits G., Ho C., Jenkins F., Katzenelson J., Koehler D., Lin P., Lindberg L., Liou M., Linvill J., Mead R., Moll J., Nakhla M., Ortega J., Parker S., Pederson D., Rheinboldt W., Richardson W., Rohrer R., Ruehli A., Sandberg I., Sechu S., Shichman H., Singhai K., Swamy M., Vlach I., Wang N., Willson A., Zobrist G.

К этому же периоду следует отнести и появление наиболее популярных средств для автоматизированного анализа цепей, таких как SPICE, ASTAP, NAP2, ПА-4, СПАРС и др. При создании программ подобного типа первоначально ставилась задача обеспечить эффективный анализ цепей, насчитывающих около сотни транзисторов. Насущные задачи сегодняшнего дня заставляют пользователей применять эти программы (или более современные, но базирующиеся на тех же принципах, такие как ПАРУС, PSPICE, ПРАМ-01, СПРОС-2) для анализа цепей, насчитывающих тысячи транзисторов, несмотря на то, что просчет одного варианта стоит очень дорого и требует многих часов процессорного времени. По данным [8], в ряде ведущих фирм, занимающихся проектированием БИС, программа SPICE запускается на решение в среднем 10000 раз в месяц, а более 70% процессорного времени IBM 3090 занимает схемное моделирование. С другой стороны, моделирование БИС, насчитывающей около 10000 транзисторов, требует примерно 1 часа IBM 3081 на одну временную точку.

"Стандартная" структура алгоритмов моделирования цепей во временной области включает в себя следующие процедуры:

1) Модифицированный узловой метод для построения системы дифференциальных уравнений на основе топологической и компонентной информации;

2) Жестко-устойчивые неявные методы интегрирования, такие как ФДН, Гира и др. для преобразования полученной дифференциальной системы в систему нелинейных алгебраических уравнений;

3) Модифицированный метод Ньютона для решения системы нелинейных алгебраических уравнений;

4) Решение систем линейных уравнений, получаемых на каждой ньютоновской итерации, методом Гаусса или Ы1 факторизации с использованием техники разреженных матриц.

Таким образом, процесс решения уравнений, описывающих поведение электрической цепи, содержится в пп.2-4 и может быть представлен в виде структуры, показанной на рис.2.1а.

Можно выделить два основных фактора, определяющих неэффективность традиционного подхода при анализе сложных цепей. Первый состоит в том, что трудоемкость решения систем линейных уравнений (СЛАУ) прямыми методами с учетом разреженности матриц растет быстрее, чем линейно при увеличении размерности цепи. На рис. 2.2 приведены типичные зависимости затрат процессорного времени ЭВМ на формирование и решение СЛАУ от числа уравнений модели N. В [14] трудоемкость решения уравнений характеризуется эмпирической зависимостью О(А^), где 1.1<5,<1.5. Затраты на решение СЛАУ в задачах схемного моделирования начинают преобладать, когда число уравнений достигает нескольких сотен - единиц тысяч, что ниже уровня сложности современных ИС.

Кроме того, для сложных цепей характерен значительный разброс постоянных времени, при котором фазовые переменные системы изменяются с весьма различными скоростями [1, 25, 26]. Непосредственное применение методов интегрирования "навязывает" каждому уравнению системы один и тот же шаг дискретизации, который определяется наиболее быстроизменяющимися переменными. Вместе с тем, для каждого уравнения или группы уравнений системы желательно выбирать наибольшую величину шага, при которой поведение соответствующих переменных отображается с достаточной точностью. Это обстоятельство особенно важно при анализе сложных

Стандартная

структура

алгоритмов

Релаксационные алгоритмы

Многоуровневые

релаксационные

алгоритмы

(а) (б) (в)

Рис.2.1. а) "Стандартная" структура программ анализа цепей; б) известные релаксационные алгоритмы; в) предлагаемое многоуровневое обобщение релаксационных алгоритмов

1,с 103

102

10

1

1 10 ю2 ю3 ю4

Рис.2.2. Зависимость времени анализа от числа уравнений цепи

1 сутки

7 часов Зчаса

1час 10 мин

Рис.2.3. Зависимость времени анализа от числа транзисторов в цепи для стандартных и релаксационных алгоритмов

Стандартные алгоритмы

Релаксационные методы

10

1<Г

10

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

В последние 1-2 десятилетия были предприняты значительные усилия, направленные на сокращение затрат при формировании и решении уравнений цепи и предложены новые подходы, такие как макромоделирование [27-29], использование табличных моделей активных элементов цепи [30, 31], применение принципов латентности [32, 33], метода подсхем [12, 34-36], программирование ряда процедур на языках низкого уровня [34], использование высокопроизводительных векторных ЭВМ [16, 37] и другие. Для решения жестких систем, описывающих электрические цепи с большим разбросом постоянных времени, были предложены адаптивные модели с переменной жесткостью [38-46]. Однако, применение всех этих подходов позволило уменьшить затраты процессорного времени не более, чем на порядок, поскольку основу соответствующих программ по-прежнему составляла рассмотренная "стандартная" алгоритмическая структура.

2.1.2. В начале 70-х годов был предложен ряд модификаций алгоритмической структуры, которые позволили исключить операции с разреженными матрицами и использовать индивидуальный выбор временного шага для различных уравнений или подсистем уравнений. Основой рассматриваемых модификаций явилось применение релаксационных методов. Хотя идея релаксации не нова, и восходит еще к работам Гаусса, впервые в задачах схемного моделирования она нашла применение только в 1975 году при построении программы МОТТБ [31], где использовался полунеявный метод, основанный на

итерациях Якоби. Применение этого метода в совокупности с табличными моделями МДП транзисторов позволило на два порядка сократить затраты при моделировании цифровых схем по сравнению с программами, использующими "стандартные" алгоритмы. Впоследствии, в программе MOTIS-C для увеличения точности результатов использовался полунеявный метод, основанный на итерациях Зейделя [49].

Как показали эксперименты, точность полунеявного алгоритма с итерациями Зейделя существенно зависела от порядка обработки уравнений системы. Если порядок их обработки соответствовал направлению распространения сигнала в цепи, алгоритм позволял получить более точные результаты. Это обстоятельство в дальнейшем было использовано в программе SPLICE [50], где полунеявный метод с итерациями Зейделя был дополнен специальной процедурой, выполняющей динамическое упорядочение уравнений, при котором отслеживалось распространение сигналов в цепи.

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

Если в первых программах, использующих методы релаксации, итерации Якоби или Зейделя применялись для решения систем линейных или нелинейных уравнений, то в программе RELAX [51]

идея релаксации была впервые использована непосредственно для решения больших систем обыкновенных дифференциальных уравнений (ОДУ), описывающих МОП БИС. Соответствующий алгоритм получил название релаксации формы сигнала (РФС, Waveform relaxation method, WR). Теоретически было показано, что РФС гарантирует сходимость итераций при анализе цепей на МДП транзисторах, если величина временного шага для каждой подсистемы выбрана достаточно малой, а число итераций РФС достаточно велико. Впоследствии был разработан ряд других программ, использующих метод РФС, прежде всего, RELAX2 [52], SWAN, ESAT, TOGGLE [53].

Суммируя результаты численных экспериментов, характеризующих алгоритмы релаксации, а также соответствующие данные для стандартного схемного моделирования [54], можно построить диаграммы (рис.2.3), отображающие затраты процессорного времени при моделировании цепей различной сложности. Приведенные результаты свидетельствуют о значительном превосходстве релаксационных алгоритмов. Существенно, что методы релаксации могут быть естественным образом реализованы на многопроцессорных системах, поскольку соответствующие алгоритмы обеспечивают структурную декомпозицию математической модели, что дает им дополнительные преимущества по сравнению со стандартными алгоритмами. Многопроцессорный вариант алгоритма РФС реализован в программах DITA, MSPLICE, RELAX2 [17,55].

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

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

и / О V \

уравнении (линеиных и нелинейных), так и для их динамических аналогов (РФС), используемых для решения систем дифференциальных уравнений.

2.2. Методы релаксации на этапе решения систем линейных и нелинейных алгебраических уравнений

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

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

АХ+В=0, АеВ.^, В.ХеЯ1*, С2-1)

имеет единственное решение, т.е. матрица А невырожденная.

Пусть Х° - некоторое начальное приближение к точному решению X*. Использование методов релаксации для решения (2.1) предполагает организацию итераций вида:

0,Х+1 + (А-0)Х1 + В=0, ' (2.2)

где /=0,1,2... - номер итерации, ОеЯМхМ - матрица расщепления [56], определяющая свойства итерационного алгоритма. В математической литературе группа алгоритмов (2.2) получила название обобщенных линейных итерационных методов; она включает метод простых итераций, методы Зейделя, Якоби, последовательной верхней релаксации, симметричной последовательной релаксации и другие [57].

Итерации (2.2) являются состоятельными, т.е. при подстановке решения Х*в (2.2) вместо Х1+1 и X' последнее обращается в тождество. Сходимость итераций зависит от спектральных свойств матриц А ж О,. Из (2.2) следует

хг+1 = -о-*(а - да - От1 в = жх1 - О:1 в, (2.3)

где IV = 1Е - ()-]А - матрица перехода, локализация собственных значений которой определяет сходимость итераций, 1Е - единичная матрица. Если спектральный радиус р(1¥)<\, то итерации (2.2), (2.3) сходятся к решению (2.1) при любом начальном приближении Х° [56].

При выборе б руководствуются следующими соображениями. Вопервых, матрица () должна быть невырожденной, т.е. должна существовать Во-вторых, элементы 0 должны легко выражаться через элементы А, в-третьих, матрица 2 должна быть "легко обратимой" или, что то же самое, прямое решение системы вида ОХ+В-О должно быть значительно проще прямого решения (2.1).

Пусть А = А1+Ав+Аи, где А0 - диагональная или блочно-диагональная матрица, АЕ, А и - соответственно нижняя и верхняя блочно-треугольные матрицы, чьи диагональные элементы (блоки)

равны нулю. Тогда, в частности, для метода простых итераций = 1е (единичная матрица), для метода Якоби (2 = Ар, для метода Зейделя £- АВ+Аь или £= АВ+А

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

Алгоритм 2.1. (Итерационный алгоритм Якоби)._

Повторять

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Дмитриев-Здоров, Владимир Борисович

8.4. Выводы

Рассматривая результаты применения многоуровневых итерационных алгоритмов, приведенные в данной главе, необходимо отметить следующее:

- МИА позволяет не только ускорить сходимость итераций при использовании традиционных способов декомпозиции системы, но и дает возможность применения новых, ранее не использовавшихся подходов, таких как декомпозиция, основанная на разделении ветвей. Расширение области сходимости при увеличении числа уровней Ь обеспечивает равномерную сходимость итераций МРФС при осуществлении декомпозиции "без перекрытия" фрагментов. Как показано в п.8.1.5., достижение равномерной сходимости итераций при использовании многоуровневых алгоритмов обеспечивает сокращение суммарных затрат до 102 и более раз. Данный эффект достигается как за счет уменьшения требуемого числа итераций, так и за счет увеличения шага интегрирования при решении уравнений отдельных подсхем;

- расширение класса допустимых методов структурной декомпозиции делает возможным анализ "смешанных" систем, осуществляемый одновременно несколькими программными пакетами. Анализ рассмотренных в данной главе смешанных систем без использования МРФС реализовать невозможно в связи с отсутствием сходимости итераций базового алгоритма. До сих пор для решения подобных проблем не было иного пути как построение приближенной, а зачастую, грубой схемной модели объекта неэлектрической природы, идентификация параметров такой модели и ее использование в программах схемного моделирования. Очевидно, что устранение всех этих этапов позволяет сэкономить десятки и сотни часов рабочего времени высококвалифицированных специалистов, значительно повысить достоверность получаемых результатов, увеличить число учитываемых в процессе моделирования факторов и сократить суммарное время на проведение анализа таких систем;

- применение многоуровневого обобщения итераций Зейделя позволило в 3-8 раз ускорить анализ ППС в программе приборно-схемотехнического моделирования ИСТОК-2Д. Подобный же подход может быть применен в других пакетах, где решаются системы сеточных уравнений большой размерности;

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

Таким образом, в числе основных практических результатов, связанных с использованием многоуровневых итерационных алгоритмов, следует назвать значительное сокращение требуемых затрат ресурсов ЭВМ при проведении моделирования: до нескольких порядков при анализе динамических систем с большим разбросом характерных времен, а также расширение класса решаемых задач, прежде всего, за счет "смешанных" систем, содержащих объекты неэлектрической природы, для которых схемная модель отсутствует, либо идентификация параметров и ее практическое использование чрезмерно дороги.

9. ЗАКЛЮЧЕНИЕ

Подводя итог, перечислим основные задачи, которые решены в диссертационной работе:

- в главах 3, 4 построено строгое многоуровневое обобщение итерационных алгоритмов, относящихся к классу одношаговых линейных итерационных методов, и соответствующих им релаксационных моделей, исследованы спектральные характеристики матриц перехода и определены достаточные условия сходимости;

- разработана схемная интерпретация построенных многоуровневых алгоритмов и способы построения эквивалентных схем на основе соответствующих схем для традиционных (одноуровневых) алгоритмов (гл.З);

- дано представление разработанных алгоритмов в форме, допускающей их использование для анализа систем, содержащих "черные ящики", то есть фрагменты, внутренняя структура которых неизвестна (гл.З);

- в главах 5, 6 методика построения многоуровневых итерационных алгоритмов обобщена на анализ нелинейных статических и динамических цепей и систем;

- в главе б (Теорема 6.1) сформулированы необходимые условия равномерной сходимости многоуровневых итерационных алгоритмов при анализе электрических цепей и систем во временной области;

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

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

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

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

Как показано в гл.З, 4, применение многоуровневого обобщения позволяет при прочих равных условиях расширить область сходимости итераций, линейные размеры которой на комплексной плоскости растут как 21 , где Ь - число используемых итерационных уровней. Как следует из структуры Алгоритмов 3.4, 3.5, 6.1, предложенное многоуровневое обобщение сохраняет такие положительные свойства релаксационных алгоритмов, как возможность независимой обработки частей или фрагментов анализируемой системы, а также линейный характер роста трудоемкости вычислений на каждой итерации от размерности рассматриваемой системы.

Отмеченные свойства разработанных в диссертации алгоритмов позволяют значительно расширить класс анализируемых цепей и систем. Прежде всего, удается обеспечить сходимость итераций при анализе цепей, характеризующихся наличием обратных связей, где передаточная функция в схеме замещения базового алгоритма отрицательна и достигает по модулю 21. Данное положение основано на теоретическом анализе, проведенном в главах 3, 4, а также на результатах решения многочисленных примеров в гл. 4-8. Кроме того, благодаря использованию многоуровневых итерационных алгоритмов, впервые становится возможным анализ смешанных систем, где для описания явлений различной физической природы одновременно используются модели различных программных средств либо сами исследуемые объекты, анализ которых осуществляется в едином итерационном цикле. Как показано в гл.7,8, это позволяет устранить дорогостоящие процедуры построения схемных моделей объектов неэлектрической природы и идентификации их параметров.

Кроме того, разработанные в диссертации многоуровневые итерационные алгоритмы позволяют значительно сократить число требуемых итераций и соответственно уменьшить суммарное время анализа. Как показано в гл.3,4, при увеличении числа итерационных уровней Ь спектральный радиус матриц перехода итераций уменьшается как р = аЬз{ 1 - а{тт:тах}]/1)> а. скорость сходимости растет как |1пр|«<9(£). При анализе нелинейных динамических систем, как показано в гл.5,6, применение многоуровневого обобщения позволяет добиться равномерной сходимости итераций РФС. В этом случае повышение эффективности алгоритмов достигается как за счет снижения числа требуемых итераций, которое более не зависит от длины интервала анализа, так и за счет снятия ограничений на величину временного шага, налагаемых условиями сходимости итераций. Иными словами, сокращение требуемого числа итераций МИА по порядку величины оказывается равным фактору разброса характерных времен рассматриваемой цепи. Для типичных радиоэлектронных устройств эта величина достигает 103-106 раз. В практических примерах, рассмотренных в гл.5-7, суммарные затраты времени анализа при использовании многоуровневых итерационных алгоритмов сокращаются на 1-2 порядка.

При использовании разработанных алгоритмов для решения сеточных уравнений физико-топологической модели биполярного транзистора в программе ИСТОК-2Д суммарное время анализа сокращается в 3-8 раз, а допустимая размерность модели при реализации программы на ПЭВМ увеличивается более чем вдвое и достигает 6-10 тыс. уравнений.

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

Список литературы диссертационного исследования доктор технических наук Дмитриев-Здоров, Владимир Борисович, 1998 год

ЛИТЕРАТУРА

1. Чуа Л., Лин П.-М. Машинный анализ электронных схем. М.Энергия, 1979. - 640 с.

2. Ильин В.Н., Коган В.Л. Разработка и применение программ автоматизации схемотехнического проектирования.- М.-.Радио и связь, 1984. - 368с.

3. Норенков И.П., Маничев В.Б. Системы автоматизации проектирования электронной и вычислительной аппаратуры.- М.: Высшая школа, 1983.- 272 с.

4. Мурога С. Системное проектирование СБИС /Пер. с англ. под ред. В.М.Кисельникова, М.: Мир, 1985, т.1-2.

5. Архангельский А.Я. Многоуровневое смешанное адаптивное моделирование элементов и узлов электронной аппаратуры: Дис. на соиск. уч. степени д-ра техн. наук. - М.: 1987.

6. Newton A.R. Timing, logic and mixed mode simulation for large MOS integrated circuits.- In Computer design aids for VLSI circuits. P. Antognetti, D.O.Pederson and H.De Man, Eds. Groningen, The Netherlands: Sijithoff and Noordhoff, 1981, pp.175-240.

7. Newton A.R. Techniques for simulation of large scale integrated circuits. - IEEE Trans., 1979, V. CAS -26, p. 741-749.

8. White J., Sangiovanni-Vincentelli A. Relaxation techniques for the simulation of VLSI circuits. Cluwer Academic Publishers, Boston, MA, 1986.-202р.

9. La Scala M., Bose A. Relaxation/Newton methods for concurrent time step solution of differential-algebraic equations in power system dynamic simulations.-IEEE Trans.on CAS, v.40 No 5, 1993, pp.317-330.

10. Моисеев H.H. Математические задачи системного анализа.-М.: Наука, 1981.- 488 с.

11. Расчет электрических цепей и электродинамических полей на ЭВМ / М.Г. Александрова, А.Н. Белякин, В. Брюкнер и др.; Под ред. Л.В.Данилова, B.C. Филипова. -М.: Радио и связь, 1983. - 344с.

12. Баталов Б.В., Егоров Б.Б., Русаков С.Г. Основы математического моделирования больших интегральных схем на ЭВМ. - М.: Радио и связь, 1982. - 168 с.

13. Крон Г. Исследование сложных систем по частям -диакоптика. М.: Наука, 1972.- 544с.

14. Newton A.R., Sangiovanni-Vincentelli A.L. Relaxation-Based Electrical Simulation.-IEEE Trans, on Electron Devices, 1983, v. ED-30, N 9, pp. 1184-1207.

15. Lelarasmee E., Ruehli A.E., Sangiovanni-Vincentelli A. The waveform relaxation method for time-domain analysis of large scale integrated circuit.-IEEE Trans.,v.CAD-1.-1982.-N 3. pp. 131-145.

16. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем/ Пер. с англ. под ред. X.Д.Икрамова, М.: Мир, 1991.- 367 с.

17. White J., Sangiovanni-Vincentelli A. Partitioning Algorithms and parallel implementations of waveform relaxation algorithms for circuit simulation, Proc.Int.Symp.on Circuits and Systems, Kyoto, Japan, June 1985.

18. Miranker W. A survey of parallelism in numerical analysis. -SIAM Review, No. 13,1971, pp.524-547.

19. Saleh R., Newton A.R. An event-driven relaxation-based multirate integration scheme for circuit simulation.-Proc.Int.Symp. on Circuits and Systems, Phil.Pennsilvania, May 1987, pp.600-603.

20. Desai M., Hajj I. On the convergence of block relaxation methods for circuit simulation.- IEEE Trans., v.CAS-36, No.7, July 89, pp.948-958.

21. Sangiovanni-Vincentelli A., Chen L.K., Chua L.O. An efficient heuristic cluster algorithm for tearing large-scale networks. - IEEE Trans., v.CAS-24, No.12, Dec.1977, pp.709-717.

22. Saviz P., Wing O. Circuit simulation by hierarchical waveform relaxation.- IEEE Trans., v.CAD-12, 1993, No.6, June 1993, pp.845-860.

23. John W., Rissek W., Paap K.L. Circuit partitioning for waveform relaxation.- In Proc. of Europ. Design Autom., 1990, pp.936942.

24. Petersen L., Mattisson S. Partitioning trade-offs for waveform relaxation in transient analysis circuit simulation.- In Distributed Сотр.Mem. Conf., 1990, pp.612-621.

25. Ракитский Ю.В., Устинов С.И., Черноруцкий И.Г. Численные методы решения жестких систем.- М.: Наука, 1979.- 208 с.

26. Тихонов А.Н. Системы дифференциальных уравнений, содержащие малый параметр при производных.- Матем.сб., 1952, т.31(73), N3, с.575-586.

27. Норенков И.П., Маничев В.Б., Жук Д.М. Математическое обеспечение задач получения и использования макромоде лей.-Изв.вузов. Сер. Радиоэлектроника, 1976, т.19, N6, с.118.

28. Бахов В.А. Макромодёлирование цифровых и импульсных схем при помощи макроэлементов. Изв.вузов. Сер.Радиоэлектроника, 1980, т.23, N 6, с.13-20.

29. Алексенко А.Г., Зуев Б.И., Ламекин В.Ф., Романов И.А. Макромоделирование аналоговых интегральных микросхем.-М.:Радио и связь, 1983.- 248 с.

30. Burns J.L., Newton A.R., Pederson D.O. Active device table look-up models for circuit simulation. Proc. 1983 Int. Symp. on Circuits and Systems, May 1983.

31. Chawla B.R., Gummel H.K., Kozak P. MOTIS - an MOS timing simulator.- IEEE Trans. v.CAS-22, Dec. 1975, pp. 901-909.

32. Yang P., Hajj I.N., Trick T.N. SLATE: a circuit simulation program with latency exploitation and node tearing. Proc. IEEE Int. Conf. Circuits Comput., Oct. 1980.

33. Rabbat N.B., Hsieh H.Y. A latent approach to large scale sparse networks.-IEEE Trans., v.CAS-23,1976, No 12, p.745-752.

34. Хэчтел Г.Д., Санджованни-Винчентелли А. Обзор методов моделирования третьего поколения. - ТИИЭР, 1981, т.69, N 6, с.100 -110.

35. Ruehli А.Е. Survey of analysis, simulation and modeling for large-scale logic curcuits.- Int. Proc. 18-th Design Autom. Conf., 1981, pp.124-129.

36. Фролкин В.Т., Тихомирова Е.М., Мошняга В.Г. Моделирование электронных схем с высокой степенью интеграции компонентов (состояние и перспективы).- Изв. вузов СССР. Сер. Радиоэлектроника., 1984, т.27, N 6.- с. 17-31.

37. Vladimiresku A., Pederson D. Perfomance limits of the CLASSIE circuit simulation program.-Proc. Int. Symp. on Circuits and Systems, May 1982.

38. Дмитриев-Здоров В.Б., Попов В.П. Адаптивный алгоритм анализа линейных цепей во временной области .- Изв. вузов СССР. Сер. Радиоэлектроника., 1983, т.26, N 6.- с.5-8.

39. Дмитриев-Здоров В. Б. Алгоритм анализа электрических цепей с помощью адаптируемых моделей.- Изв. вузов СССР. Сер. Радиоэлектроника., 1984, т.27, N 6.- с.42-46.

40. Дмитриев-Здоров В.Б. Алгоритм анализа электрических цепей, содержащих магнитно-связанные индуктивности .- Изв. вузов СССР. Сер. Радиоэлектроника., 1984, т.27, N 8.- с.90-92.

41. Дмитриев-Здоров В.Б. Асимптотический метод анализа цепей, обладающих большим разбросом постоянных времени.- В сб.: Автоматизация проектирования электронной аппаратуры.- Таганрог, ТРТИ, 1984, Вып.З, с.64-68.

42. Дмитриев-Здоров В.Б. Адаптивный анализ электрических цепей, содержащих распределенные RC-структуры,- Изв. вузов СССР. Сер. Радиоэлектроника., 1985, т.28, N 6,- с.73-77.

43. Дмитриев-Здоров В.Б., Туманов B.C. Пакет программ анализа цепей МАКРО,- Изв. вузов СССР. Сер. Радиоэлектроника., 1985, т.28, N 11.- с. 102-104.

44. Дмитриев-Здоров В.Б., Пономарев A.M., Попов В.П. Применение перестраиваемых моделей для анализа электрических цепей во временной области.- В кн. Автоматизация проектирования в электронике: Киев, Техника., Вып.32, 1985, с.37-42.

45. Попов В.П., Дмитриев-Здоров В.Б. Адаптируемые модели для автоматизированного анализа электрических цепей (обзор).- Изв. вузов СССР. Сер. Радиоэлектроника., 1986, т.29, N 6.- с.32-38.

46. Дмитриев-Здоров В.Б., Туманов B.C. Алгоритм расчета динамических характеристик цифровых схем с использованием явных методов интегрирования. - В кн. Автоматизация проектирования в электронике: Киев, Техника, Вып.34, 1986, с.44-47.

47. Дмитриев-Здоров В.Б. Перестраиваемые модели для подсистем САПР РЭА.- Мат-лы респ. школы-семинара "Методы автоматизированного проектирования электронно-вычислительной аппаратуры и СБИС", Винница, 1988, с.23.

48. Попов В.П., Дмитриев-Здоров В.Б. Возможности реализации асимптотических адаптивных моделей в программах автоматизированного анализа цепей.- В сб. "Матем. и машинное моделирование в микроэлектронике,- Вильнюс, ИФП АН Лит.ССР, 1988, с.29-32.

49. Fan S., Hsueh М., Newton A., Pederson D. MOTIS-C . A new circuit simulator for MOS LSI circuits. - In Proc. IEEE Int. Symp. Circuits Syst., Apr. 1977.

50. Newton A. The simulation of large-scale integrated circuits. -IEEE Trans. Circuits Syst., vol.CAS-26, Sept.1979, pp.741-749.

51. Lelarasmee E., Sangiovanni-Vincentelli A. RELAX: a new circuit simulator for large scale MOS integrated circuits.- In Proc. 1982 Design Automation Conf., June 1982.

52. White J., Sangiovanni-Vincentelli A. RELAX2: a new waveform relaxation approach for the analysis of LSI MOS circuits.- In Proc. 1982 IEEE Int. Large-Scale Syst. Symp., Oct.1982, pp.371-376.

53. Defebve P., Beetem J., Donath W., Hsieh H., Odeh F., Ruehli A., Wolff P., White J. A large scale MOSFET circuit analyser based on waveform relaxation. Proc. Int. Conf.on Computer Design, Rye, New York, October 1984.

54. Ruehli A. Circuit analysis, simulation and design. - Part 2, North-Holland.-1987. - 393 p.

55. White J., Saleh R., Sangiovanni-Vincentelli A., Newton A. Accelerating relaxation algorithms for circuit simulation using waveform Newton, iterative stepsize refinement and parallel techniques.-Proc.Int.Conf. on Computer aided design, Santa Clara, California, October 1985.

56. Хейгеман Л., Янг Д. Прикладные итерационные методы / Пер. с англ. - М.: Мир, 1986. - 448 с.

57. Ортега Д., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными /Пер. с англ.-М.: Мир, 1975. - 344 с.

58. Бахвалов Н.С., Жидков И.П., Кобельков Г.М. Численные методы. - М.: Наука, 1987. - 600 с.

59. Kleckner J., Saleh R., Newton A. Electrical consistency in schematic simulation. - Proc. IEEE Int. Conf. Circuits Comput., Oct. 1982, pp.30-34.

60. Burch R., Yang P., Cox P., Mayaram K. A new matrix solution technique for general circuit simulation. - IEEE Trans, on Сотр. aided design of int. circ. and syst., v.CAD of ICAS-12, 1993, No.2, pp.225-241.

61. Дмитриев-Здоров В.Б., Дудка В.Б., Попов В.П. Каноническая схемная модель линейной электрической цепи,- Изв. вузов СССР. Сер. Радиоэлектроника., 1989, т.32, N 6.- с.42-47.

62. Дмитриев-Здоров В.Б., Дудка В.Б. Алгоритм редукции математической модели цепи на основе асимптотических преобразований,- Мат-лы респ. совещания "Числ. методы и средства

проектирования и испытания эл-тов твердотельной электроники", т.2, Таллин, 1989, с.19-22.

63. Попов В.П., Дмитриев-Здоров В.Б., Дудка В.Б. Построение семейства макромоделей на основе преобразования матриц к канонической форме.- В кн. Автоматизация проектирования в электронике: Киев, Техника, Вып.40, 1989, с.45-50.

64. Попов В.П., Дмитриев-Здоров В.Б., Дудка В.Б. Канонические модели линейных цепей с простыми (некратными) собственными частотами. - В кн. Автоматизация проектирования в электронике: Киев, Техника, Вып.41, 1990, с. 124-130.

65. Дмитриев-Здоров В.Б., Дудка В.Б. Алгоритм анализа электрических цепей с помощью метода искусственной инерционности. Мат-лы I Всесоюзной конференции по теоретической электротехнике, Ташкент, 1987, т.З, с.134-135.

66. Дмитриев-Здоров В.Б., Мережин Н.И. Аналого-цифровое моделирование динамических характеристик ИС,- Изв. СКНЦ ВШ. Сер. Технические науки, 1987, N 2, с. 123-125.

67. Дмитриев-Здоров В.Б., Дудка В.Б. Анализ электрических цепей с помощью адаптивных моделей и метода искусственной инерционности. Мат-лы респ. совещания "Числ. методы и средства проектирования и испытания эл-тов РЭА", т.2, Таллин, 1987, с.72-74.

68. Дмитриев-Здоров В.Б., Дудка В.Б. Алгоритм решения системы нелинейных алгебраических уравнений с помощью адаптивных моделей. - Изв. вузов СССР. Сер. Радиоэлектроника., 1988, т.31, N 6,- с.43-48.

69. Дмитриев-Здоров В.Б. Итерационный алгоритм анализа

о гп

цепей на основе явных разностных схем.- 1ехнич. электродинамика, 1988, N6, с.91-93.

70. Brandt A. Multilevel adaptive solution to boundary value problems.- Math. Сотр., 31,. Apr. 1977, pp.333-391.

71. McCormic S. Multigrid methods for industrial and applied mathematics.- Univ.Press, Belfast, 1987.

72. Joppich W., Mijalkovic S. Multigrid methods for process simulation.- Сотр. Microelectronics, Springer-Verlag, Wien, NY, 1993.

73. Vanderwalle S., Piessens R. Numerical experiments with nonlinear multigrid waveform relaxation on a parallel processor. Appl. Numer. Math., 1991, pp. 149-161.

74. Miekkala U., Nevenlinna O. Convergence of dynamic iteration methods for initial value problems.- Institute of Math., Helsinki Univ. of Technology, SF-02150, 1985.

75. Дмитриев-Здоров В.Б. Итерационный алгоритм решения СНАУ на основе метода искусственной инерционности .- Изв. вузов СССР. Сер. Радиоэлектроника., 1990, т.ЗЗ, N 6,- с.28-33.

76. Дмитриев-Здоров В. Б. Многоуровневый итерационный алгоритм с демпфированием • на основе метода искусственной инерционности.- Изв. вузов СССР. Сер. Радиоэлектроника., 1990, т.ЗЗ, N 11.- с.55-61.

77. Дмитриев-Здоров В.Б. Многоуровневые итерационные алгоритмы: расширение области сходимости при анализе электрических цепей на основе структурной декомпозиции.- Изв. высш. учебн. зав. Сер. Радиоэлектроника., 1991, т.34, N 6.- с.22-28.

78. Fletcher R., Powell M.J.D. A rapidly convergent descent method for minimization. - Computer J., 1963, No.6, pp.163-168.

79. IBM System/360 scientific subroutine package (SSP) 360A-CM03X, Version 3, 6-th ed., March 1970.

80. Самарский А.А. Введение в теорию разностных схем.- М.: Наука, 1971,- 552 с.

81. Парлетт Б. Симметричная проблема собственных значений. Численные методы.- М.: Мир, 1983.- 384 с.

82. Гантмахер Ф.Р. Теория матриц.- М.: Наука, 1988.- 549 с.

83. Хорн Р., Джонсон Ч. Матричный анализ/ Пер. с англ.- М.: Мир, 1989,- 655 с.

84. Nagel L.M. SPICE2: A computer program to simulate semiconductor circuits, Rep. No. ERL-M520, Univ. of Calif., Berkeley, 1975.

85. Johnson В., Quarles T. SPICE3 version 3e2 user's manual.Dep. of El. Eng. and Сотр. Sc., Univ. of Calif., Berkeley, 1992.

86. Дмитриев-Здоров В.Б. Многоуровневые итерационные алгоритмы для решения уравнений динамики электрических цепей: многоуровневое обобщение метода релаксации формы сигнала .- Изв. высш. учебн. завед. Сер. Радиоэлектроника., 1992, т.35, N 6.- с.37-46.

87. Дмитриев-Здоров В.Б. Многоуровневое обобщение метода релаксации формы сигнала для анализа электрических цепей.- Мат-лы 38-й НТ и НМК ТРТИ, Таганрог, ТРТИ, 1992, с.48-50.

88. Дмитриев-Здоров В.Б. Многоуровневое обобщение методов релаксации для автоматизированного анализа электрических цепей. Мат-лы междунар. конф. "САПР-93: Новые информационные технологии в науке, образовании и бизнесе,- Гурзуф, 1993, с.84.

89. Dmitriev-Zdorov V.B. Multilevel waveform relaxation algorithms for circuit simulation.- Proc. 3-rd Int. Design Autom. Workshop, Moscow, 1993.-pp.161-170.

90. Денисенко В.В., Дмитриев-Здоров В.Б., Мережин Н.И. Спецпроцессор для анализа нелинейных электрических цепей.- Мат-лы междунар. семинара "Нелинейные цепи и системы", т.1, М., 1992, с.213-221.

91. Dmitriev-Zdorov V.B. Multilevel generalization of relaxation algorithms for circuit simulation.- Proc. of European Design Autom. Conf., EURO-DAC'94, Grenoble, France, 1994, pp.176-181.

92. Дмитриев-Здоров В.Б. Расширение класса методов структурной декомпозиции цепи при использовании многоуровневых итерационных алгоритмов.- Изв. высш. учебн. зав. Сер. Радиоэлектроника., 1994, т.37, N 1.- с.54-63.

93. Дмитриев-Здоров В.Б., Денисенко В.В. Организация процесса моделирования БИС в рабочей станции с параллельной архитектурой. Мат-лы междунар. конференции и школы молодых ученых "САПР-92. Новые инфом. технологии в науке, образовании и бизнесе".- Воронеж, 1992, с. 173-174.

94. Jun Y.-H., Lee C.-W., Lee K.-J., Park S.-B. Timing simulator by waveform relaxation considering feedback effect. -IEEE Int. Symp. on Circuits and Systems, 1987, v.2, pp.608-611.

95. Dmitriev-Zdorov V.B., Klaassen B. An improved relaxation approach for mixed system analysis with several simulation tools. Proc. of European Design Autom. Conf., EURO-DAC'95, Brighton, UK, 1995, pp.274-279.

96. Kaporin I.E. Explicitly preconditioned conjugate gradient method for the solution of unsymmetric linear systems.- Int. Jour. Computer Math., 1992, v.40,- pp. 169-187.

97. Saad Y., Schultz M.N. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. - SI AM Jour. Sci. Stat. Comput., 1986, No. 7, pp.856-869.

98. Lumsdaine A., Silviera L.M., White J.K. Massively parallel simulation algorithms for grid-based analog signal processing.- IEEE

Trans, on CAD of Int. Circ ans Syst., Vol.CAD-12, No.ll, 1993, pp. 1665-1678.

99. Burch R.,. Yang P, Cox P., Mayaram K. A new matrix solution technique for general circuit simulation.- IEEE Trans, on Сотр. Aided Design of Int. Circ. and Syst., Vol.CAD-12, 1993, No.2, pp.225241.

100. Dmitriev-Zdorov V., Klaassen В., Paap K.-L. Analogue system simulation including hardware-in-the-loop. - Proc. of First Electronic Circuits and Systems Conference (ECS'97), Bratislava, Slovakia, 1997, pp.31-34.

101. Dmitriev-Zdorov V., Klaassen В., Paap K.-L. Improvement of stability in cosimulation of tightly-coupled systems. - Proc. of 9-th European Simulation Symposium (ESS'97), Oct. 19-23, 1997, Passau, Germany, pp.639-643.

102. Влах И., Сингхал К. Машинные методы анализа и проектирования электронных схем. - М., Радио и связь, 1988.-560 с.

103. Sun J., Grotstollen Н. Fast time-domain simulation by waveform relaxation methods. - IEEE Trans, on Circuits and Systems-I, v.44, No.8, 1997, pp.660-666.

104. Klaassen B. A method for tightly coupled thermal-electrical simulation.- Microelectronics Journal, v.28, No.3, 1997, pp.239-245.

105. Dmitriev-Zdorov V. Generalized coupling as a way to improve the convergence in relaxation-based solvers. - Proc. of European Design Autom. Conf., EURO-DAC'96, Geneva, Switzerland, 1996, pp.15-20.

106. Dmitriev-Zdorov V.B. Multilevel generalization of relaxation techniques: a new way to improve the convergence in relaxation-based circuit simulators. - Proc. of Intern. Symposium on Nonlinear Theory and its Applications (NOLTA'93), IEICE, Tokyo, 1993, pp.655-658.

107. Dmitriev-Zdorov V. Multicycle generalization of relaxation-based algorithms for circuit and system simulation. - GMD -Forschungszentrum Informationstechnik GmbH. - Munchen, Wien: Oldenbourg, 1997. - 164 p.

108. Тихонов A.H., Самарский А.А. Уравнения математической физики.- M.: Наука, 1977,- 736 с.

109. Самарский А. А., Николаев Е.С. Методы решения сеточных уравнений.- М.: Наука, 1978.- 592 с.

110. Филатов H.И., Накропин Б.О., Яковлев Д.Г. Система смешанного приборно - схемотехнического моделирования двумерных полупроводниковых структур для персональных ЭВМ.-Микроэлектроника, т.21, вып.6, 1992, с.75-85.

111. Philatov N.I., Yakovlev D.G., Nakropin В.О. A system of mixed device- circuit modeling for personal computers.- Solid State Electronics, v.36, No 3, 1993, pp.463-473.

112. Мнацаканов Т.Т., Ростовцев И.Л., Филатов Н.И. О соотношении Эйнштейна в полупроводниках в условиях сильного электроннодырочного рассеяния.- Физика и техника полупроводников.- 1984.- 18, N7,- с. 1293-1296.

ИЗ. Бубенников А.Н. Моделирование интегральных микротехнологий приборов и схем.- М.: Высшая школа, 1989.- 320 с.

114. Engl W.L., Laur R., Dirks H.K. MEDUSA - a simulator for modular circuits.- IEEE Trans, on CAD of ICAS, 1985, v.CAD-4, pp.177-185.