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

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

Медведев Юрий Геннадьевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ТРЕХМЕРНОЙ КЛЕТОЧНО-АВТОМАТНОЙ МОДЕЛИ ПОТОКА ВЯЗКОЙ ЖИДКОСТИ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Новосибирск — 2005

Работа выполнена в Институте вычислительной математики и математической геофизики СО РАН

Научный руководитель:

доктор технических наук Бандман О.Л.

Официальные оппоненты:

доктор технических наук Пяткин В.П. кандидат технических наук Тарков М.С.

Ведущая организация:

Томский государственный университет

Защита состоится 29 июня 2005 г. в 15 часов на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, г. Новосибирск, пр-т Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан 26 мая 2005 г.

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

Сорокин С.Б.

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

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

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

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

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

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

Задачи. В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

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

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

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

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

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

Методы исследования. При проведении исследований использовался аппарат дискретной математики, теории автоматов, параллельного программирования и теории вероятностей, а также вычислительный эксперимент на одно- и многопроцессорных ЭВМ.

Научная новизна. В ходе исследования были получены следующие новые результаты:

- предложена новая трехмерная клеточно-автоматная модель, названная 1Ш-1, отличающаяся от известных моделей много меньшей сложностью;

- получены соотношения между физическими и модельными параметрами, сопоставляющие результаты моделирования с реальными величинами, характеризующими моделируемый поток;

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

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

Практическая значимость работы. Предложенная

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

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

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

Основные положения, выносимые на защиту.

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

2. Сложность граничных условий модели 1Ш-1 (включая случаи с пористыми средами) не оказывает существенного влияния на вычислительную сложность алгоритма.

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

4. Созданный программный комплекс эмулирует эволюцию клеточного автомата модели 1Ш-1 как на последовательных ЭВМ, так и на многопроцессорных вычислительных комплексах.

Реализация результатов работы. Работа выполнена в соответствии с темой N 25 «Исследование физических и информационных процессов с использованием моделей мелкозернистого параллелизма» (Ы госрегистрации 01.20.00.04430) плана научно-исследовательских работ отдела математического обеспечения высокопроизводительных вычислительных систем института вычислительной математики и математической геофизики СО РАН.

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на конгрессе по прикладной и индустриальной математике (Новосибирск, 1998), на конференции, посвященной 70-летию Сибирского физико-технического НИИ (Томск, 1998), на конференции с международным участием «Новые информационные технологии в исследовании дискретных структур» (Томск, 2000), на международной конференции по вычислительной математике (Новосибирск, 2001), на конференции «Моделирование неравновесных систем» (Красноярск, 2001), на Сибирской научной школе-семинаре по параллельному программированию (Томск, 2001), на конференциях молодых ученых ИВМиМГ (Новосибирск, 1999; 2002; 2004), на конференциях с международным участием «Новые информационные технологии в исследовании сложных структур» (Томск, 2002; Иркутск, 2004), а также на семинарах отдела математического обеспечения высокопроизводительных

вычислительных систем и отдела математических задач геофизики ИВМиМГ СО РАН.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы. Содержание диссертации изложено на 108 страницах, содержит 41 иллюстрацию и 8 таблиц. Библиографический список включает 127 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Клеточно-автоматные методы моделирования потоков появились около 20 лет назад и с тех пор получили большое развитие. Первыми моделями были двумерные модели: НРР-модель (Hardy,

Pazzis, Pomeau) с четырьмя соседями в клеточном автомате и FHP-модель (Frish, Hasslacher, Pomeau) с шестью соседями. Были попытки моделировать трехмерные потоки псевдочетырехмерными FCHC моделями (Face Centered Hyper Cubic) с 24-27 соседями, но они оказались практически неприменимыми в силу своей сложности (227 состояний элементарного автомата). Также известны менее сложные трехмерные модели, например, модель с 14 соседями, но они не являются чистыми клеточно-автоматными моделями, так как оперируют, в том числе, и с вещественными аргументами, тем самым, повышая сложность вычислений и внося ошибки округления.

Первая глава диссертации посвящена изложению общих принципов построения клеточно-автоматных моделей. Состояние s клетки w е W (W - множество клеток автомата) в момент времени t однозначно определяется набором некоторых гипотетических частиц, обладающих следующими свойствами.

1. Масса частицы единична m = 1.

2. Модуль вектора скорости частицы единичный |с| = I либо нулевой \с\ = 0. Частицы с нулевым вектором скорости называют частицами покоя.

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

4. В один момент времени в одной и той же клетке w не может быть двух или более частиц с одинаковыми векторами скорости с.

Таким образом, состояние клетки w можно представить булевым вектором s = (s\, ..., st, ..., s h) длины b = bm + br, где bm ~ количество соседних клеток, br - количество частиц покоя. Каждый 1-й разряд вектора s (/ = 1, ..., bm) определяет наличие или отсутствие частицы с вектором скорости С/, направленным к /-му соседу Ni (w).

Количество соседей у клетки - одна из важнейших характеристик модели. Она определяет размер q таблицы переходов элементарного автомата: q = к ■ 2Ь, где к - количество различных вариантов перехода для каждого входа. В детерминированных моделях к = 1. Количество клеток-соседей для НРР модели равно 4, для FHP-модели — 6, для FCHC-модели — 24. НРР-модель является детерминированной, FHP и FCHC модели — вероятностными.

Поведение элементарного автомата определяется следующими правилами. Каждый такт работы клеточного автомата разбит на две фазы: столкновение и сдвиг. Функция переходов S элементарного автомата А состоит, таким образом, из композиции функций Si (столкновение) и ô2 (сдвиг), т.е. S(s) = (52(<5i(s)). Каждая из этих функций

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

В фазе сдвига каждая частица перемещается на одну клетку в направлении вектора ее скорости

яг'М = Чъ'МО)),'(ад),\NbJw))), где '(Щ™)) ~ состояние после столкновения 1-го соседа клетки ил Значение функции сдвига 32 определено для каждого разряда вектора •52'0) = (521 яя, • • •, Ы') следующим образом.

,, = Для / = 1,2,.„А,

21 К/М, тя1 = Ьт,Ьк^,...,Ь где - /-й разряд вектора состояния /-го соседа клетки и» (его

вектор скорости с, направлен в сторону клетки и>).

В фазе столкновения происходит изменение состояния клеток автомата согласно некоторым правилам столкновения, не зависящим от состояний соседних клеток, т.е. 8\ зависит только от внутреннего состояния своего элементарного автомата, V = ¿1(5). На рис. 1 приведены правила столкновений для НРР модели (рис. 1а) и РНР модели (рис. 16 и 1в). Функция <5| выбирается такой, чтобы сохранялись масса и импульс частиц в клетке.

При моделировании потоков практический интерес представляют осредненные значения скоростей (и) и концентраций (п) по некоторой окрестности Ау(м>), которая для двумерных моделей имеет форму 6,,,-угольника, где Ь„, - количество соседей (рис. 3).

(и)=тттт 2 2е»' (")=итт 2 гапё(5)'

где Иу(>у)| - количество клеток, попадающих в окрестность осреднения, с, - вектор скорости, соответствующий 1-му разряду вектора состояния 5 клетки, принадлежащей окрестности осреднения Av(w), -

