автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Метод ускорения численного решения систем ОДУ и его применение для программного комплекса моделирования сверхбольших интегральных схем



Корчак Антон Борисович

МЕТОД УСКОРЕНИЯ ЧИСЛЕННОГО РЕШЕНИЯ СИСТЕМ ОДУ И ЕГО ПРИМЕНЕНИЕ ДЛЯ ПРОГРАММНОГО КОМПЛЕКСА МОДЕЛИРОВАНИЯ СВЕРХБОЛЬШИХ ИНТЕГРАЛЬНЫХ СХЕМ

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

1 О НОЯ 2011

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

Москва-2011

4859468

Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета)

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

доцент

Евдокимов Алексей Витальевич

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

старший научный сотрудник Поляков Сергей Владимирович

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

Ширков Петр Дмитриевич

Ведущая организация: Институт автоматизации

проектирования РАН

Защита состоится в на заседании

диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

Автореферат разослан (С-^» /^уг^/^г^ 2011г.

Ученый секретарь диссертационного совета Д 212.156.0^, кандидат физико-математических наук

О.С. Федько

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

Актуальность темы.

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

Проектирование КМОП СБИС (Сверхбольших Интегральных Схем — до 1 миллиона элементов на кристалле — с Комплементарной логикой на транзисторах Металл-Окисел-Полупроводник) представляет собой независимое моделирование на электрическом, логическом и топологическом уровнях. Чисто электрический уровень, включающий в себя полное решение системы ОДУ, описывающей интегральную схему (ИС), не реализуем для задач большой размерности. Логический подход, обеспечивающий возможность полного моделирования с верификацией функциональности, теряет свою применимость при переходе на глубоко субмикронные и нанометровые полупроводниковые технологии. Для этих технологий рассмотрение ИС как цифровой схемы не представляется возможным — становятся существенными перекрестные помехи, индуктивность и сопротивление шин питания и «земли» и т.п. Все это приводит к потребности возврата на «медленный» электрический уровень моделирования и повышению актуальности проблемы ускоренного моделирования СБИС.

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

вычислительную модель для ускоренного моделирования КМОП СБИС с контролем точности.

Цели и задачи работы.

Целями диссертационной работы являются:

1) создание подхода к ускоренному распределенному моделированию динамических задач, описываемых системами ОДУ большой размерности, с контролем точности;

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

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

• разработка подхода к ускоренному численному решению динамических задач большой размерности;

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

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

• применение предложенного подхода для ускорения логико-электрического уровня моделирования интегральных схем с высокой достоверностью;

• создание системы компьютерного моделирования динамических задач в приложении к проектированию КМОП СБИС.

Объекты и методы исследования.

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

«Экспериментальная» часть работы проводилась на основании компьютерного моделирования. Большая часть результатов получена с помощью предложенной системы моделирования, реализованной на языке Java с применением современных информационных технологий. Система представляет собой комплекс программ для ускоренного моделирования КМОП СБИС, позволяющий контролировать точность вычислений. Комплекс включает в себя модуль загрузки данных ИС, модуль формирования системы ОДУ, расчетную программу для декомпозированной системы (с набором подключаемых к ней реализаций численных методов), а также поспроцессор. Сравнения проводились с данными, полученными при помощи пакетов Spectre Cadence, HSPICE Synopsys и AlfaSim ИППМ РАН.

Научная новизна.

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

• разработан новый подход к ускоренному моделированию декомпозируемых динамических задач, описываемых системами ОДУ, в котором ускорение достигается за счет дополнительной неустранимой погрешности — на уровне модели, а не численного метода;

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

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

• управление точностью расчета при ускоренном моделировании КМОП СБИС впервые осуществлено на базе детерминированных математических формул, что позволяет получать решение с высокой достоверностью — в отличие от существующих эвристических приемов ускорения.

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

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

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

• аналитическое исследование численного интегрирования в рамках подхода — исследование порядка аппроксимации, оценки

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

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

