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

003485274

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

Вдовенко Марина Сергеевна

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ РАСПРОСТРАНЕНИЯ ЛЕСНЫХ ПОЖАРОВ НА ОСНОВЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 6 НОЯ 2009

Красноярск - 2009 г.

003485274

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный технологический университет» (ГОУ ВПО СибГТУ) на кафедре системотехники, г. Красноярск

Научный руководитель: доктор технических наук, профессор Доррер Георгий Алексеевич

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

доктор физико-математических наук, профессор Белолипецкий Виктор Михайлович кандидат технических наук Кузнецов Алексей Владимирович

Ведущая организация: Институт леса СО РАН, г. Красноярск

Защита диссертации состоится 9 декабря 2009 года в 14:00 часом па заседании диссертационного совета ДМ 212.099.06 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Академика Киренского, 26, УЛК-115.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета по адресу: 660074, г. Красноярск, уд. Академика Киренского, 26, Г274

Автореферат разослан « 3 » ноября

Ученый секретарь диссертационного совета

года

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

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

Актуальность работы

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

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

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

Большой вклад в решение проблемы изучения и моделирования лесных пожаров внесли И. С. Мелехов, Н. П. Курбатский, М. А. Софронов, А. М. Гришин, Э. Н. Валендик, Г. Н. Коровин, А. В. Волокитина, Г. А. Доррер, F. A. Albini, М. Е. Alexander, R. Rothermel и другие ученые. Содержательный обзор исследований в мире по проблеме моделирования распространения лесных пожаров дан в ряде обзоров и монографий.

Разработка математических моделей распространения пожара позволяет предсказать его поведение, что способствует более эффективной борьбе со стихией огня. В настоящее время сложились благоприятные условия для разработки систем моделирования и прогнозирования лесных пожаров на всей территории России. Это связано с созданием и вводом в эксплуатацию Информационной системы дистанционного мониторинга ИСДМ-Рослесхоз, созданной Институтом космических исследований РАН. С помощью этой системы ФГУ «Авиалесоохрана» осуществляет управление лесопожарной ситуацией на территории РФ. Данная система, основанная на использовании спутниковой и наземной информации о пожарной обстановке в лесах, погоде и действующих пожарах, позволяет получать ряд необходимых данных для осуществления процесса прогнозирования. Ввиду сложности расчета процессов горения в течение многих дней на больших территориях задачи математического моделирования лесных пожаров требуют серьезных вычислительных ресурсов. Об этом свидетельствует, в частности, опыт применения моделирующей лесопожарной системы BehavePlus в США.1 Одним из

"Andrews, P.L. BehavePlus Modeling System: Past, Present and Future. US Forest Service, Rocky Montana Research Statuon, Missoula,

Montana. - 2005. - 13p.

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

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

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

Цели и задачи исследования

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

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

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

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

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

Объект и предмет исследования

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

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

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

- методы математического моделирования;

- методы вычислительного эксперимента;

- методы анализа взаимодействующих систем на основе сетей Петри;

- методы параллельного программирования.

Научная новизна работы

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

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

Практическая ценность работы

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

2. Разработан алгоритм оценки параметров пожаров по данным дистанционной съемки.

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

4. Результаты диссертации использованы в учебном процессе СибГТУ при изучении дисциплины «Вычислительная математика» студентами специальности 230105.65.

Основные результаты диссертации, выносимые на защиту

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

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

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

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

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

1. Международная конференция «Сопряженные задачи механики реагирующих сред, информатики и экологии» (г. Томск, 2007).

2. Десятая Всероссийская научно-практическая конференция «Проблемы информатизации региона» (г. Красноярск, 2007).

3. VI всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2008).

4. V международная конференция студентов и молодых учёных «Перспективы развития фундаментальных наук» (г. Томск, 2008).

5. 7-я международная конференция «Математическое моделирование опасных природных явлений и катастроф» (г. Томск, 2008).

6. Всероссийская конференция с международным участием «Пожары в лесных экосистемах Сибири» (г. Красноярск, 2008).

7. «Всероссийская конференция по математике и механике», посвященная 130-летию Томского государственного университета и 60-летию механико-математического факультета (г. Томск, 2008).

8. XI Всероссийский семинар «Моделирование неравновесных систем» (г. Красноярск, 2008).

9. Четвертая Международная конференция «Параллельные вычисления и задачи управления» РАСО 2008 (г. Москва, 2008).

В 2009 году получено свидетельство о государственной регистрации программы «Комплекс параллельных программ для численного моделирования распространения кромки лесного пожара (FIRE)» №2009613363.

Публикации

По теме диссертации автором опубликовано 14 работ (из них одна по списку ВАК). Из работ, выполненных в соавторстве, в диссертацию включены результаты, полученные автором лично.

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

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, содержащего 135 наименований, и двух приложений. Диссертация содержит 22 рисунка. Объем диссертации составляет 109 страниц, приложений -21 страница.

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

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

В первой главе описаны проблемы, связанные с моделированием лесных пожаров.

В разделе 1.1 дается обзор работ, посвященных изучению лесных пожаров. Известные на сегодняшний день модели распространения пожара можно разбить в две категории: связанные с регулярной системой сеток (т. е. точечный метод) и связанные с временным планом.

По назначению модели лесных пожаров можно разделить на три класса2, соответствующие трем уровням описания объекта:

2 Доррер, Г. А. Динамика лесных пожаров. - Новосибирск: Изд-во СО РАН, 2008.. 404 с.

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

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

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

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

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

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

Раздел 1.2 посвящен описанию модели лесного пожара как динамической системы типа бегущей волны. В качестве базовой модели процесса распространения лесного пожара взято уравнение теплового баланса в лесных горючих материалах. Массив горючего представляет собой в общем случае п параллельных слоев горючего, расположенных один над другим. Произвольный /-й слой занимает по вертикали область 2п с координатами от до гк и содержит запас горючего материала а>(х,у,г,1) кг/м3 .

а»

