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

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

Логанова Лилия Владимировна

МОДЕЛИРОВАНИЕ И АНАЛИЗ ЭФФЕКТИВНОСТИ СОГЛАСОВАНИЯ ЧИСЛЕННЫХ МЕТОДОВ РЕШЕНИЯ СЕТОЧНЫХ УРАВНЕНИЙ С ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДОЙ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

-1 ИЮЛ 2015

005570337

Самара - 2015

005570337

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

Научный руководитель:

доктор физико-математических наук, доцент Головашкин Димитрий Львович. Официальные оппоненты:

Гергель Виктор Павлович, д.т.н., профессор, ФГАОУ ВО «Нижегородский государственный университет им. Н.И. Лобачевского», директор института информационных технологий, математики и механики;

Мельникова Елена Анатольевна, к.ф.-м.н., доцент, ФГБОУ ВПО «Тольяттинский государственный университет», доцент кафедры «Прикладная математика и информатика».

Ведущая организация:

ФГБОУ ВПО «Пензенский государственный университет», г. Пенза.

Защита состоится 18 сентября 2015 г. в 12:00 часов на заседании диссертационного совета Д 212.215.05 ФГАОУ ВО «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)», по адресу: 443086 Россия, г. Самара, Московское шоссе, д. 34.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГАОУ ВО «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)», http://www.ssau.ru/files/resources/disjprotection/Loganova_L_V_Modelirovanie_i_analiz.pdf.

Автореферат разослан 18 июня 2015 г.

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

д. т. н, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы диссертации.

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

На сегодняшний день для решения ленточных СЛАУ на кластерных ВС (вычислительных системах) традиционно применяются следующие программные комплексы: PLAPACK (пакет параллельных процедур линейной алгебры, включающий параллельные версии процедур решения систем линейных уравнений с помощью LU и QR-разложений. разложения Холецкого и др.), ScaLAPACK (библиотека параллельных программ для решения систем линейных уравнений, обращения магриц, поиска собственных значений и др.), BlockSolve95 (параллельная программная библиотека предназначенная для решения СЛАУ с симметричными разреженными матрицами). Для систем с GPU (графическим процессором) используются NVIDIA cuSPARSE (набор базовых подпрограмм линейной алгебры для разреженных матриц), NVIDIA cuBLAS (библиотека базовых подпрограмм линейной алгебры для NVIDIA CUDA), CULA (GPU-ускоренная версия широко используемых операций LAPACK, то есть библиотека популярных функций линейной апгебры). Однако они не специфицированы для решения совокупности СЛАУ, возникающих при решении задач математической физики, связанных с двумерными сеточными областями. В частности, использование структур данных в указанных пакетах требует предварительной обработки в этом случае.

Для создания эффективных парачлельных алгоритмов решения СЛАУ с ленточными матрицами традиционно используются следующие прямые методы: прогонки (Томаса), циклической редукции и декомпозиции области. Прогонка в отличие от циклической редукции характеризуется меньшим объёмом коммуникаций, в отличие от декомпозиции области более низкой вычислительной сложностью. Это и определило выбор автора в пользу применения метода Томаса для решения СЛАУ с матрицей ленточного вида. Следует заметить, что параллельный алгоритм выбранного метода в случае решения одной СЛАУ не допускает эффективного использования более 2 процессоров. Однако, при переходе к многомерным сеточным областям и, как следствие, к совокупности СЛАУ указанное ограничение снимается, что обуславливает актуальность использования метода прогонки для решения ленточных СЛАУ.

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

Зачастую при выборе численного метода, в тени остаются вопросы, связанные с архитектурой аппаратных средств и программным обеспечением, используемым для его реализации. Однако, при построении эффективного параллельного алгоритма численного метода особенно актуальной становится решение проблемы согласования его со структурой вычислительной системы. Еще в 70-е годы прошлого столетия академиком Г. И. Марчуком было предложено соответствующее направление исследований, получившее название «отображение задач вычислительной математики на архитектуру вычислительных систем». В настоящее время с активным внедрением в повседневную практику GPGPU (GPU общего назначения) интерес к данной тематике многократно возрос. При этом для совместного исследования параллельных алгоритмов и ВС необходимы унифицированные формы их описания, с учётом недавно появившихся архитектур. При построении новых математических моделей алгоритмов и ВС по методикам, развиваемым в работах В. В. Воеводина и Вл. В. Воеводина, В. П. Гергеля, В. Г. Хорошевского, актуальным является использование графового представления для математической модели алгоритма встречных циклических прогонок, которая позволяет рассматривать двумерные сеточные области и модели ВС, распространяемой на графические процессоры. Необходимость в таких моделях обуславливается важностью предсказания эффективности вычислений по алгоритму с помощью математической модели до его реализации на выбранной современной вычислительной системе.