• обоснование применимости подхода для ускоренного моделирования КМОП СБИС нанометрового диапазона на логико-электрическом уровне под управлением заданной точности с совместным использованием структурной и блочно-матричной декомпозиций.

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

Теоретическая и практическая значимости.

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

С практической точки зрения, проведенные исследования могут быть полезны при автоматизации схемотехнического проектирования. В работе удалось решить ряд проблем, обычно возникающих при проектировании интегральных схем для технологий 90 нм и ниже, обеспечивая высокую достоверность результатов. Последнее обстоятельство очень важно для современного схемотехнического проектирования. Алгоритм расчета позволяет осуществлять более детальную декомпозицию по отношению к структурному уровню (БССС-декомпозиция), предоставляя возможность ускоренного моделирования задач с разветвленными шинами «земли» и питания, а также приблизиться к решению проблем оптимизации моделирования Ж-ёгор.

Апробация работы.

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

• 49-я-52-я научные конференция МФТИ «Современные проблемы фундаментальных и прикладных наук», ноябрь 2006-2009 гг., Москва.

• XV Международная конференции «Математика. Компьютер. Образование», январь 2007 г., Дубна.

• XXIII Международная научная конференция «Математические методы в технике и технологиях - ММТТ-23», июнь 2010 г., Саратов.

• Вторая окружная научно-техническая конференция молодых ученых и специалистов, февраль 2010 г., Москва.

• Вторая международная научная школа для молодёжи «Прикладные математика и физика: от фундаментальных исследований к инновациям», июнь 2011 г., Москва.

• Семинары кафедры вычислительной математики МФТИ, научные семинары ФУПМ (2008-2011 гг.).

Публикации.

Результаты по теме диссертационного исследования опубликованы в 14-ти работах:

• статей в журналах, рекомендованных ВАК для публикации материалов диссертации — 2 [11, 14],

• статей в прочих изданиях — 4 [4, 6, 8, 12],

• тезисов докладов на конференциях — 8.

Личный вклад автора.

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

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

Д.т.н. Гаврилов C.B., руководитель сектора автоматизации топологического проектирования Института проблем проектирования в микроэлектронике (ИППМ РАН), активно помогал автору в освоении моделей СБИС и других схемотехнических особенностей работы, а также в анализе и интерпретации результатов.

Связь с научными проектами.

В основу диссертационного исследования положены работы, выполненные в Московском физико-техническом институте

7

(государственном университете) и Институте проблем проектирования в микроэлектронике РАН в рамках проектов:

• МНТЦ №2143;

• РФФИ 09-07-00077-а.

Структура и объем диссертации.

Диссертация состоит из введения, пяти глав, заключения и списка литературы. Общий объем диссертации составляет 112 стр., содержит 55 рисунков, 2 таблицы и список литературы из 46 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В разделе введения «Существующие подходы» приводится обзор современного состояния методов ускоренного моделирования. Существующие подходы к решению больших систем условно можно разделить на два основных класса. Одни подходы сосредотачиваются на алгоритмах распараллеливания программного кода численных методов (причем безо всякого изменения самих методов), другие делают акцент на сокращении вычислительных затрат за счет специальных эвристических приемов (обычно вытекающих из «физики задачи»). Первый класс применительно к системам ОДУ не дает существенного прироста в скорости (по сравнению, например, с системами уравнений в частных производных). Во втором классе, характерном для некоторых прикладных областей (например, для микроэлектроники), меньшее внимание уделяется точности решения. Некоторое промежуточное положение занимают современные методы по многоскоростному (multi-rate) решению систем ОДУ. В них предлагаются различные формулы для расчета нескольких групп переменных, соответствующих различным шагам интегрирования (кратным друг другу), и экономия вычислительных затрат достигается за счет меньшего числа операций, требуемых для расчета «медленных» переменных (соответствующих большим шагам) в промежуточные моменты времени. Такие методы интегрирования достаточно хорошо изучены с точки зрения оценки точности. Как недостаток, экономия вычислительных ресурсов у них получается не слишком существенной, а вопрос о распараллеливании многоскоростных методов не рассматривается.

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

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

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

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

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

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

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