(-а слои

£ 1-0. слой

-г

Рис. I. Схема расположения слоев горючих материалов Вертикальная координата середины /-го слоя обозначается г, , а его толщина <5,. При этом г^ = (гЛ + 2Х )/2, 8, = зк - г„, / = 1,..., л.

Свойства горючего в пределах каждого слоя считаются не зависящими от г.

Горючий материал в окрестностях точки С, с координатами {х,у,:) в некоторый момент времени может находиться в одном из трех состояний, описываемых функцией 3(х,у,:,1):

0, если в точке С в момент времени I имеется ненулевой запас горючего (т. е. а>(х, у, г, I) > 0, но горение не происходит;

1, если ео(х,у, г, /)> 0, и происходит горение;

2, если аЯ.х,у, г, 0 = 0, т. е. горение невозможно.

(1)

Области, соответствующие состояниям 5 = 0, 5 = 1, 5 = 2 обозначаются соответственно П0, £1,, П2. Проекции областей П0, П,, 02 на горизонтальную плоскость О обозначаются соответственно £>„, Ц, йг, причем й0ий|и£); = Д.

Усредненное уравнение нагрева горючего в у'-м слое в окрестности точки С = (х,у,г), которое в момент времени / находится в состоянии 5{х,у,г,{) = 0 имеет вид

1

где Яу(х,у,/)=-- \н,(х. У,

2 ¡К 2!Н г„

при начальном условии Я;(х, у,0) = Я0; (х, у), (х,у)е Ооу> < = 1 Здесь н(х,у,2,{) - значение энтальпии в точке (х,у,г), в момент времени 1, дж/м3; Ф, Ф, - соответственно, энергия, образующаяся при горении и поступающая от внешних источников, вт/м3; ^(х-х^у-у,) - функция влияния пламени из точки

(дг,,.у1) наточку (х,у) (функция Грина) из /-го слоя на у'-й слой; к(х,у,:)= где

рс

а - коэффициент теплоотдачи, вт/м2град; р - удельная поверхность слоя, м'1; с' -приведенная теплоемкость влажного материала, дж/кг град, р - плотность слоя.

Условие воспламенения горючего в у'-м слое, т.е. перехода горючего в состояние 5;(дг,>,г,/)= 1 имеет вид: НН]{х,у), где ¡) = '"(х,у) - время воспламенения горючего в у'-м слое в точке (х,у)е О0/, Я* - энтальпия начала газификации.

Уравнение расходования горючего:

с начальным условием а>)

У,')

Г-гу притих,у,1)> 0 0при(о1(х,у,/)= О ,(х,у,(')= <оа/(х,у), (х,у)еОу. Здесь а>1 - активный запас горючего материала, в у-м слое, кг/м3; относительная скорость сгорания у-го слоя, 1/с. Уравнение тепловыделения в у-м слое:

(2)

где И1 - теплота сгорания горючего, дж/кг.

Условие погасания (перехода в состояние 5л(х,у,1)= 2): о)/(х,у,11.)= О, (х,у)е£>2,,7 = 1.....п.

Особенностью данной модели является то, что часть входных и выходных данных представляют собой динамические области О0(>), £},(<)> описывающие процесс распространения лесного пожара.

Весь комплекс теплофизических параметров сосредоточен в функциях тепловыделения Ф,{х,у,1) и влияния (функции Грина) ^(х-х^у-у,), которая для одного слоя горючего глубиной 8 имеет вид2

4{х-х1,у-у1)=4(р,<}>)=а06

рсоъ аг I

р011 + 5та/со5(р-р,)|1 + 5т2а/)|'

где р,<р - полярные координаты, - высота пламени, р0- характерная длина влияния пламени, а/(и>) - угол отклонения пламени от вертикали, <р, - угол, определяющий направление ветра, - скорость ветра, аа- масштабирующий коэффициент.

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

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

При этом контуры пожаров удобно аппроксимировать эллипсами, воспользовавшись методом эллиптических оценок Ф. Л. Черноусько3.

Динамика лесного пожара определяется последовательностью эллипсов £(?,), 1 = 1.....к, аппроксимирующих контуры пожара и задаваемых неравенством