Результаты исследования соответствуют следующим пунктами паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ: пункту 3 - «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; пункту 4 - «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; пункту 5 - «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента».

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

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

Целью диссертационной работы является согласование численных методов решения сеточных уравнений с гетерогенной вычислительной средой.

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

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

Задачи диссертационной работы.

1. Сформулировать численный метод решения ленточных СЛАУ с ненулевыми элементами в правом верхнем и левом нижнем углах матрицы, алгоритмы которого по сравнению с известными алгоритмами, обладают внутренним параллелизмом, характеризуются относительно небольшим объёмом вычислений и коммуникаций;

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

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

4. Построить параллельные алгоритмы численного метода решения ленточных СЛАУ, упомянутого вида, для реализации на вычислительных системах, включающих один или несколько GPU. Реализовать их программно для подтверждения эффективности алгоритмов и адекватности математической модели.

Научная новизна диссертационной работы.

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

2. Построены математические модели параллельных алгоритмов встречных циклических прогонок, согласованные с ВС, основанные на графовом представлении и позволяющие предсказывать эффективность вычислений. Предложенная методика построения математических моделей параллельных алгоритмов, в отличие от известных разработок, включает строго формализованную процедуру нахождения ЯПФ (ярусно-параллельной формы).

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

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

5. Предложенная математическая модель алгоритма расширена для возможности её использования на вычислительных системах, включающих GPU.

Теоретическая и практическая значимость работы.

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

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

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

Результаты диссертации внедрены в федеральном государственном автономном образовательном учреждении высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)» и Институте Систем Обработки Изображений Российской Академии Наук.

Основные положения, выносимые на защиту.

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

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

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

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

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

6. Программные комплексы, реализующие параллельные алгоритмы метода встречных циклических прогонок для одномерной сеточной области, для двумерной сеточной области с линейным и двумерным (циклическим) разбиением сеточной области на суперкомпьютере «Сергей Королёв», циклической прогонки на гетерогенных вычислительных системах с GPU.

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

Результаты, полученные в диссертации, представлялись на IV Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи», СамГТУ (2007г.), семинаре «Компьютерная оптика и обработка изображений», СГАУ (2008г.), Всероссийской конференции, приуроченной к 80-летию академика С.К. Годунова «Математика в приложениях», институт математики СО ВАН (Новосибирск, 2009г.), международной научной конференции ПАВТ-2010," Уфа, (2010 г.), международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 90-летию со

дня рождения академика H.H. Яненко, Институт ВТ СО РАН. Новосибирск, 2011г., Всероссийской научно-технической конференции «Суперкомпьютерные технологии», ЮФУ (2012г.), Международной научно-технической конференции «Перспективные информационные технологии (ПИТ-2014)», СГАУ (2014), а также совместных семинарах кафедры «Техническая кибернетика» и ИСОИ РАН.

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

Диссертационная работа выполнена в рамках работ по проекту «Разработка комплекса технологий использования ресурсов суперкомпьютера «Сергей Королёв» в целях развития инновационной и научно-образовательной среды университета» (мероприятия 3.3 Программы развития национального исследовательского университета), программы повышения конкурентоспособности университета по направлению развития научно-образовательной деятельности

"Суперкомпьютинг, информационные технологии и геоинформатика".

Публикации по теме диссертации. Результаты диссертации опубликованы в 13 работах, из них: 4 публикации в журналах, рекомендованных ВАК. 5 работ в материалах и трудах Международных и Всероссийских конференций, 1 тезисы доклада, 1 монография. 2 свидетельства о регистрации программ для ЭВМ.

Структура и объём работы. Диссертация состоит из введения, трёх глав, заключения и 5 приложений. Объём диссертации - 146 страниц (без приложений). Диссертация содержит 30 таблиц. 65 рисунков и список литературы из 61 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Далее выполнен обзор численных методов решения сеточных уравнений с ленточной матрицей. В двумерном случае областью изменения аргументов которой является прямоугольник ~G = {{)<x<X,Q<y<Y) с границей Г, вводится двумерная сетка узлов с шагами Л, и А, в области изменения каждой переменной соответственно:

й>2 = +ihx,i = 0,1,...,Л/-\,hx = (bx-ах)/М;