О = к ~Л> 0 = h-Л ~И -Уз.

0 = ^7-У2-У5. ° = У7 ~к-У5> 0 = У5+У'б-У4>

• dx2/dt= j2 -С2\ скъ jdt= j3 • C3_1, dx4 /dt= jA ■ Q1,

0 = x2-x4-R0-j5, 0 = x3-x4-Rrj6,

0 = x3-x2-R2-j1, 0 = xl-x3-R3-j&.

Для проектирования нелинейных элементов схемы — транзисторов — использовалась модель Shichman-Hodges (MOS level 1).

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

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

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

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

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

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

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

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

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

Определение 1. Общей подматрицей двух (линейных) систем называется матрица пересечения этих систем по общим неизвестным — матрица, составленная из коэффициентов перед неизвестными, входящими в оби системы уравнений.

Определение 2. Две системы называются слабосвязанными, если

1) ранг их общей подматрицы много меньше рангов матриц обеих систем,

2) степень связанности — норма общей подматрицы — много меньше норм обеих матриц.

Определение 3. Линейные слабосвязанные системы уравнений — системы, которые при помощи равносильных преобразований можно представить в виде совокупности подсистем, попарно слабосвязанных.

Определение 4. Нелинейными слабосвязанными системами уравнений называются системы, являющиеся слабосвязанными в линеаризованном представлении.

В случае с линейными системами можно дать более наглядную интерпретацию. Линейные слабосвязанные системы уравнений — системы, матрица которых приводится к блочно-диагональному виду. Ранг матриц блочного пересечения (см. рис. 2) определяет количество переменных, по которым две подсистемы слабо связанны между собой. Координаты матриц пересечения указывают на эти переменные. Нормы матриц определяют степени связанности подсистем.

Положим, что задача задается нестационарной системой (системой ОДУ), которую можно разделить на несколько нестационарных подсистем. Каждая подсистема или набор подсистем может решаться отдельным

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

У

(1)

Рис. 2 Пример приведения матрицы к блочно-диагоналыюму виду.

Рассмотрим задачу Коши для системы ОДУ

¿Л1Дй=1"(и,г),и(г0)=и0,иеЯ".

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

а) г,

б)

* ^ ***

г,

А ъ ! А : ! *

▲ А~ I А" А" 1 А" > А";

Решатель 1

Решатель 2

5 Решатель 3

Решатель I

Решатель 2

Решатель 3

Рис. 3 Схема решения в а) последовательном и б) параллельном режимах.

13

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

Следует обратить внимание на то, что при такой стратегии процессов синхронизации (прямой и обратной) макро-расчет представляет собой последовательный (или в некоторых случаях квази-последовательный) процесс (см. рис. За). Распараллеливание таких расчетов является бесполезным (или невозможным). Если теперь рассмотреть стратегию, в которой все решатели могут начинать свои макрошаги вычислений со «старыми» данными и обмениваться «новыми» лишь в конце макрошага, то мы получим строго распараллеливающийся расчет (см. рис. 36). Таким образом, появляется возможность проводить моделирование в многопроцессорных вычислительных средах, что не является свойственным для систем ОДУ (см. выше). Отрицательной стороной такой стратегии является то, что все решатели проводят вычисления, основываясь на устаревших значениях параметров других решателей.

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

Классический явный метод Эйлера без модификаций (кратность 1) имеет следующий вид

Тогда соотношения метода расчета с ускорением для случая кратности к в параллельном режиме (пример работы алгоритма для кратности 3 представлен на рис. 36) выглядит следующим образом.

'*я+1 = + кт(ахп + Ьукп), Укп+1 = Уь,+т{сх„+<&*„),

_ Укп+2 = Уш 1 + т{схп + &кп+1). , .

Укп+к-1 = Укп+к-2 + К^л + ^Укп+к-2 )> Ук(п+\) = Уь+к-1 + т(схп + ¿Укп+к-х}

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

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

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

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

В примере подробно рассматривается классический анализ «неклассического» метода, формируемого в рамках алгоритма. Для наглядности приводится явный метод Эйлера (1-ого порядка точности), выводится погрешность интегрирования.

