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

Мамзин Евгений Анатольевич

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

05.13.18 – математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Тольятти – 2011

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

Научный руководитель: доктор технических наук, доцент, Лиманова Наталия Игоревна

Официальные оппоненты: доктор физико-математических наук, профессор, Лобанов Алексей Иванович доктор физико-математических наук, профессор, Леонтьев Виктор Леонтьевич

Ведущая организация: ГОУ ВПО «Самарский государственный университет», г. Самара

Защита диссертации состоится «30» июня 2011 года, в 13.00 часов, на заседании диссертационного совета Д 212.264.03 в ГОУ ВПО «Тольяттинский государственный университет» по адресу: 445667, Тольятти, ул. Белорусская, 14, Г-208 (зал заседаний).

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

Автореферат разослан « » мая 2011 г.

Учёный секретарь диссертационного совета Д 212.264.03 к.п.н. Пивнева С.В.

Общая характеристика работы

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

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

В настоящее время наибольшее применение клеточные автоматы нашли в задачах моделирования гидро- и газодинамических, эволюционных, поведенческих, колебательных и различных вероятностных процессов, что обусловлено сравнительной простотой их реализации, предрасположенностью к распараллеливанию и большими перспективами дальнейшего использования. Вопросам применения клеточных автоматов посвящены исследования многих отечественных и зарубежных учёных. Среди них Малинецкий Г.Г., Шакаева М.С., Лобанов А.И., Биндера К., von Neumann J., Martin O., Toffoli T., Margolus N., Wolfram S., Moore F., Cipra B., Gacs P., Gardner M., Gutowitz H. и др.

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

Работы по теме диссертации выполнялись в рамках реализации аналитической ведомственной целевой программы Министерства образования и науки РФ «Развитие научного потенциала высшей школы (2009-2010 годы)»

по мероприятию 1 (№ темы 1.2.09).

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

Основные задачи

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

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

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

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

Проведение вычислительных экспериментов на основе разработанных моделей неоднородных динамических систем.

Объект исследования В качестве объектов исследования выбрано несколько конкретных задач моделирования неоднородных динамических систем:

1. Моделирование колебательных процессов на поверхности вязкой жидкости без учета близости дна.

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

3. Моделирование порообразования в неравновесных малых металлических частицах.

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

Методы исследования В качестве аппарата исследований применялись методы вычислительной математики и математической физики, использовались методы численного анализа, математическое и компьютерное моделирование.

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

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

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

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

5. Проведены вычислительные эксперименты на основе разработанных моделей неоднородных динамических систем.

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

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

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

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

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

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

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

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

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

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

1. V Всесибирском конгрессе женщин-математиков (в день рождения С.В.Ковалевской) (Красноярск, 2008).

2. Международной междисциплинарной научной конференции «Четвертые Курдюмовские юбилейные чтения: «Синергетика в естественных науках» (Тверь, 2008).

3. XVII Международной конференции «Физика прочности и пластичности материалов» (Самара: СамГТУ, 2009).

4. Всероссийской конференции «Многомасштабное моделирование процессов и структур в нанотехнологиях» (Москва, 2009).

5. Научно-практической конференции «Инновации в условиях развития информационно-коммуникационных технологий» (Сочи, 2008, 2009).