количество единиц в векторе

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

о

■е-

-е-

о

е-

-э

-©-

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

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

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

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

Состояние каждой клетки автомата вектор скорости для РНР может быть описано булевым вектором .г ~~ модели.

..., ^¡з), я, е {0, 1}, каждый компонент которого указывает на наличие или отсутствие в клетке частицы с определенным вектором скорости. В Декартовой системе координат клеточный автомат расположен таким образом, что углы между направлениями векторов скорости частиц и координатными осями составляют либо 90°, либо 45°. Поэтому проекции единичных векторов на Декартовы оси равны либо 0, либо 0.707 соответственно.

Рис. 1. Правила столкновения для двумерных моделей а) НРР модель, б,в) FHP модель.

В различных модификациях модели возможны различные варианты правил столкновения, но во всех случаях, разумеется, должны выполняться законы сохранения массы и импульса. В проведенных с моделью экспериментах использовался полный набор правил с одной частицей покоя. Так как в структуре решетки модели 12 соседей и одна частица покоя, то число входных состояний равно 213. Каждому /-му из этих 8192 входных состояний таблицы переходов автомата соответствуют все такие выходные состояния, у которых суммарные масса и импульс частиц в клетке не изменяются при столкновении. Эти

наборы из п, выходных состояний (/ = 1,2.....

ч,!^, ..., 56) и приняты за правила столкновения с

вероятностью срабатывания каждого варианта 1 !п,.

Одно из преимуществ клеточно-автоматных моделей — это простые граничные условия. Они задаются введением в модель клеток, поведение которых отличается от описанного в первой главе. Определены следующие типы клеток: рабочие клетки, клетки-стенки и клетки-источники частиц. Автоматы каждого из этих типов имеют различные таблицы переходов. Фаза сдвига в клетках всех типов происходит одинаково, различия поведения есть только на фазе столкновения. Поведение рабочих клеток описано в первой главе диссертации. В клетках стенки частицы «отражаются» по различным правилам, определяющим свойства стенки, нарушая при этом закон сохранения импульса. Для стенок с трением законом отражения является изменение всех векторов скорости частиц на противоположные. Именно такие стенки были использованы в экспериментах, описанных в четвертой главе диссертации. В клетках-источниках происходит генерация частиц, нарушая закон сохранения массы. В каждой клетке-источнике с некоторой вероятностью появляются частицы со всевозможными направлениями вектора скорости. Выстроив такие клетки в пространстве в одной плоскости, можно получить источник равномерного потока частиц. Изменяя вероятность рождения частиц, можно варьировать концентрацию частиц в потоке. Таким образом, стенки и источники определяют граничные условия автомата. Из правил поведения автомата следует, что объем вычислений при моделировании зависит только от общего

штшттттятшт

Рис. 3 Поле скорости ламинарного потока, полученное в результате эксперимента с ИНР моделью.

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

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

Важными параметрами клеточно-автоматных моделей потоков являются модельная вязкость \мид и структурный коэффициент вносящий поправку на дискретность модели. На основе известных общих соотношений выведены формулы подсчета этих параметров для предложенной трехмерной модели. Модельная вязкость вычисляется как функция проекций векторов скоростей на декартовы оси, попарные произведения которых определяют компоненты модельной величины внутреннего трения. у =__!___к, где параметр Я имеет вид

а, Р е {х,у,г}, с,а и с,р - проекции вектора с, на оси а и /?, дц - символ Кронекера, а Ач - вероятность перехода из я, в вычисляемая по формуле

2 ДГ

вероятность перехода из 5 в п - концентрация модельных частиц (число единиц в векторе .у), = п / 13 - относительная концентрация модельных частиц.

Для подсчета модельной вязкости по этим формулам была создана специальная программа. На ее вход подавались правила столкновения, которые использовались при моделировании и концентрация частиц, а на выходе получалась модельная вязкость. Результаты работы этой программы для концентраций от п - 0.25 до п = 12.75 с шагом 0.25 приведены на рис. 4. Из графика видно, что на рабочем участке концентрации (от 4 до 9) модельная вязкость лежит в пределах 0.11-0.12 и практически не изменяется. Это дает возможность при расчетах принять модельную вязкость за константу равную 0.115.

5Я 10

Зависимость коэффициента g от концентрации модельных частиц для предложенной трехмерной модели сводится к виду

13-2 п

*(и) = 0.65 •В

0,25 1,5 2,76 4 5.26 6,6 7,75 9 10.311,612,В Концентрация модельных частиц

Рис. 4. Модельная вязкость

13-и

третьей главе

диссертации представлен

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

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

Правша столкновения представляют собой таблицу Булевых векторов, каждая строка которой соответствует какому-либо состоянию клетки в момент времени X и содержит набор состояний, в которые может перейти автомат в момент времени / + 1.

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

Проекции поля скоростей строятся в некоторых сечениях автомата, ортогональных . декартовым осям.

✓ Генератор правил

! столкновения формирует

набор правил, по которым jf взаимодействуют частицы

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

правила впоследствии автоматной модели потока жидкости

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

Конструктор граничных условий формирует начальную конфигурацию автомата. Используется один раз в начале процесса моделирования.

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

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

Один из модулей программного комплекса — симулятор ■у трехмерного потока — имеет две реализации: последовательную и

параллельную. Параллелизм реализован следующим образом. Массив, в котором хранится конфигурация клеточного автомата, разрезается на 1 слои вдоль координаты X (рис. 6) с перекрытием, изображенным

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

Генератор

правил

столкновения

Конструктор

граничных

условий

Симулятор ЗО-лотока

Модуль осреднения

I Прмаяя ствякооввння

Конфигурация КА }■—*

Данные)

I Прижяи столкновения |

I Конфигурация КА

н_К-

Нот* кон4*гурация КА

[ Конфигурация КА Проооииволя скоростей

Рис 6. Способ разрезания клеточного автомата, используемый в параллельной

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

Четвертая глава

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

Эксперименты были поставлены следующим образом. Клеточный автомат имеет форму прямоугольного параллелепипеда размером 101 х 101 х 2000 клеток, ориентированного вдоль осей X, У и Ъ соответственно. В нем клетками стенки ограничен круговой цилиндр радиусом 50 клеток. На одной из перпендикулярных оси цилиндра граней параллелепипеда выстроена плоскость из клеток - источников частиц. Каждая из этих клеток на каждой итерации с заданной вероятностью может генерировать частицы со всеми возможными направлениями векторов скорости. Для того чтобы сравнение экспериментально полученной скорости потока в трубе с аналитически рассчитанной по Пуазейлю скоростью было корректным, выполняются следующие условия.

1). Процесс должен прийти к установившемуся режиму. Это означает, что скорость потока остается неизменной.

2). Клеточный автомат должен быть настолько большим, чтобы использовать радиус осреднения достаточный для минимизации уровня автоматного шума. Шум возникает вследствие дискретности автомата, он тем меньше, чем больше радиус осреднения. Экспериментально установлено, что радиуса г = 10 клеток достаточно, чтобы шум давал погрешность не более чем в третьем знаке. Этим способом имеет смысл подсчитывать осредненные значения только для тех точек, которые отстоят от стенки трубы более чем на радиус осреднения, потому что если в окрестность осреднения попадает хотя бы одна клетка стенки, то результат будет неточным. Таким образом, диаметр внутренней части трубы, в которой могут быть получены значения скорости потока, равен