у. = ау + jhy,j = 0,1,..., N-\,hy = (by-ay)/N;}.

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

сон = {(/, ,х„у;): / = кт,к = 0,1,...,= = 0,1,...,М -1, х0=хи,у/ - jhvJ = 0,\,...,N-\,уа = у ы}, где т - шаг по времен и При этом - искомые значения сеточной функции и

Uk = [ufj,k=0,K,i = 0,M-l,j = 0,N-l).

В этом случае для решения двумерных нестационарных задач вычислительной физики широко применяются методы переменных направлений (Писмена-Рекфорда), покоординатного расщепления (Яненко H.H.) и другие.

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

AjXj=fj, (1)

где Aje RMXM, Xj,fjsRM, xj=(Ujo,...,UjM..), j=0:N-l, для ¡< j+1, j< i+1, Uj0=UjM.i

A,yrf/, (2)

где A,e RNXN, y,,f,eRN, yKUo/..».^.,,)7, /=0:М-1, a^O для i<j+l, j< i+1, U0,=UA,„

В работе был произведен анализ алгоритмов решения трёхдиагональных систем, основанных на методах циклической редукции, декомпозиции области и методе прогонки, который определил выбор автора в пользу разработки метода встречных циклических прогонок для решения трёхдиагональных СЛАУ с ненулевыми элементами в верхнем правом и левом нижнем углах матрицы системы. Указанный метод основан на циклической и встречных прогонках. Алгоритм упомянутого метода может быть распараллелен на 2 процессора в результате выполнения функциональной декомпозиции.

В работе приведено описание синтезированного метода встречных циклических прогонок:

1. Определение прогоночных коэффициентов:

А

С« с. с.

I

b¡ „ fi+aß, a¡r, . ~-:

с, - а а, с, - ад, с. - а,а,

(3)

М~\ „ _ fM-1 _ А/-1 SA/-1 ~~ 'пМ-\~ 'fM-1---•

СМ-1 сМ-\ СМ~\ (4)

а,

с,~аЛм c,~h¿,tl c,-b¿M 2. Нахождение значений промежуточных сеточных функций:

и - v _Lr„+<pn

т 1 -ajm " l-ajm '

(5)

= «,..",и + ßM > Ч- = + Гм, ¡ = m-l,l, u0 = 0, v0 = 1 (6)

= +7,, =¿;¡t]v¡+<p¡ll,i = m,M-2,uM =0,vM =1

3. Вычисление хо: х0

Со-ЯоП,-!"^

(7)

4. Определение значений искомой сеточной функции: х;= х0у, (8)

Далее автором предложена методика построения модели параллельного алгоритма метода встречных циклических прогонок. Как и в ранее упомянутых подходах, модель алгоритма представляется в виде ациклического мультиграфа Ор/,Е), где V - множество вершин, соответствующих блоку арифметических операций по алгоритму, Е - множество дуг, отражающих информационные зависимости между ними. На рисунке 1 представлен граф алгоритма метода встречных циклических прогонок. Вершины 1,2; 4.5 и 7.8 - информационно независимы.

Рисунок 1 - Граф алгоритма с учётом информационных зависимостей (1,2 - определение прогоночных коэффициентов, 3 - определение средних значений промежуточных сеточных функций, 4,5 - вычисление остальных значений промежуточных сеточных функций, 6 - поиск х0, 7,8 - нахождение искомых

значений сеточной функции) При построении ЯПФ в каждый следующий ярус помещаются вершины, зависящие от вершин предыдущего яруса (рисунок 2). Построение строгой параллельной формы алгоритма производится перенумерацией вершин графа в соответствии с ЯПФ. Вершины одного яруса нумеруются одним индексом.

ярус 1 1,2

ярус 2 3

ярусЗ 4.5

ярус 4 6

ярус 5 7,8

© XI)

Рисунок 2 - Ярусно-параллельная форма (слева), строгая параллельная форма

алгоритма (справа)

Развивая известные подходы к представлению математических моделей алгоритмов, автором работы предложена модель указанного алгоритма для решения совокупности СЛАУ с ленточной матрицей, которая возникает при рассмотрении двумерных сеточных областей (ШМ). В этом случае модель параллельного алгоритма представляется совокупностью подграфов (граф определения прогоночных коэффициентов, граф поиска значений промежуточных сеточных функций, граф нахождения значений искомой сеточной функции) в отличие от модели для одномерной области. Так как каждый из этих этапов алгоритма содержит циклические конструкции, то полученное пространство итераций является двумерным. А граф нахождения прогоночных коэффициентов аДу будет следующим (рисунок 3). Аналогично, строится граф нахождения прогоночных коэффициентов а также нахождения значений промежуточных сеточных функций. В случае

