Моделирование и анализ эффективности согласования численных методов решения сеточных уравнений с гетерогенной вычислительной средой тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Логанова, Лилия Владимировна

• Логанова, Лилия Владимировна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Логанова, Лилия Владимировна

Оглавление

Введение

1 Математические модели параллельных алгоритмов решения сеточных уравнений

1.1 Обзор математических моделей параллельных вычислительных систем и алгоритмов

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

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

1.1.3 Концепция математических моделей алгоритмов и вычислительных систем в работах Хорошевского В. Г

1.2 Методы решения сеточных уравнений трёхдиагонального вида для случая одномерных сеточных областей

1.2.1 Метод циклической редукции

1.2.2 Метод декомпозиции области

1.2.3 Метод прогонки

1.2.4 Метод Стоуна

1.2.5 Параллельный алгоритм метода прогонки

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

1.4 Решение сеточных уравнений методом встречных циклических прогонок

1.5 Математическая модель алгоритмов, основанных на методе встречных циклических прогонок

Выводы главы 1

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

2.1 Параллельный алгоритм для одномерной сеточной области

2.2 Параллельный алгоритм для двумерной сеточной области с линейным разбиением

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

2.4 Параллельный алгоритм с двумерным разбиением сеточной области

2.5 Параллельный алгоритм с циклическим разбиением сеточной области

Выводы главы 2

3 Реализация метода циклических прогонок на GPU

3.1 Модели CUDA

3.1.1 Аппаратно-архитектурная модель CUD А

3.1.2 Программная модель CUDA

3.2 Обзор алгоритмов решения сеточных уравнений трёхдиагонального вида

на GPU

3.2.1 Реализация на GPU метода редукции с использованием

быстрого преобразования Фурье

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

3.2.3 Гибридный алгоритм циклической редукции и метода Томаса

3.2.4 Сравнение алгоритмов, основанных на прямых методах

3.2.5 Сравнение библиотек для решения разреженных CJ1A У на GPU

3.2.6 Итог предложенного обзора

3.3 Математическая модель алгоритма циклической прогонки для GPU

3.4 Алгоритм циклической прогонки для одного GPU

3.5 Алгоритм циклической прогонки для двух GPU

3.6 Реализация алгоритма встречных циклических прогонок на

вычислительной системе с двумя графическими процессорами

Выводы главы 3

Заключение

Список использованной литературы

Приложение А

Приложение В

Приложение С

Приложение D

Приложение Е

Приложение F

Приложение G

Введение диссертации (часть автореферата) на тему «Моделирование и анализ эффективности согласования численных методов решения сеточных уравнений с гетерогенной вычислительной средой»

Введение

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

Актуальность темы

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

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

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

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

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

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

систем» [31]. В настоящее время с активным внедрением в повседневную практику GPGPU (GPU общего назначения) интерес к данной тематике многократно возрос. При этом для совместного исследования параллельных алгоритмов и ВС необходимы унифицированные формы их описания, с учётом недавно появившихся архитектур. При построении новых математических моделей алгоритмов и ВС по методикам, развиваемым в работах В. В. Воеводина и Вл. В. Воеводина [5-7], В. П. Гергеля [10,11], В. Г. Хорошевского [38,39], актуальным является использование графового представления для математической модели алгоритма встречных циклических прогонок, которая позволяет рассматривать двумерные сеточные области и модели ВС, распространяемой на графические процессоры. Необходимость в таких моделях обуславливается важностью предсказания эффективности вычислений ио алгоритму с помощью математической модели до его реализации на выбранной современной вычислительной системе.

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

Степень разработанности

По-видимому, к первой публикации, изданной в 1958 году и в заголовке которой употреблён термин «параллельное программирование», относится [46]. Немало книг, монографий, статей, выпущенных с тех пор, посвящено данной тематике. Особый интерес вызывают задачи, связанные с решением больших ленточных СЛАУ [35]. Первая работа, посвященная решению данной проблемы, вышла за авторством Н. Н. Миренкова и была основана на методе нрогонки[33], сформулированном И. М. Гельфандом[9]. Далее последовала работа академика

