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

российская академия наук Сибирское отделение Вычислительный центр

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

Расулов Гулям Саттарович

Разработка векторизованных алгоритмов для решения задач Физики атмосферы и охраны окружающей среды.

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

автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск-1993

Работа выполнена в. Вычислительном центре СО РАН. Научный руководитель доктор физико-математических наук,профессор, 3.В. Пененко

Официальные оппоненты: доктор Физико-математических наук,профессор, В.П. Ильин кандидат технических наук, с.н.с. Г. А. Панкееь

Ведущая организация : Институт вычислительных технологий Сибирского отделения РАН

Защита состоится ' ——-М-^Л.---- 1993 Г-

ъ!б час. мин. на заседании специализированного совета Д 002.10.02 по защите диссертации на соискание ученой степени доктора наук при Вычислительном центре СО РАН по адресу: 630090, Новосибирск-90, пр. академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале ВЦ СО РАН Спр. академика Лаврентьева, 6).

Автореферат разослан —-^-¿¿¿¿^----- 1993г.

Ученый секретарь Специализированного совета С- г. И. Эабиняко

Лктуальность_темы. Одним из способов повышения эффективности методов решения задач математической физики является использование ЭВМ с параллельными процессорами. Однако применение таких ЭВМ приводит к пересмотру существующих алгоритмов и создании новых. допускающих организацию параллельных вычислений. Кроме того, чтобы реализовать преимущества вычислительной систем, состоящей из нескольких процессоров, необходимо уметь представить задачу в виде нескольких параллельно взаимодействующих процессов. На сегодняшний день это достигнуто лишь для небольшого числа прикладных задач. Причиной тому являются некоторое проблемы, требующие значительного внимания к их решению на пути к высокопроизводительным машинам. К ним можно отнести в основном следующие вопросы. Во первых, необходмо обнаружить и выявить параллелизм в выполняег/ых пользовательских программах, причем в том виде, который в наибольшей степени согласуется со структурными особенностями используемой ЗВМ и во вторых, рационально спланировать и эффективно использовать в аппаратуре выявленные параллельные работы, направленные на максимальную загруженность машинных ресурсов.

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

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

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

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

Анализ многих работ, посвященных параллельным алгоритмам для высокопроизводительных машин показывает, что алгоритмы и программы, созданные для классической однопроцессорной машины нельзя непосредственно перенести на многопроцессорную или высокопроизводительную архитектуру. Такич образом, использование многопроцессорных систем заставляет их пользователей обращать внимание на совершенно новые проблемы. Именно, стремление эффективно^решать задачи на таких системах должно обьязательно сопровождаться согласованием структуры численных методов и архитектуры вычислительных систем. По этой причине в диссертации рассматривается программы, написанные на машинном языке ассемблера спецпроцессора ЕС-270В и которые составляют функциональное ядро в методах решения задач Физики атмосферы и окружающей среды. Это различные варианты методов прогонки, применяемые для решения систем линейных алгебраических уравнений с трех и пятидиагональными матрицами, встречающиеся очень часто в рассматриваемых нами задачах.

Целъю_работи является : >иследование возможности построения параллельных алгоритмов и программ для решения задач Физики атмосферы и охраны окружающей среды:

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

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

4

верхней релаксации для решения уравнений в пр.^оугольной области и программы группового преобразования БПФ.

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

Нацчная_новизна работы определяется предлагаемыми алгоритмами для решения конкретных задач в области физики атмосферы и охраны окружающей среды, а также организацией созданных и оформленных в виде стандартных программ ряда процедур на машинном языке СП EC-270S.

На основе опыта разработки этих программ и анализа архитектуры ЕС-2706 и МВК сформулированы требования к разрабатываемым параллельным алгоритмам для задачи ФА и ОС, а также приведены их сравнительные характеристики полученные теоретически и с помощью численных экспериментов.

П5§ктическая_ценностЬ;_ Созданные программы и алгоритмы могут быть использование при разработке других алгоритмов и пакетов программ для решения задач физики атмосферы, океана и охраны окружающей среды и др. Опыт их использования показывает, что время ^решения прикладных задач с 8-ю СП ЕС-2706 может быть уменьшено в несколькораз:Шэ сравнению со счетом на EC-106S.