2г, где с1- диаметр трубы, а г- радиус осреднения. В случаях, когда необходимо узнать скорость потока вблизи стенок, применяют

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

3). Должно выполняться соотношение / >> й, где I -длина, а с/ - диаметр трубы. Это необходимо для того, чтобы

I I S 5 » ! I } 5 5 S | ! Е г % 5 8 S S 5 I

Е

3

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

исключить краевые эффекты на концах трубы. На рис. 7 показано распределение концентрации модельных частиц с ненулевым вектором скорости вдоль трубы для вероятностей генерации частиц клетками-источниками от 20 до 90 процентов. В средней части каждой кривой есть линейный участок, на котором концентрация частиц в клеточном автомате изменяется по тому же закону, что и давление моделируемой жидкости (dp/dz = const).

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

f-±-\f-JL.\f~!L\ f =JL= „Л.;/ =PZ£l = *P

Jt ~ , J, - J i f J II S J. J p A

где /, v, и, p - физические длина, вязкость, скорость и давление соответственно, 1М!)д, vmHl, имод, п - модельные длина, вязкость, скорость и концентрация частиц, a g вычисляется так, как описано во второй главе.

В качестве иллюстрации способа получения искомых соотношений для исследуемой модели выбран пример движения нефти через трубу круглого сечения с диаметром d = 0.7 м длиной / = 100 км = 105м. Плотность нефтир = 844 кг/м3, вязкость нефтиц = 0.11 Па ■ с, кинематическая вязкость v = ц /р = 1.3 • 10"4м2/с.

Параметры эксперимента были выбраны следующим образом: 1мы> = '000 клеток (линейный участок изменения концентрации частиц), dMoö = 101 клетка. Рассчитанная кинематическая вязкость vmid = 0.115. Структурный коэффициент g = 0.4. Градиент концентрации модельных частиц, как видно из рис. 7 (кривая 60%), получился равным An = «(500) - и(1500) = 2.81. Модельная средняя скорость частиц получилась (имад) = 0.96.

Для подсчета скорости нефти вычисляются fi = 7 • 10 '3;/v = 1.13 • 10 "3. Соотношение скоростей и средняя скорость потока равны/, =

6.46 • 10 "2; (и) = 6.2 • 10'2 м/с. Давление на концах участка тогда равно Др = 3.12 Па, а коэффициент/р=\.\\.

Соответствие модели физическому потоку подтверждается совпадением модельного числа Рейнольдса с числом Рейнольдса для

физической среды.

Яе =

