На сегодняшний день все более актуальными становятся задачи моделирования реальных технических, физиологических, экономических и др. процессов, описываемых системами обыкновенных дифференциальных уравнений (далее ОДУ). Размерность таких систем может достигать высоких порядков. Как следствие подавляющее большинство таких задач требуют высокопроизводительные вычисления, при этом повышается потребность в методах ускоренного и распределенного моделированияОдной из областей, остро нуждающихся в новых подходах к моделированию, является быстро развивающаяся-микроэлектроника (см. 2-ая глава «Особенности моделирования интегральных схем»).
Классические методы решения систем обладают высокой’достоверностью результатов, хорошо изученными свойствами сходимости (в том числе устойчивости в применении к жестким задачам) и разнообразием методов оценки, точности и выбора шага интегрирования: Однако использование таких методов ¿-для решения задач большой. размерности сводитсягна нет, когда встает вопрос об оптимизации скоростных характеристик расчета. Вместе с тем, разработка и поиск методов ускоренного моделирования, обладающих заданными свойствами, берут свое начало из классических методов. В 1-ой главе «Подходы к численному решению* жестких систем ОДУ» рассмотрены особенности численного решения систем ОДУ в общей постановке, а также представлена классификация методов по применимости, — как для задач микроэлектроники, так и в рамках алгоритма ускоренного моделирования с точки зрения реализации контроля точности (см. также 2.4). В частности выделяются одношаговые методы Рунге-Кутты и Розенброка. Из методов Розенброка особое внимание уделено «¥—методам, обеспечивающих требуемую устойчивость при модифицированной матрице Якоби. В 4-ой главе «Анализ и Обоснование подхода» работы представлены современные решения контроля точности и алгоритмы выбора шага, а также приводятся обоснования возможности применения последних к предлагаемому подходу. Вчастности делается заключение, что наиболее приемлемым является правило Рунге для оценки главного члена погрешности расчета.
В' таких областях, как, например, в схемотехническом проектировании в микроэлектронике (см. 2.1), особо* остро стоит проблема поиска описанных выше методов оптимизации моделирования. Существуют разные подходы к решению этой задачи. Однако почти все исследованные подходы либо требуют классического решения упрощенной задачилибо заведомого понижают порядок метода и, как следствие, точность решения. Таким образом, современные решения не находят компромисса между скоростью и точностью решения, жертвуя гибкостью и/или общностью решения, возможностью распределенного и/или достоверного решения. Более детально с современными подходами можно «ознакомиться в разделе «Обзор существующих подходов», а также в 3.1.
Следует отметить, что во многих современных прикладных областях развитие получают методы решения ОДУ, обеспечивающие не столько точное, сколько быстрое решение задач. Развитие моделирования", в таком направлении' зачастую диктуется тем, что при решенииприкладных задач погрешность входных данных (неустранимая погрешность), обусловленная неточностью измерений тех или иных параметров физической системы, в несколько десятков раз превышает погрешность методов и вычислительные погрешности (погрешности округления). Обычно в прикладных областях от модели не требуется получение точного результата, часто ожидается обладающий определенной погрешностью, но быстрый прогноз. Однако на сегодняшний день запас точности методов достаточен, а вот запас скорости — нет. Таким образомувеличение скорости работы алгоритмов расчета может быть осуществлено за счет снижения точности численных методов, не понижая при этом точности полученных результатов.
Во 2-ой главе «Особенности моделирования интегральных схем» излагаются особенности проектирования интегральных схем и современные проблемы моделирования. Рассматриваются особенности различных уровней проектирования КМОП СБИС — логическом (см. 2.2), схемотехническом или электрическом (см. 2.3) и топологическом или структурном (см. 2.2). В разделе подчеркиваются проблемы снижения достоверности результатов ускоренного моделирования при переходе на субмикронный и нанометровый диапазоны (см. 2.1 и 2.7).
Основной целью данной работы является разработка математических алгоритмов, ориентированных не только на ускоренное моделирование динамических систем, описываемых, системами ОДУ, но и на повышение достоверности результатов за счет механизмов контроля точности. Суть подхода и алгоритма ускоренного моделирования, а также обоснование применимости подробно изложены в 3-ей главе «Алгоритм ускоренного моделирования». В разделе вводится класс задач, на которые ориентировано применение подхода (см. 3.1). Также в 3-ей главе приводится описание соответствующего пакета программ, основанного на этом алгоритме. В главе 4 «Алгоритм ускоренного моделирования» затронуты вопросы повышения достоверности приближенного решения за счет контроля выбора шага.
С развитием вычислительной техники и вычислительных технологий для современного компьютерного моделирования большее предпочтение отдается методам, способным работать в параллельном режиме. Поэтому все новые разработки вобласти параллельных вычислений представляют больший интерес по отношению к разработкам в области «последовательных». Технологии параллельной и распределенной обработки данных позволяют сокращать скорость моделирования не за счет модификации исходной задачи или понижения точности расчета, а за счет использования многопроцессорных (в том числе многоядерных) вычислительных систем. Многопоточные или многопроцессорные реализации алгоритма моделирования могут обеспечивать существенный прирост в производительности. Однако классические методы интегрирования ОДУ плохо распараллеливаются (см. «Обзор существующих подходов»). В свою очередь гибкость реализации и особенности формирования алгоритма синхронизации расчетных модулей позволяют заметно сократить временные затраты на моделирование в параллельном режиме за счет нарастания некоторой (контролируемой) погрешности решения в рамках класса слабосвязанных систем (см. 3.1). О возможностях параллельного режима моделирования предложенного алгоритма синхронизации можно ознакомиться в 3-ей главе «Алгоритм ускоренного моделирования».
Несмотря на общность работы с алгоритмической и математической' точек зрения, применение работы ориентируется на решение задач схемотехнического проектирования. Особенности современных методов-анализа в микроэлектронике, описанные в главе 2 «Особенности моделирования интегральных схем», позволяют автоматизировать процесс декомпозиции ¡-задачи в рамках предметной области. Во 2-ой главе можно также ознакомиться с моделями, используемыми при формировании систем ОДУ для проектирования интегральных схем (ИС). В качестве основных критериев точности моделирования ИС предполагается контроль точности интегральных характеристик схемы, традиционно рассчитываемых на логическом уровне (см. 2.2). К числу таких характеристик могут относится, в частности, максимально-возможная задержка, максимально-возможная помеха, максимально-возможная потребляемая мощность, максимально-возможный скачок напряжений (Ж-ёгор) и др.
В 5-ой главе «Применение алгоритма синхронизации для КМОП СБИС» приводятся результаты моделирования типовых задач микроэлектроники. На примере этих задач удается продемонстрировать возможности и преимущества излагаемого подхода формирования модели как трансформации ЯС-схемы в систему ОДУ.
В «Заключение» приводятся основные результаты диссертации, а также указываются возможные ограничения работы.
Обзор существующих подходов.
С конца 1970;х ученые начали предпринимать попытки создания численных методов, применимых к системам, имеющим высокочастотный/низкочастотный и жесткий/нежесткий характер подсистем основных переменных. Обусловлено это тем, что основной сложностью решения больших систем дифференциальных уравнений является существенное различие скорости протекания описываемых ими процессов. В работе рассматриваются только жесткие системы ОДУ с большим разбросом скоростей (с существенным различием вещественных частей собственных чисел матрицы Якоби). Однако работа может получить распространение и на случай колебательных систем с существенным разбросом частот (мнимых частей собственных чисел). Учет всех быстрых процессов на численном уровне заставляет использовать либо очень малый шаг интегрирования, либо применять специальные классы численных методов, дающие устойчивые разностные задачи при умеренном шаге. В частности, для жестких систем применяются жестко-устойчивые и другие неявные методы, которые сложнее явных в реализации. Уменьшение же шага интегрирования приводит к возрастанию числа требуемых шагови как следствие, к неприемлемому росту временных затрат на решение больших систем. Обычно число арифметических операций, требуемых для выполнения одной итерации численного решения, нелинейно зависит от размерности задачи.
Существующие подходы к решению больших систем можно разделить на несколько основных классов. Одни подходы сосредотачиваются на алгоритмах распараллеливания программного кода численных методов (причем безо всякого изменения самих методов) [1]. Однако результаты решения систем ОДУ, получаемые при таком распараллеливании на кластерных системах, не являются впечатляющими (по крайней мере, по сравнению с параллельным решением уравнений в частных производных). С методами параллельного интегрирования ОДУ можно ознакомиться в работе [3]. Это обусловлено тем, что в типичной системе ОДУ число обменов значениями переменных между процессорами пропорционально числу переменных (в то время как, например, при решении двумерных задач с частными производными число обменов пропорционально квадратному корню из числа переменных). При этом не учитываются какие-либо особенности задачи (например, слабая связанность подсистем, см. ниже), за счет которых зачастую в вычислительном смысле большие системы ОДУ могут быть сближены с системами уравнений в частных производных.
Второй класс подходов, характерный для некоторых прикладных областей (например, для схемотехники [2]), делает акцент на сокращение вычислительных затрат за счет специальных эвристических приемов (обычно вытекающих из «физики задачи»), а точности решения уделяется меньше внимания. Это оправдано тем, что при решении прикладных задач погрешность входных данных (обусловленная, в частности, неточностью измерений тех или иных параметровфизической системы) обычно на 1−2 порядка превышает погрешность методов и погрешности округления. Увеличение скорости работы алгоритмов расчета может быть осуществлено за счет снижения' точности численных методов без понижения, точности полученных результатов. Данная работа также использует этот факт (причем без привязки к определенной прикладной области), однако делает акцент на исследование точности решения.
Следует также отметить современные исследования по многоскоростному (multi-rate) решению систем ОДУ, которые занимают промежуточное положение между двумя вышеописанными классами подходов. Многоскоростные методы в основном применимы к системам, в которых основные переменные разделяются на низкочастотные и высокочастотные подсистемы [4]. В них предлагаются различные формулы для расчета нескольких групп переменных — соответствующие шаги интегрирования (кратные друг другу) различаются для каждой подсистемы переменных, при этом сам метод остается одним и тем же для всех подсистем. Экономия вычислительных затрат достигается за счет меньшего числа операций, требуемых для расчета «медленных» переменных (соответствующих большим шагам) в промежуточные моменты времени. Этот подход актуален для дифференциальных систем с большим коэффициентом жесткости. Существенной особенностью большинства подходов к решению таких систем является сохранение понятия единого вектора системы. Фактически решается задача на каждом «быстром» шаге во времени — в том числе, для «медленных» переменных. То есть, качественные изменения затрагивают только способ получения вектора решения на каждой итерации. Как правило, многоскоростные методы используют идею интерполяции (экстраполяции) значений «медленных» переменных в те моменты времени, когда вычисляются значения «быстрых» переменных. Однако здесь речь не идет о настоящем расщеплении на подсистемы (при котором медленная переменная просто не существует в тот момент времени, когда вычисляется быстрая). Примером тому является работа [5], в которой и «медленные» и «быстрые» переменные рассчитываются в одни и те же моменты времени, при этом для вычисления значений «медленных» переменных используется линейная интерполяция.
В работе [6] был предложен двухскоростной метод, основывающийся на разделенном методе Рунге-Кутты. Данный метод является весьма эффективным, т.к. для двух различных подсистем переменных используются различные методы Рунге-Кутта с разными свойствами устойчивости. Но в то же время рассматриваемый подход имеет ограниченную область применимости.
Существует подход, изложенный в работе [7], в котором попытки разделения на подсистемы делаются не для аналитической дифференциальной задачи (как в большинстве подходов), а для разностной задачи. В силу специфики предлагаемого решения используется неявный метод Эйлера — метод первого (низкого) порядка. Основное внимание в работе уделяется оптимизации алгебраических методов решения разностной задачи с целью повышения скорости расчета. В частности отдельно рассматривается возможность распараллеливания задачи.
Как преимущество, следует отметить достаточно подробное рассмотрение исследователями подобных методов вопроса о точности результатов оказывается, что интерполяция с нужным порядком точности позволяет даже сохранить высокий порядок исходного численного метода) [5,6]. Как недостаток, подобные походы лишь несущественно сокращают число арифметических операций, решая полную (но измененную) задачу — экономия вычислительных ресурсов у них получается не слишком существенной (в то время как для решения больших систем нужна экономия в десятки и сотни раз). При этом вопрос о распараллеливании многоскоростных методов вообще не рассматривается, поскольку с алгоритмической точки зрения они не отличаются от обычных методов расчета ОДУ (а они, как было указано выше, плохо поддаются распараллеливанию).
Предлагаемый подход к решению подобных задач, ориентированный на создание модифицированных моделей, запрещает интерполяцию значений «медленных переменных», то есть, при расчете используются только известные значения соответствующих функций для подзадач. Другими словами, для вычисления правых частей подсистем «быстрых» переменных в моменты времени, соответствующие минимальному шагу интегрирования всей системы, используются последние вычисленные значения «медленных» переменных.
В рамках подхода предложена модель — трансформация ЯС-схемы в систему ОДУ.
Помимо достоинств такого подхода, которые будут рассмотрены ниже, следует отметить, что такие требования к алгоритму расчета позволяют решать каждую подзадачу отдельным решателем и рассматривать такой решатель как «черный ящик».
Выводы.
На основании исследований, проделанных выше, можно сделать выводы относительно подхода к ускоренному моделированию и алгоритма численного решения систем, декомпозируемых на подсистемы. На уровне отдельных подсистем интегрирование может осуществляться методами любого порядка, однако с точки зрения экономии вычислительных затрат применяются методы невысокого порядка — явные и неявные методы 1-ого и 2-ого порядков.
Применимость явных методов оправдано’только отдельных подсистем в тех случаях, когда система может быть декомпозирована с разделением на жесткий и мягкий спектры. Причем, применение явной схемы для каждой подсистемы не представляется целесообразным с точки зрения эффективности.
Независимо от порядка методов, применяемых науровне отдельных подсистемпорядок решения всей системы целиком падает как минимум до первого. Повышение порядка не является экономически оправданным. ¦
Не имея возможности (с практической точки зрения), варьировать порядок решения всей системы целиком,.единственным механизмом оценки и контроля погрешности является правило Рунге. Хотя такой механизм требует существенного увеличения числа арифметических операций по отношению к одной итерации решения, он обеспечивает оценку точности и коррекцию шага. Альтернативой адаптивным методам является эвристический' механизм предсказания* следующего шага интегрирования, в < ожидании не превышения ошибки на следующем шаге заданной точности. Такой алгоритм обеспечивает очень быстрый расчет с адаптивным шагом, вычисляемым на основании простых и нересурсоемких критериев (в отличие от правила Рунге). Существенным недостатком такого механизма является не столько эвристичность (применение всевозможных пороговых коэффициентов), сколько отсутствие обратной связи. Применение подобных алгоритмов интегрирование подсистем даже с равными шагами приводит к существенному приросту в скорости, обусловленному нелинейностью числа арифметических операций по отношению к размерности задачи.
Декомпозиция схемы только на математическом уровне не является осуществимой задачей на практике — матричные методы приведения к блочно-диагональной форме матриц являются ресурсоемкими. К указанной проблеме следует добавить невысокую функциональность методов, описывающих арифметику с разреженными матрицами. Зачастую такие методы обеспечивают только одно действие при работе с матрицами — Ш-разложение. Применение подобных методов возможно только для подматриц невысокой размерности. Существуют более реалистичные методы разбиения системы на кластеры, однако данные алгоритмы выходят за рамки данной работы. Поэтому существует острая потребность в совместном использования как структурных, так и математических декомпозиций.
Моделирование цифровых ИС требует особого внимания к точности расчетов. Погрешность численного решения может привести не только к неточному вычислению параметров1 схемы, но и к фатально неверной картине ее работы. Цифровые схемы представляют собой набор пороговых переключателей, поэтому напряжение, недотянутое в силу грубости расчета до порога переключения, может привести к кардинально неправильной логике работы схемы — на входе элементов устанавливаются принципиально другие состояния, и переключение частей упускается. Этот факт следует всегда иметь в виду, при выборе скорости/погрешности численного решения.
В работы не вошли задачи с большим разбросом мнимых собственных значений в линеаризованной матрице Якоби системы. Это задачи принципиально отличаются от жестких задач. Речь идет о разночастотных колебательных системах. Несмотря на важность решения подобного класса задач, современные тенденции направлены на ускоренное моделирование цифровых СБИС с отсутствием колебательных процессов. Наличие паразитных элементов в цепи является неотъемлемой составляющей современных схем нанометрового диапазона, они представляют собой необходимые связи между компонентами, которые при современной технологии уже нельзя рассматривать как идеальные узлы электрической схемы. Они моделируются обычно распределенными RC-цепочками (намного реже RLC). RC-цепи не приводят к колебательным процессам, они только увеличивают задержки сигналов и приводят к изменению фронтов импульсов. Это нельзя классифицировать как усиление связей между подсистемами.
Дальнейшее развитие работы планируется ориентировать на исследование устойчивости модифицированной разностной задачи. На текущий момент требуются контрольные расчеты, подтверждающие сходимость к точному рению, что имеет место во всех других подходах к проектированию в микроэлектронике. Как было указано в работе, на практических задачах наблюдалось повышение устойчивости.