Публикация_и_аппвдбация По теме диссертации опубликовано 5 работ. Основные работы диссертационной работы докладывались на школах семинарах молодых ученых в ВЦ СО РАНСНовосибирск, 1989), на Всесоюзной конеренции по методам математического моделирования в задачах охраны природной среды и экологии СНовосибирск,1991),на 4-ой Всесоюзной школе по математическим проблемам экологии СДушанбе, 1991).

СтЕ^кту2а_и_обьем_2абдты;. Диссертация состоит из введения, трех глав, пяти таблиц, 3-рисунков, заключения, списка литературы из 47 наименований. Общий обьем работы- 115 страниц.

Содержание работы.

§9-ЕЁЁ5§Н™ обосновывается актуальность проблемы использования параллельных вычислений к разработки прикладных процедур, позволяющих вести параллельные вычислений как в задачах Физики атмосферы и окружавшей среды, так и во многих других задачах математической физики в рамках многопроцессорного вычислительного комплекса, эксплуатируемого в ВИ СО РАН, а также формулируются основные задачи диссертации, научная новизна и практическая значимость.

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

Анализ работ по параллельным алгоритмам показывает, что имеется большое' число прикладных задач, для реализации которых достаточны многопроцессорные системы с линейными связями. Задачи, рассматриваемые в диссертации, также позволяют после осуществления метода расщепления по физическим процессам выделить множество подзадач, для эффективной реализации которых достаточно иметь множество процессоров с линейными связями между собой и управляемых универсиальной машиной. По этим обстоятельствам в диссертации для проведения экспериментов была выбрана эксплуатируемая на ВД - СО РАН многопроцессорная вычислительная система ЕС-1088.17. Она состоит из управляющей ЭВМ ЕС-1068 и подключенных к ней по радиальной схеме через стандартный интерфейес от 1-го до 24-х спецпроцессоров ЕС-2706 - 38 -и разрядных векторно-конвейерных процессоров с архитектурой типа "широкая команда", пиковой производительностью 12-Мфлоп и объемом памяти данных 4 Мбайта.

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

Рассмотрены принципы построения параллельных программ с использованием процедур из библиотеки подпрограмм СП ЕС-2706, а также из совокупности специально написанных на машинном языке спецпроцессора процедур, которые являются базовыми для

реализации моделей задач физики атмосферы и округакцей среды.

Процесс построения параллельных программ на вычислительной системе ЕС-1063.17 включает планирование эффективного алгоритма, определяющего порядок выполнения задач и распределения данных и программ по процессорам.

Основу системных организаций предложенных оггорктм^в и программ составляет метод расщеплзкмя по физическим процессам и пространственным переменным. 3 самом мзтоде расцепления залоге:;;; возможности векторизация алгоритмов.

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

описываются некоторые подходы к векторизации базовых алгоритмов в задача:»: физики атмосфера и охраны окружающей среды. Представлен комплекс программ, включающий программы для решенга систем конечно-разностных уравнения методами трехточечной, пятиточечной. циклической прогонки со сравнительными характеристиками, а так~з программы для матричной прогонка, когда матрицы имеют размерность 2x2 и 3x3.

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

Как было отмечено, среды базовых алгоритмов реал^йации математических моделей для задач фисики атмосферы, океана и окружающей среды методом расщепления широко "спользуются алгоритмы для решения систем трех- и пятиточечных уравнения, получающихся в результате построения дискретных аппроксимаций модели. Большинство задач этого класса обладает внутренним параллелизмом, и системы дискретных уравнений отличаются на отдельных этапах вычислений коэффициентами и правыми частями, что позволяют параллельно решать совокупности таких задач. В связи с этим были написаны программы, реализующие алгоритмы простой, циклической и ' пятиточечной прогонки с оценкой временных характеристик для каждого метода, а так же программы для матричной прогонки, когда матрицы имеют размерности 2x2 и 3x3. Кроме этого, разработаны и реализованы

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

AC ID YCI-1Э-СС15 YCID +ВС13 УСI+1Э =—FC13, 1=0....N УС0)=йС1Ш1)+1Л1), YCЮ =мС2)YCN-l} +vC2), где мС1Э=ВС0ЭхСС0Э, yC13=FC03/CC0) И

мС 2) =АС Ю /СС Ю , vC 2) =FC ГО /СС ГО. и программа группового преобразования фурье.

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

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

