close

Вход

Забыли?

вход по аккаунту

?

Анализ параллельных алгоритмов при моделировании процесса распространения лесных пожаров.

код для вставкиСкачать
Вестник КрасГАУ. 200 9. №7
Выводы
В ходе данной работы проведено исследование процесса формирования страховой документации
ООО «Надежда». Проанализированы различные программные средства разработки и предложены альтернативные варианты для создания программного комплекса решения автоматизации задачи.
При дальнейшем развитии проекта будет разработан программный комплекс, позволяющий в короткие сроки производить необходимые дополнения и изменения в автоматизации процесса формирования
страховой документации.
Литература
1
2
3
Калянов, Г.Н. CASE: структурный системный анализ (автоматизация и применение) / Г.Н. Калянов. –
М.: ЛОРИ, 1996. – 180 с.
Розенберг, Д. Применение объектного моделирования с использованием UML / Д. Розенберг, К. Скотт. –
М.: ДМК, 2002. – 160 с.
Методология структурного анализа и проектирования / http://www.marathon.ru.
УДК 519.63
Г.А. Доррер, М.С. Вдовенко
АНАЛИЗ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ПРИ МОДЕЛИРОВАНИИ ПРОЦЕССА РАСПРОСТРАНЕНИЯ
ЛЕСНЫХ ПОЖАРОВ
Рассмотрена эффективность параллельных алгоритмов при моделировании динамики лесных пожаров. Проанализированы различные способы декомпозиции сеточной области. Приводится оценка ускорения вычислений по данным эксперимента, выполненного на кластере ИВМ СО РАН.
Ключевые слова: лесной пожар, эффективность параллельных алгоритмов, моделирование лесных пожаров.
G.A. Dorrer , M.S. Vdovenko
ANALYSIS OF PARALLEL ALGORITHMS FOR THE FOREST FIRE PROPAGATION PROCESS MODELLING
The efficiency of the parallel algorithms in forest fire dynamics modelling is considered. Various ways of decomposition of the grid area are analyzed. The estimation of calculation acceleration on the basis of experiment data
made on the Institute of Computing Modeling cluster is given.
Key words: forest fire, parallel algorithms efficiency, forest fires modelling.
Введение
Разработка математических моделей распространения пожара позволяет предсказывать его поведение, что может помочь более эффективной борьбе с огнем. Ключевой проблемой при этом является необходимость сбора большого количества данных об условиях горения и противопожарных мероприятиях. В последнее время в связи с созданием и вводом в эксплуатацию Информационной системы дистанционного
мониторинга ИСДМ-Рослесхоз [1], основанной на использовании спутниковой информации о пожарной обстановке в лесах, сложились благоприятные условия для разработки систем моделирования и прогнозирования лесных пожаров на всей территории России.
15
Математика и информатика
Проблема математического моделирования процессов горения при лесных пожарах изучается уже в
течение многих лет. Обзор результатов, полученных в этой области, приведен в работе [4]. Большой вклад в
решение данной проблемы внесли Н.П. Курбатский, Э.Н. Валендик, М.А. Софронов, А.М. Гришин,
Г.Н. Коровин, F.A. Albini, G.M. Byram, R.C. Rothermel, M.G. Cruz, M.E. Alexander и другие ученые.
Следует отметить, что для моделирования крупных многодневных лесных пожаров, а тем более для
моделирования совокупности пожаров, возникших в пределах некоторой лесной территории, требуются значительные вычислительные ресурсы, и использование кластерных вычислительных систем становится
практически неизбежным. При решении задач, связанных с исследованием природных процессов на больших территориях, общим подходом для получения равномерного распределения вычислительной нагрузки
между процессорами является разделение вычислительной области на подобласти, количество которых совпадает с числом используемых процессоров, т.е. использование принципа геометрической декомпозиции [6].
Целью настоящей статьи является разработка и анализ параллельных алгоритмов, основанных на
разбиении моделируемой области на равновеликие подобласти, и исследование их эффективности при
использовании модели лесного пожара типа бегущей волны [4].
1. Анализ задачи и выявление ее потенциального параллелизма
Разработка параллельных программ практического уровня сложности представляет собою многоэтапный технологический процесс: постановка и анализ задачи, выбор модели программирования, декомпозиция задачи на параллельные процессы, анализ производительности и организации вычислительного эксперимента.
Постановка задачи. В качестве базовой модели процесса распространения лесного пожара нами
взята модель, основанная на вычислении теплового баланса в лесных горючих материалах [4]. Массив горючего представляет собой в общем случае n параллельных однородных слоев горючего, расположенных
один над другим. Произвольный i -й слой занимает по вертикали область Z i с координатами от z iH до ziK
и содержит запас горючего материала
x, y, z , t кг/м3 .
Вертикальная координата середины i -го слоя обозначается z icp , а его толщина
zicp
ziH
ziK 2 ,
i
ziK
i
. При этом
ziH , i 1,, n .
Свойства горючего в пределах каждого слоя не зависят от z .
Горючий материал в окрестностях точки C в некоторый момент времени может находиться в одном
из трех состояний, описываемых функцией S x, y , z , t
0, если в точке C в момент t имеется ненулевой запас горючего (т.е.
x, y, z , t 0 ), но горения не происходит;
S x, y , z , t
1, если
2, если
x, y , z , t
x, y , z , t
0 и происходит горение;
0 , т.е. горение невозможно.
Области, соответствующие состояниям S 0 , S 1 , S 2 , обозначаются соответственно
1,
1,
2 . Проекции областей
2 на горизонтальную плоскость D будем обозначать соответ0,
0,
ственно D0 , D1 , D2 , причем D0
D1
D2
D.
Уравнение нагрева для горючего в окрестности точки C
ходится в состоянии S x, y , z , t
0:
16
x, y, z , которое в момент времени t на-
Вестник КрасГАУ. 200 9. №7
H j x, y , t
n
e
e
вт/м3;
x
x1 , y
y1 dx1 dy1
(1)
x, y , t
k j x, y H j x, y , t
H 0 j x, y ,
z jK
H v x, y, z , t dz , при начальном условии H j x, y,0
z jH
H 0 j x, y ,
z jH
D0 j , i 1,...,n . Здесь H x, y , z , t – значение энтальпии в точке x, y , z , в момент времени t ;
x, y
,
z jK
ij
i 1 D
1i
1
где H j x, y, t
x1 , y1 , t
i
t
ij
– соответственно, энергия, образующаяся при горении и поступающая от внешних источников,
x x1 , y
y1 – функция влияния пламени из точки x1 , y1 на точку x, y (функция Грина) из
i -го слоя на j -й слой; k x, y, z
c
, где
– коэффициент теплоотдачи, Вт/м2град;
– удельная по-
верхность слоя, м-1; c – приведенная теплоемкость влажного материала, Дж/кг град.
Условие воспламенения горючего в j -м слое, т.е. перехода горючего в состояние S j x, y, z, t
*
имеет вид H j x, y, t j
x, y
H *j x, y , где t *j
1,
t *j x, y – время воспламенения горючего в j -м слое в точке
D0 j ; H * – энтальпия начала газификации.
Уравнение расходования горючего:
j
t
с начальным условием
Здесь
j
0j
j
r j при
0 при
x, y , t
x, y
x, y, t *j
0j
j
j
x, y , t 0
x, y , t 0
x, y , x, y
(2)
D1 j .
– активный запас горючего материала, в j -м слое, кг/м3; r j – относительная скорость сго-
рания j -го слоя, 1/с.
Уравнение тепловыделения в j -м слое:
j
x, y, t
x, y, t
j
-h j x, y
t
, x, y
D1 j , j 1,...,n ,
(3)
где h j – теплота сгорания горючего, Дж/кг.
Условие погасания (перехода в состояние S j x, y, t
j
2 ):
j
x, y, t j*
0,
x, y
D2 j ,
1,...,n .
Модель теплопередачи из зоны горения к горючим материалам, задаваемая функцией влияния
(функцией Грина) ij x x1 , y y1 , подробно рассмотрена в [4].
Система уравнений (1)–(3) представляет собой модель процесса распространения горения по неоднородным слоям горючего типа бегущей волны. Особенностью рассмотренной модели является то, что
часть входных и выходных переменных представляет собой множества 0 t , 1 t и 2 t .
Метод решения. Алгоритм построения горящей кромки основан на численном решении уравнений (1)–(3),
описывающих распространение процесса горения. В каждом из слоев вводится прямоугольная сетка с шагами по координатам x и y соответственно x и y , области D0i , D1i и D2i заменяются соответствующими сеточными областями D
0i
, D
1i
, D
2i ,
l
1,2 . Перейдя к дискретному времени t
0,1,2,... с ша-
гом t и заменив в (1)–(2) частные производные по времени разностными отношениями, а интеграл по области D1i суммой, получим расчетные уравнения, которые использовались при дальнейших исследованиях.
Функции влияния
ij
x x1, y
y1 зависят от характеристик леса, природных и погодных факторов
и вычислялись по специальным подпрограммам [4].
17
Математика и информатика
В качестве исходных данных использовались:
область моделирования в виде двух множеств узлов D
i, j , i 1,..., nl , j 1,..., ml , l
l
начальный и конечный моменты времени t 0 и t f , временной шаг
участки с одинаковыми характеристиками горючих материалов
1,2 ;
t;
kl ,
k 1,..., K ,