(«У-

334;

^ :----«

« Щг>:___

Л'" '4 '|в* - Л; ^ г :

1:■ С* • -' : --: «

Яе.

Рис 8 Поле скорости потока в пористой среде

= (РтМшб_ =334,

где <ы) и (м^,) -физическая и модельная средние скорости потока, а в качестве характерного размера объектов <1 и с1мод выбран диаметр трубы.

Еще одна серия экспериментов, описанная в четвертой главе диссертации, представляет собой моделирование потока вязкой жидкости через пористую среду. Размер клеточного автомата был выбран 800 х 50 х 800 клеток. Поток распространялся вдоль оси Ъ. На рис. 8 изображено поле скорости потока в сечении XX при у ~ 25 клеток после 150 тысяч итераций. Серыми областями обозначены участки твердой породы, а белыми — поры. Длина и направление стрелок соответствуют модулю и направлению проекции скорости потока на плоскость Х7.. На рисунке не видна составляющая скорости, направленная вдоль У и расположение пор в соседних по У слоях, поэтому некоторые стрелки, направленные в сторону препятствий, нужно воспринимать как обтекание потоком препятствия сверху или снизу. В экспериментах исследовалась зависимость скорости потока от плотности пор. Результаты хорошо соотносятся с законом Дарси.

Экспериментальное исследование эффективности

распараллеливания производилось на кластерах МВС-1000/М, принадлежащих Сибирскому суперкомпьютерному центру (ССКЦ, Новосибирск) и Межведомственному суперкомпьютерному центру (МСЦ, Москва). Клеточный автомат, использовавшийся в этих экспериментах, имел размер 2000 х 2000 х 101 клеток и разрезался на

различное количество процессоров вдоль оси X (2000 клеток). При этом измерялась зависимость времени выполнения 100 тактов от количества процессоров. На кластере МСЦ эксперименты проводились с числом процессоров от 1 до 384. Эффективность распараллеливания в пределах одной стойки (32 процессора) составила более 90 процентов, а в пределах кластера (более 32 процессоров) — порядка 60 процентов. Падение производительности при числе процессоров большем, чем 32, объясняется двухуровневой структурой сети кластера.

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

1. Предложена трехмерная клеточно-автоматная модель потока вязкой жидкости с 12 соседями, отличающаяся от известных моделей меньшей сложностью вычислений.

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

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

4. Создан программный комплекс, эмулирующий эволюцию клеточного автомата предложенной модели в последовательной и параллельной реализации.

5. Экспериментально показано соответствие предложенной модели потоку реальной жидкости путем сравнения результатов моделирования с аналитическими расчетами распределения скорости потока в трубе по закону Пуазейля.

6. Показано соответствие скорости просачивания жидкости через пористую среду, полученной в результате эксперимента, со скоростью, найденной по закону Дарси.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Медведев Ю.Г. Клеточно-автоматные модели в задачах газовой динамики. // Конгресс по прикладной и индустриальной математике. Новосибирск. 1998. Т.З. С. 91.

2. Медведев Ю.Г. Дискретные методы решения задач газовой динамики. // Новые информационные технологии в исследовании дискретных структур. Екатеринбург. НИСО УрО РАН. 1998. С. 117-120.

3. Медведев Ю.Г. Клеточно-автоматные модели в задачах газовой динамики. // Тезисы докладов на конференции, посвященной 70-летию Сибирского физико-технического НИИ, Томск, изд-во ТГУ, 1998. С. 39.

4. Medvedev Yu.G. Modification of a 2D Gas-Lattice Model. // Bulletin of the Novosibirsk Computing Center. Special issue. NCC Publisher, 1999. P. 82-87.

5. Медведев Ю.Г. Модификация клеточно-автоматной модели потока жидкости. // Новые информационные технологии в исследовании дискретных структур, Томск, ТНЦ СО РАН, 2000. С. 84-90.

6. Медведев Ю.Г. Моделирование потоков жидкостей и газов клеточными автоматами. // Моделирование неравновесных систем -2001, Красноярск, ИПЦ КГТУ, 2001. С. 98.

7. Medvedev Yu.G. Gas-Lattice Simulation of High Viscous Fluid Flows. // Bulletin of the Novosibirsk Computing Center. Series: Computer Science, Issue: 17 (2002), NCC Publisher, Novosibirsk, 2002. P 63-73.

8. Медведев Ю.Г. Трехмерная клеточно-автоматная модель потока жидкости. // Труды конференции молодых ученых ИВМиМГ, Новосибирск, 2002. С. 98-103

9. Медведев Ю.Г. Моделирование трехмерных потоков клеточными автоматами. // Вестник Томского Государственного университета N1(11), Приложение, Томск, изд-во ТГУ, 2002. С. 236-240.

10. Медведев Ю.Г. Трехмерная клеточно-автоматная модель потока вязкой жидкости. // Автометрия, т.39, N 3, 2003, С. 43-50.

11. Medvedev Yu.G. The Wall Cells in the Cellular Automaton Fluid Flow Simulation. // Bulletin of the Novosibirsk Computing Center. Series: Computer Science, Issue: 19 (2003), NCC Publisher, Novosibirsk, 2003. P. 51-59.

12. Медведев Ю.Г. Вычислительные эксперименты по определению связи физических величин с параметрами трехмерной КА-модели потока жидкости. // Труды конференции молодых ученых ИВМиМГ, Новосибирск, 2004. С. 120-127.

13. Медведев Ю.Г. Параллельная реализация трехмерной клеточно-автоматной модели потока жидкости. // Материалы международного семинара «Вычислительные методы и решение оптимизационных задач», Новосибирск, 2004. С. 107-112.

14. Медведев Ю.Г. Соотношение модельных и физических величин для трехмерной клеточно-автоматной модели потока жидкости. // Вестник Томского Государственного университета, N9(1), Приложение, Томск, изд-во ТГУ, 2004. С. 117-120.

Медведев Юрий Геннадьевич

Разработка и исследование трехмерной клеточно-автоматной модели потока вязкой жидкости

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 24.05.2005. Формат 60 х 84 1/16 Усл. Печ. Л. 2. Уч.-изд. л. 2. Печать офсетная. Тираж 80 экз._Заказ № _

Отпечатано в ООО «Омега Принт» 630090, Новосибирск, пр. Ак. Лаврентьева, 6

#118 28

РНБ Русский фонд

2006-4 6864

Введение

Глава 1. Общие принципы клеточно-автоматного моделирования потоков жидкости

1.1. Основные определения

1.2. Клеточно-автоматные модели потоков жидкости

1.3. Двумерная модель с 4 соседями (НРР модель)

1.4. Двумерная модель с 6 соседями (FHP модель)

1.5. Четырехмерная модель с 24 соседями (FCHC модель)

1.6. Моделирование потоков жидкости с меньшей вязкостью. Модификация FHP модели

Выводы к главе

• Глава 2. Трехмерная КА модель потока жидкости RD-I с 12 соседями

2.1. Структура модели

2.2. Правила перехода клеточного автомата

2.3. Граничные условия модели

2.4. Осреднение значений

2.5. Модельные параметры. Соотношения модельных и физических величин

Выводы к главе

Глава 3. Программный комплекс моделирования потоков жидкости

3.1. Назначение и блок-схема комплекса

3.2. Основные модули комплекса

3.3. Симулятор потока жидкости

3.4. Параллельная реализация симулятора

3.5. Форматы данных

3.6. Методика проведения вычислительных экспериментов 65 Выводы к главе

Глава 4. Эксперименты с моделью RD-I

4.1. Алгоритм моделирования стационарного потока

4.2. Поток вязкой жидкости в трубе. Сравнение с законом Пуазейля

4.3. Поток вязкой жидкости в трубе с задвижкой

4.4. Моделирование пористых сред. Сравнение с законом Дарси

4.5. Оценки эффективности распараллеливания 91 Выводы к главе

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

В традиционном подходе в качестве модели изучаемого процесса используются дифференциальные уравнения в частных производных. Дифференциальные уравнения, используемые в реальных задачах, невозможно решить аналитически, поэтому возникает необходимость применять численные методы их решения, с которыми при больших размерах задачи связан ряд проблем. [1, 2, 3]. Так, например, в большинстве задач при использовании явных схем решение сходится очень медленно из-за малого шага по времени, поэтому приходится использовать неявные схемы. При вычислении неявных схем на многопроцессорных вычислительных системах трудно достигнуть высокой эффективности распараллеливания.

Поиск путей преодоления вышеперечисленных трудностей ведется по двум направлениям: совершенствование численных методов решения дифференциальных уравнений и способов их распараллеливания и поиск новых моделей, отличных от дифференциальных уравнений [4, 5, 6]. Одно из направлений этого поиска осуществляется путем создания и исследования новых моделей, обладающих следующими свойствами.

• Дискретность. Модели должны иметь булев базис для возможности прямого отображения на структуру вычислителя, легкой аппаратной реализации на базе современной микроэлектроники, а также для возможности эмуляции на универсальной ЭВМ.

-5* • Природные свойства. В основу модели должен быть положен принцип близкодействия и другие физические законы, чтобы свойства модельных объектов были максимально схожими с физическими свойствами природных объектов, а интерпретация результатов моделирования была простой.

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

Один из новых классов моделей, разрабатываемых для описания широкого круга задач пространственной динамики, в том числе и для ^ моделирования потоков жидкостей, и обладающих вышеперечисленными свойствами составляют модели, основанные на клеточных автоматах [7, 8]. Впервые клеточный автомат был предложен Дж. Фон Нейманом (J. von Neumann) в 1948 году [9]. Затем эта модель развивалась и находила применение в различных областях, в том числе и в задачах моделирования пространственной динамики. Приведем некоторые важные даты, связанные с развитием клеточно-автоматных моделей потоков жидкости.

1973 год. J. Hardy, О. de Pazzis, Y. Pomeau. Предложена двумерная НРР модель потока [10]. Клетки этой модели имеют четыре соседа. В модели выполняются «лишние» законы сохранения, что приводит к ее анизотропии. Модель не получила применения для описания потоков жидкости.

1986 год. U. Frisch, В. Hasslacher, Y. Pomeau. Предложена двумерная FHP модель с шестью соседями [11]. Эта модель изотропна, ее элементарные автоматы имеют вероятностные правила переходов. Доказано, что FHP модель аппроксимирует уравнение Навье-Стокса и может быть использована для моделирования потоков жидкости на плоскости.

1987 год. Т. Toffoli, N. Margolus. Построен спецпроцессор, аппаратно

• реализующий клеточный автомат, так называемая машина клеточных автоматов САМ-8 (Cellular Automata Machine) [12]. Создание этого устройства дало толчок к поиску новых моделей и развитию клеточно-автоматного моделирования как самостоятельной отрасли науки.

1987 год. U. Frisch, D. d'Humieres, В. Hasslacher, P. Lallemand, Y. Pomeau, J.-P. Rivet. Предложена четырехмерная FCHC (Face Centered Hyper Cubic) модель, построенная на гранецентрированном гиперкубе [13]. Проекция этой вероятностной модели с 24 соседями на трехмерное пространство адекватно описывает трехмерные потоки жидкости и полностью удовлетворяет условиям изотропии. Несмотря на это, FCHC модель не получила широкого распространения в силу большой вычислительной сложности.

Кроме задач газовой [14 - 21] и гидродинамики [22 - 29] клеточные автоматы применяются во многих других областях для моделирования самых различных физических процессов, таких как пространственная диффузия [30 - 33], эволюция спиральных галактик [34], нелинейные химические системы [35, 36, 37], рост ветвящихся кристаллов [38, 39], фазовые переходы [40, 41], пространственная структура турбулентных потоков [42], рост, поведение и функционирование биологических организмов [43, 44], обработка изображений, распознавание образов [45], движение групп людей и толпы [47 - 52], распространение эпидемий [53], сейсмические волны [54], магнитогидродинамические явления [55, 56] и многое другое [57, 58, 59]. В связи с обилием вышеперечисленных применений клеточно-автоматные модели приобретают все большую актуальность.

Важным условием эффективности моделирования является способ реализации модели [60]. Клеточные автоматы могут быть реализованы на универсальных ЭВМ [61 - 64], на многопроцессорных вычислительных системах [65], в виде специализированных машин клеточных автоматов [12, 66] и даже известны проекты реализации клеточных автоматов на молекулярном уровне [3].

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

Для сокращения времени вычислений используют параллельную реализацию. Клеточно-автоматные модели обладают высокой эффективностью распараллеливания на многопроцессорных вычислительных системах и системах с массовым параллелизмом [12, 65, 66]. Параллелизм заложен в самой структуре этих моделей, поэтому они реализуются на любых многопроцессорных архитектурах с сотнями, тысячами и даже десятками тысяч процессоров при минимальной деградации эффективности распараллеливания.

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

Задание граничных условий в клеточно-автоматных моделях осуществляется заданием типов клеток автомата. Группы клеток, образующие границы, состоят из клеток типа стенки. Хотя поведение клеток стенки и отличается от поведения обычных клеток, вычислительная сложность обработки одной клетки не зависит от ее типа. Это означает, что время вычислений клеточного автомата заданного размера остается неизменным, какими бы сложными ни были его границы. В силу легкости задания граничных условий клеточно-автоматные модели приобрели особенное значение для исследования потоков вязкой жидкости через пористые среды [67 - 74]. Также клеточно-автоматные модели позволяют моделировать движение нефти в трубопроводах сложной конфигурации и в грунте.

Моделирование трехмерных потоков является чрезвычайно сложной задачей. С одной стороны, модель должна удовлетворять условиям изотропии, а с другой стороны - иметь приемлемую вычислительную сложность, которая зависит от количества соседних клеток. Условия изотропии накладываются на тензоры изотропии до четвертого порядка включительно [75, 76]. Среди трехмерных моделей нет таких, которые обладали бы изотропией четвертого порядка. Были найдены четырехмерные модели, но они оказались слишком сложными для практического использования [13]. В связи с этим возникла задача поиска трехмерной модели, в которой условия изотропии выполнялись бы приближенно (до третьего порядка), и которая была бы приемлемой по сложности. Предлагаемая в диссертации трехмерная клеточно-автоматная модель, названная RD-I, имеет третий порядок точности соответствия с условиями изотропии, но ее вычислительная сложность на несколько порядков ниже, чем у точных моделей.

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

Цель работы.

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

Задачи.

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

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

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

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

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

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

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

При проведении исследований использовался аппарат дискретной математики, теории автоматов, параллельного программирования и теории вероятностей, а также вычислительный эксперимент на одно- и многопроцессорных ЭВМ.

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

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

- предложена новая трехмерная клеточно-автоматная модель, названная RD-I, отличающаяся от известных моделей много меньшей сложностью;

- получены соотношения между физическими и модельными параметрами, сопоставляющие результаты моделирования с реальными величинами, характеризующими моделируемый поток;

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

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

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

Предложенная трехмерная клеточно-автоматная модель RD-I может быть использована для моделирования потоков вязкой жидкости в объектах с границами любой сложности. Созданный в рамках работы программный комплекс может применяться для моделирования потоков вязкой жидкости, в том числе и в пористых средах.

Достоверность результатов.

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

Основные положения, выносимые на защиту.

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

2. Сложность граничных условий модели RD-I (включая случаи с пористыми средами) не оказывает существенного влияния на вычислительную сложность алгоритма.

3. Результаты моделирования с помощью RD-I укладываются в пределы допустимой погрешности относительно аналитических расчетов. Модельное и физическое числа Рейнольдса также различаются на допустимую величину погрешности. Предел допустимой погрешности находится в обратной зависимости от используемого радиуса осреднения.

4. Созданный программный комплекс эмулирует эволюцию клеточного автомата модели RD-I как на последовательных ЭВМ, так и на многопроцессорных вычислительных комплексах.

Содержание диссертации изложено в четырех главах.

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

Во второй главе диссертации предлагается трехмерная КА модель потока жидкости RD-I с 12 соседями и одной частицей покоя в каждой клетке [77]. Структура автомата основана на полярном комплексе ромбического додекаэдра. Если заполнить трехмерное пространство ромбическими додекаэдрами с единичным расстоянием между двумя противолежащими гранями, то координаты узлов решетки автомата будут совпадать с координатами центров додекаэдров. При этом соседние узлы будут находиться в центрах додекаэдров, имеющих общую грань. Узлы решетки при данном пространственном распределении совпадают с центрами плотно упакованных шаров в одном из вариантов плотной упаковки. Предложенная модель RD-I достаточно проста в реализации, т.к. производит операции над булевыми векторами. Также в этой главе изложен метод задания граничных условий [78] и выведены формулы для вычисления параметров, таких как модельная вязкость и структурный коэффициент [79].

В третьей главе диссертации представлен программный комплекс, созданный для реализации трехмерной клеточно-автоматной модели RD-I на последовательных компьютерах и параллельных вычислительных системах [80]. В ней сказано о целях создания и о назначении программного комплекса, описаны форматы данных, используемых при моделировании [81], алгоритмы ввода-вывода, алгоритм эмуляции элементарного автомата, алгоритм осреднения, алгоритм распределения клеток автомата по процессорам в параллельной реализации. Также в этой главе приведены рекомендации по использованию комплекса.

Четвертая глава диссертации содержит описание вычислительных экспериментов [82]. Серия экспериментов по моделированию потока вязкой жидкости в трубе круглого сечения была поставлена для того, чтобы подтвердить соответствие модели RD-I реальному потоку, скорость которого в трубе можно рассчитать аналитически из закона Пуазейля [83]. Далее в четвертой главе описан эксперимент по моделированию движения нефти с такими же физическими характеристиками в трубе такого же размера, как и в предыдущем эксперименте, но с наполовину закрытой задвижкой, имеющей форму полукруга в поперечном сечении трубы. Еще одна серия экспериментов, описанная в четвертой главе диссертации, представляет собой моделирование потока вязкой жидкости через пористую среду. В них исследовалась зависимость скорости потока от плотности пор. Результаты этих экспериментов коррелируют с законом Дарси. Также в этой главе даны оценки эффективности распараллеливания, полученные в результате серии экспериментов с использованием параллельной версии программного комплекса на мультикомпьютерах.

Реализация результатов работы.

Работа выполнена в соответствии с темой N 25 «Исследование физических и информационных процессов с использованием моделей мелкозернистого параллелизма» (№ госрегистрации 01.20.00.04430) плана научно-исследовательских работ отдела математического обеспечения высокопроизводительных вычислительных систем института вычислительной математики и математической геофизики СО РАН, а также поддержана грантом РФФИ № 01.00.00026 (1999г.) и Программой фундаментальных исследований РАН № 17 (2004г.)

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

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

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

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

Основные результаты диссертации докладывались и обсуждались на конгрессе по прикладной и индустриальной математике (Новосибирск, 1998), на конференции, посвященной 70-летию Сибирского физико-технического НИИ (Томск, 1998), на конференции с международным участием «Новые информационные технологии в исследовании дискретных структур» (Томск, 2000), на международной конференции по вычислительной математике

Новосибирск, 2001), на конференции «Моделирование неравновесных систем» (Красноярск, 2001), на Сибирской научной школе-семинаре по параллельному программированию (Томск, 2001), на конференциях молодых ученых ИВМиМГ (Новосибирск, 1999; 2002; 2004), на конференциях с международным участием «Новые информационные технологии в исследовании сложных структур» (Томск, 2002; Иркутск, 2004), а также на семинарах отделов Математического обеспечения высокопроизводительных вычислительных систем и Математических задач геофизики Института вычислительной математики и математической геофизики СО РАН.