Н. Н. Яненко, основанная на том же алгоритме [43]. Первый алгоритм характеризовался повышенным временем простоев, второй - увеличением объёма вычислений. Далее Р. Хокни, К. Джессхоуп, Дж. Ортега обратили внимание на метод циклической редукции и последовательно развивали его в двух следующих работах[35,48]. Недостатком предложенных параллельных алгоритмов являлся повышенный объём коммуникаций. В той же монографии [35] был предложен более удачный в смысле коммуникаций алгоритм декомпозиции области, но количество арифметических операций возросло в 1,5 раза. Наиболее эффективным для решения задач данной диссертации представляется подход, предложенный академиком Б. Н. Четверушкиным[40,41]. Более современные работы касаются вариантов конвейерного алгоритма прогонки и блочной прогонки[54,55]. Однако их программная реализация представляет значительную сложность по сравнению с алгоритмами [40,41]. К сожалению, в литературе отсутствуют параллельные алгоритмы, основанные на методе циклической прогонки, которые широко применяются при моделировании процессов в периодических и круглых областях.

Долгое время вопросы, связанные с архитектурой ВС, численными методами и программным обеспечением, рассматривались в большинстве случаев отдельно. Например, Самарский А. А. «Введение в численные методы»[36], Мэтыоз Дж. «Численные методы ...»[34], Максимов II. В., Попов И. И., Партыка Т. Л. «Архитектура ЭВМ и вычислительных систем» [30], Каган Б. М. «Электронные вычислительные машины и системы»[17]. Исключение составляют, пожалуй, монографии Дж. Голуба, В. Лоуна «Матричные вычисления» [15] и Дж. Ортеги «Введение в параллельные и векторные методы решения линейных систем»[35]. В последние годы появились работы, в которых совместно рассматриваются математические основы параллельных численных методов и параллельных вычислительных систем [5-7,10,11,38,39]. В них уделено внимание проблемам, связанным с математическим представлением алгоритмов и ВС, возможности отображения модели алгоритма на модель ВС. Развитие данного

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

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

В соответствии с поставленной целью определены основные задачи диссертации:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты диссертации внедрены в Самарском государственном аэрокосмическом университете и Институте Систем Обработки Изображений Российской Академии Наук.

Методология и методы исследования

Построение параллельных алгоритмов основано на методике Фостера [45]. При распараллеливании сформулированного алгоритма встречных циклических прогонок применяется линейная и двумерная (циклическая) декомпозиция сеточной области. Математические модели алгоритмов и ВС являются развитием подходов [5-7,10,11,38,39]. Параллельные алгоритмы сформулированного метода и адекватность предложенных математических моделей верифицировались методом вычислительного эксперимента.

На защиту выносятся:

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

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

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

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

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

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

Степень достоверности и апробация результатов

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

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

1 Математические модели параллельных алгоритмов решения

сеточных уравнений

1.1 Обзор математических моделей параллельных вычислительных систем и алгоритмов

При решении задач математического моделирования основной интерес исследователей нередко связан с разработкой или выбором эффективного численного метода. Однако, зачастую при выборе численного метода в тени остаются вопросы, связанные с архитектурой аппаратных средств и программным обеспечением, используемым для его реализации. Появление новых архитектурных решений для вычислительных систем, дающих возможность одновременного использования большого числа процессоров для обработки информации, привело к необходимости модификации известных и разработке новых численных методов. И как оказывается, возможное по отношению к однопроцессорным ЭВМ независимое развитие направлений, связанных с вычислительной техникой, алгоритмическими языками и численными методами, является недопустимым для эффективной организации вычислений на параллельных вычислительных системах. Для параллельных ВС особенно актуальной становится решение проблемы согласованности алгоритмов со структурой таких систем. Приступая к синтезу параллельных алгоритмов, необходимо выделить те общие ограничения, продиктованные особенностями архитектур ВС, которые могут потребовать изменений структуры алгоритма для его эффективной реализации[6]. Ещё в 70-е годы прошлого столетия академиком Г. И. Марчуком было сформировано соответствующее направление исследований, получившее название «отображение проблем вычислительной математики на архитектуру вычислительных систем»[31].

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

модели алгоритма, реализуемого на суперкомпьютере, приведём несколько нотаций представления математических моделей алгоритмов и ВС [57,10,38,11,39], после чего выделим особенности авторского подхода для выбранной ВС.

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

В [5,7] представление алгоритма предполагается в виде графа, вершины которого отождествляются с операциями по алгоритму, дуги представляют информационные зависимости между ними, то есть С=(У,Е) - ориентированный ациклический мультиграф, где V - множество вершин, Е - множество дуг графа.