Алгоритм реализован в виде процедуры PARI.

Входные параметры: АСГО ,В(Ю ,ССГО ,FCNM3, ALFCN5 .ВЕТСГОО. YCNM3 и числа N.M, где ACNi=0,BCI0=0,NM=N*M, М- число

параллельно решаемых задач, N - число узлов.

Обращение к этой процедуре осуществляется следующим образом:

CALL PAR1CIA, IB. 10, IF.IAL.IBT, IY.N.M». где 1д..... iy - базовые адреса передаваемых векторов

А, В, С, .... Y соответственно.

1.2. Система дискретных уравнений, отличающихся правыми частями и коэффициентами CCI).

Алгоритм реализован в виде процедуры PARFC.

Входные параметры: АСГО, ВСЮ, ССЮО, FCNM), ALFCNM). BETCNM), YCNM) и числа N.M, где ACN)=0,BCN)=0.NM=N*M. М-число параллельно решаемых задач', N - число узлов.

Обращение к этой процедуре осуществляется следующий

образом:

CALL PARFCCIA, 10, 1С, IF.IAL.IBT. IY.N.M),

где IA..... IT - базовые адреса передаваемых векторов

А, В, С, .... Y соответственно.

1.3. Система дискретных уравнений, отличающихся правыми частями и коэффициентами BCD.

Алгоритм реализован в виде процедуры PARFB.

Входные параметры: АСГО, BCNM), ССГО, FCNM5, ALFCNM), BETCNM). YCNM) и чиола N.M, где АСГО =0, ВСЮ =0,NM=N»M, М-число параллельно решаемых задач, N - число узлов.

Обращение к этой процедуре осуществляется следующим образом:

CALL PARFBCIA, IB, 1С, IF.IAL.IBT, IY.N.M),

где IA..... IY - базовые адреса передаваемых векторов

А, В, С.....Y соответственно.

1.4. Система дискретных уравнений, отличающихся правыми частями и коэффициентами ACI),BCI),CCI).

Алгоритм реализован в виде процедуры PABCF.

Входные' параметры: ACNM) , ВСЛЮ, CCNM), FCNM), ALFCNM), BETCNM), YCNM) и числа N, М, где АСЮ =0,BCro=0,NM=N*M, М-число параллельно решаемых задач, N - число узлов.

Обращение к этой процедуре осуществляется следующим образом:

CALL PABCFCIA, IB, 1С, IF.IAL.IBT, IY.N.M), где IA, ..., IY - базовые адреса передаваемых векторов А, В, С, .... Y соответственно.

В рассматриваемых нами задачах очень часто встречаются

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

С учетом того, что загрузка .данными матричньа: процессоров занимает значительное время, были написаны программы, которые вместо Nl*N2xN3...кратного обращения к перечисленным выше программам, позволяют обращаться к ним только один раз :

2.1. Программа для решения групповых прогонок, когда системы дискретных уравнений отличаются правыми частями внутри вложенных циклов.

Алгоритм реализован в виде процедуры FFN. Обращение к ней имеет следующий вид : CALL FFNCIA, IB, 1С, IF,IAL,IBT, IY,N,M, L), где IA.....IY - имеют прежний смысл.

2.2. Программа для решения групповых прогонок, когда системы дискретных уравнений отличаются как правыми частями, так и коэффициентами CCI) внутри вложенных циклов.

Алгоритм реализован в виде процедуры FCN. Обращение к ней имеет следующий вид : CALL FCNCIA, IB, 1С, IF,IAL,IBT, IT.N.M, L), где IA.....IY - имеют прежний смысл как и в 1.1.

2.3. Программа для решения групповых прогонок, когда системы дискретных уравнений отличаются как правыми частями, так и коэффициентами BCI) внутри вложенных циклов.

Алгоритм реализован в виде процедуры FBN. Обращение к ней имеет следующий вид : CALL FBNCIA, IB, 1С. IF,IAL,IBT, IY.N.M, L3, где IA.....IY - имеют прежний смысл как и в 1.1.

2.4. Программа для решения групповых прогонок, когда системы дискретных уравнений отличаются как правыми частями, так и коэффициентами ACD,ВС 13 ,СС1) внутри вложенных циклов.