Публикации.

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

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы. Содержание диссертации изложено на 108 страницах, содержит 41 иллюстрацию и 8 таблиц. Библиографический список включает 127 наименований.

Выводы к главе 4

1. Выполнена серия вычислительных экспериментов, проведенных при помощи программного комплекса, описанного в третьей главе, с КА моделью RD-I, представленной во второй главе.

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

3. Получено поле скорости потока жидкости в эксперименте с более сложными граничными условиями — моделировании потока жидкости в трубе с наполовину закрытой задвижкой.

4. Приведены результаты экспериментального исследования распространения жидкости в пористой среде, они совпадают с ожидаемыми согласно закону Дарси значениями.

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

-96-Заключение

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

1. Предложена трехмерная клеточно-автоматная модель потока вязкой жидкости с 12 соседями, отличающаяся от известных моделей малой сложностью вычислений.

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

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

4. Создан программный комплекс, эмулирующий эволюцию клеточного автомата предложенной модели в последовательной и параллельной реализации.

5. Экспериментально показано полное соответствие предложенной модели потоку реальной жидкости через сравнения результатов моделирования с аналитическими расчетами распределения скорости потока в трубе по fc? закону Пуазейля.

6. Показано соответствие скорости просачивания жидкости через пористую среду, полученной в результате эксперимента, со скоростью, найденной по закону Дарси.