где 1 = [^Г, текущие координаты на плоскости, а(!) = [а' (0,аг(')Г, координаты центра эллипса,

(2(0-2x2 матрица, определяющая размеры, эксцентриситет и ориентацию эллипса. При этом £(/,)<£(/,) при Скорость увеличения большого

диаметра эллипса дает оценку скорости фронта пожара V/ (!).

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

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

3 Черноусько Ф. Л. Оцениааниефжзоеотосостояннядкнамическихсистем. М.: Нжути, 1948. — 319 с.

4,19 la0p,j<M>(l + S/3hf)

v =---

7 И -Я0

Определив величину vf путем обработки аэрокосмических снимков, можно

уточнить значения необходимых для моделирования параметров пожара.

Во второй главе диссертации проведен анализ технических и программных средств, предназначенных для организации параллельных вычислений. Дан обзор таких средств как OpenMP, EXPRESS и PVM (Parallel Virtual Machine), отражена парадигма параллельной обработки данных, реализованная в языке высокого уровня HPF.

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

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

В данной главе приведена характеристика параллельной среды, в которой проводилось тестирование и вычислительные эксперименты с использованием разработанной нами программы, а также проведен обзор существующих параллельных реализаций программ для моделирования динамики распространения лесных пожаров (Global Fireline Propagation Model, ELFM (Everglades Landscape fire model), Parallel CFD fire modeling, FDS (Fire Dynamics Simulator)).

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

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

В п. 3.1 рассмотрен метод решения задачи, основанный на дискретизации модели, рассмотренной в первой главе. В каждом из слоев горючего вводится прямоугольная сетка с шагами по координатам х и у соответственно Дх и Ду, области D0I, Du и Dh заменяются соответствующими сеточными областями £>Л0/, Од„, DiV, / = 1,2-

Введено дискретное время, при котором система рассматривается в моменты < = 0,1,2,... с шагом At. Заменив в (1) частную производную по времени

разностными отношениями, а интеграл по области £)„ суммой, получим уравнение нагрева лесного горючего в виде:

2

1*1 (4)

+ Ф„(/,7,/)Дг - Д/*,(/,у)х [яД/.у,/)-//«(/, Д

с начальными условиями: //;((,у,0) = #„,(/, у), (/,у)е Од0|, / = 1,2.

Условие воспламенения горючего в /-м слое, при / = /": Н((/,у,/")£Я,'(1,7).

При этом узел (/,;) исключается из £>л0,(/') и присоединяется к Од„(/').

Уравнение расходования горючего:

/. . , |<у((|,У,О-'',Д'при й)Д|,у,0>О гиД|,у,/ + 1)=< , , , ч (3)

' Ц(/,/,/) при а;,(г,у,/)5 О

с начальным условием: ®/(«,у,<*)=в0|(/,у). (',у)е 1>д1,, / = 1,2. Уравнение тепловыделения:

/=1,2. (6)

Условие погасания при * = ».: <и,(/,у,/.) = 0, (/,у')е£>Д1(, при этом точка (;,у)

исключается из £>4„((.) и присоединяется к 041,(/.).

Функции влияния ^(х-лг,,^-^,) задаются формулами с учетом

дискретизации по пространству.

Предложенная схема дискретизации проста в реализации и экономична

(поскольку при ее использовании число арифметических действий необходимое

для нахождения решения на очередном временном шаге, пропорционально

)

количеству узлов сетки Л' = Р[Л,а). Но данная схема не является абсолютно

устойчивой, и для проведения корректных вычислений необходимо соблюдать

которое

условие согласования шагов сетки, которое для эквивалентной задачи теплопроводности имеет вид4

Д/ <

3-[ Л1ах *„(*.')]

где ка = ка(х,1)~ коэффициент теплопроводности в направлении а в момент времени г в точке д: е П, И,- шаг сетки в направлении а, Д/- шаг по времени. В качестве исходных данных используются:

- область моделирования в виде двух множеств узлов О» ={(/,у),| = 1,...,и„у=1,....>и,},/ = 12;

- начальный и конечный моменты времени /0 и ¡г, временной шаг Л(;

- участки с одинаковыми характеристиками горючих материалов йи, * = 1.....К,[)Ои = Оа,1 = \Л\

4 Самарский, А. А. Математическое модслйромннс: Идеи. Методы. Примеры. - М.: ФИЗМАГЛИГ, 2002. - 320 с.

■ - теплофизические характеристики горючего для каждого из участков Du в каждый момент времени: #„„(«)> H'u{f), kt,(t), hu(t), л>с1,,Ф,к1('), 1 = 1,2, k = l,...,K, t = *„,/„ +

- параметры функции, описывающей тепловое воздействие локального пламени pou(t), am(t), <?„(/), h^t), <pt{t), w{l);

- скорости сгорания rB(f), Для всех участков Dt в каждый момент времени ' = 'о,t0+&,■■■,'/, к = 1,...,К;

- начальное состояние системы - области DM[ (f0), D4U (f„), Dhl, (r0). Используя информацию о лесном горючем и внешней среде, можно

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

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

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

E = SplP,

где ускорение,

Т, - время вычислений на одном процессоре, Тр - время вычислений на р процессорах.

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

¥ соmm —

2 ■ N1 • г, при одномерном разбиении; V1D«m~ = -fc ■ N3 ■ г, при двумерном разбиении;

где Л^1-размерность задачи,

5Воевадин, В. В. Параллельные вычисления. / В. В. Воеводин, Вл. В. Воеводин. - СПб.: БХВ-Лстгрсург. 2002.-608 с.

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

Алгоритм и его программная реализация являются масштабируемыми, если ускорение и производительность зависят линейно от количества используемых процессоров3: Я,-О(р). На практике алгоритмы, для которых = 0(р/(\пр)), также считаются масштабируемыми.

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

- считывание исходных данных из соответствующих файлов;

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

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

- основной расчетный цикл, направленный на определение границ контура горения:

• выполнение параллельной обработки исходных данных (решение уравнений теплопроводности на данном временном шаге);

• обмен данными между соседними процессорами (передача информации о величине энтальпии для всех граничных данных);

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

- запись полученных результатов в выходной файл;

- освобождение занимаемой памяти.

Учитывая особенности параллельной вычислительной системы, на которой предполагается программная реализация алгоритма, схема обменов данными сделана как не зависящая от способа распределения данных по процессорам. При таком подходе варьируется только число процессоров, с которыми происходят операции обмена. Для предотвращения «тупиковых» блокировок при организации обменов информацией между процессорами использовались неблокирующие функции передачи сообщений.

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

Для распараллеливания процесса вычислений предлагается схема, вытекающая из физического содержания данной задачи. Расчет энтальпии для точки (/.У) на (/+1) -м временном шаге происходит с использованием некоторого количества точек на г-м шаге. Численный расчет ведется итеративно: по имеющимся значениям <-го временного шага выстраивается (< + 1)-й, и т.д. Последовательность вычислений в виде иерархической сети Петри представлена на рисунке 2.

Рисунок 2. Последовательность вычислений при моделировании распространения пожара. Позиции: Pi - данные для инициализации функций библиотеки MPI, Рг - данные о метеоусловиях и характеристиках горючего, Р} - отображение рассчитанной горящей кромки на карте местности. Составные переходы: I, - операции по вводу данных, t2 -основной расчетный цикл.

Таким образом, исходную задачу можно разбить на р подзадач для областей £>*,,, DkLV, Z)J„, / = 1,2,* = 1,...,р, пересекающихся только по границе разбиений, независимых друг от друга на каждом расчетном шаге. В случае технологии MPI каждый процесс получает часть сетки, причем сетки соседних процессов пересекаются по двум узлам. Это пересечение сеток позволяет частично продублировать вычисления на соседних процессорах, что сокращает межпроцессорные обмены. Далее, в каждом процессоре происходят вычисления последовательно по временным шагам на части сетки. Иерархическая сеть Петри, моделирующая основной расчетный цикл для одного процессора, показана на рисунке 3.

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

4S

I > Ifinal

yQr^Or-i&T

'21 к Tl U r22 T2 U Г2} T3 LI

Р» ^

-От^Ут

Рисунок 3. Модель основного расчетного цикла для одного процесса. Позиции: Р21 -данные о метеоусловиях, характеристиках горючего, горящих участках, начальном и конечном моментах времени горения, Р21 - данные о локальных функциях влияния, Рп -данные об энтальпии горючего, Р2А - данные об энтальпии с учетом влияния соседних участков, Р2, - данные о состоянии горящих участков. Составные переходы: г, -вычисление текущего временного шага (выполняется при условии 1йфпа1), г2 -определение границы локальных массивов, г, - вычисление значения энтальпии горючего, г4- обмен данными с соседними процессорами, г5 - определение новых воспламенившихся и погасила точек, г6 - вывод в файл данных о конфигурации пожара.

Рисунок 4. Схема обмена процесса " ргос" с соседними процессами: операции обмена up - dw, left - right, upleft - dwright, upright - dwleft выполняются одновременно.

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

6 Message-Passing Interface Fonim, MPI-2: Extensions to the Message-Passing Interface, 1997. (http-7/www.unix.mcs.anI.gov/mpi/1,13.03.2007 RS/6000 SP: Practical MPI Programming. lwww.redbooks.ibra.com), 11 .OT.200J

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

предотвращает опасность взаимной блокировки процессов. Схема операций обмена данными (операция г4 на рисунке 3) показана на рисунке 5.

чЛ, п*7

Рисунок 5. Модель обмена данными одного процесса с соседними. Позиции: Рю -разрешение обмена; Р(, - завершение обмена; Ptl - Р„ - данные для обмена с соседними процессами (согласно рисунку 3, 4); Рп - Р,ъ - завершение обмена по направлениям; tk -/, - начало и завершение операций обмена; обмены; - up-dw, r„ - left-right, r„ -upleft - dwright, r„ - upright -dwleft.

Более детально схема одной из операций обмена показана на рисунке 6.

Рисунок 6. Модель операций межпроцессорного обмена на примере операции г4| (рисунок 5), остальные операции выполняются аналогично: РА" данные, приготовленные для обмена, - данные, полученные при обмене, г4„,г4|2 -

операции пересылки данных, к1,кг,к,,к,,к5 - маркеры готовности к обмену данными, ¡н -начало операции обмена, 1, - конец операции обмена.

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

Для распределения построенной глобальной сетки на заданное количество процессоров используется программа-препроцессор. При разбиении сетки используются: в первом случае Ш декомпозиция (рисунок 7, а), а во втором - 20 декомпозиция (рисунок 7, б).

,/ / / Л

а б

Рисунок 7. Варианты разбиения расчетной области

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

В п. 3.5 рассмотрены модели распространения пожара в различных ситуациях. В п. З.б описаны несколько серий вычислительных экспериментов на модельной задаче. В качестве модельной задачи выбирался случай неоднородной среды (слой горючих материалов с возвышением). При запуске параллельных программ измерялось время их работы в секундах. На основе данных о времени работы программ вычислялись такие характеристики параллельных программ, как ускорение и эффективность распараллеливания. Расчеты производились на кластерной системе ИВМ СО РАН (г. Красноярск) на тестовой сетке 400x400 при использовании до 16 процессоров. Тестовая область П представляет «квадрат» на сфере: П = [1.6л] х [1.6л]. Возвышение поверхности задается косинусоидой г(х) = 1 + соб(*) /150.

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

14

12

10

I В

4 2 0

0 2 4 6 8 10 12 14 16 1В Копичестко процессоров

—Ускорение при двучерной разбиении -»- Ускорение при линейном разбиении

г

Рисунок 8. Зависимость ускорения от количества доступных процессоров

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

Также был проведен вычислительный эксперимент, выявивший зависимость ускорения от роста размерности задачи. Были рассмотрены случаи крупной (10000 узлов) и мелкой (640000 узлов) сетки. Тестовая область П представляет «квадрат» на сфере: О = [1.6л] * [1.6л]. Возвышение поверхности задается выражением 1{х) = 1+соз(х)/150. В вычислительных экспериментах было сделано 100 шагов по времени. Декомпозиция расчетной области - двумерная.

Рашерность сдачи

Рисунок 9. Зависимость ускорения от размерности задачи

На рисунке 9 показана зависимость ускорения вычислений от размерности задачи. При увеличении размерности задачи в 4 раза ускорение вычислений при использовании 4 процессоров возрастает.

Независимо от выбранного способа декомпозиции расчетной области и размерности задачи, подобласти, полученные в результате разбиения, включают взаимно перекрывающиеся подобласти. Величина перекрытия зависит от параметров функции влияния 4ЛХ~Х\-У~У>)> например, от скорости и направления ветра.

Данные собраны на основании серии расчетов, выполненных на разном количестве процессоров (от 1 до 16) при вычислительной нагрузке на один процессор в 100 ячеек. Результаты показывают, что время счета колеблется от 0.6 до 5 минут в зависимости от объема пересылок. Увеличение их числа естественным образом ведет к увеличению времени счета.

На рисунке 10 представлены графики зависимости ускорения вычислений от величины области перекрытия.

Как видно из рисунка 10, с увеличением величины области перекрытия увеличивается как время счета, так и относительное ускорение вычислений.

>

10 с

Г- <

■-<*~Перефмт*ав1 расчеткуюточгу - м-Псспгрытиса 4 рксметмисточсн

—»- ПсрнчштисиЗрасчстлмточак

8 10 Количество процессоров

- Псрсгрытмс в г р*счетии«точ(м

- пврадота в 5 ррсчап* ы* точвв

- П«р в«р«#тмс ■ 15 расчстмх гочм

-»■'ПврссрытисаЗрвсчетммвтомм -«-Пвмсрутнввграсчвтиыхточвг

Рисунок 10. Зависимость ускорены вычислений от величины области перекрытия

На рисунках 11, 13, 14 приведены графические изображения состояния области моделирования в последовательные моменты времени. На рисунке 12 изображено схематическое представление неоднородного слоя (2 типа горючего) с препятствием в центре (препятствие определено на основе эллипса с использованием в качестве длины полуосей случайных чисел).

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

Рисунок 11. Распространение процесса горения по однородному слою (ветер в направлении -у■)

X

Рисунок 12. Схематическое представление неоднородного слоя (2 типа горючего) с препятствием в центре (препятствие определено на основе эллипса с использованием в качестве длины полуосей случайных чисел)

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

Рисунок 14. Распространение пожара по двум слоям горючего

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

исследования.

В трех приложениях содержатся характеристики лесных горючих материалов и специальные формулы для вычисления функции Грина, а также иллюстрации к диссертационному исследованию. В Приложении 1 приведены характеристики лесных горючих материалов, и модель Ротермела1 для расчета скорости фронта пожара распространяющегося по слою лесных горючих материалов. В Приложении 2 подробно рассмотрены основы организации вычислений на многопроцессорных системах (характеристика библиотеки функций MPI и среды параллельного программирования, базовые функции MPI, коммуникационные операции, способы пересылки разнотипных данных), которые необходимы для понимания организации взаимодействия процессоров в параллельной реализации программы, предназначенной для численного моделирования динамики распространения лесных пожаров. В Приложении 3 представлены иллюстрации к главе 3 с результатами численных расчетов.

Заключение

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

Поставленные цель и задачи были успешно решены:

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

- разработана методика и программа оценки параметров пожаров по данным азрокосмической съемки;

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

алгоритма на параллельных ЭВМ, а также оптимизации и верификации трудно распараллеливаемых блоков;

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

Комплекс параллельных прикладных программ для численного моделирования процесса распространения кромки лесного пожара включает следующие программы:

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

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

- программа' для численного моделирования распространения кромки лесного пожара и отображения областей, пройденных пожаром.

При численном решении задачи моделирования динамики распространения лесного пожара возможно применение как одномерной, так и двумерной декомпозиции. Однако, результаты тестирования программ показали, что наиболее эффективной (средняя эффективность около 83%) при использовании, по крайней мере, от 4 до 16 процессоров является двумерное разбиение исходной области. При этом наблюдается увеличение ускорения в полтора раза при возрастании размерности задачи в 4 раза. Исследование влияния объема пересылаемых при расчетах данных на время счета основного цикла программы показало, что при увеличении объема пересылаемых данных в 15 раз время счета возрастает от 0.6 до 5 минут. На основании полученных данных об ускорении и эффективности распараллеливания сделано заключение о целесообразности применения МР1-технологии при распараллеливании вычислений на достаточно большом числе процессоров.

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

Список публикаций по теме работы

в научном журнале, включенном в перечень ВАК

1. Вдовенко М. С., Доррер Г. А. Об эффективности параллельных алгоритмов при моделировании динамики лесных пожаров // Вестник Сибирского государственного аэрокосмического университета М. Ф. Решетнева. Серия "Математика, механика, информатика", 2009. Вып. 2 (23), с. 152-156.

¿з

другие публикации

2. Вдовенко М. С. Моделирование распространения горящей кромки лесного пожара на многопроцессорной ЭВМ И Сопряженные задачи механики реагирующих сред, информатики и экологии: Материалы Международной конференции. - Томск: Изд-во Том. ун-та, 2007, с. 31-32.

3. Вдовенко М. С. Расчет распространения горящей кромки лесного пожара с использованием технологии МР1 // Проблемы информатизации региона. ПИР-2007: Материалы десятой Всероссийской научно-практической конференции. Красноярск, 1-2 ноября 2007: В 2 т. Т. 2 (секция 2-3) / Отв. ред. Л. Ф. Ноженкова. Красноярск: Сиб. федер. ун-т; Политехи, ин-т, 2007, с. 8-9.

4. Вдовенко М. С., Доррер Г. А. Моделирование распространения горящей кромки лесного пожара на многопроцессорной ЭВМ // Молодежь и современные информационные технологии. Сб. трудов VI всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск, 26-28 февраля 2008, с. 221-222.

5. Вдовенко М. С., Доррер Г. А. Сравнительный анализ различных параллельных алгоритмов, моделирующих распространение горящей кромки лесных пожаров // Математическое моделирование опасных природных явлений и катастроф. Материалы 7-й международной конференции. - Томск: Томский государственный университет, 2008, с. 24-25.

6. Вдовенко М. С., Карепова Е. Д. Сравнительный анализ различных параллельных алгоритмов численного решения краевой задачи для уравнений мелкой воды II Всероссийская конференция по математике и механике, посвященная 130-летию Томского государственного университета и 60-летию механико-математического факультета: Сборник тезисов (Томск, 22 - 25 сентября 2008) - Томск: Томский государственный университет, 2008 г, с. 244.

7. Вдовенко М. С., Доррер Г. А. Моделирование распространения горящей кромки лесных пожаров // Всероссийская конференция по математике и механике, посвященная 130-летию Томского государственного университета и 60-летию механико-математического факультета: Сборник тезисов (Томск, 22 - 25 сентября 2008) - Томск: Томский государственный университет, 2008 г, с. 243-244.

8. Вдовенко М. С., Доррер Г. А. Исследование двух различных реализаций параллельных алгоритмов для расчета распространения кромки лесного пожара // Вестник томского государственного университета: Математика и механика - Томск: Томский государственный университет, 2008, №2(3), с. 99-104.

9. Вдовенко М. С., Доррер Г. А. Моделирование распространения лесного пожара на многопроцессорной ЭВМ // Моделирование неравновесных систем // Материалы XI Всероссийского семинара, 26 - 28 сентября 2008 / Под ред. В.В. Слабко; Отв. за вып. М.Ю. Сенашова; ИВМ СО РАН. -Красноярск, 2008, с. 36-37.

10. Вдовенко М. С., Доррер Г. А. Моделирование распространения лесных пожаров с использованием параллельных вычислительных систем //

Пожары в лесных экосистемах Сибири: Материалы Всероссийской конференции с международным участием. - Красноярск: Институт леса им. В.Н. Сукачева СО РАН, 2008, с. 211-213. 1 11. Карепова Е. Д.,Шайдуров В. В., Вдовенко М. С. Сравнительный анализ ' различных параллельных алгоритмов численного решения краевой задачи для уравнений мелкой воды // Труды Четветой Международной конференции «Параллельные вычисления и задачи управления» РАСО "2008. Москва, 27-29 октября 2008. - М.: Институт проблем управления им. В. А. Трапезникова РАН, 2008, с. 104-121.

: 12. Карепова Е, Д., Шайдуров В. В., Вдовенко М. С. Параллельные реализации метода конечных элементов для краевой задачи для уравнений мелкой воды // Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Нбвгород, 30 марта - 3 апреля 2009). - Челябинск: Изд. ЮУрГУ, 2009, с. 205-216.

13. Вдовенко М. С., Доррер Г. А. Разработка параллельных алгоритмов, моделирующих распространение лесных пожаров И Параллельные вычислительные технологии (ПаВТ'2009): Труды международной научной конференции (Нижний Новгород, 30 марта - 3 апреля 2009). -Челябинск: Изд. ЮУрГУ, 2009, с. 420-426.

14. Карепова Е. Д., Шайдуров В. В., Вдовенко М. С. Параллельные реализации метода конечных элементов для краевой задачи для уравнений мелкой воды // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2009. № 17 (150). Вып. 3, с. 73-85.

Вдовенко Марина Сергеевна

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ РАСПРОСТРАНЕНИЯ ЛЕСНЫХ ПОЖАРОВ НА ОСНОВЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать Об. 1Л09 г. Формат 60x84/16. Бумага типографская. Печать плоская. Усл. печ. л. 1,5 Уч.-нзд. л. 1,7 Тираж 100 экз. Заказ

Тигюгафия «Экспресс-Офсет».

660075 г. Красноярск, ул. Брянская 140 стр. 2

Введение.

1. Математические модели лесных пожаров.

1.1. Обзор работ, посвященных изучению лесных пожаров.

1. 2. Модель лесного пожара как динамической системы типа бегущей волны.

1.3. Идентификация процессов распространения по экспериментальным данным.

1.4. Выводы.

2. Среда параллельного программирования.

2. 1. Классификация вычислительных систем.

2. 2. Краткая характеристика средств программирования многопроцессорных систем.

2. 3. Характеристика среды параллельного программирования.

2. 4. Параллельные программы для численного решения задач моделирования.

2. 5. Выводы.

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

3.1. Постановка задачи и метод ее решения.

3. 2. Анализ задачи и выявление ее потенциального параллелизма.

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

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

3. 4. 1. Прспроцессорная обработка данных.

3. 4. 2. Программа для расчета процесса горения.

3.5. Модели распространения пожара в различных ситуациях.

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

3. 7. Выводы.

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

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

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

Большой вклад в решение проблемы лесных пожаров внесли Э. Н. Валендик, А. М. Гришин, Ю. А. Гостинцев, Г. Н. Коровин, Н. П. Курбатский, М. А. Софронов, F. A. Albini, М. Е. Alexander, R. Rothermel и другие ученые. Содержательный обзор исследований в мире по проблеме моделирования распространения лесных пожаров дан в работе [36, 37].

Разработка математических моделей распространения пожара позволяет предсказать его поведение, что способствует более эффективной борьбе со стихией огня. Однако одной из главных трудностей является отсутствие информационного обеспечения разработанных математических моделей, в частности о характеристиках горючих материалов, погоде, топографии местности и др. В настоящее время сложились благоприятные условия для разработки систем моделирования и прогнозирования лесных пожаров на всей территории России. Это связано с созданием и вводом в эксплуатацию Информационной системы дистанционного мониторинга ИСДМ-Рослесхоз, созданной Институтом космических исследований РАН. С помощью этой системы ФГУ «Авиалесоохрапа» осуществляет управление лесопожарной ситуацией на территории РФ. Данная система, основанная на использовании спутниковой и наземной информации о-пожарной обстановке в лесах, погоде и действующих пожарах, позволяет получать ряд необходимых данных для осуществления процесса прогнозирования. Ввиду сложности расчета процессов горения в течение многих дней на больших территориях задачи математического моделирования лесных пожаров требуют серьезных вычислительных ресурсов. Об этом свидетельствует, в частности, опыт применения моделирующей лесопожарной системы BehavePlus в США [94]. При этом, задачи математического моделирования требуют серьезных вычислительных ресурсов. Одним из способов решения этой проблемы является использование кластерных вычислительных систем. Наиболее общим подходом равномерного распределения вычислительной нагрузки между процессорами при решении задач динамики лесных пожаров является разделение вычислительной области (карты лесной территории) на подобласти, количество которых совпадает с числом используемых процессоров, т. е. использование принципа геометрической декомпозиции [26]. Существующие параллельные реализации программ для моделирования динамики распространения лесных пожаров (Global Fireline Propagation Model, ELFM, Parallel CFD fire modeling, FDS) предназначены для моделирования динамики пожара в определенных географических областях (ELFM), определенным кругом пользователей (FDS) или требуют специального аппаратного и программного обеспечения (CFD).

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

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

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

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

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

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

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

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

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

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

Основные результаты диссертации, выносимые на защиту:

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

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

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

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

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

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

1. Международной конференции «Сопряженные задачи механики реагирующих сред, информатики и экологии» (г. Томск, 2007).

2. Десятой Всероссийской научно-практической конференции «Проблемы информатизации региона» (г. Красноярск, 2007).

3. VI всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2008).

4. V международной конференции студентов и молодых учёных «Перспективы развития фундаментальных наук» (г. Томск, 2008).

5. 7-й международной конференции «Математическое моделирование опасных природных явлений и катастроф» (г. Томск, 2008).

6. Всероссийской конференции с международным участием «Пожары в лесных экосистемах Сибири» (г. Красноярск, 2008).

7. «Всероссийской конференция по математике и механике», посвященной 130-летию Томского государственного университета и 60-летию механико-математического факультета (г. Томск, 2008).

8. XI Всероссийском семинаре «Моделирование неравновесных систем» (г. Красноярск, 2008).

9. Четвертой Международной конференции «Параллельные вычисления и задачи управления» РАСО 2008 (г. Москва, 2008).

По теме диссертации автором опубликовано 14 работ (из них одна по списку ВАК). Из работ, выполненных в соавторстве, в диссертацию включены результаты, полученные автором лично.

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, содержащего 135 наименований, и трех приложений. Диссертация содержит 22 рисунка. Объем диссертации составляет 109 страниц, приложений — 21 страница.

3. 7. Выводы

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

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

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

Разработка параллельных приложений в качестве своей цели имела не только уменьшение времени выполнения, но и обеспечение возможности решения задач с большим пространственным разрешением. Поэтому также был проведен вычислительный эксперимент, выявивший зависимость ускорения от роста размерности задачи. При увеличении размерности задачи наблюдается увеличение ускорения вычислений, по крайней мере, для задач размерностью не более 800x800 и применения четырех процессоров. Значения ускорения вычислений с увеличением размерности задачи при использовании двумерной декомпозиции расчетной области возрастают логарифмически, что говорит о наличии важной характеристике параллельных вычислений [26] - масштабируемости.

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

1(Х~Х\'У~У\)} например, от скорости, направления ветра. Приведены обобщенные статистические данные по времени счета в зависимости от объема пересылок. Под объемом пересылок понимается число граничных ячеек сеточной области, через которые осуществляются межпроцессорные обмены. Данные собраны на основании серии расчетов на разном количестве процессоров (от 1 до 16) при вычислительной нагрузке на один процессор в 100 ячеек. Результаты показывают, что время счета колеблется от 0.6 до 5 минут в зависимости от объема пересылок. Увеличение последних, естественным образом, ведет к увеличению времени счета.

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

Заключение

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

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

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

Поставленные цель и задачи были успешно решены:

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

- реализована программа оценки параметров пожаров по данным аэрокосмической съемки;

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

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

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

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

- программу для препроцессорной обработки данных — «разрезания» данных на отдельные файлы для многопроцессорных вычислений;

- программу для численного моделирования распространения кромки лесного пожара.

Проведенные исследования позволяют сделать вывод о том, что при численном решении задачи моделирования динамики распространения лесного пожара возможно применение как одномерной, так и двумерной декомпозиции. Однако, результаты тестирования программ показали, что наиболее эффективной (средняя эффективность около 83%) при использовании, по крайней мере, от 4 до 16 процессоров является двумерное разбиение исходной области. При этом наблюдается увеличение ускорения в полтора раза при возрастании размерности задачи в 4 раза. Исследование влияния объема пересылаемых при расчетах данных на время счета основного цикла программы показало, что при увеличении объема пересылаемых данных в 15 раз время счета возрастает от 0.6 до 5 минут. На основании полученных данных об ускорении и эффективности распараллеливания сделано заключение о целесообразности применения МРЬтехнологии при распараллеливании вычислений на достаточно большом числе процессоров.

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

1. Амосов, Г. А. Некоторые закономерности развития лесных низовых пожаров. / Г. А. Амосов // Возникновение лесных пожаров. — М.: Наука, 1964. С. 152-171.

2. Антонов, А. В. Системный анализ. Учеб. для вузов / А. В. Антонов. М.: Высш. шк, 2004. - 454 с.

3. Антонов, А. С. Введение в параллельные вычисления: метод, пособие. / А. С. Антонов. М.: Изд-во МГУ, 2002. - 69 с.

4. Антонов, А. С. Вычислительный практикум по технологии MPI. / А. С. Антонов. URL: http://parallel.ru/tcch/techdcv/MPlcourse/

5. Антонов, А. С. Параллельное программирование с использованием технологии MPI: учеб. пособие. / А. С. Антонов. М.: Изд-во МГУ, 2004. -71 с.

6. Барский, А. Б. Параллельные информационные технологии. / А. Б. Барский. БИНОМ. Лаборатория знаний, 2007. - 504 с.

7. Барский, А. Б. Параллельное программирование. / А. Б. Барский. URL: http://www.intuit.ru/department/se/parallprog/

8. Берзигияров, П. К., Султанов В.Г. Технология разработки масштабируемых массивно-параллельных вычислений для SMP-систем на базе MPI. / П. К. Берзигияров, В. Г. Султанов. URL: http://parallel.ru/ftp/chg99/Berzigiyarov.doc.zip

9. Бочаров, Н. В. Технологии и техника параллельного программирования. / Н. В. Бочаров. URL: http:Wdks.invitation.ru

10. Букатов, А. А. Программирование многопроцессорных вычислительных систем. / А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Ростов-на-Дону. Издательство ООО «ЦВВР», 2003. 208 с.

11. Валендик, Э. H. Идентификация скоростей распространения лесных пожаров по их инфракрасным снимкам. / Э. Н. Валендик, Г. А. Доррер, Н. А. Калнина, А. И. Сухинин, Б. А. Хрептов // Исследование Земли из космоса. 1982. - №5. С. 46-53.

12. Воеводин, В. В. Вычислительная математика и структура алгоритмов. / В. В. Воеводин. М.:Изд-во МГУ, 2006. - 112 с.

13. Воеводин, В. В. Математические модели и методы в параллельных процессах. / В. В. Воеводин. М.: Наука, 1986. - 296 с.

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

15. Воеводин, В. В. Супервычисления и структура алгоритмов. / В. В. Воеводин. URL: http://parallel.ru/ftp/chg99A/oevodin.doc.zip

16. Воеводин, Вл. В. Вычислительное дело и кластерные системы. / Вл. В. Воеводин, С. А. Жуматий.-М.: Изд-во МГУ, 2007. 150 с.

17. Гергель, В. П. Многопроцессорные системы и параллельное программирование. / В. П. Гергель. URL: http://vvww.software.unn.ac.ru/ccam/mskurs/cs338pprindex.htm

18. Гергель, В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем. / В. П. Гергель, Р. Г. Стронгин. URL: http://www.software.unn.ac.ru/ccam/illes/HTMLVersion/index.html

19. Гергель, В.П. Теория и практика параллельных вычислений. / В. П. Гергель. Изд-во БИНОМ. Лаборатория знаний, 2007. - 424 е.

20. Гришагин, В.А. Параллельное программирование на основе MPI. Учебное пособие. / В. А. Гришагин, А. П. Свистунов. Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2005. - 93 с.

21. Гришин, А. М. Математические модели лесных пожаров. / А. М. Гришин. -Томск: Изд-во ТГУ, 1981.-278 с.

22. Гришин, А. М. Математические моделирование лесных пожаров и новые способы борьбы с ними. /А.М.Гришин! Новосибирск: Наука, 1992. -408 с.

23. Гришин, А. М. О математическом моделировании природных пожаров и катастроф. // Вестник томского государственного университета: Математика и механика. Томск: Томский государственный университет, 2008 г. №2(3). С. 105-114.

24. Гришин, А. М. Физика лесных пожаров. / А. М. Гришин Томск: Изд-во Томского ун-та, 1994. 207 с

25. Гришин, А. М. О распараллеливании задачи распространения верхового лесного пожара вдоль просеки / А. М. Гришин, Д. А. Макаренко. URL: http://www.ict.nsc.ru/ws/ws.dhtml73

26. Доррер, Г. А. Динамика лесных пожаров. / Г. А. Доррер. Новосибирск: Изд-во СО РАН, 2008. - 404 с.

27. Доррер, Г. А. Математические модели динамики лесных пожаров. / Г. А. Доррер. М: Лесн. пром-сть, 1979. - 161 с.

28. Доррер, Г. А. Методы оценки динамики процессов распространения на поверхности земли. / Г. А. Доррер, П. Е. Федоров // Сибирский экологический журнал. 2001. - №5. С. 591-597.

29. Евсеев, И. MPI для начинающих. / И. Евсеев. URL: http://www.csa.ru:81/~il/mpitutor/

30. Евсеев, И. MPI программный инструмент для параллельных вычислений. / И. Евсеев. URL: http://www.csa.ru: 8 l/41/mpiJ:utor/intro.shtmr

31. Забродин, А. В. Параллельные вычислительные технологии. Состояние и перспективы. / А.В.Забродин. URL: http://paraIlel.ru/flp/chg99/Zabrodin.doc.zip

32. Ильин, В. П. О стратегиях распрараллеливания в математическом моделировании. / В. П. Ильин //Программирование. 1999. № 1. С. 41-46.

33. Информационно-аналитические материалы по параллельным вычислениям. URL: http://www.parallel.ru/

34. Информационные материалы Центра компьютерного моделирования Нижегородского университета. URL: http://www.software.unn.ac.ru/ccam

35. Информационные материалы рабочей группы IEEE по кластерным вычислениям. URL: http://www.ieeetfcc.org/

36. Карпов, В. Е. Параллельные вычисления на кластерах из персональных компьютеров в математической физике. / В. Е. Карпов, А. И. Лобанов. URL: http://www.intuit.rU/department/calculate/nmdiffeq/10/l.html

37. Комолкин, А. В. Программирование для высокопроизводительных ЭВМ. / А. В. Комолкин, С. А. Немнюгин. URL: http://www.hpc.nw.ru/KOI/COURSES/I-IPC/index.html

38. Конев, Э. В. Физические основы горения растительных материалов. / Э. В. Конев. Новосибирск: Наука, 1977. - 239 с.

39. Концепция построения параллельных программ с использованием формальной теории сетей Петри. URL: http://www.iacp.dvo.ru/labl l/otchet/ot2000/concept.html

40. Коровин, Г. Н. Методика расчета некоторых параметров низовых лесных пожаров. / Г. Н. Коровин // Сборник научно-исследоват. работ по лесному хозяйству / Труды ЛенНИИЛХ. Вып. XII Л., 1969. С. 244-262.

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

42. Крюков, В. А. Разработка параллельных программ для вычислительных кластеров и сетей. / В. А. Крюков. URL: http://parallel.ru/ftp/krukov-cldvm2002f.pdf

43. Курбатский, И. П. Современная теория распространения лесных низовых пожаров. / И. П. Курбатский, Г. П. Телицын // Современные исследования типологии и пирологии леса. — Архангельск, 1976. С. 90-96.

44. Курбатский, Н. П. Статистическая многофакторная модель кромки низового лесного пожара. / И. П. Курбатский, Г. А. Иванова // Моделирование в охране лесов от пожаров. Красноярск: ИЛиД СО АН СССР, 1979. С. 17-32.

45. Кучунова, Е. В. Вычислительный алгоритм для расчета волновых полей в блочных средах на многопроцессорных вычислительных системах. / Е. В. Кучунова, В. М. Садовский // Journal of Siberian Federal University. Mathematics & Physics, 2008, №2. Pp. 210-220.

46. Лесные и торфяные пожары: причины и последствия. URL: http:// fire.nad.ru/who.htm

47. Лопатин, И. В. Экспериментальное сравнение технологий параллельных вычислений в кластерных системах. Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Международного научно-практического семинара. / И. В. Лопатин,

48. A. Н. Свистунов, А. В. Сысоев / Под ред. проф. Р. Г. Стронгина. Нижний Новгород: Изд-во Нижегородского университета, 2002. С. 98-103.

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

50. B. М. Мальбахов, В. А. Шлычков, А. А. Лежнин, О. А. Дубровская. География и природные ресурсы. 2004, спец. выпуск. С. 170-174.

51. Миллер, Р. Последовательные и параллельные алгоритмы. Общий подход: пер. с англ. / Р. Миллер, Л. Боксер; под ред. С. М. Окулова. М.: БИНОМ, Лаб. знаний, 2006. - 406 с.

52. Немнюгин, С. А. Параллельное программирование для многопроцессорных вычислительных систем. / С. А. Немнюгин, О. Л. Стесик. БХВ-Петербург, 2002. - 400 с.

53. Овчинников, Ф. М. Моделирование распространения и тушения лесных пожаров. / Ф. М. Овчинников, А. П. Латынцев //Охрана лесов от пожаров, лесовосстановление и лесопользование. Сб. науч.ст. / ФГУ "ВНИИПОМлесхоз". Красноярск: ИПЦ КГТУ, 2003. С. 138-150.

54. Ортега, Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ. / Дж. Ортега. М.:Мир, 1991.

55. Применение информационной системы дистанционного мониторинга «ИСДМ-Рослесхоз» для определения пожарной опасности в лесах Российской федерации: Учебное пособие. г. Пушкино (МО), ФГУ «Авиалесоохрана», 2007. - 82 с.

56. Противопожарное устройство лесов. URL: http://www.glossary.ru/cgi-bin/

57. Профилактика и тушение лесных пожаров: Сб. науч. тр. / Редкол.: Б. П. Яковлев (отв. ред.); Федер. служба лссн. хоз-ва: Всерос. научно-исслед. ин-т противопож. охраны лесов и механизации лесп хоз-ва. -Красноярск: ВНИИПОМлесхоз, 1998. 252 с.

58. Самарский, А. А. Математическое моделирование: Идеи. Методы. Примеры. / А. А. Самарский. М.: ФИЗМАТЛИТ, 2002. - 320 с.

59. Самарский, А. А. Теория разностных схем. / А. А. Самарский. — М.: Наука, 1988.- 616 с.

60. Сухинин, А. И. Экспериментальное исследование механизма распространения пламени по хвое. Автореф. Дис. . физ.-мат.наук. / А. И. Сухинин. Чебоксары, 1975. - 22 с,

61. Федотов, И. Е. Некоторые приемы параллельного программирования: Учебное пособие. / И. Е. Федотов. М.: Изд-во МГИРЭА(ТУ), 2008. -188 с.

62. Численные методы, параллельные вычисления и информационные технологии: Сборник научных трудов. / Под ред. Вл. В. Воооеводина и Е. Е. Тыртышникова. — М.: Издательство Московского Университета, 2008. 320 с.

63. Шаталова, А. Параллельное движение. / А. Шаталова // ПОИСК: Еженедельная газета научного сообщества, 2007, №10 (928). С. 8

64. Шпаковский, Г. И. Программирование для многопроцессорных систем в стандарте MPI: Пособие. / Г. И. Шпаковский, Н. В. Серикова. Мн.: БГУ, 2002. - 323 с.

65. Andrews, P.L. BehavePlus Modeling System: Past, Present and Future. / P.L. Andrews. US Forest Service, Rocky Montana Research Statuon, Missoula, Montana, 2005. - 13 p.

66. Balay, S. Efficient Management of Parallelism in Object-Oriented Numerical Software Libraries, Modern Software Tools in Scientific Computing. / S. Balay, W. D. Gropp, L. C. Mclnnes and others. Birkhauser Press, 1997. Pp. 163-202.

67. Barker, M. Cluster Computing Whitepaper. URL: http: //www. dcs .p ort. ac. uk/~m ab/tfcc/WhiteP ар er/

68. Booth, S. Introduction to the T3D. / S. Booth, J. Fisher, N. MacDonald and others. URL: http://www.hpc.nw.ru/PDF/Intro.pdf

69. Booth, S. Perfomance Optimization. / S. Booth, N. MacDonald. URL: http://www.hpc.nw.ru/PS/optimisation.zip

70. Byram, G. M., Martin R.E. The modeling of fire whirlwinds. / G. M. Byram, R. E. Martin // Forest Science, 1970, vol. 16, N 4. Pp. 586-398.

71. Clark, T. L. Descrption of coupled atmosphere-fire model. / T. L. Clark, J. Coen, D. Latham // Int. J. Wildland Fire, 2004, №13. Pp. 49-63.

72. Coen, J. Simulation of the Big Elk Fire using coupled atmosphere-fire modeling. / J. Coen // Int. J. Wildland Fire, 2005, №14. Pp. 49-59.

73. Cruz, M. G. Prediction the ignition of crown fuelsabove a spreding surface fire. Part I: model idealization. / M. G. Cruz, B. W. Butler, M. E. Alexander and others // Int. J. Wildland Fire, 2006, №15. Pp. 47-60.

74. Cruz, M. G. Prediction the ignition of crown fuelsabove a spreding surface fire. Part I: model evaluation. / M. G. Cruz, B. W. Butler, M. E. Alexander // Int. J. Wildland Fire, 2006, №15. Pp. 61-72.

75. Dupuy, J.-L. Numerical study of a crown fire spreading toward a fuel break using a multiphase physical model. / J.-L. Dupuy, D. Morvan // Int. J. Wildland Fire, 2005, №14. Pp. 141-151.

76. Fire Danger. URL: http://www.state.nj.us/dep/parksandforests/fire/index.html

77. Fons, W. L. Analysis of fire spread in light forest fuels. / W. L. Fons // Journal of Agric. Res, 1946, v. 72, N 3. Pp. 93-121.

78. Foster, I. Designing and Building Parallel Programs. / I. Foster. URL: http://www.hensa.ac.uk/parallel/books/addison-wesley/dbpp http://rsusul.rnd.runnet.ru/ncube/design/dbpp/book-info.html

79. Grandison, A. J. Parallel CFD fire modelling on office PCs with dynamic load balancing. / A. J. Grandison, E. R. Galea, M. K. Patel, J. Ewer. URL: http://www3.interscience.wiley.com/cgi-bin/fulltext/112649754/PDFSTART

80. Group, W. Using MPI. Portable Parallel Programming with the Message-Passing Interface. / W. Group, E. Lusk, A. Skjellum. URL: http://www.mcs.anl.gov/mpi/index.html

81. High Performance Computing and Communications Glossary. URL: http://www.hpc.nw.ru/ENG/COURSES/hpccgloss.html

82. Introduction to Parallel Computing (Teaching Course). URL: http://www.ece.%20nwu.edu/~choudhar/C58/

83. Introduction to Parallel Programming. URL: http://www.academicresorcecenter.net/curriculum/pfv.aspx?lD=6594

84. Linn, R. R. Modeling interaction between fire and atmosphere in discrete element fuel beds. / R. R. Linn, J. Winterkamp, J. J. Colman and others // Int. J. Wildland Fire, 2005, №14. Pp. 37-48.

85. Linn, R. R. Studying wildfire behavior using FIRETEC. / R. R. Linn, J. Reisner, J. J. Colman, J. Winterkamp // Int. J. Wildland Fire, 2002, №11. Pp. 233-246.

86. MacDonald, N. Writing Message-Passing Parallel Programs with MPI. / N. MacDonald, E. Minty, T. Harding and others. URL: http://www.hpc.nw.ru/PS/mpi-course.zip

87. McBryan, O. A. An overwiev of message passing environments. / O. A. McBryan // Parallel Computing. 1994. V 20. Pp. 417-441.

88. Mell, W. A physics-based approach to modeling grassland fires. / W. Mell, M.A.Jenkins, J. Gould, Ph. Cheney // Int. J. Wildland Fire, 2007, №16(1) . Pp. 1-22.

89. Message-Passing Interface Forum, Document for a Standard Message-Passing Interface, 1993. Version 1.0. URL: http://www.unix.mcs.anl.gov/mpi/

90. Message-Passing Interface Forum, MP 1-2: Extensions to the Message-Passing Interface, 1997. URL: http://www.unix.mcs.anl.gov/mpi/

91. Minty, E. Decomposing the Potentially Parallel. / E. Minty, R. Davey, A. Simpson and others. URL: http://vvww.hpc.nw.ru/PS/decomposing.zip

92. Minty, E. Scientific Visualisation: A Practical Introduction. / E. Minty, P. Maccallum, J. Fisher and others. URL: http://www.hpc.nw.ru/PS/scivis.zip

93. MPI Performance Topics. URL: http://www.llnl.gov/computing/tutorials/mpiperformancc/MPI Performance Topics.htm

94. MPI: The Complete Reference. URL: http://www.hpc.nw.ru/PS/mpi-book.zip

95. National Geophysical Data Center. URL: http://www.ngdc.noaa.gov/ngdc.html

96. Plume rise model for Forest Fire Using ArcGIS Modeling Tool. URL: http://www.crwr.utexas.edu/gis/gishydro03/Classroom/trmproj/Nopmongcol/Plu me rise model for Forest Fire.mht

97. Press, W. H. Numerical Recipes in C. / W. II. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery. URL: http://ftp.kinetics.nsc.ru/chichinin/books/math/numrec.zip

98. Richards, G. D. The mathematical modeling and computer simulations of wildland fire perimeter grown over a 3-dimentional surface. / G. D. Richards // International Journal of Wildland Fire. 1999. - Vol. 9(3). Pp. 213-221.

99. Rothermcl, R. C. A mathematical model for fire spread predictions in wildland fuels. / R. C. Rothermel USDA forest Service Research Paper INT-115, Ogden, 1972, - 40 p. (Intermountain Forest and Range Exp. Stn.).

100. RS/6000 SP: Practical MPI Programming. URL: www.redbooks.ibm.com

101. Van Wagner, C. E. Effect of slope on fires spreading downhill. / C. E. Van Wagner // Can. J. For. Res., 1988, №18. Pp. 818-820.

102. Viegas D. X. On the existence of a steady state regime for slope and wind driven fires. / D. X. Viegas // Int. J. Wildland Fire, 2004, №13. Pp. 101-117.

103. Viegas D. X. Parametric study of eruptive fire behavior model. / D. X. Viegas // Int. J. Wildland Fire, 2006, №15. Pp. 169-177.

104. Weber, R. O. Toward a Comprehensive Wildfire Spread Model. / R. O. Weber // Int. J. Wildland Fire, 1991, №1(4). Pp. 245-248.