The Investigation of Two Varios Realization of ParallelAlgorithm for Calculation of Firest Fire Spread .pdf Разработка программньгх комплексов для проведения крупномасштабных вычислительных экспериментов на параллельных вычислительных системах для решения задач, связанных с моделированием пожарной ситуации в лесах, представляет собой сложную в теоретическом и практическом плане задачу. Разработка параллельных программ практического уровня сложности для задач математической экологии представляет собою многоэтапный технологический процесс, включающий в себя анализ задачи, выбор модели программы, декомпозиция задачи на параллельные процессы, анализ производительности и организации вычислительного эксперимента.Анализ задачи и выявление ее потенциального параллелизмаПостановка задачи и метод решенияДанная работа основана на полуэмпирической модели процесса распространения лесного пожара [1]. Рассмотрим алгоритм построения горящей кромки, основанный на численном решении уравнений, описывающих распространение процесса горения, по нескольким слоям лесного горючего. Введя в каждом из слоев прямоугольную сетку с шагами по координатам x и y соответственно Ax и Ay, введем сеточные области DA0;, DA1;, DA2i, где DA0i - область, где горючий материал находится в исходном состоянии, DAij - область, где происходит горение, DA2i -область, где горение невозможно, / = 1,2 . Алгоритм состоит в последовательном определении данных областей. Система рассматривается в дискретные моменты t = 0,1,2,.... с шагом At.Уравнение нагрева горючего в области DA0i имеет вид2Ие ((, j,t +1) = He ((, j,t) + AtAxAy^X Ф(m,n,t)x^sl (m-i,n- j) +s=l (m,n)&Dis+Фе1 (i, j, t) At - Atki (i, j) x [Hi (i, j, t) - H0i (i, j)],где He (i, j, t) - энтальпия горючего, Ф (m, n, t) - интенсивность тепловыделения в горящей области, Фе, (i, j, t) - интенсивность внешних тепловых источников,(m - i, n - j) - функция влияния локального пламени в горящей области на горючее в области D&0i, k, (i, j) - коэффициент тепловых потерь. Система рассматривается при начальных условиях Hl (i, j, 0) = H0l (i, j), (i, j) e DA0l, / = 1,2 .Условие воспламенения горючего в l-м слое при t = t : Hr (i, j,t ) > Hr (i, j),при этом узел (i, j) исключается из DД0/ (t*) и присоединяется к DД1/ (t*). Уравнение расходования горючего:Го>/ (i, j, t) - г, At при со, (i, j, t) > 0,[ю, (i, j, t) при со, (i, j, t )< 0 с начальным условием со, (i, j, t*) = ю0, (i, j), (i, j) e D&ll, / = 1,2 . Уравнение тепловыделения:Ф, (/, j,t) = Д, (/, j)[со, (/,у,t)-co, (/,у,t-At)], (i, j) e D&u, I =1,2, где A, (i, j) - теплотворная способность горючего.Условие погасания при t = t*: со, (i, j,t*) = 0 , (i, j) e D&u , при этом точка (i, j) исключается из D&ll (t*) и присоединяется к D&2l (t*).Функции влияния \j (x - xj, y - yx, z - zj) задаются формулами с учетом дискретизации по пространству и приводятся в работе [1].ПараллелизмДля распараллеливания процесса вычислений предлагается схема, вытекающая из физического содержания данной задачи. Расчет энтальпии для точки i,j на (г+1)-м временном шаге происходит с использованием некоторого количества точек на t-м шаге. Численный расчет ведется итеративно: по имеющимся значениям n-го временного шага выстраиваем (t+ 1)-й и т.д.Следовательно, исходную задачу можно разбить на несколько подзадач для областей, пересекающихся только по границе разбиений, независимых друг от друга на каждом расчетном шаге. Исходная область не включает взаимно перекрывающиеся подобласти, поэтому пересчет значений на границах между данными областями предполагает согласно алгоритму суммирование при обмене вычисленными значениями для граничных элементов. Для перехода к следующей итерации необходимо согласование границ, так как первая область должна передать второй ее левую границу для следующего шага по времени, в свою очередь вторая область должна предать первой ее правую границу и т.д.Определим теперь потенциальный параллелизм алгоритма количественно. Общий объем вычислений Vcaic в алгоритме определяется соотношением Vcaic = s-k-N2, где N2 - количество расчетных точек в двухмерной области моделирования, k - количество операций, выполняемых в одной расчетной точке, s - количество шагов по времени. Для простоты полагаем, что все операции, в томчисле и обмены, имеют одинаковое время исполнения, равное t. Рассмотрим наихудший случай, когда все операции в одной точке выполняются последовательно. Следовательно, на каждом шаге итерации алгоритм требует для своей реализации k этапов. Тогда средняя степень параллелизма r будет равна r = s- kN2/(s-k) = N2.Ускорение и масштабируемостьПотенциальное ускорение алгоритма можно оценить исходя из следующего соотношения: Sp = Tx/Tp, где T - время вычислений на одном процессоре, Tp -время вычислений на p процессорах. При этом время перевычислений будет определяться следующим образом: Tc = 2smN, где m - количество значений для одной расчетной точки, передаваемых соседнему процессу.Рассмотрим случай с использованием неблокирующих передач. В общем случае обмены с использованием таких передач не зависят от количества используемых процессоров и потребуют Tc = const единиц времени. Тогда ускорение с использованием неблокирующих передач будет определяться следующим соотношением:Г11 < p < r,s

Скачать электронную версию публикации