1. Tofolli Т. Cellular Automata as an Alternative to (rather as an Approximation of) Differential Equations in Modeling Physics // Physica. 1984. 10D. P. 117.

2. Lattice Gas Methods for Partial Differential Equations / Doolen G. (editor), MA: Addison- Wesley. 1990.

3. Wolfram S. A New Kind of Science. Wolfram Media. 2002.

4. Бандман О.Л. Клеточно-нейронные модели пространственной динамики//Программирование. 1999. №1.С. 1.

5. Бандман O.JI. Мелкозернисый параллелизм в вычислительной математике//Программирование. 2001. №4. С. 1.

6. Бандман O.JI. Методы композиции клеточных автоматов для моделирования пространственной динамики // Вестник Томского университета. 2004. №9(1). С. 188.

7. Codd E.F. Cellular Automata. New York: Academic Press, 1968.

8. Gutowitz H.A. Cellular Automata. Cambridge, MA: MIT Press, 1990.

9. Фон Нейман Дж. Общая и логическая теория автоматов. Приложение к книге А. Тьюринга Может ли машина мыслить? М.: Физматгиз, 1960. (Доклад прочитан 20 сентября 1948 года на симпозиуме по механизмам мозга в поведении.)

10. Hardy J., Pomeau Y. and de Pazzis О // J. Math. Phys. 1973. №14. P. 1746.

11. Frisch U., Hasslacher B. and Pomeau Y. Lattice-Gas automata for Navier-Stokes equations // Phys. Rev. Lett. 1986. N 56. P. 1505.

12. Тоффоли Т., Марголус H. Машина клеточных автоматов. М.: Мир, 1991.

13. Frisch U., d'Humieres D., Hasslacher В., Lallemand P., Pomeau Y. and Rivet J.-P // Complex Systems. 1987. N 1. P. 649.-98* 14. Boghosian B.M. Lattice Gases and Cellular Automata // Future Generation Computer Systems. 1999. N 16(2-3). P. 171.

14. Appert C., and Zaleski S. Dinamical Liquid-gas phase transition // J. Phys. II France. 1993. Vol. 3. P. 309.

15. Малинецкий Г. Г., Степанцов М. Е. Клеточные автоматы для расчета ^ некоторых газодинамических процессов // Журнал вычислительнойматематики и математической физики. 1996. Том 36. N 5. С.137.

16. Малинецкий Г. Г., Степанцов М. Е. Применение моделей класса решеточных газов для решения задач газодинамики // Известия Высших учебных заведений. Прикладная нелинейная динамика. 1996. Том 4. N4,5. С. 59.

17. Малинецкий Г. Г., Степанцов М. Е. Модели класса решеточных газов в задачах газодинамики // Интеллектуальные системы. 1997. Том 2. N1-4. С. 157.

18. Sommers J. A. and Rem Р.С. Obtaining Numerical Results from the FCHC-Lattice Gas // Workshop on Numerical Methods for the Simulation of Multiphase and Complex Flow. Werheggen T.M.M. (Ed.), Springer, Berlin, 1992.

19. Медведев Ю.Г. Дискретные методы решения задач газовой динамики // Новые информационные технологии в исследовании дискретныхструктур. Екатеринбург. НИСО УрО РАН. 1998. С. 117.

20. Медведев Ю.Г. Клеточно-автоматные модели в задачах газовой динамики // Тезисы докладов на конференции, посвященной 70-летию Сибирского физико-технического НИИ. Томск: изд-во ТГУ. 1998. С. 39.

21. Rivet J. P., Henon M., Frisch U. et d'Humieres D. // Europhys. Lett. 1988. Vol.7. P.231.

22. Fritz J. Stationary States and Hydrodynamics of FHP Cellular-Automata // Journal of Statistical Physics. 1994. N 77(1-2). P. 53.

23. Медведев Ю.Г. Моделирование потоков жидкостей и газов клеточными автоматами // Моделирование неравновесных систем. Красноярск: ИПЦ КГТУ. 2001. С. 98.

24. Medvedev Yu. Gas-Lattice Simulation of High Viscous Fluid Flows // Bulletin of the Novosibirsk Computing Center. Series: Computer Science. 2002. Issue 17. P. 63.

25. Медведев Ю.Г. Метод моделирования трехмерных потоков жидкости клеточными автоматами // Автометрия. 2005. N 3. В печати.

26. Qian Y. Н., d'Humieres D. and Lallemand P. Diffusion Simulation with a Deterministic One-Dimensional Lattice-Gas Model // Journal of Statistical Physics. 1992. Vol. 68. Nos. 3/4. P. 563.

