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



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

ДМИТРИЕВ-ЗДОРОВ Владимир Борисович

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

Специальности: 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях 05.09.05 - Теоретическая электротехника

Автореферат диссертации на соискание ученой степени доктора технических наук

Таганрог - 1998

Работа выполнена в Таганрогском Государственном Радиотехническом

университете

Научный консультант: доктор технических наук, профессор В.П.Попов

Официальные оппоненты:

1. Доктор технических наук, профессор Архангельский А .Я.

2. Доктор технических наук, профессор Волков Е.А.

3. Доктор физико-математических наук, профессор Сухинов А. И.

Ведущая организация:

Российский НИИ космического приборостроения

Зашита состоится 1998 г. на заседании диссертационного

совета Д063.13.02 по присуждению ученых степеней в Таганрогском Радиотехническом университете по адресу 347928 Таганрог, ГСП-17А, пер. Некрасовский 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан "_"_1998 г.

Ученый секретарь диссертационного совета, кандидат технических на;

доцент

А.Н.Целых

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

АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. Необходимость дальнейшего развития методов анализа сложных систем вызвана резким усложнением создаваемых технических устройств, конструкций, технологий, а также потребностью изучения биологических >бъектов и проблем экологии. Среди наиболее сложных технических устройств следует <азвать устройства радиоэлектроники и вычислительной техники, создаваемые с томощью микроэлектронной технологии, а также электроэнергетические системы.