6. IV Международной школе «Физическое материаловедение» (Тольятти, 7. Седьмой Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи» (Самара, 8. Второй Международной научной конференции «Моделирование нелинейных процессов и систем» (Москва, 2011).

Публикации По теме диссертации опубликовано 14 работ, из них 4 – в изданиях, рекомендованных ВАК.

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

Общий объем диссертации составляет 152 страницы.

Основное содержание работы

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

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

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

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

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

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

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

Проведено исследование работы клеточных автоматов с использованием реконфигурируемого шаблона и без его использования для всех типов сеток:

для клеточного автомата на квадратной сетке были рассмотрены двухтактные реконфигурируемые шаблоны для окрестностей Неймана и Рис. 1. Двухтактные реконфигурируемые шаблоны клеточного автомата на квадратной сетке для окрестности Неймана (а) и Мура (б) для клеточного автомата на гексагональной сетке рассмотрены двухтактный и трехтактный реконфигурируемые шаблоны.

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

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

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

Границы области моделирования являются неподвижными ячейками, в которых значения величин отклонения от положения равновесия u t j 0, в остальных случаях значение данной величины определяется в два этапа:

1. на первом этапе рассчитывается скорость движения каждой ячейки моделируемой области. Для расчета с помощью клеточного автомата на квадратной сетке формула будет иметь следующий вид:

Здесь v i, j, vi,j1 - скорость движения ячейки с координатами i, j в момент времени t, t 1 соответственно; u t j - величина отклонения амплитуды от поi, ложения равновесия ячейки с координатами i, j в момент времени t ; A - коэффициент, отражающий характер распространения волны; d - элементарный временной интервал – продолжительность одной итерации;

рестности Неймана.

2. на втором этапе выполняется расчет отклонения от положения равновесия каждой ячейки моделируемой области. Для клеточного автомата на квадратной сетке:

Данный клеточный автомат реализован на всех рассмотренных типах сеток с применением и без применения реконфигурируемых шаблонов.

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

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

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

4(б)). Исследуемым параметром здесь является продолжительность расчетов для моделей на всех типах регулярных сеток для разных площадей области моделирования. Результаты проведенных вычислительных экспериментов представлены на рисунках 5 и 6.

Рис. 5. График зависимости продолжительности расчетов от площади области моделирования На рисунке 5 приведены результаты исследования быстродействия разработанных моделей для шести типов клеточных автоматов: 1 и 2 – квадратные клеточные автоматы с окрестностью Неймана без реконфигурируемого шаблона и с его использованием; 3 и 4 – шестигранные клеточные автоматы;

5 и 6 – четырехгранные клеточные автоматы с окрестностью Мура. Здесь время T измеряется в секундах, а под площадью S области моделирования понимается количество ячеек с порядком 10 3.

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

Если за эффективность вычислений в данном случае взять отношение площади области моделирования к затраченному времени, то получим зависимость, представленную на рисунке 6.

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

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

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

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

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

1. Модель структуры первого типа строилась на основе неоднородного уравнения диффузии без учета неоднородного поля напряжений, но с учетом стоков на дисклинационном ядре частицы и её поверхности. В основу моделирования релаксационных процессов была положена диффузионнодеформационная модель, согласно которой начальное состояние частицы характеризуется избыточной концентрацией вакансий, неоднородным по объему значением коэффициента диффузии, что связано с наличием внутренних и внешних границ, на которых диффузия (самодиффузия) протекает гораздо активнее, чем в областях с кристаллической фазой. Рассмотрим неоднородное уравнение диффузии:

Здесь C (r,t) - концентрация вакансий в точке с радиусом-вектором r в момент времени t, D (r ) - коэффициент диффузии, qe (r,t) - плотность источника-стока, являющаяся заданной функцией.

Уравнение диффузии становится неоднородным, когда в объеме, где происходит чистая диффузия, имеются внешние источники-стоки диффундирующего компонента.

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

Здесь характеризует скорость вакансий на границе, (r ) характеризует распределение механических напряжений по объему частицы.

Коэффициент самодиффузии экспоненциально зависит от температуры (соотношение Аррениуса):

Здесь D0 - фактор диффузии, Ea - энергия активации, R - универсальная газовая постоянная.

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

Выбор граничных и начальных условий определялся физикой процесса и морфологией частиц. Граничные условия задавались в зависимости от состояния поверхности частицы в начальный момент времени - ее температуры, структуры и свойств, граничащей с ней фазы. Простейший случай статических граничных условий - граничные условия 1-ого рода: внешняя поверхность – поверхность стока вакансий Cv (rb,t) = 0. Здесь rb задавалось уравнением поверхности частицы.

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