27. Малинецкий Г. Г., Степанцов М. Е. Моделирование диффузионных процессов с помощью клеточных автоматов с окрестностью Марголуса // Журнал вычислительной математики и математической физики. 1998. Том 38, N6. С.1017.

28. Бандман O.JI. Клеточно-автоматное моделирование диффузионно-реакционных процессов // Автометрия. 2003. № 3. Том 39. С. 1.-10034. Gerola Н., Seiden P. Stochastic star formation and spiral structure og galaxies // Astrophys. J. 1978. Vol. 223. P. 129.

29. Бандман О.Л. Клеточно-нейронный автомат. Дискретная модель динамики активных сред // Сборник трудов конференции, посвященной 90-летиюсо дня рождения А.А.Ляпунова (Новосибирск, 2001). http://www.sbras.ru/ws/Lyap2001/23-34.

30. Seybold P.G., Kier L.B., Cheng C.K. Modeling Dynamic Chemical Systems Using Cellular Automata // Abstracts of Papers of the American Chemical Society. 1999. Vol. 217. P. 662.

31. И.Ю. Зубко, И.Э. Келлер, П.В. Трусов. Кинетическая модель образования периодических дислокационных структур в кристалле в терминах клеточных автоматов // Физическая мезомеханика. Том 2. Номер 1-2. С. 17.

32. Ситников П.В., Левин Е.С., Семенов В.Н. Формы роста первичных кристаллов в эвтектических сплавах германия с З-d переходными металлами // Известия АН СССР. Серия "Неорганические материалы". 1986. С. 332.

33. Малинецкий Г. Г., Степанцов М. Е. Моделирование процессов конденсации и неизотермических течений газа с помощью клеточных автоматов // Журнал физической химии. 1995. Том 69. N 8ю С. 1528.

34. Appert С., and Zaleski S. Lattice gas with a liquid-gas transition // Physical Review Letters. 1990. Vol. 64. P. 1.

35. Crutchfield J. P., and Hanson J. E. Turbulent pattern bases for cellular automata // Physica. 1993. D 69. P. 279.

36. Wolfram S. Cellular automata as models of complexity // Nature. 1984. Vol. 311. P. 419.

37. Войтикова М.В. Клеточно-автоматные модели эволюции комплексных систем // Доклады Академии Наук Беларуси. 1999. N 43(5). С. 48.

38. Theory and Applications of Cellular Automata / Wolfram S. (editor). Singapore: World Scientific. 1986.

39. Малинецкий Г. Г., Степанцов М. Е. Моделирование движения толпы при помощи клеточных автоматов // Известия Высших учебных заведений. Прикладная нелинейная динамика. 1997. Том 5. N 5. С. 75.

40. Степанцов М. Е. Моделирование движения группы людей на основе решеточного газа с нелокальными взаимодействиями // Известия Высших учебных заведений. Прикладная нелинейная динамика. 1999. Том 7. N 5. С. 44.

41. Степанцов М.Е. Моделирование движения толпы при заданной конфигурации препятствий // Проблемы управления безопасностью сложных систем. Материалы X международной конференции. М.: РГГУ. 2002. Т. 2. С. 130.

42. Степанцов М.Е. Расчет некоторых случаев движения неорганизованной группы людей // Математические модели и приложения. Труды десятых математических чтений МГСУ. Москва. 2003. С. 136.

43. Степанцов М.Е. Математическая модель направленного движения группы людей // Математическое моделирование. 2004. Т. 16. №3. С. 43.

44. Степанцов М.Е. Клеточные автоматы и их применение при изучении социальных процессов // Моделирование социально-политической и экономической динамики. М.: РГСУ. 2004.

45. Rothman D. Н. Modeling Seismic P-waves thith Cellular Automata // Geophisics. 1988. Vol. 14. P. 17.

46. Chen H., Matthaeus W.H. New Cellular Automaton Model for

47. Magnetohydrodynamics // Physical Review Letters. 1987. Vol. 58(18). P. 1845.

48. Hatori T. Magnetohydrodynamic Cellular Automata // Progress of Theoretical Physics Supplement. 1989. Vol. 99. P. 229.

49. Bremond R. and Jeulin D. Morphogenesis Simulations with Lattice Gas // Mathematical Morphology and Its Applications to Image Processing. Serra J., Solie P. (Eds). Kluwer Academic Publisher: Dordrecht. 1994.

50. Степанцов М.Е. Клеточные автоматы как модели нелинейных явлений // Математические методы и приложения. Труды девятых математических чтений МГСУ. Москва. 2002. С. 141.

51. Pechatnikov E.L., Frankowicz М., Danielak R. Cellular-Automaton for Surface-Reactions // Acta Physica Polonica. 1994. В 25(6) P. 993.

52. Bandman O.L. Algebraic Properties of Cellular Automata: The Basis for Composition Technique // Proceedings of the International Conference

53. ACRI-2004. Lecture Notes in Computer Science. 2004. Vol. 3305. (Eds: P.

54. M. A. Sloot, B, Chopard, A. G. Hoekstra). P. 688.

55. Toffolli Т., Margolus N.H. Invertible cellular automata: a review // Physica D. 1990. N.45.P. 229.

56. Mitchell, M., Crutchfield, J. P., and Hraber, P. T. Evolving cellular automata to perform computations: Mechanisms and impediments // Physica. 1994. D 75. P. 361.

57. Медведев Ю.Г. Параллельная реализация трехмерной кпеточно-автоматной модели потока жидкости // Материалы международного семинара «Вычислительные методы и решение оптимизационных задач». Новосибирск. 2004. С. 107.

58. Пискунов С.В. Специализированные процессоры для высокопроизводительной обработки данных/ Под ред. В.Е. Котова, Н.Н. Миренкова. Новосибирск: Наука. Сибирское отделение. 1988. Гл. 6. Методы проектирования архитектуры спецпроцессоров. С. 157.

59. Di Pietro L.B., Melayah A., Zaleski S. Modeling water infiltration in ^ unsaturated porous media by interacting lattice gas Cellular automata //

60. Water recources research. Vol. 30. NolO. P 2785.

61. Rothman D. H. Cellular-automaton fluids: A model for flow in porous media // Geophisics. 1988. Vol. 53. No. 4. P. 509.

62. Lee J., Koplik J. Network model for deep bed filtration // Physics of fluids. 2001. Vol. 13. No5. P. 1076.

63. Physical nonequilibrium in soils: modeling and application / Edited by H. Magdi Selim, Liwang Ma. 1998.

64. Lenormand R. Pattern Growth and Fluid Displacements through Porous Media // Physica. 1986. Vol. 140A. P. 114.

65. Chou H.-H., Huang W., Reggia J. A. The Trend Cellular Automata Programming Environment// Simulation. 2002. Vol. 78, Issue 2. P. 59.

66. Kohring G. A. Calculation of the Permeability of Porous-Media Using Hydrodynamic Cellular Automata // Journal of Statistical Physics. 1991. Vol. 63(1-2). P. 411.

67. Вустер У. Применение тензоров и теории групп для описания физических свойств кристаллов. М.: Мир. 1977.