Увеличение степени интеграции до ЮМО6 транзисторов на кристалле выдвигает гачественно новые требования к алгоритмам и программным средствам, (спользуемым для синтеза и верификации проектных вариантов БИС. В настоящее 1ремя для моделирования процессов в БИС с целью их верификации используются «сколько различных по характеру процедур. При классификации обычно выделяют ]рограммы алгоритмического или функционального моделирования, моделирования ¡а уровне регистров, временного, схемного, а также компонентного моделирования. В юследнее десятилетие как у нас в стране, так и за рубежом был разработан ряд [рограмм смешанного моделирования, сочетающих в себе возможности нескольких [азванных процедур.

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

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

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

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

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

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

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

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ состоит в разработке нового класса релаксационных алгоритмов, являющегося строгим обобщением известных декомпозиционных методов анализа цепей и систем, позволяющего при прочих равных условиях расширить область сходимости последних и сохраняющего такие их положительные свойства, как возможность независимой обработки фрагментов системы и квазилинейный характер роста трудоемкости анализа при увеличении размерности системы. Как следствие, разработанные в диссертации алгоритмы обеспечивают расширение класса анализируемых цепей и систем, а также снижение требуемых затрат ресурсов ЭВМ на проведение их анализа.

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

Для достижения поставленной цели в работе решены следующие задачи:

• разработан способ построения многоуровневого обобщения алгоритмов, относящихся к классу одношаговых линейных итерационных методов и применимых к анализу цепей и систем, содержащих "закрытые" блоки, математическое описание которых не задано;

• исследованы спектральные характеристики итерационных матриц и области сходимости для синтезированных алгоритмов и определены достаточные условия сходимости последних;

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

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

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

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

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

НОВЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ:

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

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

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

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

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

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

НА ЗАЩИТУ ВЫНОСЯТСЯ:

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

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

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

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

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ.

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

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

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

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

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Теоретические и практические результаты диссертационной работы вошли как составная часть в Госбюджетные НИР N3.22.008 "Методы моделирования и автоматизированного анализа радиоэлектронных цепей" и N 11151 "Разработать и исследовать адаптивные модели сложных электронных цепей и пространственно-временных сигналов с целью повышения точности и быстродействия работы САПР радиоэлектронных устройств и эффективности радиотехнических систем", хоздоговорные НИР NN Ш118, 111125, ПП31, в контракт 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. Список 29 основных работ по теме диссертации приведен в конце автореферата.

СТРУКТУРА И ОБЪЕМ РАБОТЫ.

Диссертация состоит из восьми глав и заключения, изложенных на 277 страницах машинописного текста, иллюстрированного рисунками на 53 страницах, списка литературы, включающего 114 наименований.

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

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

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

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

. Можно выделить два основных фактора, определяющих неэффективность традиционного подхода при анализе сложных цепей. Первый состоит в том, что трудоемкость решения систем линейных уравнений (СЛАУ) прямыми методами растет быстрее чем линейно при увеличении размерности цепи. Согласно эмпирическим оценкам, трудоемкость решения уравнений с учетом разреженности матриц характеризуется зависимостью 0(^1, где N - число уравнений системы, I .!<.?< 1.5. Затраты на решение СЛАУ в задачах схемного моделирования начинают преобладать, когда число уравнений достигает нескольких сотен - единиц тысяч, что значительно ниже уровня сложности современных ИС. Кроме того, для сложных цепей характерен значительный разброс постоянных времени, при котором фазовые переменные системы изменяются с весьма различными скоростями. Непосредственное применение методов интегрирования "навязывает" каждому уравнению системы один и тот же шаг дискретизации, который определяется наиболее быстроизменяющимися переменными. Вместе с тем, для каждого уравнения или группы уравнений системы желательно выбирать наибольшую величину шага, при которой поведение соответствующих переменных отображается с достаточной точностью. Это обстоятельство особенно важно при анализе сложных цифровых схем, где большинство переменных в каждый момент времени являются неактивными или латентными, то есть не изменяют своих значений.

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

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

АХ+В = 0, (1)

описывающая некоторую модель цепи (рис.1), имеет единственное решение, т.е. матрица А невырожденная. Пусть Хд - некоторое начальное приближение к точному решению X*. Использование методов релаксации для решения (I) предполагает организацию итераций вида

(>Х1+1 + (А-а)Х' + В = 0, (2)

где ¿=0.1,2... - номер итерации, беЯ'1'*^ - матрица расщепления, определяющая свойства итерационного алгоритма. Итерации (2) являются состоятельными, т.е. при подстановке решения X* в (2) последнее обращается в тождество. Для выбранной матрицы расщепления существует взаимно однозначное соответствие между выражением (2) и некоторой релаксационной моделью (рис.2), получаемой из исходной после ее декомпозиции и упорядочения фрагментов. Если независимые переменные исходной модели удовлетворяют системе (1) с матрицей коэффициентов А, то независимые (нерелаксированные) переменные релаксационной модели удовлетворяют системе (2) с матрицей коэффициентов

Итерационный процесс, описываемый выражением (2), в дальнейшем будем называть базовым итерационньш алгоритмом (БИА).

Сходимость БИА зависит от спектральных свойств итерационной матрицы (матрицы перехода) УУ=1е-(У1Л. Если спектральный радиус р(И/)<1, то итерации (2)

Рис.1. Исходная модель (пример)

Рис.2. Релаксационная модель (один из вариантов)

Рис.3. Соответствующая многоуровневая релаксационная модель

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

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

Решение системы нелинейных алгебраических уравнений

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

С(ДГ) = 0, (3)

где ХеЯ^ - искомый вектор узловых напряжений, (?- функция из в

Тогда, в частности, нелинейный вариант алгоритма Зейделя принимает вид:

¿=0;

Повторять { для_всех

{решать ,XJ■^+l,xj+¡1,.. относительно х^+1}

¡=1+1\ }

пока (ЦА^-А^е)_

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

Анализ динамических систем методом релаксации формы сигнала (РФС)

Методы релаксации используются и для непосредственного решения систем ОДУ в форме

С(Х,и)с1Ш1 + Р(Х,и)= О, Х(0)=Х0, (4)

где ХеЯ,у - вектор узловых напряжений, и(1)еК^ - вектор входных воздействий, С ■ симметричная диагонально доминирующая матричная функция из Я^хЯ^ в ЯЛ'хЛ причем есть суммарная "плавающая" или незаземленная емкость, включенная

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

В принятых обозначениях динамический аналог алгоритма Зейделя может быть представлен в виде:

i=0;

Повторять {

' для_всех (j=l...N) {

решать ^Cjk(x/+l,...Xj.]i+J.x/+{xj+¡i....xNi,u)dxik+i/dt +

/г-l

+ f,C;k(x¡i^....x).¡'+l.xJ^l.xJ+¡',...xN'.u)dx'k/dt +

k-j* I

относительно xj*'(t), /е[0,7] с начальным условием xf(0)=xp. i=i+l\ }

пока max/<,</vmaxtg^ x\\Xi+J(i) -Xl(t)\ >s_

Известна теорема, согласно которой приведенный алгоритм (а также модификация метода РФС, базирующаяся на итерационной схеме Якоби) сходится, если матрица С(Х,и) в (4) является диагонально преобладающей и ограниченной по Липшицу по отношению к переменным X,и.

Общая характеристика релаксационных алгоритмов

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

Применение методов релаксации на этапе решения систем алгебраических уравнений (например, в программах MOTIS, MOTIS-C, SPLICE) позволило на 1-2 порядка сократить трудоемкость расчетов по сравнению с традиционными алгоритмами за счет того, что появилась возможность независимо вычислять элементы (подвекторы) искомого вектора X при выполнении итераций на каждом временном шаге. Еще более перспективным оказалось использование динамического аналога релаксационных методов, где элементы (подвекторы) искомой векторной функции X(t) определялись независимо друг от друга на некотором временном интервале (программы RELAX, RELAX2, ESAT, SWAN, TOGGLE). В последнем случае становится возможным независимый выбор временного шага при решении соответствующих подсистем уравнений.

Существенно, что методы релаксации могут быть естественным образом реализованы на многопроцессорных системах, поскольку соответствующие алгоритмы обеспечивают структурную декомпозицию математической модели. Многопроцессорный вариант алгоритма РФС реализован в программах DITA, MSPLICE, RELAX2.

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

Специфической особенностью поведения итераций РФС является то, что сходимость последовательности {X(t)\ к точному решению, как правило, неравномерна, и наблюдается лишь в узком временном интервале (интервале притяжения). Таким образом, общее число итераций, необходимое для получения

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

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

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

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

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

• Величина временного шага ограничена сверху шириной "временного окна". Это ограничение имеет место и в том случае, когда состояние цепи или системы на рассматриваемом интервале времени является квазистационарным. Таким образом, РФС не позволяет использовать временную латентность в системе.

Выводы

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

• медленная сходимость итераций;

• ограниченность класса цепей, для которых сходимость итераций имеет место;

• сложность алгоритмов разбиения системы на части и упорядочения полученных фрагментов с целью оптимизации скорости сходимости;

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

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

• уменьшения затрат на их реализацию путем исключения избыточных вычислений при использовании алгоритмов с "временными окнами";

• ускорение анализа путем распараллеливания вычислений во времени и в пространстве, их реализация на многопроцессорных системах;

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

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

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

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

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

Многоуровневый итерационный алгоритм

Рассматривая БИА (2), можно прийти к качественному заключению, что проблемы сходимости итерационного процесса вызваны различием спектральных свойств матриц и А, то есть, различием между исходной (рис.1) и релаксационной (рис.2) моделями. Поскольку структура А и £) предполагается фиксированной, мы не можем непосредственно уменьшить Вместо этого мы попытаемся построить

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

Предположим, что в (2) <2 формально заменена на Н/=д^+Г]А, где д/, г/ -некоторые неотрицательные коэффициенты. Если равен 2, то итерации

Н]Х1+' + (А - Н1)Х< ■+ 5 = 0 (5)

имеют такую же скорость сходимости, как (2). Если Н[ приближается к А, то скорость сходимости (5) увеличивается и становится бесконечной, когда Н[=А. В этом случае (5) совпадает с (1) и решение X* определяется за один шаг. С другой стороны, возникает необходимость решения (5) относительно X, что по трудоемкости равносильно решению исходной системы (1).

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

радиус матрицы перехода итераций (5) оказывается меньше, чем для БИА (2). Однако, если г;>0, то Н[ уже не является, подобно (?, "легко обратимой" матрицей. Таким образом, для каждого известного X1 требуется решать (5) относительно А"'4''. В действительности мы можем рассматривать (5) как новую систему уравнений с матрицей Н], неизвестным вектором Х'+1 и известным (А-Н¡) Х'+В. Для ее решения введем внутренний итерационный цикл с матрицей расщепления •

Аналогичным образом, мы можем ввести несколько внутренних итерационных циклов и представить процесс решения (1) в виде ¿>1 вложенных друг в друга итерационных циклов или уровней. Если Нт является матрицей расщепления для итераций уровня т<Ь, она также является "матрицей системы" для более внутреннего уровня т+1. Это означает, что матрица перехода \Ут для итерационного уровня т есть:

Пт=1Е - (матрица расщепления уровня лг)'/(магрица системы уровня т}= =1Е - IIт'II,„.,=!Е - (<7„,/£+г„Л-/(<?)„.у/£+г,п.,Р), т-1...Ь, где Р^Ог'А. (6)

Естественно, что Нд=А как матрица системы уровня 1 (внешнего), и //¿=2 как матрица расщепления уровня Ь (внутреннего), то есть (?о=0, г0=1, ^¿=1, '•¿=0.

Не умаяяя общности, можно предположить, что собственные значения Р локализованы внутри окружности с центром на действительной оси, проходящей через точки (ат1п, 0), (атах, 0), атах>ат^. Если коэффициенты дт, гт определять из уравнений

гшп «т+'т« тах О)

удается выровнять верхние (и нижние) спектральные границы для всех Цгт. В результате

р^^ахШ-а,™'^, 11-ап,«^}. (8)

Как следует из (6), спектральный радиус в (8) есть мера различия между релаксационными моделями уровней т и т-1. Области сходимости БИА (1=1) и МИА (£>1), полученные из (8) и условия р(И/т)<1, показаны на рис.4. Многоуровневый итерационный алгоритм с демпфированием Многоуровневый итерационный алгоритм с демпфированием или оптимальной экстраполяцией (МИАД) может быть получен из МИА путем выравнивания модулей собственных значений итерационной матрицы по границам области локализации спектра матрицы Я для каждого из итерационных уровней. Если коэффициенты дт, гт определять из уравнений qm+rma где ^=2/(ат1П^+атах-'^),то р(1^)<(аП1ах^-аП1т^У(атах^+атш^). (9)

Приведенная оценка является обобщением известной оценки спектрального радиуса матрицы перехода экстраполированного БИА. Последняя получается из (9) при ¿=1. Из (9) следует, что с ростом! спектральный радиус итерационных матриц быстро уменьшается, соответственно увеличивается асимптотическая скорость сходимости.

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

Пусть Л"^ обозначает оценку вектора X, полученную на итерации уровня т с

номером ¡т. Пусть также 'т=<^т+гт, то есть где В этих

обозначениях МИА и МИАД могут быть представлены в канонической форме, являющейся обобщением (2):

-+ [('о-'/)(2+ (го-г^Х^ +1оВ = 0. (10) Итерационные схемы замещения МИА

Показано что итерационные схемы замещения для ¿-уровневого процесса можно получить из соответствующих схем для БИА (¿=1). Для этого достаточно формально заменить каждый источник напряжения (тока), управляемый релаксированной переменной х', совокупностью I последовательно (параллельно) соединенных источников напряжения (тока) с управляющими параметрами кгт~

гт-1 " гт)х'Сту гп=\...Ь. Отсюда следует состоятельность многоуровневых моделей

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

Используя каноническое представление МИА (МИАД) в виде итерационной формулы (10), а также схемы замещения МИА, процесс вычислений можно описать в виде следующего алгоритма:

Рис.4. Области сходимости БИА (¿=1) и МИА при ¿=2,3...

Рис.5. Области сходимости несмещенного МИА при /¡,...«¿=2

Полагаем ij = = ...iL = 0; X'(lL)~Xq (начальное приближение);

LABi : определяем компоненты X'^1 из (10) или схемы замещения; = +• 1;

если (УВ(Ь)=.false.) переход к LABZ ; 1АВД.;: Х)\у iL., = 1Ы + 1; iL = 0;

если (yS(L-i)- false.) переход к LAB^ ;

ЬАВ;: Л^у, - ¡! + 1; = = ... ¡2 =0;

если (УB(l)=.false.) переход к ЬАВд ;

Ь.УВд: вывод результатов_

Здесь УВ(т) обозначает условие выхода из итерационного цикла уровня т.

В приведенном алгоритме вычисления выполняются на внутреннем итерационном цикле (ЬАВ£), а на остальных - лишь операции с индексами и запись в память векторных переменных.

Выводы

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

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

Область сходимости построенных многоуровневых итерационных алгоритмов на плоскости собственных значений матрицы Р=(У!А представляет собой диск с центром в точке (20) и радиусом 21-'1, что значительно шире, чем область сходимости базового алгоритма, когда Ь-\. Если область локализации собственных значений Р определяется параметрами атт, атах>0, то спектральный радиус матрицы перехода итераций на каждом из уровней МИА равен максимальному из чисел |1-ат)П^|,|1-а тз.\/1\- Таким образом, спектральный радиус для МИА (¿>1) существенно меньше, а скорость сходимости больше, чем для базового алгоритма, когда Ь-[.

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

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

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

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

Оценки спектрального радиуса матриц перехода (6), (8), (9) и области сходимости на рис.4 были получены в предположении, что система (5) и ее аналоги на внутренних уровнях решаются "точно", то есть число итераций пт внутренних уровней т=2...Ь достаточно велико. Вместе с тем, необходимо дать оценку фактической матрицы перехода для внешних уровней с учетом того, что число внутренних итераций ограничено. Как показано в работе, фактическая матрица перехода уровня т равна:

= + ПУтЧТт+' (¡Е - »V. (11)

Соотношение (11) выражает фактическую матрицу перехода уровня т через ее теоретическую оценку (6) и фактическую матрицу перехода более внутреннего уровня. Очевидно также, что IV¿* = IVпоскольку отсутствует уровень более внутренний чем ¿-й.

Области сходимости МИА при ограничении числа итераций отличаются от окружностей, показанных на рис.4. Так, семейство областей сходимости при пт-2, т-2...1, ат,п=1, атах=2£- приведено на рис.5. При пт+1~>х \ут*—>уут, т=1...Ь-1, и соответствующие области приближаются к изображенным на рис.4.

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

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

минимум целевой функции ^¿^.г/...^«^..^) - [ аЬз (г}1*) ^ гдс

Чт*~ 1т + (1т+1*)Пт+1(1 - Пт)■ лС'ПЬ ПтЧ1т-1+гт-1а)КЧт+гта).

В качестве иллюстрации рассмотрена оптимизация параметров МИА при решении уравнений, описывающих схему фильтра на операционных усилителях. Для решения дискретизованных по времени уравнений использовался БИА в виде точечного метода Зейделя, причем исходная задача была плохо обусловленной. По сравнению с БИА получен выигрыш по числу итераций в 3.78 раза при ¿=2 и в 4.71 раза при ¿=3. Примерно во столько же раз улучшается потенциальная точность алгоритма и сокращается требуемое время решения задачи. При ухудшении обусловленности задачи преимущества многоуровневого алгоритма дополнительно возрастают. Во всех случаях ускорение сходимости МИА достигается без изменения способа структурной декомпозиции цепи или системы, то есть для заданного расщепления.

Несмещенные итерации МИА

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

В связи с этим, рассмотрено подмножество МИА/МИАД, для которого собственные значения матриц перехода т=1...Ь, порождаемые собственным

значением а= 1 матрицы Р, находятся в точке (0,0). Несмещенными названы алгоритмы, обладающие отмеченным свойством.

Доказаны теоремы, утверждающие, что

• МИА оказывается несмещенным в том и только в том случае, когда коэффициенты (?„,, гт, т=0...Ь, удовлетворяют соотношению ¡т~ qm+ гт~ 1.

• МИА оказывается несмещенным, если коэффициенты д„„ гт, т=0...Ь, определяются из (7), когда ат(п=1 или атах=1, причем ат|п*атах.

• Условия несмещенности МИА можно всегда обеспечить совместно с условиями его сходимости.

В дальнейшем предложено использовать несмещенный вариант МИА с двумя итерациями на всех внутренних уровнях, ат,п=1, атах=2/- и единственным варьируемым параметром ¿=1,2...

Выводы

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

сократить трудоемкость решения плохо обусловленных задач по сравнению с оптимальным БИАД.

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

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

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

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

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

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

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

Пусть задана система нелинейных алгебраических уравнений

ДДГ)=0, Р(.), -ГеМ, (12)

которая имеет хотя бы одно решение а .Х^еВЛ есть некоторое начальное

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

Несмещенный МИА может быть представлен в канонической форме

/УГ„) = 0, (13)

где Рч- у-е уравнение системы (12), У„= '+<//./ -г^Я^ •Х'^1,+...+(гд -т1 •

Х^. Здесь 2,5- матрицы-шаблоны для составляющих ()иЗ якобиана системы (12).

Шаблоны определяются следующим образом: каждый элемент ()^ (или $если и

только если Qj¡i (или для всех А"е11л', иначе (или Sд-)-1. являются v-

ми транспонированными строками соответствующих матриц-шаблонов, а символ "•" обозначает операцию поэлементного матричного умножения или произведения Шура.

При £=1 (13) обобщает известные релаксационные алгоритмы с различными типами расщепления, а его линеаризация дает несмещенный линейный МИА (10).

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

заменить на "для всех у=1..../У решаем у-е уравнение (13) относительно компоненты

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

Сходимость МИА при решении систем нелинейных алгебраических уравнений характеризуется следующей теоремой:

Пусть Р(Х): непрерывна по Липшицу в некоторой окрестности 8 точки X*,

для которой Р{Х*)=0, и А&КХ*^ определена как А-[ёР//дх^, пусть (? еЯ-'^ есть шаблон некоторого базового алгоритма (БЙА) и () *А обратима, а все собственные значения Р = ((5 %А\1А для Ае0 лежат внутри окружности с центром на вещественной оси, проходящей через точки (е ,0), (атах,0), атах>е>0. В этом случае можно построить несмещенный МИА с числом уровней ¿>^2атах, обеспечивающий достаточные условия сходимости на каждом из уровней, если начальное приближение Хдев достаточно близко к Л" и число итераций п^.м^ внутренних уровней достаточно велико.

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

Выводы

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

Кроме того, показано, что с увеличением числа итерационных уровней Ь снижаются требования к линейности характеристик элементов цепи, налагаемые условиями сходимости итераций. Так, при ¿=1,2 сходимость итераций при анализе цепей на МДП-транзисторах наблюдается только при шунтировании каналов проводимостями не менее ЗхЮ"4 и 4х10"5 Ом"1 соответственно, в то время как при ¿>3 МИА не требует включения дополнительных элементов в анализируемую цепь.

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

Теоретически и экспериментально показана возможность существенного :окращения трудоемкости решения (в рассмотренных примерах - до 1-3 порядков) и расширения класса решаемых задач при замене традиционных декомпозиционных алгоритмов их многоуровневым обобщением.

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

Каноническая структура МРФС

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

ДЖЛ, X, I) = С(<1Хт +АХ + В-0, (14)

где функция ДйЛУЛ, X, /) удовлетворяет условиям Липшица по отношению к своим первым аргументам при любых СЛеВ.^*^; кроме того, заданы начальные

условия Х(0) и начальное приближение Хо(1) к искомому решению Х*(1) на интервале 1€(0,Т) такие, что Х0(О)-)С (0)=Х(0).

Предполагается также, что для каждого независимого узла цепи имеется по крайней мере одна емкость, соединяющая его с базисным узлом. В этом случае якобиан [Э/уЗсо;] функции ¥(&., 2, /), а также матрица С обратимы и характеризуются преобладанием диагональных элементов.

В принятых обозначениях несмещенный МРФС может быть представлен в виде канонической структуры

Р'ДЛУЛ, IV/) = 0, у=1...Л', (15)

где Ру- у-е уравнение (14), Щ.Х^Цг^-г^' .Х()у Хп (0) =

Х*(0).

При ¿=1 (15) соответствует известным алгоритмам РФС.

Метод МРФС может быть также описан с помощью алгоритмической структуры, приведенной в Гл.З, где все векторные переменные вида Х^ следует заменить

векторными функциями Х'(£,)(0> определяемыми из (15) путем решения

соответствующей задачи Коши.

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

Сходимость МРФС характеризуется следующей теоремой:

Пусть Дс/Х/А, X, ¡) - дифференцируемая по I векторная функция из Я^хЯ^хК' в

удовлетворяющая условиям Липшица по отношению к <£Х/<&, X, ( при всех г за исключением, быть может, конечного числа точек разрыва. Для /-"(П. 2, /) определим матричные функции А=А(С1,2,1)-[дРк/(Зг^]. Пусть, кроме того,

матрицы б «С и <2*А обратимы, где (>- шаблон матрицы расщепления некоторого базового алгоритма, и спектры матриц Рс-{0. »С)'1 С, Ра~(0. »А)'1 А для всех С2, ¿еИ.^', I >0 лежат внутри окружности с центром на вещественной оси, проходящей через точки ( е ,0), (атах,0), атах>£>0. В этом случае можно построить многоуровневое обобщение метода РФС с числом уровней для которого на каждом из т-\...Ь

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

необходимые условия равномерной сходимости.

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

В качестве иллюстрации на рис.7 и 8 соответственно показано поведение итераций РФС (-¿=1) и МРФС (¿.=2) при анализе фильтра с обратной связью (см. рис.6),

Рис.6. Схема фильтра и способ декомпозиции

Рис.7. Поведение итераций РФС (сходимость неравномерная)

Рис.8. Поведение итераций МРФС при ¿=2 (сходимость равномерная)

разделенного на подсхемы А, В и С. Видно, что итерации РФС сходятся весьма неравномерно. Каждая из них уточняет решение, полученное ранее, лишь в узком временном интервале (около 0.1 мс). Это обстоятельство накладывает ограничение сверху на величину временного шага, используемого для анализа каждой из подсхем. Кроме того, общее число требуемых итераций оказывается пропорциональным длительности интервала анализа. С другой стороны, МРФС при Ь~2 обладает практически равномерной сходимостью. Число требуемых итераций МРФС не зависит от длины интервала моделирования, кроме того, отсутствуют ограничения на величину временного шага, вызванные условиями сходимости итераций.

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

Выводы

Предложенное новое семейство алгоритмов МРФС является строгим обобщением методов РФС и совпадает с последними при числе итерационных уровней £,=1.

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

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

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

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

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

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

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

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

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

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

Для реализации модифицированных итераций в разделенной системе (А, В...) необходимо использовать "грубую" модель части В при анализе А, если на каждой итерации В анализируется после А. В более общем случае, если при анализе части лу, /</<Л', используются результаты от х¡...х^^ полученные на текущей итерации, и результаты от ..,х.у, которые найдены на предыдущей итерации, то сходимость можно улучшить при использовании "грубых" моделей входных характеристик частей •Су+у...хдгпри моделировании Ху

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

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

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

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

В частности, рассмотрен анализ схемы памяти на основе ее декомпозиции. Показано, что ни один из базовых типов сшивания (Р-тип, где для сшивания используются управляемые источники напряжения, а связующий элемент включен во все смежные подсхемы; /-тип, в котором используются управляемые источники разных типов, а связующий элемент отсутствует) не обеспечивает приемлемой скорости сходимости на протяжении всего интервала моделирования. Для решения данной задачи был применен обобщенный метод сшивания, а параметр у* изменялся так, чтобы в режиме записи схема сшивания работала как схема К-типа, а в режиме чтения -как схема /-типа. Оказалось, что для решения задачи данным способом достаточно всего 2-х итераций. Более того, управляющий параметр (емкость С*) не обязательно должен быть определен с большой точностью. При уменьшении или увеличении его величины вдвое сходимость все еще достаточно быстрая, хотя ошибка может либо менять свой знак, как в итерациях /-типа, либо убывать монотонно, как в итерациях V-типа.

Выводы:

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

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

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

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

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

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

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

До сих пор структурная декомпозиция анализируемых цепей осуществлялась на основе точечного или блочного алгоритмов Зейделя или Якоби, обеспечивающих сходимость итераций в области "малых времен". Способ разделения цепи на фрагменты в этом случае соответствует рис.9. В то же время, данный подход не гарантирует равномерной сходимости, и для получения искомого решения на всем интервале анализа может потребоваться значительное количество итераций. Для обеспечения равномерного характера сходимости итераций желательно выбрать иной способ декомпозиции цепи, основанный на разделении ветвей цепи и учитывающий высокую входную и низкую выходную резистивную составляющую импедансов функциональных блоков цепи и тем самым, обеспечивающий сходимость в области "больших времен" (см. рис.10). При разделении ветвей скорость сходимости определяется не глубиной связи между фрагментами, а отношением входной проводимости (емкостной или резистивной) второго фрагмента к выходной проводимости первого. Если декомпозиция цепи проведена на основе ее разбиения на функциональные блоки с низким выходным и высоким входным импедансом, то в области больших времен итерации имеют высокую скорость сходимости. Обеспечение необходимых условий сходимости для области малых времен может быть достигнуто применением многоуровневого обобщения рассматриваемых итераций (МРФС).

В работе показано, что если цепь содержит только двухполюсные емкостные и резистивные элементы с неотрицательными параметрами, то собственные значения матрицы Л в случае декомпозиции по методу Зейделя локализованы на отрезке (0,1) вещественной оси, а в случае разделения ветвей могут находиться во всей правой полуплоскости за исключением окружности радиуса 1/2 с центром в точке (1/2,0) (рис.11). Видно, что рассматриваемые области локализации "дополняют" друг друга. Сочетание различных способов декомпозиции для различных участков цепи дает возможность значительно ускорить сходимость и уменьшить требуемое число итераций (в рассмотренных примерах на 2-3 порядка).

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

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

А

"X

х / Л х2 х1 К х

О О

Рис.9. Декомпозиция цепи на основе метода Зейделя

J

А

X

'" Г'

X, .—

Ф О

Рис.10. Декомпозиция цепи на основе разделения ветвей

Рис. 11. Возможная локализация собственных значений матрицы Р в случае декомпозиции методом Зейделя и при разделении ветвей

сходимости указанный способ декомпозиции должен применяться совместно с МИА и модифицированным методом сшивания. Предложенный подход в сочетании с методом модифицированного сшивания использовался при анализе смешанной системы "электрическая цепь - пьезоэлемент". Для моделирования схемного фрагмента использовалась программа ELDO 4.3.1, а для пьезоэлементов - ANSYS 5.0. Кроме того, рассмотрено применение МРФС для моделирования смешанной системы электрическая цепь - электродвигатели. Цепь представлена моделью программы SPICE3. С помощью специального интерфейса полученные отсчеты напряжения преобразуются в аналоговый сигнал и подаются на электродвигатель постоянного тока. Ток электродвигателя после измерения и аналого-цифрового преобразования используется как входной сигнал для схемной модели. В обоих рассмотренных случаях сходимость процесса моделирования удалось обеспечить только при использовании МРФС при 1=2 и L=3.

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

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

Примером системы приборно-схемотехнического моделирования подобного типа является ИСТОК-2Д, разработанный в 90-95 гг. в Российском НИИ Информационных Систем. В одной из последних версий данной системы автором диссертационной работы были внедрены многоуровневые итерационные алгоритмы.

Размерность СЛАУ для типичных элементов БИС имеет порядок 2500-8000, а структура якобиана показана на рис. 12а. Здесь ЗУ,- - вектор приращений внутренних переменных /'-го элемента, дЪс - вектор приращений внешних переменных; D,-, Е, -соответственно матрица Якоби и правая часть вычислительной модели i-ro элемента; Vc - матрица Якоби схемы включения; R,- и Ф,- - подматрицы, отражающие связи внутренних переменных /-го элемента с внешними переменными. В свою очередь, матрицы D, имеют блочко-диагональную структуру (рис.126). Каждый элемент в диагональных и субдиагональных блоках является блочной матрицей 3x3, содержащей коэффициенты дискретизованных уравнений для соответствующей точки сетки.

Для решения данной задачи был использован метод матричной прогонки в сочетании с многоуровневой модификацией блочного метода Зейделя, L-2, для решения уравнений отдельных ППС. Рис.13 иллюстрирует поведение ошибки доминирующей компоненты искомого вектора на итерациях БИА и МИА (внутренних) при расчете первой точки передаточной характеристики биполярного транзистора. В целом, при решении различных задач подобного типа использование МИА в программе ИСТОК-2Д позволило в 3-8 раз сократить трудоемкость вычислений по сравнению со случаем БИА (блочного метода Зейделя), приблизительно равного по эффективности прямым методам. При решении задач на сетке 30x16, когда число неизвестных достигало 5760, трудоемкость прямых методов возросла в 8 раз, а итерационных (БИА и МИА) примерно вдвое. Выигрыш МИА по сравнению с БИА в этом случае остается прежним.

Выводы

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

н

§

5

Б

5

В

б)

Рис. 12. Система уравнений ППС (а) и структура блочной матрицы коэф-тов (б)

1.8п+

180П

18 28 за 48 58 60 78 В8 98

Рис. 13. Поведение ошибки для итераций БИА и МИА (Ь~2)

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Dmitriev-Zdorov V. Multicycle generalization of relaxation-based algorithms for circuit and system simulation. - GMD - Forschungszentrum Informationstechnik GmbH. -München, Wien: Oldenbourg Verlag, 1997. - 164 p. (ISBN 3-486-24334-9) (Дмитриев-Здоров В.Б. Многоцикловое обобщение релаксационных алгоритмов для моделирования цепей и систем. - Нац. Исслед. Центр ФРГ по Информац. Технологиям. - Мюнхен, Вена. - Олденбург Ферлаг, 1997. - 164 стр.)

2. Dmitriyev-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. (Дмитриев-Здоров В.Б. Многоуровневое обобщение итерационных методов: новый способ улучшения сходимости в программах моделирования основанных на релаксации. - Междунар. симпозиум по нелинейной теории и ее применению (NOLTA'93), Токио, 1993, стр. 655-658.)

3. 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. (Дмитриев-Здоров В.Б. Многоуровневое обобщение

релаксационных алгоритмов для анализа электрических цепей. - Европейская конференция по автоматизации проектирования, EURO-DAC'94, Гренобль, Франция, 1994, стр. 176-181.)

4. Dmitriev-Zdorov V.B., Klaassen В. 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. (Дмитриев-Здоров В.В., Клаассен Б. Модифицированный метод релаксации для анализа смешанных систем с использованием нескольких моделирующих программ. - Европейская конференция по автоматизации проектирования, EURO-DAC'95, Брайтон, Великобритания, 1995, стр. 274-279.)

5. Dmitriev-Zdorov V.B. 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. (Дмитриев-Здоров В.Б. Модифицированное сшивание как способ улучшения сходимости в программах моделирования, использующих релаксацию. - Европейская конференция по автоматизации проектирования, EURO-DAC'96, Женева, Швейцария, 1996, стр. 15-20.)

6. Dmitriev-Zdorov V., Klaassen В., Раар K.-L. Improvement of stability in cosimulation of tightly-coupled systems. - Proc. of 9-th European Simulation Symposium (ESS'97), Passau, Germany, 1997, pp.639-643. (Дмитриев-Здоров В.Б., Клаассен Б., Паап К.-Л. Улучшение стабильности при моделировании сильно связанных систем. - 9-й Европ. симпозиум по моделированию (ESS'97), Пассау, Германия, 1997, стр.639643.)

7. Dmitriev-Zdorov V., Klaassen В., Раар 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. (Дмитриев-Здоров В.Б., Клаассен Б., Паап К.-Л. Моделирование аналоговых систем с включением "реальных" моделей. - Первая конф. по электронным цепям и системам (ECS'97), Братислава, Словакия, 1997, стр.31-34.)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22. Дмитриев-Здоров В.Б. Итерационный алгоритм анализа цепей на основе явных разностных схем. - Технич. электродинамика, 1988, N6, с.91-93.

23. Dmitriev-Zdorov V.B. The multilevel generalization of waveform relaxation method. -Proc. of 3-rd biennial Conf. "Automation, simulation & measurement", Tallinn Tech. Univ., 1992, pp.47-53. (Дмитриев-Здоров В.Б. Многоуровневое обобщение метода релаксации формы сигнала. - Мат. конф. "Автоматизация, моделирование и измерение", Таллинн. Техн. унив., Таллинн, 1992, стр.47-53)

24. Dmitriev-Zdorov V.B., Dudka V.B., Popov V.P. Automation of the electrical network macromodeling. - Proc. of 3-rd biennial Conf. "Automation, simulation & measurement", Tallinn Tech. Univ., 1992, pp.54-59. (Дмитриев-Здоров В.Б., Дудка В.Б., Попов В.П. Автоматизация макромоделирования электрических цепей. - Мат. конф. "Автоматизация, моделирование и измерение", Таллинн. Техн. унив., Таллинн, 1992, стр. 54-59)

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

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

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

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

29. Dmitriev-Zdorov V.B. Multilevel waveform relaxation algorithms for circuit simulation.-Proc. 3-rd Int. Design Autom. Workshop, Moscow, 1993.- ррЛ61-170. (Дмитриев-Здоров В.Б. Многоуровневые алгоритмы релаксации формы сигнала для анализа цепей. - Мат-лы 3-го междунар. семинара по автоматизации проектирования, Москва, 1993, стр. 161-170)

В работах, опубликованных в соавторстве, автору принадлежат следующие результаты:

в [4] - МРФС для "сшивания" решений при моделировании смешанной системы; в

[6] - методы обеспечения устойчивости при реализации "параллельной релаксации"; в

[7] - МРФС для обеспечения сходимости моделирования смешанной системы; в [9,18] -семейство алгоритмов решения СНАУ и СОДУ; в [10,19-21,24] - метод разделения движений и алгоритм редукции математической модели на основе ее приведения к канонической форме; в [15] - декомпозиционный алгоритм решения уравнений цифровых схем; в [16] - алгоритм решения систем нелинейных уравнений и его обоснование; в [17] - численный алгоритм решения СОДУ, базирующийся на методах релаксации; в [25,27] - реализация РФС и МРФС в рабочей станции.

ззидиум ВАК России

I (решение от " " -

í присудилученую с^е ; Д ■ .'■ у; ¿'ОРД

________ НИИ'

непппшн управления ВАК носси:

Министерство общего и профессионального образования

Российской Федерации Таганрогский Государственный Радиотехнический университет

ДМИТРИЕВ-ЗДОРОВ Владимир Борисович

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

Специальности:

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

05.09.05 - Теоретическая электротехника

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

УДК 681.3.062:621.3.011.1

Диссертация на соискание ученой степени доктора технических наук

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

В.П.ПОПОВ

Таганрог 1998

СОДЕРЖАНИЕ

1. Введение ..................................................................5

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

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

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

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

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

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

и У «_» о

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

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

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

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

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

3.5. Выводы ...................................................................86

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

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

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

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

4.4. Выводы ..................................................................126

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

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

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

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

5.4. Выводы ..................................................................144

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

...........................................................................................146

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

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

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

6.4. Выводы ..................................................................166

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

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

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

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

7.4. Выводы ..................................................................219

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

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

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

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

8.4. Выводы ..................................................................260

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

Литература............................................................268

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. Предложенный класс алгоритмов дает возможность использовать новые, ранее не применявшиеся способы декомпозиции цепей, что, в свою очередь, делает возмо