поиска значений искомых сеточных функций информационные зависимости отсутствуют.

Рисунок 3 - Граф нахождения прогоночньгх коэффициентов аДу

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

При описании модели параллельного алгоритма введены дополнительные характеристики:

Для каждой вершины V; е V определена функция р: V—>Z+, p(v;) - количество вычислительных операций;

т. V—>Т, т.е. x(vj) eTj, T| - универсальный процессор, Т: - графический процессор; р: V-»Z+, p(Vi) - количество вычислительных операций, выполненных i -ой ветвью; 5: Е-> Z+, 5(Vj) - объём данных, пересылаемых i-ой ветвью j-ой, соответствующий ребру Cij; v: Е—> Zb v(vj) - число коммуникаций, соответствующего e;j ребра. Шаблон коммуникаций тор описан с помощью матрицы смежности М .

Моделирование состоит в исследовании математической модели алгоритма, согласованной с ВС (суперкомпьютер «Сергей Королёв).

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

Модель вычислительной системы есть граф S(C,L) где С - множество вычислительных устройств, L- множество дут, связывающих их, или 8ДСДЦ'), где i - уровень иерархии,] — номер устройства Шаблон коммуникаций также может быть представлен матрицей смежности Му, где lV=l, если устройства i и j соединены напрямую; 0 - иначе, к - уровень иерархии.

Заданы дополнительные функции на множестве вычислителей: т(Ср) - ставит в соответствии вершине Ср тип (Ti или Т2) вычислительного ядра р; р(Ср) -производительность вычислительного устройства р; P(/jjk) - значение пропускной способности линии связи между вычислительными элементами i и j на уровне k; v (/дк) - значение латентности линии связи между вычислительными элементами i и j на уровне к.