Согласно утверждению из [7], для графа в, состоящего из п вершин, 3 П1< п и можно произвести разметку вершин графа У; одним из индексов /, где 1 </ <пь Если имеет место дуга из У; вершины в У), то К]. Выполнив разметку в соответствии с утверждением, получим строгую параллельную форму. При этом вершины, отмеченные одним индексом, отнесём к одному ярусу параллельной формы, число ярусов определяет её высоту (т), максимальное число вершин на каждом из ярусов - ширину параллельной формы(ц).

Выберем максимальную параллельную форму, которая характеризуется минимальной высотой. Останавливаясь на примере перемножения п чисел, где п=8, рассмотрим две формы, одна из которых имеет максимальную высоту (последовательный алгоритм), а вторая - минимальную. Па рисунке 1.1 представлены параллельные формы алгоритма умножения 8 чисел, на рисунке 1.2 - схемы вычислений, соответствующие им.

б)

1

1

1

1

4 ш=3, 4=4

Рисунок 1.1— Графы алгоритма умножения 8 чисел (а) линейная параллельная

форма, б) строгая параллельная форма)

Рисунок 1.2 - Схемы вычислений, реализующие алгоритм умножения п чисел (п=8, левая схема соответствует линейной параллельной форме, правая - строгой

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

а1а2

{аха2)аъ (а{а2а,)аА (а{а2а3а4)а5 (а1а2а3о4о5)а6 (а{а2а3а4а5а6)а7 (а,а2аза4а5а6а7 )а1

Ярус\ Ярус 2 ЯрусЪ Ярус 4 ЯрусЪ Ярус 6 Ярус!

а,а2 а2а4 а}а6 апа% (о,а2)(а3а4) (а5а6)(а7а8) (а,а2а3а4)(а5а6а7а8)

параллельной форме)

Рисунок 1.3 - Пример строго направленного графа (штрихпунктирные

линии - гиперплоскости)

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

Вычислительная система из [5,7] определена, как совокупность функциональных устройств и также имеет графовое представление, где вершины - это функциональные устройства (ФУ), дуги - связи между ними. Базовая ВС может быть построена путём помещения ФУ в узлы графа алгоритма. При этом согласно приведённому утверждению [7], связывая характеристики

N

алгоритма и ВС, максимальное ускорение S=—, где N - количество операций

т

алгоритма, m - высота параллельной формы, количество процессоров (Р)

определяется шириной параллельной формы min P-q. Построив граф

S—>шах

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

Р

hzini

при реализации заданного алгоритма. Действительно, согласно [7] S = 1--,

шах п-1 <i<P 1

где z,-— загруженность, а щ — производительность функциональных устройств ВС. Тогда, если применяются устройства одинаковой производительности, то

Р

S = ^zt. Ускорение алгоритма определяется в соответствии с законом Амдала Р

S =-, где В - доля последовательных операций.

р.р + (\-р)

Таким образом, поход из [5,7] позволяет проектировать вычислительную систему, наилучшим образом согласованную с рассматриваемым алгоритмом. Вместе с тем не формализована оценка коммуникационных расходов. Автор затрудняется в применении данного подхода для ВС с GPU.

1.1.2 Концепг\ия математических моделей алгоритмов и вычислительных

систем в работах Гергеля В. 77.

Модель ВС, предложенная Гергелем В. П. [11] учитывает современный уровень развития архитектур ВС, когда фактически оборудование и технологии для их построения в значительной степени стандартизированы и используют готовые решения. Например, в качестве стандартизированных элементов кластера могут рассматриваться блейд-серверы с определённым типом системной сети, например, InfiniBand; управляющая вспомогательная сеть, например, Gigabit, Ethernet и так далее. В общем случае, модель ВС включает совокупность вычислительных узлов Ри={рьр2>---рп}5 множество коммутаторов K={ki,k2,...kz}, множество направленных сетевых связей между ними Е. Выделенный узел ро не входит в множество Ри, но связан со всеми вычислительными узлами кластера с помощью выделенной управляющей сети, он обеспечивает работу управляющей системы. В качестве характеристик модели предлагаются следующие величины: пропускная способность каждой сетевой связи в байтах в секунду Ь, функции c(pi),m(pi),d(pl)^(pi), которые для каждого вычислителя pi определяют количество его вычислительных ядер, объёмы оперативной и дисковой памяти, относительную производительность соответственно. Эти величины являются статическими характеристиками вычислителя. Динамическими величинами

являются загруженность его вычислительных ядер u,(t), объём доступной оперативной m,(t) и дисковой памяти d,(t), в момент времени t е[0;+со). При этом

О < щ (0 <1, 0 < т1 (/) < М, , 0 < (0 < Д, где Мь Д - объём оперативной и дисковой памяти вычислителя. Тогда

Ч ЛГе^.

где для р1 узла, имеющего С; вычислительных ядер, Х,={хпХ25- • -50с>} - множество

п

вычислительных ядер (для всех узлов Х = \^)Хг), ¡с1(х,10 - номер задачи,

/=I

исполняемой на ядре % в момент времени т, ,^ - объёмы оперативной и дисковой памяти, необходимой каждому процессу параллельной задачи у. Если ядро х свободно в момент времени то ¡с!(х,0=0- Время передачи сообщения от сетевого устройства п,0 к п,Л'

Т(а,р) = ^ 8 + + //?(# +1), где а(п п) - путь

к=0Ь(п п ) шш,Ь(п п ) 'о !ы

" * 1 к=0,Ы-1

прохождения сообщения, / - среднее время маршрутизации одного пакета, g -размер пакета.

Структура типичного вычислительного 8МР-узла (симметричное мультипроцессирование) представлена на рисунке 1.4. Вычислительные ядра могут относиться как к отдельным процессорам (по одному ядру на каждом), так и к нескольким многоядерным процессорам.

/- г г. - _ ,

I Вычисли 1С.1ын>е 1 Вм'исьлшс.зми*;

1 [ • • • 1

^_Я ф4> 1_| ^ * 1р»> С*

Онер^щйная^ \ Л.4км>'мя ( < сктля | I им я •»« \ § «-л н я г». ! | но. к" нсч см а | |

^ К. „ - у К J }

Ь\1Р->им I *

< «мсвыссос аимсин* с

<!?*>! ИМИ > 11«»МЛ И (И

Рисунок 1.4 - Модель вычислительной системы Данная модель может быть представлена графом вт = (Ри,К.,Е>Ь,с,т,с1,я).

Графовая модель алгоритма является развитием подхода, предложенного [5,7], а новое понятие «расписание» есть не что иное, как программа взаимодействия

устройств модели [5], формализованной с помощью математических символов. На заданной схеме вычислений в расписание Нр = {(¡.р^^.чеУ} предполагает, что в момент времени X. процессор р. начал выполнение /-ой операции[10]. Реализуемость расписания определяется следующими требованиями:

1. Для V/,/бГ: Л =/. =>р.фр,.

I J г I г ] ■>

2. ДляУ(/,./)еД =>/> (1 + !

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

Т

Тоо^Тр^-ч-Тоо, где Тр=1шп(ттТр(0,Нр)), а Тр(С,Н) - время

Р

выполнения параллельного алгоритма, Тос(0)=с1(0) - минимально возможное время выполнения параллельного алгоритма, которое определяется длиной максимального пути графа алгоритма. Анализ эффективности использования

процессоров проводится, исходя из следующей оценки: Ер=—когда

1+1? Г1

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

Список литературы диссертационного исследования кандидат наук Логанова, Лилия Владимировна, 2015 год

Список использованной литературы

1. Антонов, А. С. Параллельное программирование с использованием технологии ОрепМР: учебное пособие. - М.: Изд-во МГУ, 2009. -11 с.

2. Бахвалов, Н. С. Численные методы. - М.: Наука, 1975. - 468 с.

3. Бартеньев О. В. Современный Фортран: Учебник. - М.: Издательство Диалог-МИФИ, 2005. - 390 с.

4. Боресков, А. В. Основы работы с технологией CUDA / А. В. Боресков, А. А. Харламов. - М.: ДМК Пресс, 2010. - 232 с.

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

6. Воеводин, В. В. Отображение проблем вычислительной математики на архитектуру вычислительных систем // Вычислительные методы и программирование. - 2000. - Т.1. - С. 37-44.

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

8. Гатиятуллин, М. 3. Сравнительное исследование эффективности ряда библиотек реализующих алгоритмы решения разреженных СЛАУ на графических процессорах Nvidia / М. 3. Гатиятуллин, А. В. Юлдашев // Вектор науки ТГУ. - 2012. - Т.4 (22). - С. 130-134.

9. Гельфанд, И. М. Метод "прогонки". Дополнение к книге С. К.Годунова, В. С.Рябенького Введение в теорию разностных схем / И. М. Гельфанд, О. В. Локуцневский. - М.: Физматгиз, 1962. - С. 283-309.

10. Гергель, В. П. Теория и практика параллельных вычислений: учебное пособие /В. П. Гергель. - М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. - 423 с.

11. Гергель, В. П. Теоретические основы экспериментального исследования алгоритмов планирования задач для вычислительного кластера с помощью симулятора / В. П. Гергель, П. Н. Полежаев // Вестник ОГУ. - 2010. - Т.9 (115). - С. 115-121.

12. Годунов, С. К. Разностные схемы. Введение в теорию/ С. К. Годунов, В. С. Рябенький. - Изд. 2, перераб. и доп.- М.: Наука, 1977. - 440 с.

13. Головашкин, Д. Л. Параллельные алгоритмы решения сеточных уравнений трёхдиагонального вида, основанного на методе встречных прогонок // Математическое моделирование. - 2005. - Т. 17, № 11 - С. 118128.

14. Головашкин, Д. Л. Исследование параллельных алгоритмов решения трёхдиагональных систем линейных алгебраических уравнений / С. В. Ярмушкин, Д. Л. Головашкин // Вестник Самарского государственного

технического университета. Серия: Физико-математические науки. - 2004. -Т. 26.-С. 78-82.

15. Голуб, Дж. Матричные вычисления / Голуб Дж., Ван Лоун Ч. - М.: Мир, 1999.-548 с.

16. Демель, Дж. Вычислительная линейная алгебра. Теория и приложения / Дж. Демель ; Пер. с англ. - М.: Мнр, 2001. - 430 с.

17. Каган, Б. М. Электронные вычислительные машины и системы. - М.: Энергия, 1979.-528 с.

18. Коновалов, А. II. Введение в вычислительные методы линейной алгебры. -Новосибирск: «Наука»,1993.- 159 с.

19. Корнеев, В. Д. Параллельное программирование в MPI. - Москва-Ижевск: "Институт компьютерных исследований", 2003. - 303 с.

20. Элементы параллельного программирования / В. А. Вальковский, В. Е. Котов, А. Г. Марчук, H. II. Миренков ; Под редакцией В. Е. Котова. - М: Радио и связь, 1983. - 240 с.

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

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

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

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

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

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

27. Логанова, Л. В. Реализация параллельного алгоритма встречных циклических прогонок на гетерогенной вычислительной системе / Л. В. Логанова // Материалы 2-й Всероссийской научно-технической конференции «Суперкомпыотерные технологии». - Ростов-на-Дону: Издательство Южного Федерального Университета, 2012. - С. 140 - 144.

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

29. Логанова, Л. В. Выбор математической модели параллельного алгоритма с учетом особенностей архитектуры суперкомпьютера «Сергей Королёв» / Л. В.Логанова // Перспективные информационные технологии (ПИТ-2014): Труды Международной научно-технической конференции. -Самара, 2014.-С. 335-339.

30. Максимов, Н. В. Архитектура ЭВМ и вычислительных систем: Учебник -3-е изд., перераб. и доп. / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. -М.: Форум, 2010.-512 с.

31. Марчук, Г. И. Проблемы вычислительной техники и фундаментальные исследования / Г. И.Марчук, В. Е.Котов // Автоматика и вычислительная техника. - 1979. - Т.2. - С. 3 -14.

32. Миренков, Н. Н. Реализация продольно-поперечных прогонок на ВС «Минск 222» // Вычислительные системы. - 1968. - № 30. - С. 84- 1.

33. Миренков, Н. II. Параллельные алгоритмы для решения задач на однородных вычислительных системах // Вычислительные системы. -1973. - № 57. - С.3-32.

34. Мэтыоз, Д. Численные методы. Использование МАТЬАВ /Д. Мэтыоз, К. Финк. - М.: Издательский дом «Вильяме», 2001. - 720 с.

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

36. Самарский, А. А. Введение в численные методы. - М.: Наука, 1982. — 287 с.

37. Самарский, А. А. Методы решения сеточных уравнений /А. А. Самарский, Е. С. Николаев. - М.:Наука,1978. - 561 с.

38. Хорошевский, В. Г. Однородные вычислительные системы / Э. В. Евреинов, В. Г. Хорошевский. - Новосибирск: Наука. - 1978. - 319 с.

39. Хорошевский, В. Г. Архитектура вычислительных систем: учебное пособие / В. Г. Хорошевский - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2008. - 520 с.

40. Четверушкин, Б. Н. О возможности реализации квазигидродинамической модели полупроводниковой плазмы на многопроцессорных вычислительных системах / JI. Ю. Бирюкова, Б. Н. Четверушкин // Математическое моделирование. - 1991. - Т.З, № 6. - С. 61-71.

41. Четверушкин, Б. II. Применение многопроцессорных транспьютерных систем для решения задач математической физики / Т. Г. Елизарова, Б. Н. Четверушкин // Математическое моделирование. - 1992. - Т.4, № 11. -С. 75-100.

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

43. Об организации параллельных вычислений и «распараллеливание» прогонки / Н. Н. Яненко, А. Н. Коновалов, А. Н. Бугров, Г. В. Шустов // Численные методы механики сплошной среды. - Новосибирск: ИТПМ СО АН СССР, 1978. - Т. 9. - С. 139-146.

44. Andrew Davidson, Yao Zhang, John D. Owens An Auto-tuned Method for Solving Large Tridiagonal Systems on the GPU. Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium.Washington, 2011, p. 956-965.

45. Foster I. Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading. MA. Addison-Wesley, 1995.

46. Gill S. Parallel programmin. The Computer J, 1958, Vol. 1(1), p. 2 - 10.

47. Ilockney R.W. A fast direct solution of Poisson's equation using Fourier analysis. J. ACM, 1965, Vol.l2(l), p. 95-113.

48.Hockney R.W., Jesshope C. R. Parallel Computers: Architecture, Programming and Algorithms. Bristol: Adam Hilger,1981, 392 p.

49. Hockney R.W. The communication challenge for MPP: Intel Paragon and Meiko CS-2. Parallel Computing, 1994, Vol.20 (3), p. 389 - 398.

50. Stone Harold S. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations. Journal of the Association for Computing Machinery, 1973, Vol.20(l), p. 27-30.

51. Kogge P. M. The Architecture of Pipelined Computers. McGraw Hill, N Y:Hemisphere Press, 1981, 153 р.

52. Paulius Micikevicius NVIDIA. Multi-GPU Programming for Finite Difference Codes on Regular Grids. Stanford AHPCRC/iCME Colloquium Series, January

23, 2012. URL: http:

www.stanford.edu/dept/ICME/docs/seminars/Micikevicius-2012-01 -23 .pdf)

53. Paulius Micikevicius NVIDIA. 3D Finite Diference Computation on GPUs using CUDA. In Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units, NY, 2009, p. 79-84.

54. Povitsky Parallelization of the pipelined Thomas algorithm. ICASE Report No. 98-48. Hampton: NASA Langley Research Center, 1998, 21 p.

55. Sak H., Ozekici I., Boduroglu, S. Parallel Computing in Asian Option Pricing. Parallel Computing, Vol.33(2), 2007, p. 92-108.

56. Sakharnykh N.A. Tridiagonal solvers on the GPU and applications to fluid simulation. GPU Technology Conference (GTC). 2009.

URL: http://www.nvidia.com/content/GTC /documents/1058 GTC09.pdf

57. Stefanski Tomasz Pawel Multi-GPU Accelerated Finitedierence Time-domain Solver in Open Computing Language / Tomasz Pawel Stefanski, Nicolas Chavannes, and Niels Kuster // PIERS Online. - 2011. - Vol. 7(1). - p. 71-74.

58. Zhang Y. Fast Tridiagonal Solvers on the GPU / Y. Zhang, J. Cohen and J. D. Owens // Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2010). - Bangalore. - 2010,

P.127-136.

59. NVIDIA CUDA Reference Manual. - NVIDIA Corporation. - 2010. - Version 3.0.

60. NVIDIA CUDA computer unified device architecture, programming guide. -NVIDIA Corporation. - 2009. - Version 2.0

61. CUDA CUFFT Library. - NVIDIA Corporation. - 2009. - Version 2.2.