68. Медведев Ю.Г. Трехмерная клеточно-автоматная модель потока жидкости // Труды конференции молодых ученых ИВМиМГ. Новосибирск. 2002. С. 98.

69. Medvedev Yu. The Wall Cells in the Cellular Automaton Fluid Flow Simulation // Bulletin of the Novosibirsk Computing Center. 2003. Series: Computer Science. Issue: 19. NCC Publisher: Novosibirsk. P. 51.

70. Медведев Ю.Г. Соотношение модельных и физических величин для трехмерной клеточно-автоматной модели потока жидкости // Вестник Томского Государственного университета. 2004. N 9 (I). Приложение. Томск: изд-во ТГУ. С. 223.

71. Медведев Ю.Г. Моделирование трехмерных потоков клеточными автоматами // Вестник Томского Государственного университета. 2002. N 1 (II). Приложение. Томск: изд-во ТГУ. С. 236.

72. Медведев Ю.Г. Трехмерная клеточно-автоматная модель потока вязкой жидкости //Автометрия. 2003. Том 39. N 3. С. 43.

73. Медведев Ю.Г. Вычислительные эксперименты по определению связи физических величин с параметрами трехмерной КА-модели потока жидкости // Труды конференции молодых ученых ИВМиМГ. Новосибирск. 2004. С. 120.

74. Лойцянский Л.Г. Механика жидкости и газа. М: Наука. 1987.

75. Фон Нейман Дж. Теория самовоспроизводящихся автоматов. М: Мир. 1971.

76. Burks A. W. Von Neumann's self-reproducing automata // Essays on Cellular Automata. Urbana, IL: University of Illinois Press. 1970.- 10586. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. Поведение и синтез. М: Наука. 1970.

77. Айзерман М.А., Гусев JI.A., Розоноэр Л.И., Смирнов И.М., Таль А.А. Логика, автоматы, алгоритмы. М: Физматгиз. 1963.

78. Гилл А. Введение в теорию конечных автоматов. М: Наука. 1966.

79. Глушков В.М. Синтез цифровых автоматов. М: Физматгиз. 1962.

80. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. М: Физматгиз. 1962.

81. Карпов Ю.Г. Теория автоматов. Спб: Питер, 2002.

82. Минский М. Вычисления и автоматы. М: Мир. 1972.

83. Поспелов Д.А. Логические методы анализа и синтеза схем. М: Энергия. 1974.

84. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М: Наука. 1971.

85. Агибалов Г.П., Оранов A.M. Лекции по теории конечных автоматов. Томск: Изд-во Том. ун-та. 1984.

86. Bandman O.L. Simulation Spatial Dynamics by Probabilistic Cellular Automata // Lecture Notes in Computer Science. Spriger:Berlin. 2002. Vol. 2493 (Ed. B.Chopard). P. 10.

87. Wolfram S. Statistical mechanics of cellular automata // Review of Modern Physics. 1983. Vol. 55. P. 601.

88. Demasi A., Esposito R., Presutti E. Kinetic Limits of the HPP Cellular Automaton //Journal of Statistical Physics. 1992. Vol. 66(1-2). P. 403.

89. Margolus N. Physics-like models of computation // Physica. 1984. D 10. P. 81.

90. Rothman D. H., Zaleski S. Lattice-gas cellular cutomata: simple models of complex hydrodinamics- Cambridge University Press. 1997.

91. Adler C., Boghosian В., Flekkoy E.G., Margolus N., Rothman D.H.

92. Simulating 3-Dimensional Hydrodynamics on a Cellular-Automata Machine //Journal of Statistical Physics. 1995. Vol. 81(1-2). P. 105.

93. Nourgaliev R.R., Dinh T.N., Theofanous T.G., Joseph D. The lattice Boltzmann equation method: theoretical interpretation, numerics and implications // International Journal of Multiphase Flow. 2003. Vol. 29. P. 117.

94. Chen Sh., Wang Zh., Shan X. and Doolen G.D. Lattice Boltzmann Computational Fluid Dynamics in Three Dimensions // Journal of Statistical Physics. 1992. Vol. 68. Nos. 3/4. P. 379.

95. McNamara G.R. and Zanetti G. Use of the Boltzmann Equation to Simulate Lattice-Gas Automata // Physical Review Letters. 1988. Vol. 61. No 20. P. 2332.

96. Sterling J.D. and Chen Sh. Stability Analysis of Lattice Boltzmann Methods //Journal of Computational Physics. 1996. Vol. 123. P. 196.ф 108. Artoli A. M., Hoekstra A. G. and Sloot P. M. A. Accuracy of 2D Pulsatile

97. Flow in the Lattice Boltzmann BGK Method // ICCS 2002. LNCS. 2002. Vol. 2329. P. 361.

98. Bernaschi M., Succi S. and Chen H. Accelerated Lattice Boltzmann Schemes for Steady-State Flow Simulations // Journal of Scientific Computing. 2001. Vol. 16. No. 2. P. 136.

99. Медведев Ю.Г. Клеточно-автоматные модели в задачах газовой динамики // Конгресс по прикладной и индустриальной математике. Новосибирск. 1998. С. 91.

100. Hayot F. Reynolds Stresses in a Lattice Gas // Journal of Statistical Physics. 1992. Vol. 68. Nos. 3/4. P. 557.

101. Medvedev Yu. Modification of a 2D Gas-Lattice Model // Bull. Nov. Сотр. Center. 1999. Special issue, NCC Publisher. P. 82.

102. Медведев Ю.Г. Модификация клеточно-автоматной модели потока жидкости // Новые информационные технологии в исследовании дискретных структур. Томск: ТНЦ СО РАН. 2000. С. 84.

103. Pogudin Yu. and Bandman O.L. Simulating Cellular Computations with ALT. A Tutorial // Lecture Notes in Computer Science. 1997. Vol. 1277. Berlin: Springer. P. 424.

104. Pogudin Yu. Simulation of Fine-Grained Parallel Algorithms with the ALT System // Proc. of the First Intern. Workshop on Distributed Interactive Simulation. N.Y.: IEEE Press, 1998. P. 22.

105. Achasova S., Bandman O., Markova V., Piskunov S. Parallel Substitution Algorithm: Theory and Application // Singapore et al.: World Scientifc. 1994.

106. Белоцерковский O.M. Численный эксперимент в турбулентности: от порядка к хаосу. М: Наука. 1997.

107. Шаскольская М.П. Кристаллография. М: Высш. шк. 1984.

108. Зигальская Ю.Г., Литвинская Г.П. Геометрическая кристаллография. М. 1973.

109. К. Роджерс. Укладки и покрытия. М: Мир. 1968.- 108123. Conway J. H. and Sloane N. J. A. The Leech Lattice, Sphere Packings, and Related Topics. Springer-Verlag. 1984.

110. Ландау Л.Д., Лифшиц Е.М. Гидродинамика. М: Наука. 1988.

111. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб: БХВ-Петербург. 2004.

112. Корнеев В.Д. Параллельное программирование в MPI. Новосибирск: Изд-во СО РАН. 2002.

113. Sahami М. Flow phenonena in rocks: from continuum models to fractals, cellular automata, and simulated annealing // Review in Modern Physics. 1993. Vol. 65. N4. P. 1393.