Введение к работе
АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. Необходимость дальнейшего развития методов шализа сложных систем вызвана резким усложнением создаваемых технических устройств, конструкций, технологий, а также потребностью изучения биологических )бъекгов и проблем экологии. Среди наиболее сложных технических устройств следует іазвать устройства радиоэлектроники и вычислительной техники, создаваемые с томощью микроэлектронной технологии, а также электроэнергетические системы.
Увеличение степени интеграции до 105-106 транзисторов на кристалле выдвигает гачественно новые требования к алгоритмам и программным средствам, іспользуемьім для синтеза и верификации проектных вариантов БИС. В настоящее іремя для моделирования процессов в БИС с целью их верификации используются «сколько различных по характеру процедур. При классификации обычно выделяют ірограммьі алгоритмического или функционального моделирования, моделирования іа уровне регистров, временного, схемного, а также компонентного моделирования. В юследнее десятилетие как у нас в стране, так и за рубежом был разработан ряд грограмм смешанного моделирования, сочетающих в себе возможности нескольких іазванньїх процедур.
В то же время, эволюция технологии производства БИС приводит к тносительному возрастанию роли схемного моделирования. Прогноз относительно >аботоспособности сложной электронной системы, реализованной на одном ристалле, можно получить только в результате детального электрического анализа, ыполняемого программами схемного моделирования. Используя лишь >ункциональный (функционально-логический) уровень моделирования, невозможно честь такие эффекты, как влияние шин питания и земли, зависимость задержки ереключения вентилей от комбинации входных сигналов, эффекты в длинных линиях ередачи, нелинейный характер емкостей нагрузки, особенности формы сигналов. Для екоторых типов БИС, например, аналоговых или содержащих аналоговые ірагментьі, а также элементов памяти, схемное моделирование является единственно озможным.
Схемное моделирование является не только наиболее надежной, но и самой рудоемкой и дорогостояшей процедурой. Для проведения схемного моделирования іирмьі - разработчики БИС ежегодно тратят несколько тысяч часов компьютерного ремени, а на работы по совершенствованию соответствующего программного беспечения выделяется несколько миллионов долларов. Необходимость в быстром и адежном электрическом анализе сложных систем возникает и в электроэнергетике, где рёбуется проводить в реальном времени моделирование кратковременной естабильиости, возникающей при коммутациях в энергосистеме.
На этапе моделирования электрической цепи могут быть реализованы несколько идов анализа, такие как анализ по постоянному току, в частотной области, расчет увствительности, оптимизация и другие, однако наиболее общим, информативным и в э же время, наиболее дорогостоящим, является анализ нелинейной инерционной цепи о временной области. Этот вид анализа электрической цепи включает в себя роцедуры формирования математической модели цепи и решения полученных ифференциальных (ОДУ) или алгебраических уравнений электрического равновесия.
В течение двух последних десятилетий сформировался "классический" набор роцедур, на котором базируется алгоритмическое обеспечение программ схемного оделирования. Он включает в себя неявные жестко-устойчивые методы пгебраизации ОДУ, ньютоновские итерации для решения нелинейных алгебраических равнений и "прямые" методы гауссовского типа для решения систем линейных равнений. Подобные программы позволяют проводить моделирование цепей, писываемых системами, насчитывающими до 102-103 уравнений, что не обеспечивает
насущных потребностей при решении задач автоматизации и выполнении исследовательских работ. Несмотря на многочисленные и в целом небезуспешные попытки модернизации алгоритмического обеспечения, в рамках приведенной структуры к настоящему времени не удалось существенно расширить возможности программ автоматизированного анализа цепей, сделать их достаточно эффективными при моделировании БИС.
Надежда на существенный прогресс в области схемного моделирования БИС возникла в начале 80-х годов с появлением программ, базирующихся на методах релаксации, позволяющих реализовать структурную декомпозицию анализируемой цепи. По сравнению со своими предшественниками программы этого типа позволили в 10-100 раз сократить затраты процессорного времени при обработке систем, насчитывающих до нескольких сотен уравнений, довести размерность анализируемых систем до нескольких десятков тысяч уравнений. Кроме того, структурная декомпозиция модели дает возможность проводить независимую (последовательную или параллельную) обработку отдельных фрагментов, что открывает дополнительные возможности для реализации релаксационных методов на многопроцессорных системах.
Основным недостатком, сдерживающим широкое применение релаксационных методов, является их медленная сходимость, а также ограниченность класса цепей, в котором выполняются условия такой сходимости. Попытки решения крайне актуальной задачи улучшения сходимости релаксационных методов в известных работах сводятся к выбору оптимальной стратегии разбиения исходной модели на фрагменты и определению порядка обработки подсхем, минимизирующего число итераций. Вместе с тем, возможности улучшения характеристик релаксационных методов при таком подходе ограничены, поскольку он не затрагивает структуры самих алгоритмов, не ведет к расширению соответствующих областей сходимости.
В связи с этим, в диссертационной работе задача улучшения характеристик релаксационных алгоритмов решается с иных позиций - путем разработки нового класса релаксационных алгоритмов, позволяющих расширить область сходимости в том числе и без изменения способа декомпозиции анализируемой системы.
ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ состоит в разработке нового класса релаксационных алгоритмов, являющегося строгим обобщением известных декомпозиционных методов анализа цепей и систем, позволяющего при прочих равных условиях расширить область сходимости последних и сохраняющего такие их положительные свойства, как возможность независимой обработки фрагментов системы и квазилинейный характер роста трудоемкости анализа при увеличении размерности системы. Как следствие, разработанные в диссертации алгоритмы обеспечивают расширение класса анализируемых цепей и систем, а также снижение требуемых затрат ресурсов ЭВМ на проведение их анализа.
Совокупность результатов, полученных при достижении поставленной цели и решении соответствующих задач, можно охарактеризовать как новое крупное достижение в развитии методов моделирования и анализа сложных цепей и систем на основе их структурной декомпозиции.
Для достижения поставленной цели в работе решены следующие задачи:
разработан способ построения многоуровневого обобщения алгоритмов, относящихся к классу одношаговых линейных итерационных методов и применимых к анализу цепей и систем, содержащих "закрытые" блоки, математическое описание которых не задано;
исследованы спектральные характеристики итерационных матриц и области сходимости для синтезированных алгоритмов и определены достаточные условия сходимости последних;
разработана схемная интерпретация построенных многоуровневых алгоритмов и способы построения эквивалентных схем на основе соответствующих схем для традиционных (одноуровневых) алгоритмов;
методика построения многоуровневых итерационных алгоритмов обобщена на случай нелинейных статических и динамических цепей и систем;
сформулированы необходимые и достаточные условия равномерной сходимости многоуровневых итерационных алгоритмов при анализе электрических цепей и систем во временной области;
предложен ряд новых подходов, включая методы разделения быстрых и медленных движений на основе приведения модели цепи к канонической форме, модифицированный и обобщенный методы сшивания, которые в сочетании с многоуровневыми алгоритмами обеспечивают дополнительное улучшение характеристик итерационных методов;
проведены широкие экспериментальные исследования разработанных многоуровневых алгоритмов в задачах анализа электрических цепей и систем.
-
Построен новый класс многоуровневых релаксационных методов анализа, включающих как частный случай обобщенные линейные итерационные алгоритмы Зейделя, Якоби, последовательной верхней релаксации (ПВР) и соответствующее ему многоуровневое обобщение релаксационной модели исследуемого объекта. Разработанный класс моделей и алгоритмов применим к системам, содержащим "закрытые" блоки или "черные ящики".
-
Определены условия и значения параметров, при которых разработанные релаксационные модели и соответствующие им алгоритмы превосходят по скорости сходимости известные методы либо позволяют обеспечить сходимость там, где она не может быть достигнута другими средствами.
-
Сформулированы многоуровневые итерационные алгоритмы (МИА) для анализа нелинейных динамических цепей, описываемых системами нелинейных алгебраических и дифференциальных уравнений, а также построены схемные модели рассмотренных алгоритмов.
-
Даны канонические представления многоуровневых релаксационных моделей и алгоритмов, отображающие их в единой форме, независимо от выбора матрицы или оператора расщепления и включающие как частный случай известные релаксационные методы.
-
Получен алгоритм формирования матрицы расщепления для случая декомпозиции цепи на основе разделения ветвей, модифицированного и обобщенного методов сшивания подсхем. Найдены области локализации собственных значений оператора перехода, и определены условия, при которых может быть обеспечена равномерная сходимость многоуровневых итераций.
-
Показано, что использование МИА в сочетании с декомпозицией на основе разделения ветвей, методами модифицированного и обобщенного сшивания делает возможным эффективный анализ смешанных систем с одновременным использованием нескольких различных программ моделирования.
-
Разработанные в диссертации модели и алгоритмы, являющиеся строгим многоуровневым обобщением известных релаксационных процедур, используемых для анализа цепей и систем в статическом и динамическом режимах.
-
Полученные в работе оценки областей сходимости разработанных алгоритмов, а также сформулированные в виде теорем условия сходимости последних.
-
Методики выбора параметров разработанных моделей и алгоритмов, оптимизирующие скорость их сходимости.
-
Предложенный в работе метод декомпозиции цепей на основе разделения ветвей, а также оценки областей локализации собственных значений матрицы перехода при реализации этого метода.
-
Результаты экспериментальных исследований эффективности разработанных алгоритмов в задачах анализа цепей и систем, их сравнение с известны м и подходами к решению подобных задач.
-
Разработан новый класс релаксационных моделей и алгоритмов, характеризующихся при прочих равных условиях линейной зависимостью затрат от размерности анализируемой цепи при анализе сложных систем. Ускорение достигается как по числу обращений к вычислительным моделям (числу итераций), так и по суммарным затратам времени ЭВМ.
-
Ускорение сходимости при использовании разработанных алгоритмов достигается и при анализе систем, содержащих "черные ящики", то есть фрагменты, внутренняя структура которых неизвестна.
-
Использование разработанных алгоритмов при анализе динамических систем позволяет добиться равномерной сходимости итераций. Последнее обстоятельство дает возможность значительно ослабить или снять ограничения на величину временного шага, налагаемые условиями сходимости. Кроме того, требуемое число итераций, в отличие от традиционных методов релаксации, не зависит от величины временного интервала моделирования. В результате экспериментальных исследований предложенного подхода было показано, что для типичных задач схемного моделирования выигрыш по сравнению с 1-уровневыми релаксационными алгоритмами достигает 1-2 порядков.
-
Предложенный класс алгоритмов дает возможность использовать новые, ранее не применявшиеся способы декомпозиции цепей, что, в свою очередь, делает возможным моделирование смешанных систем, включающих объекты различной физической природы, в одном итерационном цикле с помощью нескольких программных средств. До сих пор реализация данного подхода была возможна только для систем со слабой или преимущественно однонаправленной связью между объектами.
-
Предложенные в диссертации методы и алгоритмы служат основой для создания специализированных пакетов программ расчета и оптимизации смешанных систем, электрических цепей большой размерности, а также пакетов приборно-схемотехнического моделирования. Применение разработанных в диссертации алгоритмов в программе ИСТОК-2Д позволило в 3-8 раз ускорить анализ полупроводниковых структур. Перспективным является использование предложенных подходов для решения задач в других областях техники, требующих быстрого и эффективного анализа сложных систем.
Теоретические и практические результаты диссертационной работы вошли как составная часть в Госбюджетные НИР N3.22.008 "Методы моделирования и автоматизированного анализа радиоэлектронных цепей" и N 11151 "Разработать и исследовать адаптивные модели сложных электронных цепей и пространственно-временных сигналов с целью повышения точности и быстродействия работы САПР радиоэлектронных устройств и эффективности радиотехнических систем", хоздоговорные НИР NN 111 US, 111125, 111131, в контракт N 24176821/95 "Моделирование смешанных систем", выполнявшийся по заказу Национального
исследовательского центра ФРГ по вычислительной технике и информационным технологиям, а также в контракт 84O/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 наименований.