Отображение графа алгоритма G(V, Е) на структуру вычислительной системы, заданной графом S=(C, L), обозначены как <p:V —»С и представляется матрицей X={x;j, где хд = 1, если (?(vi) =Cj, и х„ = 0 иначе, v( eV, с, еС }.

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

P(v,) „ ,, [0, г(г', ) * г(с„) ■ 1 , V, е V,cm бС,г„ = Р(0 \l,r(v,) = r(0

Тарр. = т„-хт

: max ( тт -xm

P(v,) MO

), V,. 6 l',c, 6 С, r„

Оценка времени выполнения коммуникаций кратчайший путь от вершины с„, к сг:

<ЯО,

0,ф,)*т{ст)

1,r(v,) = r(cj

между i 1-

j ветвями, где L^

т.;

Vе'-..

ж/-)

Г™"™ = шах (*„,.*,„• X (v(e„) v(^) + ^4)); г »Г*+7"""" " VеI*'

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

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

Вычислительные эксперименты проводились на суперкомпьютере «СЕРГЕИ КОРОЛЁВ»: общее число серверов/процессоров/вычислительных ядер: 165/332/1712; общая оперативная память: 4375 Гб; тип системной сети: QLogic/Voltaire InfiniBand DDR, QDR; тип управляющей вспомогательной сети: Gigabit Ethernet.

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

PO Р! Р2 Pi ро pi pi PI pn

uEH

M

Рисунок 4 - Этапы прямого хода четырёхпроцессорного алгоритма (аналогично

выполняется обратный ход и нахождение х), «»»-простои Р|, При этом завершение обратного хода сопровождается вычислениями, связанными с нахождением значений искомой сеточной функции.

Программная реализация алгоритма в случае прямоугольных сеточных областей обеспечила ускорение до 12 (32 процессора, рисунок 5). продемонстрировав его эффективность. Векторизация вычислений по алгоритму, основанная на применении векторных операций (т.е. поэлементного умножения, сложения), а также передачи

данных блоками, позволила увеличить значение ускорения (около 3 раз. рисунок 6, Р=4).

.. в ------ ■■

Рисунок 5 - Зависимость ускорения от Рисунок 6 - Зависимость ускорения от формы сеточной области (пунктирная размеров векторного операнда

линия - прямоугольная сеточная область. (пунктирная линия - прямоугольная сплошная - квадратная, N=1600) сеточная область, сплошная -

квадратная)

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

ЛЬ-

г*.

-ем

ы.

<г "V

со5 (0,

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

Его программная реализация в случае решения трёхдиагональных СЛАУ на квадратных сеточных областях позволила получить ускорение 6,2 (16 процессоров, рисунок 8). Для векторизации вычислений по алгоритму использовался тот же приём, как и в случае линейного разбиения, что обеспечило рост ускорения на рассмотренном диапазоне значений размеров сеточных областей до 4 раз (рисунок 9, Р=4).

>№ -4СС- <«Л I : ^ 1» >5 1ГС «[' Ш 1№

Рисунок 8 - Зависимость ускорения Рисунок 9 - Зависимость от размеров сеточной области ускорения от длины векторного (М=М) операнда на квадратной сеточной

области

Сравнение длительности вычислительных экспериментов и оценок этой величины согласно авторской модели свидетельствует об адекватности последней (рисунок 10, Р=32). При этом в случае двухпроцессорного алгоритма СКО=3,18Е-О5с (среднекватратичное отклонение), для четырёхпроцессорного алгоритма с двумерным разбиением сеточной области СКО=7,621Е-О2с, для тридцати двух процессорного с линейным разбиением СКО=0.05с.

1600 Î200 Ç60G 1КОЭО 320СО 64000 128СОО

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

В третьей главе разработаны векторные и векторно-параллельные алгоритмы циклической прогонки для реализации на графическом процессоре. Этапы векторного алгоритма на одном GPU:

1. Задание характеристик ядра. 1 (ередача данных на GPU (a,b,c,d s RM);

2. Вызов ядра (Kernel 1). Вычисление прогоночных коэффициентов a,,ß,,y; (3);

3. Освобождение памяти GPU от a,b,c,d;

4. Вызов ядра (Кегпе12). Нахождение векторов значений промежуточных сеточных функций u,v (6);

5. Освобождение памяти GPU от векторов a,ß,y. Передача векторов значений промежуточных сеточных функций u.v на ЦПУ;

6. Вычисление х0 на ЦПУ. Передача их на GPU (7);

7. Вызов ядра (КегпеВ). Определение искомого вектора значений х и пересылка его на ЦПУ (8).

Вычислительные эксперименты проводились на системе с 2 видеокартами GeForce GTX 470 , CPU Intel Core 2 Duo E8500 3.16 ГГц. операционная система Microsoft Windows ХР, NVIDIA CUDA Version 2.3. Microsoft Visual Studio 2008 (OpenMP), PCI-Express xl6 4Гб/с.

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

По сравнению с последовательной реализацией на CPU, реализация векторного алгоритма на GPU позволила достичь пятикратного ускорения. Программная реализация синтезированного параллельного алгоритма циклической прогонки на 2 GPU обеспечила ускорение в 1,7 раз по сравнению с решением на одном (рисунок 11а).

Сравнение времени выполнения вычислений по алгоритму циклической прогонки с оценкой согласно авторской модели говорит об адекватности таковой (рисунок 116, СКО= 0,19с для одного GPU).

а) б)

Рисунок 11 - Зависимость ускорения реализации алгоритма циклической прогонки от размеров сеточной области (М=500, а) сплошная линия - два GPU, пунктирная -одно GPU; б) сплошная - на модели, пунктирная - экспериментально) Таким образом, в данной главе показана эффективность подхода к синтезу векторных и векторно-параллельных алгоритмов метода циклической и встречных циклических прогонок на гетерогенной ВС.

В заключении сформулированы основные выводы и результаты, полученные в работе:

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

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

3. Синтезированы параллельные алгоритмы перечисленных методов решения сеточных уравнений, основанные на двумерном (циклическом) и линейном разбиениях сеточной области. Вычислительные эксперименты, проведённые на суперкомпьютере «Сергей Королёв» показали эффективность программных реализаций построенных алгоритмов и подтвердили адекватность, предложенной для них математической модели. При этом максимальное достигнутое ускорение составило до 12 раз (для 32 процессоров).

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

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

Статьи в изданиях, рекомендованных ВАК:

1. Логанова, Л. В. Параллельный алгоритм метода циклических встречных прогонок для двумерной области // Вестник Самарского государственного аэрокосмического университета имени академика С. П. Королева. - 2008. - Т.2 (15).-С. 167- 174.

2. Логанова, Л. В. Параллельный алгоритм метода циклической редукции для периодической краевой задачи /Л.В.Логанова, Д. Л. Головашкин,

О. С. Сягайло //Вестник Самарского государственного технического университета. Серия Физико-математические науки. - 2010. - Т. 1(20). - С. 197-204.

3. Логанова, JI.B. Параллельный алгоритм реализации метода встречных циклических прогонок для двумерных сеточных областей /Д.Л. Головашкин, Л.В. Логанова // Вычислительные технологии. - 2011. - Г.16(4). - С. 64-71.

4. Логанова, Л.В. Решение сеточных уравнений неявных разностных схем с циклическими краевыми условиями на двумерных сеточных областях с использованием нескольких графических вычислительных устройств /Л.В. Логанова, Д. Л. Головашкин // Компьютерная оптика - 2012. - Т.36(4). -С. 534 - 540.

Монографии:

1. Параллельные алгоритмы решения сеточных уравнений: Монография / Д. Г. Воротникова, Д. Л. Головашкин, Н. Л. Казанский, А. В. Кочуров, Л. В. Логанова, С. А. Малышева; под ред. Н. Л. Казанского. - Самара: ИСОИ РАН, 2013.-146 с.

Работы в материалах и трудах Международных и Всероссийских конференций:

1. Логанова, Л. В. Векторный алгоритм метода встречных прогонок для потока задач /Д. Л. Головашкин, Л. В. Логанова // Труды IV Всероссийской научной конференции с международным участием. Ч. 4: Информационные технологии в математическом моделировании. - Самара: Изд-во СамГТУ, 2007. - С. 25-28.

2. Логанова, Л. В. Параллельный алгоритм метода встречных циклических прогонок с циклическим разбиением / Д. Л. Головашкин, Л. В. Логанова // Математика в приложениях: Всероссийская конференция, приуроченная к 80-летию академика С. К. Годунова - Новосибирск: Изд-во Институт математики СО РАН, 2009. - С. 86 - 87.

3. Логанова, Л. В. Векторно-параллельные алгоритмы метода встречных циклических прогонок [Электронный ресурс] / Логанова, Л. В. // Параллельные вычислительные технологии (ПаВТ-2010): Труды международной научной конференции (Уфа, 29 марта - 2 апреля 2010 г.) -Челябинск: Издательский центр ЮУрГУ, 2010. - С. 673. - URL: http://omega.sp.susu.ac.ru/books/conference/PaVT2010/ (дата обращения: 20.01.2015)

4. Логанова, Л. В. Реализация параллельного алгоритма циклической прогонки на графическом вычислительном устройстве / Л. В. Логанова //Труды Международной конференции «Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященной 90-летию со дня рождения академика Н. Н. Яненко. - Новосибирск: Институт вычислительных технологий СО РАН, 2011. - С. 30.

5. Логанова, Л. В. Реализация параллельного алгоритма встречных циклических прогонок на гетерогенной вычислительной системе / Л. В. Логанова // Материалы 2-й Всероссийской научно-технической конференции

«Суперкомпьютерные технологии». - Ростов-на-Дону: Издательство Южного Федерального Университета, 2012. - С. 140-144. 6. Логанова, Л. В. Выбор математической модели параллельного алгоритма с учётом особенностей архитектуры суперкомпьютера «Сергей Королёв» / Л.

B.Логанова // Перспективные информационные технологии (ПИТ-2014): Труды Международной научно-технической конференции. - Самара, 2014, -

C.335-339.

Свидетельства государственной регистрами программы для ЭВМ:

1. Логанова, Л.В. Параллельная программа для организации вычислений по неявным разностным схемам на двумерной сеточной области с циклическими граничными условиями методом встречных циклических прогонок, предусматривающая исполнение на кластерной вычислительной системе / Л.В. Логанова // Свидетельство о государственной регистрации программы для ЭВМ. Per. № 2014619701 от 19 сентября 2014 г.

2. Логанова, Л.В. Параллельная программа для организации вычислений по неявным разностным схемам на двумерной сеточной области с циклическими граничными условиями методом циклических прогонок, предусматривающая реализацию на графическом вычислительном устройстве / Л.В. Логанова // Свидетельство о государственной регистрации программы для ЭВМ. Per. № 2014619834 от 23 сентября 2014 г.

Подписано в печать 8.06.2015 г. Формат 60 х 84 1/16. Бумага ксероксная. Печать оперативная. Объем - 1,0 усл. печ. л. Тираж 100 экз. Заказ №.81.

Отпечатано в типографии ООО «Инсома-пресс» 443080, г. Самара, ул. Санфировой, 110А, оф. 22А, тел. 222-92-40, E-mail: insoma@bk.ru