Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах
Подождите немного. Документ загружается.
31
и графики сечения поверхностных токов, полученные во время
предыдущего запуска расчетов. Для запуска вычислений по вновь
введенным данным необходимо нажать кнопку «Запуск вычислений».
После этого задача ставится в очередь на выполнение, сообщение об
этом выводится вместо кнопки запуска. Обновляя окно браузера
можно увидеть сообщение о запуске программы с указанием времени
ее запуска. После окончания расчета графики будут выводиться на
основе вновь полученных данных. Для более подробного изучения
каждый график можно открыть в отдельном окне. Также на странице
результатов имеются ссылки на файл с исходными данными и файл с
числовыми результатами вычислений.
Организация параллельных вычислений
В вычислительном комплексе периодически проверяется наличие
новых
данных для выполнения вычислений (данные считаются
подготовленными после нажатии кнопки «Запуск вычислений»). При
наличии таковых файл с информацией для расчета копируется на
вычислительную систему, на которой установлена программа расчета,
реализующая алгоритм решения задачи дифракции. Данная программа
может быть написана на любом языке программирования и может
работать на любой вычислительной системе,
единственным условием
является возможность передавать ей входные данные через файл и
возможность ее удаленного запуска.
После выполнения программы файл с результатами копируется
обратно и предоставляется пользователю. Передача данных
осуществляется с использованием протокола FTP, выполнение команд
на запуск вычислений – использованием протокола SSH.
В настоящее время вычислительная программа написана на языке
Си с использованием библиотеки
MPICH. Вычислительный комплекс
размещен на серверах РЦСВ. Тестирование комплекса производится с
использованием вычислительных ресурсов НИВЦ МГУ.
Заключение
Удобство подобной реализации состоит, с одной стороны, в том,
что пользователю вычислительного комплекса не надо иметь
специализированных средств и программ, а также специальных знаний
в области параллельных вычислений для получения доступа к
высокопроизводительной вычислительной
системе. С другой стороны,
имея один и тот же пользовательский интерфейс, вычислительную
программу можно запускать на различных параллельных кластерных
32
системах, причем даже независимо от их загруженности и доступности
в конкретный момент времени, что позволит работать в «on-line»
режиме, сокращая время, затрачиваемое пользователем для решения
сложной математической задачи.
Работа выполнена в рамках программы СКИФ-ГРИД при
поддержке гранта РФФИ-06-07-89063.
Литература
1. Ильинский А. С., Смирнов Ю. Г. Дифракция
электромагнитных волн на
проводящих тонких экранах М.:
Радиотехника, 1996.
2. Колтон Д., Кресс Р. Методы интегральных уравнений в теории
рассеяния. М.: Мир, 1987.
3. Rao S.M. , Wilton D.R. , Glisson A.W. . Electromagnetic
Scattering by Surface of Arbitrary Share..// IEEE Transactions on
antennas and propagation. Vol. Ap-30. Pp 409-417, May 1982.
4. Медведик М.Ю., Смирнов Ю.Г. Субиерархический
параллельный вычислительный алгоритм и сходимость метода
Галеркина в задачах дифракции электромагнитного поля на
плоском экране // Известия высших учебных заведений.
Поволжский регион.
Естественные науки. – 2004. – № 5. – С.
3–19.
5. Медведик М. Ю., Родионова И. А. Субиерархический
параллельный вычислительный метод для электромагнитной
задачи дифракции в экранированных слоях, связанных через
отверстие // Труды международного симпозиума "Надежность
и качество". Том 1. 2006. С. 272-274.
6. Антонов А. В., Токарев А. Н. Принципы организации
параллельной вычислительной системы с доступом через
Интернет // Материалы XIII
Международной школы-семинара
«Синтез и сложность управляющих систем» (Пенза, 14-20
октября 2002).
33
НОВАЯ КОНЦЕПЦИЯ ПРОГНОЗА ЛЕСНОЙ ПОЖАРНОЙ
ОПАСНОСТИ И ЛАНДШАФТНОЕ РАСПАРАЛЛЕЛИВАНИЕ
Н.В. Барановский
ОСП НИИ прикладной математики и механики
Томского государственного университета
Введение
Лесные пожары наносят огромный экономический и
экологический ущерб. В настоящее время широко известны
следующие методики прогноза лесной пожарной опасности –
канадская [1] и американская [2] системы, европейская система [3] и
критерий Нестерова [4],
который с 1999 года используется в качестве
ГОСТа [5] на территории РФ. Большинство методов базируется на
метеоданных, которые получают с метеостанций или с помощью
спутникового зондирования [6]. Ни первый, ни второй варианты не
позволяют проводить прогнозных расчетов, а только позволяют
оценивать текущую пожарную опасность лесопокрытых территорий.
Новая концепция прогноза лесной пожарной опасности
Анализ обстановки
в области охраны лесов от пожаров позволяет
выделить основные узкие места существующего подхода к
прогнозированию лесной пожарной опасности.
Существующие методы прогноза лесной пожарной опасности не
учитывают физико-химические процессы сушки и зажигания слоя
ЛГМ, которые являются одними из определяющих в наступлении
пожарной опасности.
На больших малоосвоенных территориях, как правило, имеется
лишь редкая и неразвитая сеть метеостанций, а в настоящий момент
именно эта информация используется для оценки пожарной опасности
по существующему ГОСТу.
Факторы антропогенной нагрузки и грозовой активности должным
образом не учитываются.
В системе охраны лесов от пожаров отсутствует вычислительный
центр для централизованной обработки исходной информации и
выработки прогноза.
Чтобы ликвидировать данные
недостатки, предлагается новая
концепция прогноза лесной пожарной опасности [7]. Входная
информация по метеопараметрам генерируется в программах,
34
реализующих глобальные [8] или региональные [9] модели атмосферы,
и поступает в качестве входной в подсистемы оценки вероятности
возникновения лесных пожаров по метеоусловиям и сценариям
зажигания. Данная идея предложена автором в 2003 году [10].
Отметим, что годом позже такой же подход был предложен в работе
американских исследователей [11]. Следует разработать систему
усвоения данных об уровне антропогенной
нагрузки (С.У.Д.А.Н.) [12]
на контролируемой лесопокрытой территории, чтобы учесть
пространственно-временной характер антропогенной нагрузки.
Информация из систем пеленгации разрядов облако-земля [13]
поступает в качестве входной в модель. В итоге детерминированно-
вероятностная модель [14] позволяет определить вероятность
возникновения лесных пожаров. Предполагается создание
общегосударственного центра мониторинга лесной пожарной
опасности, где собирается
исходная информация и в результате
генерируется и направляется заинтересованным потребителям
прогнозная информация. В центре функционирует многопроцессорная
вычислительная система МВС, которая будет являться ядром всей
информационно-вычислительной системы. Вся система может быть и
распределенной, главное, чтобы была осуществима оперативная
передача информации из различных подсистем для обработки на МВС.
Ландшафтное распараллеливание и
прогноз лесных пожаров
В аналитическом обзоре [15] представлены последние данные – в
России 1807 лесхозов, 7851 лесничество, в каждом лесничестве более
100 кварталов, в каждом квартале может быть до 100 выделов
(однородных участков). Необходимо применять МВС, и необходима
разработка соответствующего проблемно-ориентированного подхода
ландшафтного распараллеливания для прогноза лесной пожарной
опасности на крупных лесопокрытых территориях, который бы
базировался на трех основах: физически содержательная методика
определения вероятности лесопожарного происшествия (в данном
случае – возникновение лесного пожара), использование достаточно
дешевых МВС, существующая структура устройства лесного
хозяйства [16]. Сформулированы основные положения подхода
ландшафтного распараллеливания [17].
Математическая постановка должна быть такой, чтобы расчеты
для каждого отдельного однородного участка леса не зависели от
других участков
леса. Другими словами, необходимо разработать
35
математическую постановку, которая бы позволяла вести расчет
отдельно по всем выделам.
Однородный участок леса должен совпадать с однородными
участками леса, принятыми в лесотаксационных описаниях [16].
Отсюда берет свое начало термин «ландшафтное распараллеливание».
Для обеспечения более или менее равномерной вычислительной
загрузки процессорных узлов МВС необходимо использовать модель
распараллеливания по данным [18]. В MPI, например,
может быть
использована SPMD-модель вычислений [19]. Хотя равномерная
загрузка данными не всегда обеспечивает равномерность
вычислительной загрузки.
Возможность обеспечивать высокую производительность
(быстродействие) параллельной программы на как можно большем
количестве МВС, различных по архитектуре, имеющих при этом
хорошее соотношение цена/производительность, доступность и
массовое распространение.
Обеспечение как можно меньшего количества обменов
информационными пакетами
между ветвями параллельной программы
в процессе ее выполнения, так как основное узкое место МВС - это
коммуникационная среда, применяемая для связи между
процессорными узлами. Таким образом, самым оптимальным
вариантом по критерию цена/производительность можно считать
кластерные вычислительные системы, имеющие, однако, очень низкие
показатели скорости обмена между процессорными узлами. Это и
обусловливает необходимость
как можно меньшего числа обменов и
обеспечения возможности перекрытия вычислений и обменов.
Обеспечение однозначного отображения административно-
хозяйственного, лесотаксационного разделения лесного фонда
государства (по крайней мере, Российской Федерации) на архитектуру
МВС. Разбиение лесного фонда по выделам и распределение
вычислительной нагрузки по процессорным узлам МВС.
С учетом сформулированных выше положений ландшафтного
распараллеливания
был разработан ряд различных по сложности
математических моделей для определения времени сушки слоя ЛГМ.
Их применение позволяет обеспечить равномерность вычислительной
нагрузки, высокую производительность и возможность использования
недорогих МВС (вычислительных кластеров).
В случае когда вычислительная система состоит из одного узла
(М=1), время выполнения цикла - T
o
=pNV/c, где р - количество
36
операций, необходимых для вычисления одной итерации цикла, NV -
число итераций цикла, с - производительность узла. Тогда, если NV >
М и NV делится нацело на М, на каждом процессоре выполняется
NV/M итераций цикла и время выполнения цикла равно T
M
=pNV/(Mc).
Определим ускорение S
M
через отношение T
0
к T
M
и в итоге получим:
S
M
=M. Эта формула для ускорения справедлива при полном
отсутствии потерь. Под эффективностью понимается отношение
M
MT
T
E
0
=
, которая в данном случае будет равна единице, так как не
учитываются потери.
Если NV не делится нацело на М, то задача об оптимальном
распределении итераций цикла по процессорным узлам системы
является задачей целочисленного программирования и, как отмечено в
[20], не всегда имеет точное решение. Рассмотрим здесь следующую
эвристику: сначала [NV/M] итераций
равномерно распределяются по
узлам, затем количество оставшихся итераций распределяется на
NV-[NV/M]
⋅
M процессорных узлов, что приведет к тому, что на
некоторых узлах будет больше итераций.
Кроме того, перед выполнением цикла, как правило, необходимо
разослать исходные данные по узлам вычислительной системы, а
после выполнения цикла необходимо собрать результаты с
процессорных узлов. Время, которое необходимо на выполнение
указанных действий, обозначим через T'
M
. Если NV не делится нацело
на М, а при распределении данных по узлам была использована
некоторая эвристика, то на часть узлов попадут "лишние" данные [20],
время обработки которых тоже присоединим к Т'
M
. В итоге время
выполнения параллельного цикла равно T
M
=T
0
M
+T'
M
=T
0
M
+
α
M
T
0
M
, где
T
0
M
- время выполнения параллельного цикла при отсутствии потерь, а
α
M
=T'
M
/T
0
M
. Таким образом, с учетом потерь ускорение равно
S
M
=M/(1+
α
M
). Когда необходимо учитывать потери, эффективность
вычисляется по формуле
()
00
00
MMM
M
TTM
T
MT
T
E
α
+⋅
==
и будет равна 1/(1+
α
M
).
Расчеты проводились на вычислительном кластере Томского
государственного университета. Технические характеристики:
18 процессоров Pentium III 650 MHz, 2.5 Гб ОЗУ, 36 Гб дискового
37
пространства, Fast Ethernet. Программное обеспечение: операционная
система FreeBSD 4.2, кластерный пакет LAM MPI v 6.3.2. Кроме того,
был создан и запущен в эксплуатацию вычислительный кластер на
базе компьютеров локальной вычислительной сети кафедры [17],
который состоит из 4-х однопроцессорных компьютеров на базе
процессоров Intel Pentium III 800 МГц. На компьютерах установлено
по 128 Мб оперативной памяти и жесткий диск на 20 GB. Компьютеры
объединены с помощью сетевой
технологии Ethernet. Для организации
параллельных вычислений на кластере установлен кластерный пакет
LAM MPI 6.5.1. Узлы кластера в одно и то же время могут
использоваться как в качестве пользовательских станций, так и
непосредственно для проведения вычислений.
Реализация параллельной программы осуществляется на языке
программирования Си с применением функций библиотеки передачи
сообщений MPI. Алгоритм параллельной программы: исходные
данные
разрезаются и рассылаются корневым процессом параллельной
программы. Затем на каждом узле параллельная программа
обрабатывает свою часть данных. Межпроцессорных обменов нет,
распараллеливание организовано крупнозернистыми блоками. По
окончании вычислений корневой процесс собирает результаты со всех
процессорных узлов и сохраняет их в файле результатов. Разработаны
масштабируемые параллельные программы (число задействованных
процессоров является параметром программы
).
Проанализировав полученные результаты, можно сделать вывод о
том, что алгоритм рассматриваемой задачи очень хорошо подходит
для параллельной реализации на МВС. В результате имеет место
ускорение, практически пропорциональное числу задействованных
процессоров МВС. Эффективность практически не зависит от числа
задействованных процессоров, так как в процессе работы программы
нет межпроцессорных передач данных. Установлено,
что падение
производительности невелико и
(
)
09,0max
]16,1[
=
∈
M
M
α
.
Следует заметить, что несмотря на применение эвристики для
распределения данных в случае, когда NV не делится нацело на M
(статическая эвристика с предварительным распределением перед
началом выполнения параллельного цикла), это не приводит к
заметной разбалансировке вычислительной нагрузки и нет
необходимости применять средства динамической перебалансировки
вычислительной нагрузки в процессе выполнения параллельной
38
программы. Рассылка и сбор данных корневым процессом
параллельной программы технически реализованы посредством
векторных вариантов функций рассылки и сбора данных библиотеки
MPI.
Подход ландшафтного распараллеливания является проблемно-
ориентированным, но в пределах области своего приложения
достаточно гибок и универсален. Разработаны прототип аппаратно-
программного комплекса для лесопожарного мониторинга крупных
лесопокрытых территорий и параллельный программный
комплекс
прогноза возникновения лесных пожаров на крупных лесопокрытых
территориях.
Разработанный аппаратно-программный комплекс
(вычислительный кластер, параллельный программный комплекс,
сопутствующее методическое обеспечение) использовался в 2002 году
в учебном и научно-исследовательском процессах на кафедре
физической и вычислительной механики ММФ ТГУ.
Заключение
В рамках новой концепции прогноза лесной пожарной опасности
разработан проблемно-ориентированный
подход ландшафтного
распараллеливания. Как показал анализ результатов проведенного
исследования, данный подход очень эффективен при решении задач
лесопожарного созревания слоя ЛГМ, определения вероятности
возникновения лесных пожаров, оценки экологических последствий
лесных пожаров. Параллельная программа достигает практически
максимально возможного ускорения, когда ускорение практически
пропорционально числу задействованных процессоров.
Литература
1. Stocks B.J., Alexander M.E., McAlpine R.S. et al. Canadian Forest
Fire Danger Rating System. Canadian Forestry service, 1987.
500 p.
2. Курбатский Н
.П., Костырина Т.В. Национальная система
расчета пожарной опасности США // Сб. «Обнаружение и
анализ лесных пожаров». Красноярск: ИЛиД СО АН СССР,
1977. С. 38–90.
3. Camia A. , Barbosa P. , Amatulli G. , San-Miguel-Ayanz J. Fire
Danger Rating in the European Forest Fire Information System
(EFFIS): Current developments // Forest Ecology and
Management. 2006. Vol. 234. Supplement 1. P. S20.
39
4. Нестеров В.Г. Горимость леса и методы ее определения. М.;
Л.: Гослесбумиздат, 1949. 76 с.
5. ГОСТ Р 22.1.09-99 “Мониторинг и прогнозирование лесных
пожаров. Общие требования”.
6. Сухинин А.И., Пономарев Е.И. Картирование и краткосрочное
прогнозирование пожарной опасности в лесах Восточной
Сибири по спутниковым данным // Сибирский экологический
журнал. 2003. № 6. С. 669 – 675.
7.
Барановский Н.В. Новая концепция прогноза лесной
пожарной опасности // Современные методы математического
моделирования природных и антропогенных катастроф:
Тезисы IX Всероссийской конференции (17–22 сентября 2007
г., Барнаул). – Барнаул: Изд-во Алт. ун-та, 2007. С. 13.
8. Толстых М.А. Полулагранжева модель атмосферы с высоким
разрешением для численного прогноза погоды //
Метеорология и гидрология, 2001, № 4, С. 5 – 15.
9. Lixiang Z., Xiaoshan Z., Yongzuo L., Jinggui W. Case study on
tropical cyclone track prediction with MM5 // Journal of Nanjing
Institute of Meteorology. Nanjing, China, 2000. Vol. 23. N 1. P. 73
– 80.
10. Барановский Н.В., Гришин А.М., Лоскутникова Т.П.
Информационно-прогностическая система определения
вероятности возникновения лесных пожаров //
Вычислительные технологии. 2003. № 2. С. 16 – 26.
11. Hoadley J.L., Westrick K.J., Ferguson S.A., Goodrick S.L.,
Bradshaw L., Werth P.A. The effect of increased model resolution
in predicting meteorological parameters used in fire danger rating
// Journal of Applied Meteorology. 2004. Vol. 43. P. 1333 – 1347.
12. Барановский Н.В. Математические основы системы усвоения
данных об уровне антропогенной нагрузки на контролируемой
лесопокрытой территории // Наука на рубеже тысячелетий
“Progressive technologies of development”: 3-я Международная
научно-практическая конференция: 24 – 25 ноября 2006 г.
Тамбов: ОАО “Тамбовполиграфиздат”, 2006. С. 120 – 121.
13. Cummins K.L., Murphy M.J., Bardo E.A., Hiscox W.L., Pyle R.B.,
Pifer A.E. A combined TOA/MDF technology upgrade of the U.S.
national lightning detection network // Journal of Geophysical
Research. 1998. Vol. 103. P. 9035–9044.
40
14. Барановский Н.В. Математическое моделирование наиболее
вероятных сценариев и условий возникновения лесных
пожаров: Дисс. … канд. физ.-мат. наук. Томск: Томский
государственный университет, 2007. 153 с.
15. Исаев А.С., Коровин Г.Н., Титов С.П. и др. Экологические
проблемы поглощения углекислого газа посредством
лесовосстановления и лесоразведения в России:
Аналитический обзор. М.:
Центр экологической политики,
1995. 156 с.
16. Проект организации и развития лесного хозяйства
Тимирязевского мехлесхоза Томского лесохозяйственного
территориального производственного объединения
министерства лесного хозяйства РСФСР. Том III.
Таксационные описания Тимирязевского лесничества. Книга
3. Кварталы 91-145. Инв. № 390. Томск: Гослезхоз СССР.
Всесоюзное объединение "Леспроект". Западно-Сибирское
лесоустроительное предприятие, 1990. 400 с.
17. Барановский Н.В. Ландшафтное распараллеливание и прогноз
лесной пожарной опасности // Сибирский журнал
вычислительной математики. 2007. Том 10. № 2. С. 141–152.
18. Малышкин В.Э. Основы параллельных вычислений: Учеб.
пособие. Новосибирск: Изд-во НГТУ. 1998. 60 с.
19. Snir M. , Otto S.M. , Huss-Lederman S. et al. MPI: The Complete
Reference. - Boston: MIT Press. 1996.
20. Аветисян А.И., Гайсарян С.С., Самоваров О.И. Возможности
оптимального выполнения параллельных программ,
содержащих простые и итерированные циклы, на
неоднородных параллельных вычислительных
системах с
распределенной памятью // Программирование. № 1. 2002. С.
38 – 54.