kl
D l, l
1,2 ;
k
теплофизические характеристики горючего для каждого из участков
H 0kl t , H kl* t , k kl t , hkl t ,
0 kl ,
ekl
t ,
i, j, t , l
l
1,2 , k
kl
1,..., K , t
раметры функции, описывающей тепловое воздействие локального пламени
h fkl t ,
b
в каждый момент времени:
t0 , t0
0 kl
t ,..., t f ; па-
t , a0 kl t ,
kl
t ,
t ,wt ;
скорости сгорания rkl t для всех участков
начальное состояние системы – области D
k
в каждый момент времени t
0l
t0 , D
1l
t0 , D
2l
t0 , t0
t ,..., t f , k 1,..., K .
t0 .
Используя информацию о лесном горючем и внешней среде, можно получить исходные данные для
рассмотренной модели. Наибольшую сложность представляет вычисление функции влияния пламени
x1, y y1 . При моделировании крупных многодневных пожаров оценку этой функции можно полуij x
чить также путем анализа аэрокосмических снимков пожара, полученных в последовательные моменты времени [4]. На основе этих снимков могут быть вычислены необходимые для расчетов значения функций
x1 , y y1 и скоростей. Поскольку конфигурация кромки реальных пожаров часто является достаij x
точно сложной, то для упрощения расчетов целесообразно применять сглаживание границы контура на
снимке пожара, например, аппроксимацию его эллипсом. Это позволяет оперативно получать необходимые
для моделирования исходные данные.
Распараллеливание вычислений. Для распараллеливания процесса вычислений предлагается
схема, вытекающая из физического содержания данной задачи. Расчет энтальпии для точки (i, j ) на
(t 1) -м временном шаге происходит с использованием некоторого количества точек на t -м шаге. Численный расчет ведется итеративно: по имеющимся значениям t -го временного шага выстраивается (t 1) -й,
и т.д. Последовательность вычислений в виде иерархической сети Петри представлена на рис. 1.
P1
t1
P2
t2
P3
Рис. 1. Последовательность вычислений при моделировании распространения пожара. Позиции:
P1 – данные для инициализации функций библиотеки MPI; P2 – данные о метеоусловиях
и характеристиках горючего; P3 – отображение рассчитанной горящей кромки на карте местности.
Составные переходы: t1 – операции по вводу данных; t 2 – основной расчетный цикл
Таким образом, исходную задачу можно разбить на p подзадач для областей, D k1i , D k 2i , D k 3i ,
l
1,2, k
1,..., p , пересекающихся только по границе разбиений, независимых друг от друга на каждом
расчетном шаге. В случае технологии MPI каждый процесс получает часть сетки, причем сетки соседних
процессов пересекаются по двум узлам. Это пересечение сеток позволяет частично продублировать вычисления на соседних процессорах, что сокращает межпроцессорные обмены. Далее, в каждом процессоре
происходят вычисления последовательно по шагам по времени на части сетки. Иерархическая сеть Петри,
моделирующая основной расчетный цикл для одного процессора, показана на рисунке 2.
18
Вестник КрасГАУ. 200 9. №7
P21
1
P22
2
P23
3
4
P24
5
P25
6
Рис. 2. Модель основного расчетного цикла. Позиции: P21 – данные о метеоусловиях, характеристиках
горючего, горящих участках, начальном и конечном моментах времени горения, P22 – данные
о локальных функциях влияния, P23 – данные об энтальпии горючего, P24 – данные об энтальпии
с учетом влияния соседних участков, P25 – данные о состоянии горящих участков. Составные
переходы: 1 – вычисление текущего временного шага (выполняется при условии t tfinal ),
2 – определение границы локальных массивов, 3 – вычисление значения энтальпии горючего,
4 – обмен данными с соседними процессорами, 5 – определение новых воспламенившихся и погасших
точек, 6 – вывод в файл данных о конфигурации пожара
На каждом шаге по времени соседние процессоры осуществляют обмен граничными значениями при
помощи функций неблокирующих пересылок и приема данных MPI_Isend и MPI_Irecv. Схема обмена с соседними процессорными узлами процессора показана на рисунке 3. По окончании расчетов каждый процесс
обрабатывает свой массив вычисленных значений, записывая его в отдельный файл.
up
left
up
up
right
left
pr OC
right
du
left
du
du
right
Рис. 3. Схема обмена процесса " prOC " с соседними процессами: операции обмена
up dn, left right , upleft
dnright , upright
dnleft выполняются одновременно
Для сбалансированности вычислений и минимизации межпроцессорных обменов ключевая роль отводится выбору способа распределения данных и вычислений по процессорам. В рассматриваемом случае
возможны два различных способа разбиения исходной области по вычислительным узлам – одномерное и
двумерное разбиение. В обоих случаях исходная область включает взаимно перекрывающиеся подобласти,
и пересчет значений на границах между данными областями предполагает, согласно алгоритму, суммирование при обмене вычисленными значениями для граничных элементов. При этом для перехода к следующей
итерации необходимо согласование значений на границах расчетных подобластей. Пересылка данных осу-
19
Математика и информатика
ществляется с использованием процедур библиотеки MPI [7- 9]. Схема операций обмена данными (операция
4 на рисунке 2) показана на рисунке 4.
P41
P42
41
P43
42
43
P44
P45
44
Рис. 4. Модель обмена данными с соседними процессами. Позиции: P41, P42 , P43 , P44 , P45 – данные
для обмена с соседними процессорами (согласно рисунку 2). Составные переходы:
42
– обмен left
right ,
43
обмен upleft
dnright ,
44
41
– обмен upright
– обмен up
dnt ,
dnleft
Более детально схема одной из операций обмена показана на рисунке 5.
411
P411
K1
P413
K2
412
K3
P412
P414
K4
K5
tt
th
Рис. 5. Модель операций межпроцессорного обмена на примере операции
41
(рисунок 4), осталь-
ные операции выполняются аналогично: P411 , P412 – данные, приготовленные для обмена; P413, P414 –
данные полученные при обмене;
411
,
412
– операции пересылки данных; k1 , k 2 , k3 , k 4 , k5 – маркеры го-
товности к обмену данными; t h – начало операции обмена; t t – конец операции обмена.
Потенциальное ускорение алгоритма. Будем оценивать время работы параллельной программы
исходя из соотношения S p T1 / T p , где S p – ускорение, T1 – время вычислений на одном процессоре, T p
– время вычислений на p процессорах.
Для получения реалистических оценок помимо классической формулы Амдала [6] будем учитывать также
время, затрачиваемое программой на обмены между процессами. Как следует из принятой нами схемы распределения данных, на каждом временном шаге требуется обмен границами. Время пересылок для различных способов декомпозиции можно приблизительно выразить через количество пересылаемых данных [6]:
20
Вестник КрасГАУ. 200 9. №7
V 1D comm
V 2 D comm
2 N 3 , при одномерном разбиении,
4
N 3 , при двумерном разбиении,
p
где N 3 – размерность задачи, p – количество вычислительных узлов, – время пересылки одного
числа. Алгоритм и его программная реализация являются масштабируемыми, если ускорение и производительность зависят линейно от количества используемых процессоров [6, 9]: S p O( p) . На практике алгоритмы, для которых S p
O( p /(ln p)) также считаются масштабируемыми.
2. Проведение вычислительного эксперимента и анализ результатов
Параллельные программы тестировались на модельных задачах. Для модельной задачи был выбран
один однородный слой горючего, расположенный на местности с уклоном, который изменяется по заданному закону.
Таблица 1
Значение ускорения, показанного на кластере ИВМ СО РАН
Количество процессоров
1
2
4
8
Разбиение расчетной области на квадраты (двумерное разбиение)
Время выполнения основного цикла T [c ] 700,868934 359,8456 188,142001 81,975424
1,000000
1,947693
3,725213
8,549745
Ускорение, S
Эффективность, E S / p
1,000000
0,973847
0,931303
1,068718
Разбиение расчетной области на полосы (одномерное разбиение)
Время выполнения основного цикла T [c ] 700,868934 359,8456
207,0777
105,2597
1,000000
1,947693
3,384569
6,658474
Ускорение, S
Эффективность, E S / p
1,000000
0,973847
0,846142
0,832309
16
53,29919
13,14971
0,821857
87,26806
8,031219
0,501951
Расчеты производились по формулам (4)–(6) на кластерной системе МВС 1000 ИВМ СО РАН (г. Красноярск) на тестовой сетке 400 400 узлов при использовании от 1 до 16 процессоров.
Тестовая область представляла квадрат
= [1,6 ] × [1,6 ]. Возвышение поверхности задавалось
выражением z ( x) 1 cos(x / 150 ) . Процесс распространения пожара инициировался из узла с координатами (0.5, 0.5). При запуске параллельных программ измерялось время их работы в секундах. На основе
данных о времени работы программ (табл. 1) вычислялись другие характеристики параллельных программ,
такие как ускорение и эффективность распараллеливания. В вычислительных экспериментах было сделано
по 100 шагов по времени.
Значения ускорения, показанного на кластере ИВМ СО РАН, приведены в таблице 1. При применении
двумерной декомпозиции и 8 процессоров значение эффективности больше единицы, что объясняется использованием в программе «динамических» массивов с подстраиваемыми под выделенное число процессоров размерами. Таким образом, необходимы меньшие временные затраты на выборку обрабатываемых
данных из оперативной памяти и передачу их через КЭШ-память. В случае использования 8 процессоров
при данной размерности сетки весь массив помещается в КЭШе, что и определяет более быстрое выполнение вычислений за счет отсутствия необходимости обмена между оперативной памятью и КЭШем.
На рисунке 2 приводятся полученные графики зависимости ускорения алгоритмов и эффективности
распараллеливания в зависимости от количества используемых процессоров.
21
Математика и информатика
Рис. 6. Зависимость ускорения от количества доступных процессоров
Как видно из рисунка 6, результаты вычислительного эксперимента показали наличие хорошего ускорения при решении данной задачи.
Также был проведен вычислительный эксперимент, выявивший зависимость ускорения от роста размерности задачи. Были рассмотрены случаи мелкой (100х100=10000 узлов) и крупной (800х800=640000 узлов) сетки. Тестовая область представляла, как и ранее, квадрат: = [1,6 ] × [1,6 ], а возвышение поверхности задавалось формулой z ( x) 1 cos(x / 150 ) . Характеристики горючего также не изменялись.
В вычислительных экспериментах было сделано также по 100 шагов по времени. Декомпозиция расчетной
области – двумерная. Полученные значения ускорения, показанного на кластере ИВМ СО РАН
(г. Красноярск), приведены в таблице 2.
Значение ускорения, показанного на кластере ИВМ СО РАН
Размерность задачи
Время выполнения основного цикла на 1
процессоре T , c
Время выполнения основного цикла на 4
процессорах T , c
Ускорение S
Эффективность E S / p
Таблица 2
100×100
200×200
400×400
800×800
0,464515
7,300380
122,961800
1532,029398
0,185772
2,149292
33,887110
394,943400
2,5004621
0,625116
3,3966438
0,849161
3,6285715
0,907143
3,879111
0,969778
Выполненные расчеты показали, что с увеличением размерности задачи при использовании четырех
процессоров наблюдается увеличение ускорения вычислений, по крайней мере, для задач размерностью не
более 800×800. Из таблицы 2 видно, что при учете размера кэш-памяти можно добиться эффективности
больше 1. Значения ускорения вычислений с увеличением размерности задачи при использовании двумерной декомпозиции расчетной области возрастают логарифмически. Эту зависимость можно аппроксимировать выражением y = 0,3151Ln(x ) - 0,2059, с достоверностью аппроксимации R 2 0,8821 .
22
Вестник КрасГАУ. 200 9. №7
Рис. 7. Зависимость ускорения от размерности задачи
На рисунке 7 показана зависимость ускорения вычислений от размерности задачи. При увеличении
размерности задачи в 4 раза ускорение вычислений при использовании 4 процессоров возрастает. Средний
уровень эффективности распараллеливания составляет около 83%, что связано с неизбежными затратами
времени на организацию межпроцессорных обменов и записи результатов в файл.
Заключение
Мы видим, что, при численном решении задачи моделирования динамики лесного пожара возможно
применение как одномерной, так и двумерной декомпозиции. Однако результаты тестирования программ
показали, что наиболее эффективной при использовании, по крайней мере, от 4 до 16 процессоров является
двумерное разбиение исходной области.
В результате исследования были созданы следующие программы: программа, решающая обратную
задачу – получения значений скоростей на основе аэрокосмических снимков контуров пожара в последовательные моменты времени; программа для препроцессорной обработки данных – «разрезания» данных на
отдельные файлы для многопроцессорных вычислений; программа для численного моделирования распространения кромки лесного пожара, программа обмена данными между процессорами.
Получены расчетные значения ускорений, позволяющие оценить масштабируемость алгоритма и его
программной реализации. Эти результаты показывают, что алгоритм обладает значительным объемом потенциального параллелизма и хорошей, с точки зрения распараллеливания, структурой, что позволяет надеяться на получение ускорений, близких к линейным в зависимости от количества используемых процессоров для кластерных вычислительных систем. Значения ускорений, полученные в ходе вычислительного эксперимента, хорошо согласуются с теоретическими оценками.
Литература
1.
2.
3.
4.
Применение информационной системы дистанционного мониторинга «ИСДМ-Рослесхоз» для определения пожарной опасности в лесах Российской Федерации: учеб. пособие / ФГУ Авиалесоохрана. –
Пушкино (МО), 2007. – 82 с.
Софронов, М.А. Огонь в лесу / М.А. Софронов, А.Д. Вакуров. – Новосибирск: Наука, 1981. – 128 с.
Гришин, A.M. О математическом моделировании природных пожаров и катастроф / А. М. Гришин //
Вестн. Томского гос. ун-та: Математика и механика. – Томск: Изд-во ТГУ, 2008. – №2(3). – С. 105–114.
Доррер, Г.А. Динамика лесных пожаров / Г.А. Доррер. – Новосибирск: Изд-во СО РАН, 2008. – 404 с.
23
Математика и информатика
5.
6.
7.
8.
9.
Weber, R.O. Modeling fire spread through fuel beds / R.O. Weber // Prog. Everg. Combust. Sci. – 1990. –
V. 17. – P. 65–82.
Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. – СПб.: БХВ-Петербург,
2002. – 608 с.
Message-Passing Interface Forum, MPI-2: Extensions to the Message-Passing Interface, 1997.
[http://www.unix.mcs.anl.gov/mpi/], 13.03.2007.
RS/6000 SP: Practical MPI Programming. [www.redbooks.ibm.com], 11.08.2008.
Корнеев, В.Д. Параллельное программирование в MPI. – 2-е изд. / В.Д. Корнеев. – Новосибирск: Издво ИВМиМГ СО РАН, 2002. – 215 с.
24
Документ
Категория
Без категории
Просмотров
5
Размер файла
704 Кб
Теги
анализа, пожаров, моделирование, алгоритм, лесные, процесс, распространение, параллельное
1/--страниц
Пожаловаться на содержимое документа