При оценке погрешности будем предполагать, что система описывает поведение двух гетерогенных физических процессов — |6с|«\ас1\, а < 0 и

с1 <0. Для определенности Щ >|а|, что всегда можно получить перестановкой строк в матрице, компонента х будет являться «медленной», а у — «быстрой». Для собственных значений тогда справедливо |Дх|<|Лу|. В базисе из собственных векторов решение представляется в виде

хп=Схе'"х^-к1пЯ\Ф+о(г2\ уп =С2е'"Лу (\+1п((к-\)с12~кЛ2у}/2+о{т2)) Тогда погрешность численного метода (2) составляет &;=\Сх(„\е1"Л>кА1т12+о(т2) & =\с^„({к-\У ~кЯ)\е'^ ф+о(т2)

Погрешность «медленной» компоненты не превышает погрешность соответствующей компоненты классического метода Эйлера. Погрешность

«быстрой» компоненты дуп линейно растет с ростом кратности шагов по отношению к погрешности метода Эйлера при фиксированном шаге «быстрой» компоненты и пропорционально увеличивающимся шаге

«медленной»; скорость роста определяется разностью с12 -Я2у~Ьс/а-с1.

Однако при некоторых соотношениях параметров системы величина ду'п может быть существенно меньше погрешности, вносимой методом Эйлера — 'г/2. В таком случае условие на кратность шагов, при котором

погрешность модифицированного метода не будет превышать погрешность классического метода

к<\с!{а-(1)1Ъс\.

Из полученного результата видно, что чем больше разбегание скоростей процессов а-<1, тем большую кратность шагов можно использовать. Величина погрешности определяется степенью связности или разнородностью процессов, а именно произведением Ьс. Чем больше разнородность (меньше произведение Ьс), тем большую кратность шагов можно применять. Результаты позволяют судить о корректности предпосылок формирования подхода к ускоренному расчету систем ОДУ, а также создания алгоритма синхронизации. В том числе, следует еще раз подчеркнуть, что полученные выводы могут быть обобщены как на задачи любой размерности, так и на методы любого порядка, как явные, так и неявные.

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

Операторное представление дифференциальной задачи (1) имеет

/ ч / ч Ídu/dt-{(t,u),í>0, Í0,/>0,

следующий вид: ¿(u)=F, где ¿(u)=^ , ч и F=H .

W W [u(0),/=0; [u°,/=0.

Пусть исходная разностная задача записывается в виде Zr(uT)=Fr, где Lr — разностный оператор, Fr — проекция F на расчетную сетку. Модифицированную разностную задачу ускоренного моделирования обозначим как Z* (ur)=Fr. Имеют место следующие утверждения.

Утверждение 1. Если разностная задача ¿r(ur]-Fr аппроксимирует исходную дифференциальную задачу i(u)=F с порядком р, то модифицированная разностная задача для декомпозированной системы I*(ur)=Fr также аппроксимирует исходную дифференциальную задачу, при этом для порядка р метода справедливо соотношение 1 <р* <р. При равенстве шагов интегрирования порядки обеих разностных схем совпадают.

В диссертационной работе данное утверждение доказывается для схем явного метода Эйлера (1-ого порядка) и неявного метода трапеций (2-ого порядка). Экспериментально показывается падение порядка до 1 для метода Рунге-Кутты 4-ого порядка.

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

Утверждение 2. Если модифицированная разностная задача ZT(uT)=FT, основанная на аппроксимирующей численной схеме, устойчива, то для оценки погрешности решения применимо правило Рунге.

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

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

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

Суть подхода покажем на простой линейной интегральной схеме. Рассмотрим несложную КС-схему (см. рис. 4) с характерными значениями параметров элементов (ёмкостей на «землю» и сопротивлений), описываемую линейной системой ОДУ. Из параметров системы (см. рис. 5) видно, что она может рассматриваться как слабосвязанная с коэффициентом жесткости

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

У,

I I

19 ' .Л®» " — ^П Ун> | О^Уж-У* -З^ю -Л-1

у ^

° = Уп-Уп> ° = Ут 0=у^0Лу11-у6,

о=у$+олув~у2, 0=у,+0.2ул-уу

" У14*

у'5=1014уаг 0 = уа-уи,

о = у„ о~Ун

О = у, + 0.1уи - у4, 0 = у,+0Ау1,~у?, 0 = у2+0Лу1(1-уг

■Ум ~У> -У»>

Уп.

Рис. 5 Блочно-матричиая декомпозиция.

В рассматриваемом примере результаты декомпозиций (структурной и математической) совпали. Пунктирной линией выделены «медленная» подсхема и соответствующая подсистема уравнения, остальная часть — «быстрая» подсхема.

Ускорение

1.0 4

16

Кратность шагов

64

256

Рис. 6 Ускорение моделирования ИС для различных кратностей шагов.

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

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

а 3,ОЕ-04 _-2,9Е-04 ш 2,8Е-04 | 2,7Е-04 » 2,бЕ-04 ё 2,5Е-04 | 2,4 Е-04 « 2,ЗЕ-04

О.

о 2,2Е-04 С

0,0016 0,0014 -0,0012 0,001 й 0,0008 < 0,0006 £

0,0004 х 0,0002 1 О Г

с

—г

2 8 32

Кратность шагов

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

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

Рнс. 8 Декомпозиция внутри 1)ССС-блока.

20

На рис. 8 приведен пример ИС характерный для технологий 90 нм и ниже. Наличие подобных подсхем, представляющих собой неделимый ОССС-блок, служит серьезным препятствием для ускоренного моделирования. Подобный характер имеет схема с Ш-с1гор (падением напряжения на внутреннем активном сопротивлении), описанная во второй главе диссертационной работы. Особо остро эта проблема проявляется на схемам, состоящих более чем из 10000 элементов. Однако с математической точки зрения декомпозиция системы обеспечивает не только прирост в скорости расчета, но и повышает устойчивость разностной задачи.

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

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

О

-i b 1Е-11

8Е-12 а

' -♦-Рсшеиие

«Шаг интегрирования

6Е-12

4Е-12

5Е-09 1Е-08 1.5Е-08

Время, сек

2Е-08

к s

со о а.

Р

2Е-12 |

1—

ffi

n 3

Рис. 9 Выбор шага сетки (при кратности 1) для получения решения с точностью 2%.

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

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

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

2) Разработан алгоритм эффективного расчета ОДУ с возможностью проведения ускоренного распределенного моделирования с контролем точности, основанным на аналитическом исследовании численного интегрирования. Ускорение вносит дополнительную контролируемую неустранимую погрешность.

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

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

Публикации автора по теме диссертации

1. КорчакА.Б. Система интеграции гетерогенных моделей (расчетных программ) // Труды 49-й научной конференции МФТИ. Аэрофизика и космические исследования. — М.: МФТИ, 2006. С. 64-65.

2. Корчак А.Б. Решение слабосвязанных систем дифференциальных уравнений // Труды 50-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть VII. Управление и прикладная математика. Том 2. — М.: МФТИ 2007. —С. 129-131.

3. Корчак А.Б. Система интеграции гетерогенных моделей и ее применение к расчету слабосвязанных систем дифференциальных уравнений // Тезисы докладов XV Международной конференции «Математика. Компьютер. Образование». Дубна, 2007. — С. 86.

4. Корчак А.Б., Евдокимов A.B. Система интеграции гетерогенных моделей динамических систем // Моделирование и обработка информации. — М.: МФТИ, 2008. — С. 4-9.

5. КорчакА.Б. Метод расчёта расщеплённых систем дифференциальных уравнений с кратными шагами // Труды 51-й научной конференции

МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть VII. управление и прикладная математика. Том 2. — М.: МФТИ, 2008, —С. 124-128.

6. Корчак А.Б., Евдокимов A.B. Система интеграции гетерогенных моделей и ее применение к расчету слабосвязанных систем дифференциальных уравнений // Математика. Компьютер. Образование: Сб. научных трудов. Том. 2. Под ред. Г.Ю.Ризниченко и А.Б.Рубина. — М.-Ижевск: НИЦ "Регулярная и хаотическая динамика". 2008. — С. 140-149.

7. Корчак А.Б., Евдокимов A.B. Контроль точности ускоренного моделирования СБИС на электрическом уровне // Труды 52-й научной

, конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть VII. Управление и прикладная математика. Том 3. — М.: МФТИ, 2009. — С. 62-64.

8. Корчак А.Б., Евдокимов A.B. Система интеграции гетерогенных моделей и ее применение к расчету слабосвязанных систем дифференциальных уравнений // Компьютерные исследования и моделирование, т. 1, № 2. — 2009 —С. 127-136

9. Корчак А.Б., Евдокимов A.B. Алгоритм синхронизации решателей расщепленных систем дифференциальных уравнений при моделировании КМОП СБИС // XXIII Международная научная конференция «Математические методы в технике и технологиях — ММТТ-23» — Саратов, 2010. — С. 149-151.

10. Корчак А.Б. Моделирование КМОП СБИС с контролем скорости и точности // Тезисы докладов 2-ой окружной научно-технической конференции молодых ученых и специалистов. — М.-Зеленоград,

2010, —С. 24.

11. Корчак А.Б., Евдокимов A.B. Метод параллельного расчёта расщеплённых систем дифференциальных уравнений с кратными шагами // Труды МФТИ. - Том 2, №2 г. Долгопрудный, 2010. - С. 77-85.

12. Корчак А.Б., Гаврилов C.B., Евдокимов A.B. Метод ускоренного моделирования интегральных схем с оценкой точности // Информационные технологии моделирования и управления, №5 (70),

2011, —С. 534-543

13. Корчак А.Б. Ускоренное схемотехническое моделирование с контролем точности // Вторая международная научная школа для молодёжи «Прикладные математика и физика: от фундаментальных исследований к инновациям». Сб. научных трудов. — М.: МФТИ, 2011. — С. 56-58.

14. Корчак А.Б., Гаврилов C.B., Евдокимов A.B. Метод ускоренного моделирования интегральных схем с оценкой точности // Системы управления и информационные технологии — №3 (45), 2011, —С. 75-80.

Корчак Антон Борисович

МЕТОД УСКОРЕНИЯ ЧИСЛЕННОГО РЕШЕНИЯ СИСТЕМ ОДУ И ЕГО ПРИМЕНЕНИЕ ДЛЯ ПРОГРАММНОГО КОМПЛЕКСА МОДЕЛИРОВАНИЯ СВЕРХБОЛЬШИХ ИНТЕГРАЛЬНЫХ СХЕМ

Автореферат

Подписано в печать 24.10.2011. Формат 60 х 84'/16. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 95 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

ВВЕДЕНИЕ.

ГЛАВА 1. ПОДХОДЫ К ЧИСЛЕННОМУ РЕШЕНИЮ ЖЕСТКИХ СИСТЕМ ОДУ.

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

1.2. Методы Розенброка.

1.3. АМ-методы. Методы с неточной матрицей Якоби.

ГЛАВА 2. ОСОБЕННОСТИ МОДЕЛИРОВАНИЯ ИНТЕГРАЛЬНЫХ СХЕМ.

2.1. Особенности моделирования КМОП СБИС.

2.2. Логическое моделирование. Понятие БССС.

2.3. Электрический уровень моделирования.

2.4. Применение одношаговых методов при моделировании СБИС.

2.5. Подходы к ускоренному моделированию СБИС.

2.6. Транзисторные модели.

2.7. Проблема Ш.-с1гор.

ГЛАВА 3. АЛГОРИТМ УСКОРЕННОГО МОДЕЛИРОВАНИЯ.

3.1. Слабосвязанные системы дифференциальных уравнений.

3.2. Алгоритм расчета.

3.3. Комплекс программ.

ГЛАВА 4. АНАЛИЗ И ОБОСНОВАНИЕ ПОДХОДА.

4.1. Оценка погрешности на шаге для явного метода Эйлера для параллельного режима.

4.2. Исследование неявного метода Эйлера.

4.3. Устойчивость неявного метода Эйлера.

4.4. Исследование модифицированного метода трапеций.

4.5. Существующие методы контроля точности и применимость их для решения декомпозированных систем ОДУ.

4.6. Повышение порядка точности метода численного интегрирования.

ГЛАВА 5. ПРИМЕНЕНИЕ АЛГОРИТМА СИНХРОНИЗАЦИИ ДЛЯ КМОП СБИС.

5.1. Анализ вычислительных затрат.

5.2. Линейная интегральная схема «а rc2 R2».

5.3. Нелинейная интегральная схема «chain».

На сегодняшний день все более актуальными становятся задачи моделирования реальных технических, физиологических, экономических и др. процессов, описываемых системами обыкновенных дифференциальных уравнений (далее ОДУ). Размерность таких систем может достигать высоких порядков. Как следствие подавляющее большинство таких задач требуют высокопроизводительные вычисления, при этом повышается потребность в методах ускоренного и распределенного моделирования; Одной из областей, остро нуждающихся в новых подходах к моделированию, является быстро развивающаяся-микроэлектроника (см. 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-цепи не приводят к колебательным процессам, они только увеличивают задержки сигналов и приводят к изменению фронтов импульсов. Это нельзя классифицировать как усиление связей между подсистемами.

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

1. ЭндрюсГ. Основы многопоточного параллельного и распределенного программирования. — Москва, Санкт-Петербург, Киев, 2003.Эндрюс Г.

2. Денисенко В. Проблемы схемотехнического моделирования КМОП СБИС. — Компоненты и технологии, 2002, № 3^4.9

3. Фельдман JI. П., Дмитриева О. А. Эффективные методы распараллеливания численного решения задачи Коши для обыкновенных дифференциальных уравнений // Матем. моделирование, 2001, том 13, номер 7, страницы 66-72.

4. Crow M.L., Chem James G. The multirate methods for simulations of power system dynamics // IEEE Transactions on Power System — 1994. Vol. 9, N. 3 — pp. 1684-1690.

5. Siddhartha S. Shome, Edward J. Haug, Laurent O. Jay. Dual-rate integration using partitioned Runge-Kutta methods for mechanical systems with interacting subsystems // Mechanics based design of structures and machines — 2004, Vol. 32, N. 3—pp. 253-282.

6. Andrus J.F. Automatic Integration of systems of second-order ODE's separated into subsystems. — SIAM Journal on Numerical Analysis, Vol. 20, No. 4, pp. 815-827, 1983.

7. Skelboe S. Adaptive partitioning techniques for ordinary differential equations // BIT NumericabMathematics, 2006.

8. Gear C.W. Numerical' solutions of ODE: is there anything left to do? — SIAM Review. 1981. vol 23. N I; p. 10—24.

9. Русаков С.Г. Применение одношаговых методов1 интегрирования при моделировании переходных процессов в БИС. 1987.

10. Newton A.R. Techniques for the simulation of large scale IS. — IEEE Trans, on CAS, 1979, vol. CAS—26, p. 741—749:

11. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. — М.: Мир, 1999. —685 с.

12. Хайрер Э., Нерсетт С., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Нежесткие задачи. — М.: Мир, 1990. — 512 с.

13. Федоренко Р.П. Введение в вычислительную физику. М.: Изд-во МФТИ, 1994, 526 с.

14. МарчукГ.И. Вычислительные процессы и системы. Вып. 8. М.: Наука, 1991. 380 с.

15. Rosenbrock Н. Н. Some general implicit processes for the numerical solution of differential equations //Computer, 1963. №5. P. 329-330.

16. SteihaugT., Wolfbrandt A. An Attempt to Avoid Exact Jacobian ad Nonlinear Equations in the Numerical Solution of Stiff Differential Equations. Mathematics Of Computation, Volume 33, Number 146, 1979, P: 521-534.

17. ДеккерК., Вервер Я. Устойчивость методов Рунге-Кутты для жестких нелинейных дифференциальных уравнений. — Москва, «Мир», 1988.

18. Ширков П.Д. AN-устойчивость ROW методов. // Препринт Института прикладной математики им. М.В. Келдыша РАН, № 16, 2001. сс. 20.

19. Точчи Р.Дж., Уидмер Н.С. Цифровые системы. Теория и практика. Москва; С.-Петербург; Киев: Вильяме, 2004.

20. Meinel Ch., Theobald Th. Algorithms and data structures in VLSI design // Berlin: Springer-Verlag, 1998, 268 p.

21. Bryant R.E. A Switch-Level Model and Simulator for MOS Digital Systems // IEEE Trans, on Computers, 1984. Vol. 33. P. 160.

22. Стемпковский A.JI., Гаврилов C.B., Глебов А.Л. Методы логического и логико-временного анализа цифровых КМОП СБИС; Ин-т проблем проектированиям микроэлектронике РАН. — М.: Наука, 2007. — 220 с.

23. Петров И.Б., Лобанов А.И. Лекции по вычислительной математике. — М.: Интернет-Университет Информационных технологий; Бином. Лаборатория знаний, 2006. — 523 с.

24. Cadance. Cadence Device Model Reference, Cadence Design Systems, Inc. 2007.

25. Yang P., Chattejee P.K. Spice Modeling for Small Geometry MOSFET Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems CAD-1 (No. 4) 1982. —pp. 169-182.

26. Spectre. Components and Device Models Manual. Virtuoso® Spectre® Circuit Simulator. 2004

27. Базилевич Ю.Н., Коротенко JI.M., Швец И.В.Численное решение задач иерархической декомпозиции линейных математических моделей // Мтждержавна наукова-методична конференщя. Комп'ютерне моделювання.

28. Дншродзержинськ: ДДТУ, 2001. — С. 45-46.

29. Баталов Б.В., ЕгоровЮ.Б., Русаков С.Г. Основы математического моделирования БИС на ЭВМ. — М.: Радио и связь, 1982.— 108 с.

30. Ismail F., Al-Khasawaneh R.A. SuleimanMl Embedded Pair of Diagonally Implicit. Runge-Kutta Method for Solving Ordinary Differential Equations. — Malaysians: Sains, 2010— 1049-1054 p.

31. Корчак А.Б. Система, интеграции гетерогенных моделей (расчетных программ) // Труды 49-й научной конференции МФТИ. Аэрофизика и космические исследования. — М.: МФТИ, 2006. С. 64 65.

32. Корчак А.Б;, Евдокимов A.B. Контроль точности ускоренного моделирования: СБИС на электрическом уровне // Труды: 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»:'Часть VII. Управление и прикладнаяматематика. Том 3.

33. М.: МФТИ,.2009; — С. 62-64.

34. Корчак А.Б., Евдокимов A.B. Система интеграции гетерогенных моделей и ее применение к расчету слабосвязанных . систем дифференциальных уравнений // Компьютерные исследования и моделирование, т. 1, № 2. — 2009 —С. 127-136

35. Корчак А.Б. Моделирование КМОП СБИС с контролем скорости и точности // Тезисы докладов 2-ой окружной научно-технической конференции молодых ученых и специалистов. — М.-Зеленоград, 2010. — С. 24.

36. Корчак А.Б., Евдокимов A.B. Метод параллельного расчета расщепленных систем дифференциальных уравнений с кратными шагами // Труды МФТИ. Том 2, №2 г. Долгопрудный, 2010. - С. 77-85.

37. Корчак А.Б., Гаврилов C.B., Евдокимов A.B. Метод ускоренного моделирования интегральных схем с оценкой точности // Информационные технологии моделирования и управления, №5 (70), 2011. — С. 534-543

38. Корчак А.Б., Гаврилов C.B., Евдокимов A.B. Метод ускоренного моделирования интегральных схем с оценкой точности // Системы управления и информационные технологии — №3 (45), 2011. — С. 75-80.