Алгоритм реализован в виде процедуры PABCFN. Обращение к ней имеет следующий вид : CALL PABCFNCIA. IB, 1С, IF.IAL.IBT, IY.N.M, L),

где IA.....IY - имеют прежний смысл как и в 1.1.

- Отсюда становится ясным, что в случае применения процедура FFN, внутри цикла по L изменяются только векторы правых частей F,a в случае применения процедуры FCN или FBN изменяются векторы С, F или В, F соответственно.

В ЕС-2706 в отличие от некоторых ЭВМ, например, ЭВМ типа

CRAY,нет непосредственных векторных команд. Векторные операции в нем реализуется программно, т. е. в каждый тактовый~ период выдается 84-х разрядная команда, содержащая поле, которое управляет работой всех устройств ЭВМ в течение этого тактового периода. Из этого следует, что на ЕС-270В могно эффективно обрабатывать векторы большой длины, которые и возникает в задачах физики атмосферы, скеана и окружающей среди.

Известно, что в процессе нахождения решений во всех методах прогонки участвует реккурентные соотношения, которые затрудняют распараллеливание этих методов на ЕС-2703. Однако, можно показать, что в случае параллельой работы нескольких СП. с применением вышеуказанных программ, эффективность алгоритма будет выше, чем решение этой же задачи на однопроцессорной ЭВМ.

С целью эффективного использования памяти СП ЕС-2706, в главе также определены приемлемые длины векторов для вышеописанных процедур.

На основе предложенных параллельных алгоритмов, изложенных в главе 1 и включенных в состав действующей модели гидротермодинамики и переноса примесей проведен вычислительный эксперимент для расчета динамических полей в пограничном слое атмосферы до высоты < 3 км над динамически и термически неоднородной подстилающей поверхность!) в трехмерной области. Параметры конкретных объектов и физико географические характеристики, . функции распределений источников и параметры выбросов примесей задаются на уровне входной информации. Результатом работы программы являются метеорологические поля в различные моменты моделируемого времени, такие как трехмерное поле скорости ветра, температуры, удельной влажности, энергии турбулентности и их производные, а также значения мгновенной и интегральной концентрации аэрозоля.

В результате численного эксперимента на вычислительной системе ЕС-1088.17 было 'получено ускорение в 5 раз по сравнению с соответствующей последовательной программой на EC-106S.

В_ТЕ§тьей_главе рассмотрены вопросы технологии параллельного программирования прикладных задач на МВК, приведены результаты и сделан анализ численных экспериментов

по решение задач ФА и ОС.

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

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

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

В главе рассматриваются также реализации 1 высокопроизводительной системе ЕС-1068.17 решения краев* задачи для уравнения Пуассона в прямоугольной области краевыми условиями первого рода. Соответствующая систе разностных уравнений решается методом последователь:: верхней релаксации. Алгоритм решения этой задачи являет базовым для решения задач динамического согласования пол метеоэлементов с постоянным параметром Кориолисса. Программ реализующая данную задачу написана на машинном языке ЕС-2708 и оформлена в виде стандартной процедуры.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ .

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

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

Определена допустимая длина векторов с целью эффективного использования памяти СП.

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

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

По теиэ диссертации опубликованы следую еще работы:

Кгвтат-уыИ »гч -г /1 ТТ гч т>

п А б^ШПил апи**»^! яи 4

прогонки на матричном процессоре ЕС-2705 //'Численное моделирование для задач динамики атмосферы и охраны окружающей срсды. -Новосибирск, 1989, -с 74-81.

2. Расулов Г. С. Использование параллельных вычислений для реализации базовых алгоритмов для задач физики атмосферы и окружаюаей среды. Новосибирск. 1891. -28 с-СПрепринт /АН СССР, Сиб. отд-ние, ВЦ:939)

3. Расулов Г.С. Моделирование задач физики атмосферы и окружающей среды на Спецпроцессоре ЕС-2706 //Тезиш доклада Новосибирск,1991 г.

4. Расулов Г.С. Применение параллельных вычислительных алгоритмов для решения задач физики атмосферы и экологии //В сб. Математические проблемы экологии, Душанбе 91, стр. 25.

5. Расулов Г.С. Векторизация базовых процедур Физики атмосферы и окружающей среды на спецпроцессоре ЕС-2706//Численное моделирование для задач динамики атмосферы и окружающей среды. Новосибирск. 1992.СВ печати).