Параллельный алгоритм моделирования роста дендритных кристаллических структур
Автор работы: Пользователь скрыл имя, 18 Ноября 2013 в 07:47, курсовая работа
Описание работы
Уфимский государственный авиационный технический университет
В данной работе рассмотрена имитационная модель образования дендритов при кри-
сталлизации биологической жидкости. Разработан параллельный алгоритм динами-
ческой визуализации и численного расчета процесса кристаллизации для вычисли-
тельных систем с общей памятью. Проведены расчеты роста кристаллов при различ-
ных начальных условиях.
Файлы: 1 файл
Параллельный алгоритм моделирования роста дендритных
кристаллических структур
Д.И. Халирахманов, С.А. Маякова
Уфимский государственный авиационный технический университет
В данной работе рассмотрена имитационная модель образования дендритов при кри-
сталлизации биологической жидкости. Разработан параллельный алгоритм динами-
ческой визуализации и численного расчета процесса кристаллизации для вычисли-
тельных систем с общей памятью. Проведены расчеты роста кристаллов при различ-
ных начальных условиях.
1. Введение
На сегодняшний день разработка и совершенствование методов исследования биологиче-
ских жидкостей представляют большой интерес при диагностике и моделировании различных
патологических состояний. Данные современных исследований [1 – 6] свидетельствуют о том,
что первичные изменения, связанные с действием патогенного фактора на организм возникают,
прежде всего, на молекулярном уровне.
В биологических жидкостях происходят постоянные изменения молекулярного состава и
характера взаимодействия различных компонентов. Такие изменения являются наиболее ин-
формативными при исследовании гомеостаза молекулярного уровня и могут служить основой
для диагностики ранних стадий различных заболеваний.
Одним из направлений в разработке новых, доступных для практической лаборатории ди-
агностических методов является исследование структур биологических жидкостей, которые
образуются при переходе их в твердое состояние в процессе кристаллизации. Преимуществами
таких методов являются простота, информативность и массовость.
В настоящее время используются различные подходы к изучению структур твердой фазы
биожидкостей с целью получения диагностической информации, однако основная часть полу-
ченных данных остается на уровне описания отдельных феноменов без выявления их ассоциа-
тивных связей с теми или иными патологическими отклонениями. Плохо изучена взаимосвязь
процесса кристаллизации биологических жидкостей с данными их химического состава и фи-
зическими показателями. В большинстве работ, посвященных вопросам роста кристаллов, рас-
сматриваются процессы роста из переохлажденной жидкости, что малоприменимо к жидкостям
биологическим.
Математическое моделирование дает возможность построения моделей подобных процес-
сов и структур, а также значительно упрощает процедуру самой диагностики. Проблемой при
подобном изучении может стать значительная вычислительная ресурсоемкость, что можно
обойти, использую параллелизм при моделировании.
Основной целью данного исследования является разработка параллельных алгоритмов мо-
дели роста дендритных структур в биологических жидкостях и тестирование эффективности
этих алгоритмов на вычислительных системах с общей памятью.
2. Теоретическая часть
2.1. Математические модели физических процессов, проходящих при кристалли-
зации
Данная работа основана на развитии модели, описанной в статье Баранова В.Г. и
Хра-
мова А.Г. «Моделирование процесса роста дендритных кристаллических структур» [1]. В ней
рассматривается кристаллизация небольшого количества раствора заданного вещества с приме-
сями, зажатого между двумя стеклами, что исключает испарение капли. При росте кристалла в
таких условиях главную роль играет диффузия. Однако скорость диффузии – величина очень
704
незначительная. Следовательно, у удаленных молекул мало возможности попасть к поверхно-
сти кристалла. При создавшихся условиях кристалл может расти только таким образом, чтобы
при минимальной затрате строительного материала продвинуться максимально дальше в ту
сторону, где этот материал имеется. Кристалл начинает расти тонкими отростками - дендрита-
ми. На практике для диагностики используется схожий метод клиновидной дегидратации – бы-
строго высушивания образца в течение 2 – 3 часов.
Разобьем область, в которой рассматривается образование кристалла, сеткой на элементар-
ные квадратные ячейки. Одну ячейку этой сетки мы будем считать минимальной неделимой
единицей пространства – элементарным объемом. Каждая элементарная ячейка характеризует-
ся своим состоянием: раствором или кристаллом, находящимся в этой ячейке; концентрацией
вещества в ячейке; концентрацией примеси в ячейке.
В растворе происходит диффузия вещества и примеси. В каждой точке границы между рас-
твором и кристаллом в каждый момент времени есть вероятности кристаллизации элементар-
ной ячейки около границы роста кристалла за определенный промежуток времени. При реали-
зации этого случайного события происходит перенос вещества и примеси помимо диффузии:
недостающая примесь поступает в ячейку из окружающего раствора, избыточное вещество
распределяется по соседним ячейкам. Стоит также отметить, что из каждой ячейки количество
забираемой примеси пропорционально ее изначальной концентрации. Примесь в уже кристал-
лизованных ячейках в вышеописанных процессах не участвует.
2.2. Диффузия вещества и примеси
Процессы диффузии вещества и примеси описываются следующим дифференциальным
уравнением:
2
2
2
2
y
C
x
C
D
t
C
,
(2.1)
где C – концентрация, D – коэффициент диффузии.
Считаются известными начальные условия (распределение концентрации вещества и при-
меси в начальный момент времени) и граничные условия (через границу раствора и кристалла
диффузия не переносит вещество и примесь).
Для решения дифференциальных уравнений была выбрана простейшая пятиточечная явная
разностная схема, имеющая следующий вид:
k
j
i
k
j
i
k
ij
k
j
i
k
j
i
x
t
k
ij
k
ij
C
C
C
C
C
h
h
D
C
C
1
,
1
,
,1
,1
2
1
4
,
)
,(
,0
,
0
j
i
C
C
k
ij
ij
ij
. (2.2)
Эта разностная схема имеет первый порядок аппроксимации по пространству h
x
и времени
h
t
и устойчива при выполнении условия
D
h
h
x
t
4
1
2
.
2.3. Вероятности кристаллизации
Кристаллизация элементарных ячеек – это случайные события, происходящие с некоторой
вероятностью. Рост грани кристалла рассматривается как пуассоновский поток событий. Собы-
тием является кристаллизация элементарной ячейки. Вероятности кристаллизации p элемен-
тарной ячейки в зависимости от шага по времени Δt равна:
x
t
V
p
exp
1
,
(2.3)
где V – средняя скорость роста грани кристалла; Δt, Δx – соответственно шаги дискретизации
по времени и пространству. За один шаг по времени кристаллизуется одна ячейка, выбранная
случайно среди ячеек с одинаковой вероятностью кристаллизации, равной максимальной.
Скорость роста грани кристалла зависит, в свою очередь, от концентрации примеси. Кон-
центрация примеси в растворе C
в
может меняться от нуля до плотности этого вещества в твер-
дой фазе ρ
в
. Очевидно, что скорость роста грани равна нулю при нулевой концентрации и стре-
705
мится к бесконечности при приближении концентрации к максимальной ρ
в
. Концентрация на-
сыщенного раствора соли C
0
и базовая скорость роста кристалла V
0
являются известными вели-
чинами. Окончательные выражения для скорости роста имеют вид:
в
в
в
в
C
C
C
C
V
V
0
0
0
.
(2.4)
2.4. Перенос вещества и примеси при кристаллизации
В момент осуществления события кристаллизации концентрация примеси в ячейке ниже
плотности кристалла, и в ней имеется некоторое количество вещества. Таким образом, при из-
менении статуса ячейки необходимо корректировать в ней концентрации вещества и примеси.
При этом в кристаллизующейся ячейке необходимо сохранять общее количество жидкости.
Для этого при кристаллизации одной ячейки приходится корректировать состояния соседних
ячеек – лишнее вещество вытесняется в них, а недостающая примесь забирается из них.
Пусть кристаллизуется ячейка с концентрацией примеси C. После кристаллизации ее кон-
центрация должна стать равной плотности вещества кристалла ρ. То есть в эту ячейку должна
дополнительна поступить примесь в количестве C
н
= ρ − C из соседних ячеек. Если примеси в
них не хватает, то нужное ее количество добирается из следующей группы соседей. В группу
относятся все ячейки из раствора, находящиеся на одинаковом расстоянии от кристаллизуемой
ячейки. Количество доступных «донорских» групп ограничено из соображений сохранения фи-
зичности процесса. Если же примеси не хватает во всех доступных группах, то кристаллизации
не происходит и эта ячейка на следующем временном шаге как потенциальный претендент не
рассматривается. При отсутствии изменения количества кристаллизованных ячеек на протяже-
нии заданного числа шагов по времени процесс роста кристалла считается прекращенным.
3. Реализационная часть
3.1. Этапы алгоритма программы
На рис. 1 схематично представлен алгоритм, реализованный в про-
грамме. Проанализировав данную схему, можно сделать вывод, что не
все ее модули имеет смысл подвергать параллелизации (в частности
модуль отрисовки кристаллизованной на данном шаге ячейки и потен-
циальных претендентов на кристаллизацию или модуль вывода полу-
ченных результатов). Модули цикла по времени и модуль переноса ве-
щества также не предрасположены к параллелизму изначально, так как
они требуют для своего вычисления значений предыдущих операций,
вычисляемых в них же. Цикл эффективно распараллеливается, если от-
сутствуют перекрестные зависимости между его итерациями. Таким
образом, выделена та часть алгоритма, расчет которой возможно уско-
рить. Далее рассмотрим подробнее все оставшиеся модули, которые
будут впоследствии распараллелены (выделены на рисунке заливкой).
В модуле генерации матриц заполняются два массива: массив кон-
центраций примеси в ячейках случайным образом из заданного диапа-
зона и массив состояний ячеек нулями, а также задаются несколько
кристаллизованных ячеек в центре для начала роста кристалла. В моду-
ле уравнения диффузии пересчитываются значения в еще не кристалли-
зованных ячейках согласно разностной схеме и вычисляется макси-
мальная вероятность кристаллизации среди ячеек, у которых есть уже
кристаллизованные соседи, что также реализовано с использованием
двойного цикла. В эту же часть алгоритма включена реализация усло-
вия непротекания на границе рассматриваемой области. В модуле опре-
деления кристаллизуемой ячейки снова происходит обход всех ячеек и выявление тех из них,
вероятность кристаллизации которых равна максимальной (если таковых несколько, то выби-
Рис. 1. Схема модулей
алгоритма программы
706
рается одна из них случайным образом). На всех этих этапах выполнения программы подав-
ляющее большинство расчетов происходит внутри циклов.
На этапе просмотра соседей происходит определение количества примеси во всех доступ-
ных группах соседей-доноров и их общее количество. Уже кристаллизованные ячейки при этом
не учитываются. Здесь же принимается решение о возможности кристаллизации на основе на-
личия или отсутствия необходимого объема примеси, а также происходит планирование пере-
распределения вещества и примеси.
3.2. Тестирование последовательного алгоритма моделирования
На основе рассмотренного выше алгоритма была написана последовательная программа,
способная динамически визуализировать процесс
кристаллизации раствора с заданными начальными
условиями. Вместе с этим программа выводит рядом
с изображением дополнительные данные о самом
процессе, такие как фрактальная клеточная размер-
ность, средняя концентрация примеси в некристал-
лизованных ячейках, время роста кристалла, время
работы программы и количество шагов роста. Также
предусмотрена опция роста до определенного задан-
ного момента времени и алгоритм отображения не
только кристаллизованных ячеек, но и потенциаль-
ных претендентов на кристаллизацию.
Проведены эксперименты с разными начальны-
ми параметрами, полученные изображения и посчи-
танная клеточная размерность кристалла говорят об
адекватности построенной модели. В результате по-
лучены изображения кристалла с изрезанной грани-
цей и довольно сложной структурой. Исследована зависимость фрактальной размерности от
таких параметров, как коэффициент диффузии, равновесная концентрация, равновесная ско-
рость и максимальная концентрация примеси в ячейке.
Пример работы программы при размере решетки 100×100 ячеек с концентрацией примеси
от 0 до 4.7%, коэффициентом диффузии 1.5*10
-5
см
2
/сек, базовой скоростью роста 0.01 мм/сек и
глубиной забора вещества при кристаллизации в 3 группы ближайших ячеек представлен на
рис. 2.
Данный кристалл имеет клеточную фрактальную размерность ≈ 1.62 и среднюю удельную
концентрацию примеси в некристаллизованных ячейках 1.8%. При выборе диапазона началь-
ных концентраций в ячейках от 0 до 3.5% кристаллизация при таких же условиях вообще не
наблюдается.
Рис. 2. Пример визуализации растущего
кристалла
Рис. 3. Графики зависимости клеточной фрактальной размерности (слева – от максимальной кон-
центрации примеси, справа – от коэффициента диффузии)
707
Клеточная фрактальная размерность поначалу сильно зависит от максимальной концентра-
ции примеси в растворе, но при достижении концентрации ≈ 7% рост клеточной размерности
замедляется и асимптотически стремится к 2 (рисунок 3, слева). Также можно отметить, что
клеточная размерность слабо зависит от базовой скорости кристаллизации V
0
и имеет обрат-
ную зависимость от концентрации насыщения C
0
. При вариации коэффициента диффузии на-
блюдается эффект смены преобладания химических процессов к диффузионным, как основных
кристаллообразующих сил (рис. 3, справа).
Очевидно, что для получения достоверных результатов требуется брать гораздо более мел-
кое разбиение сетки. Соответственно растет количество требуемых для проведения экспери-
мента вычислений. При тестовом запуске последовательной программы на одном ядре процес-
сора расчет сетки 1000×1000 элементов занял 16.7 минут, при расчете сетки размером
5000×5000 время возросло до 509.5 минут. Подобная ресурсоемкость обуславливает необходи-
мость адаптации алгоритма для параллельных вычислений.
3.3. Создание параллельного алгоритма
3.3.1. Идеология распараллеливания
Предварительно было произведено профилирование последовательной программы, на ос-
нове которого проводился дальнейший анализ и оптимизация алгоритма программы. При ис-
пользовании явной разностной схемы, которая занимает значительную часть расчетного време-
ни, а также реализованного алгоритма переноса вещества, модель программирования на общей
памяти наиболее предпочтительна. Поэтому в ходе разработки параллельной программы было
решено использовать библиотеки OpenMP, где все потоки могут иметь доступ к общим масси-
вам данных, таким образом отсутствуют затраты на пересылку.
3.3.2. Приемы распараллеливания
Во всех вышеописанных модулях применено распараллеливание циклов путем распреде-
ления итераций между потоками с использованием управляемого планирования, так как при
статическом планировании нет никакого способа, позволяющего сбалансировать нагрузку
на разные потоки. При динамическом и управляемом планировании нагрузка распределяется
автоматически, но, как правило, при управляемом планировании код выполняется быстрее, чем
при динамическом, вследствие меньших издержек на само планирование. Наибольшая эффек-
тивность применения именно такого планирования проверена множественными тестовыми за-
пусками программы при разных размерностях расчетной сетки. Использование подобного
приема может обеспечить довольно хорошую масштабируемость алгоритма, особенно при ус-
ловии основной вычислительной нагрузки внутри циклов.
Участки алгоритма, не входящие в циклы и не зависящие друг от друга, были выделены в
области параллельных структурных блоков. При выполнении программы каждой секции
в параллельном регионе ставится в соответствие один поток из группы потоков, и все секции
выполняются одновременно.
Исключениями из параллельных областей распараллеленных модулей остались участки
кода отвечающие за выделение памяти (в модуле генерации матриц), задание начальных кри-
сталлизованных ячеек (также в модуле генерации матриц), случайный выбор одной из уже най-
денных ячеек с вероятностью кристаллизации, равной максимальной (в модуле кристаллизуе-
мой ячейки). Однако стоит отметить, что время их выполнения в программе много меньше
времени выполнения модулей, содержащих эти участки.
Таким образом, были ускорены все расчетные части алгоритма.
4. Экспериментальная часть
В ходе оптимизации последовательной программы для ее дальнейшего распараллеливания
было ощутимо снижено как количество операций в отдельных частях алгоритма, так и количе-
708
ство обращений к памяти. Это позволило не только ускорить программу более чем в два раза,
но и упростить задачу выделения участков потенциального параллелизма.
Все запуски последовательной и параллельной версий программы производились на рабо-
чей станции с четырехядерным процессором Intel Xeon (2.00 GHZ), 4 Mb Cache, 4 Gb RAM и
операционной системой Windows 7 x64.
Таблица 1. Результаты запуска распараллеленной программы на разном числе ядер процессора
p
Время, с
Ускорение Эффективность
Процессорное время
Время простоя
1
595,2
1,00
1,00
589,4
5,8
2
435,6
1,37
0,68
805,4
65,8
3
365,7
1,63
0,54
959,3
137,8
4
310,2
1,92
0,48
1130,9
109,9
Результаты тестовых запусков параллельной программы при размерности решетки
1500×1500 ячеек с максимальной концентрацией примеси 5.5%, коэффициентом диффузии
1.5*10
-5
см
2
/сек, базовой скоростью роста 0.01 мм/сек и глубиной забора вещества при кристал-
лизации в 3 группы ближайших ячеек представлены в табл. 1 и на рис. 4.
5. Заключение
В ходе данной работы разработан универсальный алгоритм для решения задачи моделиро-
вания и изучения процесса роста дендритных кристаллических структур из растворов биологи-
ческих жидкостей. На основе данного алгоритма спроектирована программная система с гра-
фическим пользовательским интерфейсом, который позволяет редактировать параметры алго-
ритма и входные данные, запускать этот алгоритм на исполнение, а также визуализировать
процесс роста рассматриваемого кристалла. Исследована зависимость клеточной фрактальной
размерности растущего кристалла от основных физических параметров раствора. Использова-
ние директив OpenMP позволило ощутимо сократить время выполнения программы на много-
поточных системах с общей памятью по сравнению с последовательной версией, особенно при
больших размерностях расчетной сетки. Представленные результаты вычислительных экспе-
риментов показывают эффективность предложенного алгоритма
В будущем с помощью имитационного моделирования планируется исследовать влияние
основных параметров, рассмотренных в работе, на форму кристаллов, а также предполагается
установление взаимосвязи между доступными для измерения геометрическими парамет-
рами изображений кристаллов и физическими параметрами раствора, а также расширить
функциональность и информативность программы путем расчета дополнительных параметров
изучаемого процесса.
Также в дальнейшем планируется использовать GPU с целью проверки эффективности ре-
шения подобного класса задач на гибридных системах и получения еще более производитель-
ного параллельного алгоритма.
Рис. 4. Оценка распараллеливания алгоритма (слева – полученное ускорение, справа - эффективность)
709
Литература
1. Баранов В.Г., Храмов А.Г. Моделирование процесса роста дендритных кристаллических
структур // Компьютерная оптика, Самара-Москва, 2001, № 21, с. 193-197.
2. Шабалин В. Н., Шатохина С. Н. Структурная форма информации в биологических жидко-
стях // Актуальные проблемы геронтологии.- М., 1999, c. 139-143.
3. Денисов А.Б. Слюнные железы. Слюна. М: РАМН 2003; 132.
4. Шабалин В.Н., Шатохина С.Н. Морфология биологических жидкостей человека. М 2001; c.
303.
5. Егорова Э.В., Шплкин Г. А., Толчипская А.И. и др. Кристаллографический анализ слезной
жидкости пациентов с катарактой до и после оперативного вмешательства // Брошевские
чтения: Тр. Всерос. конф.- Самара, 2002, с. 530-531.
6. Бузоверя М.Э., Сельченков В.Л., Сельченкова Н.И. и другие. Математический анализ
структур твердой фазы биологических жидкостей // Альманах «Геронтология и гериатрия»
Вып. 1. - М., 2001, с. 55-60.
710
Информация о работе Параллельный алгоритм моделирования роста дендритных кристаллических структур