Решение некоторых задач математической физики методами Монте-Карло

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

.

С расширением использования сверхбольших интегральных схем и развитием высокочастотной электротехники значительное влияние на работу электронных систем стали оказывать значения паразитных элементов сопротивления, индуктивности и ёмкости. Для вычисления паразитных элементов и определения их влияния на части системы на различных этапах проектирования и изготовления разрабатываются системы автоматизированного проектирования микроэлектромеханических систем (Microelectromechanical Computer-Aided Design system, MEMCAD) [1]. Основными элементами таких систем являются: программа для моделирования структуры объекта (structure Simulator), база данных со свойствами материалов, модуль механического анализа и модуль электростатического анализа (рис. 0.0.1, [1]). В зависимости от методов, используемых при электростатическом и механическом анализе, трёхмерная модель может Рис о.0.1. Архитектура являться приближением исходного объекта с помощью тех или иных примитивов геометрических, объектов со схожими свойствами и пр.), так и выражать.

База данных материалов.

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

Так как при проектировании схем может потребоваться моделирование сотен или даже тысяч различных их конфигураций, к программам, вычисляющим значения паразитных параметров, выдвигаются высокие требования по быстродействию и точности вычислений. Аналитическое решение данной проблемы возможно лишь в случае небольшого количества проводников достаточно простой формы (параллелепипеды, сферы, цилиндры), поэтому для оценки взаимных электростатических ёмкостей трёхмерных систем из большого количества объектов, требуется применение тех или иных способов численного решения этой задачи [2−13].

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

Знание первого собственного числа для оператора Лапласа может потребоваться для оценки применимости различных алгоритмов решения краевых задач, например, при решении задачи Гельмгольца с помощью «блуждания по шарам и сферам». В работе рассматриваются алгоритмы нахождения оценок итераций оператора Грина для оператора Лапласа и первого собственного числа для оператора Лапласа. Исследуется возможность использования оценок итераций оператора Грина для расширения области применимости методов Монте-Карло при решении уравнения Гельмгольца.

Использование метода Монте-Карло для решения описанных задач позволяет заметно упростить реализацию алгоритма для параллельного вычисления, в том числе на графических видеопроцессорах (General Purpose Graphical Processing Unit, GPGPU), и не требует значительных затрат для хранения промежуточных данных.

Цели работы.

• Разработка алгоритмов вычисления взаимных электростатических ёмкостей методами Монте-Карло.

• Исследование оценок итераций оператора Грина с целью вычисления первого собственного числа оператора Лапласа и решения уравнения Гельмгольца.

• Реализация перечисленных алгоритмов для вычислений с использованием MPI-кластеров и графических процессоров общего назначения (видеокарт).

• Создание программного комплекса, упрощающего «обычную» и «параллельную» реализацию указанных программ.

Методика исследования.

Методика исследования включает применение методов статистического моделирования к решению краевых задач математической физики. С помощью формул Грина краевые задачи сводятся к интегральному уравнению, которое затем решается методом Монте-Карло. При решении уравнения Гельмгольца используется аналитическое продолжение решения методом замены переменных [14]. Для нахождения первого собственного числа краевых задач используются известные итерационные методы [15]. Реализация алгоритмов выполнена на языке программирования С++ с использованием реализации MPI MPICH-2 [16] и технологии CUDA [17].

Практическая значимость.

Разработанные статистические алгоритмы вычисления взаимных электростатических ёмкостей проводников могут быть использованы для оценки паразитных электростатических ёмкостей в больших и сверхбольших интегральных схемах и многослойных печатных платах. Проведены вычислительные эксперименты для алгоритмов, использующих методы Монте-Карло при решении задачи Дирихле для уравнения Гельмгольца. Рассмотрены различные методы вычисления итераций оператора Грина методами Монте-Карло. Проведены вычислительные эксперименты, позволяющие оценить возможность использования аналитического продолжения решения методом замены переменных. Представлены новые алгоритмы вычисления оценок первого собственного числа для оператора Лапласа с помощью оценок степеней оператора Грина. Разработан программный комплекс для реализации вычислительных задач, использующих методы Монте-Карло. Программный комплекс позволяет упростить реализацию и проведение вычислительных экспериментов как на выделенных компьютерах, так и на МР1-кластере или графическом процессоре общего назначения.

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

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

• пятой Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи» (СамГТУ, Самара, 29−31 мая 2008 г.);

• II ежегодном смотре-сессии аспирантов и молодых учёных по отраслям наук. Секция «Математика. Информатика. Методика преподавания» (Вологда, 12−14 ноября 2008 г.) — в научной школе-конференции молодых исследователей «Математические идеи П. Л. Чебышева и их приложение к современным проблемам естествознания» (Обнинск, 14−18 мая 2011 г.).

Основные результаты опубликованы в работах [18−21].

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

Диссертация состоит из введения, 4-х глав, заключения и списка литературы.

Заключение

.

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

• Разработан новый универсальный стохастический алгоритм вычисления взаимных электростатических ёмкостей с помощью «блуждания по сферам». Алгоритм не требует того, чтобы границы объектов были плоскими. В случае же, если все или часть границ являются плоскими, «блуждание по сферам и полусферам» позволяет ускорить вычисления и повысить точность расчётов за счет построения несмещённой оценки.

• Проведены вычислительные эксперименты для алгоритмов, использующих методы Монте-Карло при решении задачи Дирихле для уравнения Гельмгольца.

• Рассмотрены различные методы вычисления итераций оператора Грина методами Монте-Карло. Представлены новые алгоритмы вычисления итераций оператора Грина.

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

• Представлены новые алгоритмы вычисления оценок первого собственного числа для оператора Лапласа с помощью оценок степеней оператора Грина.

• Выполнена реализация рассмотренных алгоритмов для вычисления на МР1-кластере.

• Для алгоритмов оценки первого собственного числа выполнена реализация вычислений на GPU (графических процессорах общего назначения).

• Реализован программный комплекс, упрощающий (параллельную) реализацию вычислений методами Монте-Карло.