Содержание к диссертации
Введение
ГЛАВА 1. Анализ состояния проблемы 9
1.1. Постановка проблемы 10
1.2. Обзор существующих разработок в области исследования 14
1.3. Пути решения 20
ГЛАВА 2. Методы решения задач физико-химической гидродинамики 22
2.1. Расчёт в переменных "Скорость - Давление" 22
2.2. Расчёт в переменных "Вихрь - Функция тока" 26
2.3. Интегрирование динамических уравнений 28
2.4. Методы решения уравнения Пуассона 33
2.5. Методы решения жёстких систем обыкновенных дифференциальных уравнений 52
2.6. Выводы 67
ГЛАВА 3. Оптимизация и распараллеливание вычислительного процесса 69
3.1. Многосеточный подход с функциями перехода на основе полиномов Лагранжа 72
3.2. Создание параллельных схем с использованием MPI 76
3.3. Создание параллельных схем в системе CUDA. Проблемы, пути решения 82
3.4. Создание параллельной схемы для нескольких устройств CUDA 95
3.5. Перспективы, проблемы и подходы к созданию параллельных схем в гетерогенной среде 98
3.6. Сравнение параллельных схем 101
3.7. Выводы 108
ГЛАВА 4. Применение результатов исследования 109
4.1. Моделирование плоского течения 109
4.2. Моделирование распространения воздушных масс в районе над лесным пожаром 114
4.3. Моделирование задачи химической кинетики по газофазному окислению метана 121
4.4. Выводы 124
Основные выводы и результаты 125
Список использованных источников 126
Приложение 1 143
Приложение 2 145
- Обзор существующих разработок в области исследования
- Интегрирование динамических уравнений
- Создание параллельной схемы для нескольких устройств CUDA
- Моделирование задачи химической кинетики по газофазному окислению метана
Введение к работе
Актуальность темы
Применение численных методов становится всё более и более востребованным в связи с увеличивающейся трудоёмкостью проведения натурных экспериментов и сложностью получения детальной информации о течениях и химических процессах, происходящих в них, например: при исследовании химических лазеров, моделировании процессов, происходящих при пожаре, изучении распространения загрязнений.
Использование высокопроизводительных вычислительных систем принципиально изменило возможности теоретического анализа сложных процессов. Стало доступным оперативно анализировать сложные модели с большим объёмом данных. При этом точность моделирования определяется математической моделью и точностью необходимых данных, учитывающих физические условия проведения процесса. В настоящее время в большинстве исследований перед проведением натурного эксперимента проводится его математическое моделирование для определения наиболее оптимальных параметров. Этим достигается экономия сил, средств и времени. Другой несомненный плюс от использования вычислительных экспериментов заключается в возможности проведения испытаний в критических условиях или в тех областях параметров, где нельзя провести реальные эксперименты на имеющемся оборудовании.
Моделирование течений, осложнённых химическими процессами, является сложной математической и вычислительной задачей.
В большинстве случаев уравнения Навье - Стокса, описывающие поведение течения вязкой несжимаемой жидкости, аппроксимируются различными сеточными методами. Основным требованием, предъявляемым к таким методам, является обеспечение высокой точности получаемых результатов при минимально необходимых вычислительных затратах (времени, объёме памяти).
При решении уравнений Навье - Стокса требуется многократно использовать уравнение Пуассона. Оно является вычислительно сложным и составляет основную вычислительную нагрузку.
Моделирование активно реагирующей среды требует надёжного метода решения жёстких дифференциальных уравнений. В качестве такого метода может выступать метод Гира на основе формул дифференцирования назад (ФДН). Его преимуществом по сравнению с многошаговыми методами является возможность использования стратегий с переменным шагом интегрирования и простое построение параллельной схемы.
К настоящему времени существует множество работ по моделированию как обычных течений, так и осложнённых различными физико-химическими реакциями.
Основы методов моделирования были заложены в работах С.К. Годунова, Н.Н. Калиткина, А.А. Самарского, Р.П. Федоренко, Г.И. Марчука, Л.Г. Лойцян-ского, Н.Н. Яненко, Р. Хокни, Дж. Бетчелора, Г. Биркгофа, Д. Андерсона.
Значительный вклад в моделирование турбулентных течений внесли А.Дж. Рейнольде, В.М. Ковеня, В.А. Перминов, A.M. Гришин, С.А. Лосев, А.Е. Алоян, П.Г. Фрик, Б. Сполдинг, С. Патанкар.
Проблемы интегрирования уравнений химической кинетики описываются в работах У. Гира, Л.С. Полака, Э. Хайрера.
В сфере научных вычислений всё большую популярность набирают вычисления с использованием графических ускорителей. Современные видеоакселераторы представляют собой массивно-параллельные процессоры с общей памятью. В отличие от центрального процессора с несколькими ядрами, один графический процессор содержит от нескольких десятков до одной тысячи ядер, которые могут проводить вычисления параллельно. Наиболее развитой на данный момент технологией является система CUDA (Compute Unified Device Architecture), предложенная компанией NVidia в 2007 году.
Использование кластерных систем с системой параллельного программирования MPI (Message Passing Interface) и графических ускорителей для решения описанных задач приводится в работах В.Э. Витковского, Н.А. Сахарных, Дж. Коуэна (J.Cohen), Я. Джао (Y. Zhao), Т. Брандвика (Т. Brandvik).
Таким образом, тема диссертации является актуальной, так как она посвящена разработке в системе CUDA быстрых параллельных алгоритмов решения сеточных уравнений (Навье - Стокса, Пуассона) и химической кинетики, получаемых при решении задач моделирования течений с протекающими в них реакциями множества веществ.
Цель работы
Целью работы является разработка усовершенствованных методов моделирования течений, осложнённых химическими превращениями, с использованием графических процессоров, позволяющих значительно повысить скорость вычислений, эффективно использовать ресурсы гетерогенного суперкомпьютера с несколькими графическими ускорителями, а также разработка комплекса программ для решения класса таких задач.
Задачи исследования
Поставлены следующие задачи исследования:
Исследовать существующие способы решения уравнений Навье -Стокса, Пуассона, химической кинетики, массообмена.
Разработать и реализовать общий алгоритм решения задачи расчёта течения жидкости или газа, осложнённого химическими реакциями на основе методов вычислительной гидродинамики и химической кинетики.
Разработать методику оптимизации вычислительного процесса, позволяющую значительно сократить затраты машинного времени и повысить точность решения данной задачи за счёт использования многосеточных методов с функциями перехода на основе интерполяционных полиномов Лагранжа.
Разработать стратегию распараллеливания для решения поставленной задачи с учётом предложенной методики оптимизации на гетерогенном супер-
компьютере с несколькими графическими ускорителями, позволяющую значительно уменьшить время решения задачи.
5. Использовать разработанные методы для решения ряда задач: модельное плоское ламинарное движение, расчёт поведения воздушных масс в районе над лесным пожаром, окислительные превращения метана.
Методы исследования
Для решения поставленных задач используются методы гидродинамики, химической кинетики, решения систем жёстких дифференциальных уравнений, вычислительной математики, теории распараллеливания вычислений, теории алгоритмов, теории разностных схем.
Научная новизна
Разработаны новые параллельные вычислительные алгоритмы методов решения уравнений Навье - Стокса и Пуассона для системы CUDA.
Разработана новая параллельная реализация метода Гира для системы CUDA.
Предложен и разработан способ интерполяции многосеточного метода на основе полиномов Лагранжа для системы CUDA.
Разработано новое алгоритмическое и программное обеспечение, позволяющее моделировать течения, осложнённые химическими превращениями, с использованием суперкомпьютера с несколькими графическими ускорителя-mhCUDA.
Практическая ценность работы
В результате исследования разработан программный комплекс, позволяющий моделировать движение среды, осложнённой химическими превращениями.
Он может работать с любым количеством графических ускорителей, имеющихся в кластерной системе, оптимальным образом распределяя объём вычислений между ними, позволяет повысить скорость и точность вычислений.
Разработанные программы могут быть использованы для быстрого решения ряда практически значимых задач. Например, моделирование распространения воздушных масс при пожарах, воздействие лазерного излучения на вещество, получение новых топлив из продуктов окисления алканов. Ценность комплекса в том, что решения можно получать оперативно, в режиме реального времени для больших объёмов данных.
Реализация и внедрение результатов работы
Предложенные параллельные схемы и алгоритмы были внедрены в процесс выполнения комплексного проекта по созданию высокотехнологичного производства "Разработка программно-технического комплекса обнаружения и прогнозирования крупномасштабных природных пожаров" (2010-218-02-139)
при поддержке Министерства образования и науки РФ (ГК № 13.G25.31.0077) сотрудниками ГОУВПО "Ивановский институт ГПС МЧС России".
Составные части представленного программного комплекса зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.
Апробация работы
Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: межвузовская научно-техническая конференция аспирантов и студентов "Молодые учёные - развитию текстильной и лёгкой промышленности" (ПОИСК-2009) (Иваново, 2009); IX международная конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (Владимир, 2009); X международная научно-практическая конференция "Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности" (Санкт-Петербург, 2010); X международная конференция "Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010) (Пермь, 2010); V международная научно-практическая конференция "Пожарная и аварийная безопасность" (Иваново, 2010); межвузовская научно-техническая конференция аспирантов и студентов "Молодые учёные - развитию текстильной и лёгкой промышленности" (ПОИСК-2011) (Иваново, 2011); семинар "Физико-химическая кинетика в газовой динамике" НИИ механики МГУ (Москва, 6 октября 2011 года).
Публикации
По теме диссертации опубликовано 14 работ, среди которых 4 публикации в ведущих рецензируемых изданиях, рекомендованных в действующем перечне ВАК, 6 публикаций в трудах и материалах конференций, 2 монографии, 2 свидетельства о государственной регистрации программы для ЭВМ.
Личный вклад автора
Основные научные и практические результаты диссертации получены автором лично. В работе [1] автору принадлежит методика численного моделирования задачи динамики вязкой несжимаемой жидкости на графических ускорителях с системой CUDA. В [2, 6] автором предложен способ организации вычислений указанной выше задачи на системе с несколькими графическими ускорителями. В работе [3] автором описывается способ решения задачи моделирования течения, осложнённого физико-химическими преобразованиями в системе параллельного программирования CUDA. В работах [4, 5, 10, 11] автором рассматриваются и сравниваются различные способы решения уравнения Пуассона как в однопроцессорном варианте, так и в многопроцессорном. В работах [8, 9] автором предлагается методика организации вычислительного процесса на гетерогенном суперкомпьютере для задач моделирования течения среды, с проходящими в ней физико-химическими процессами. В монографии [12] автором описывается способ решения жёстких задач химической кинетики с
использованием метода Гира. Автор принимал участие в подготовке и представлении докладов на конференциях.
Структура и объём работы
Работа состоит из введения, 4-х глав, заключения и списка цитируемой литературы из 145 наименований. Полный объем диссертации составляет 198 страниц, включая 37 рисунков, 5 таблиц и 2 приложения. Каждая глава разбита на параграфы.
Обзор существующих разработок в области исследования
К настоящему времени проведено множество исследований и работ в области моделирования гидродинамических процессов. Как отмечается, основную трудность при создании математической модели и алгоритма решения задачи состоит в нахождении неизвестного поля давления. Существуют несколько подходов для его нахождения. Кроме того, применяются разные подходы и к интегрированию самих уравнений Навье - Стокса и уравнения Пуассона. Ещё одним важным моментом организации численного решения является тип используемой сетки расчётной области [62; 81].
Одним из подходов к решению уравнения Навье - Стокса является предложенный С. Патанкаром и Б. Сполдингом метод SIMPLE (Semi-Implicit Method for Pressure-Linked Equations), что означает полунеявный метод для связывающих давление уравнений [63; 64; 99; 113]. В этом методе вычисления проводятся в несколько шагов: 1. Задание приближённого поля давления Р . 2. Решение уравнений движения для получения приближённых U , V , W . 3. Решение уравнения для получения поля коррекции давления Р. 4. Расчёт Р из уравнения путём добавления Р к Р . 5. Расчёт U, V, W с учётом соответствующих значений со звёздочкой и с помощью формул для поправки скорости. 6. Решение дискретных аналогов для других полей (таких, как температура, концентрация и турбулентные характеристики), если они влияют на поле течения через физические свойства жидкости, источниковые члены и т. д. (если какое-то определённое поле не влияет на поле течения, лучше рассчитать его после получения сходимости решения для поля течения). 7. Представление скорректированного давления Р как нового Р , воз вращение к пункту 2 и повторение всей процедуры до тех пор, пока не будет получено сходящееся решение. Данный метод обладает высокой точностью решения, но в тоже время зависит от вида функции, корректирующей давление Р. Впоследствии были разработаны методы, расширяющие или улучшающие исходный алгоритм, например, SIMPLER [63], разработанный Патанкаром с новым способом поправки давления, SIMPLEC, SIMPLEX, SIMPLEM, SIMPLEST .
А.Н. Есаулов и А.В. Старченко предложили маршевый метод решения уравнения Навье - Стокса [44]. В этом методе на конечно-разностном уровне проведено исключение сеточной функции давления. Суть метода заключается в последовательном расчёте по столбцам значений сеточной функции скорости U во всей расчётной области (значения переменных из соседних столбцов берутся из текущей или предыдущей итерации). Таким образом, расчёт горизонтальной компоненты скорости U из СЛАУ, заменяется схемой, дающей приближение к точному решению этих сеточных уравнений. Подобная замена замедляет сходимость алгоритма в целом, но упрощает его программную реализацию и требования к вычислительным ресурсам, поскольку в нём не требуется вычислять уравнение Пуассона. Однако данный метод при больших размерностях разностной задачи в общем случае требует разработки специальных методов решения. Одним из способов нахождения поля давления является метод слабой сжимаемости [9; 27; 73; 96]. Он основывается на допущении слабой сжимаемости среды при малых скоростях. В этом методе в систему уравнений добавляется уравнение для поправки плотности среды и нахождения давления на его основе. В этом случае также исключается интегрирование уравнения Пуассона из общего алгоритма решения задачи, что позволяет ускорить вычисления. Однако у данного метода есть недостаток в том, что при постепенном накоплении машинной погрешности происходит "раскачивание" поля давления, поэтому необходимо либо останавливать вычисления не дожидаясь полной стабилизации процессов, либо применять особые методы стабилизации вычислений.
В.М. Ковеня предложена экономичная разностная схема второго порядка аппроксимации [49; 50]. При построении схемы введено специальное расщепление операторов по физическим процессам, что позволило свести решение системы уравнений к решению отдельных уравнений скалярными прогонками по одному из направлений с введением итераций. Данные алгоритм предлагается применять на многопроцессорных вычислительных машинах.
Из нестандартных подходов можно отметить использование сетей радиальных базисных функций [121]. В данных сетях используется скрытый слой нейронов с радиальной функцией, которая зависит от расстояния до входного вектора. Автором предлагаются радиальные функции, связанные с расчётом движения среды. Однако данный подход всё же является в большей степени приближённым, оценочным. Он не предполагает точного моделирования физической среды, а лишь делает предположение о её состоянии.
Кроме того, многими исследователями используется подход к решению уравнений Навье - Стокса на основе схемы второго порядка точности метода МакКормака [136]. Этот метод обладает достаточно высокой точностью, устойчивостью, простой параллельной реализацией. Этот метод относится к классу "предиктор-корректор".
Качественно иной подход можно отметить у М. Квадрио (М. Quadrio) [130]. В своей работе он предлагает эффективный параллельный алгоритм ре 17 шения уравнения Навье - Стокса с использованием БПФ, с переводом решения из обычного в Фурье-пространство.
В настоящее время в мире проводится множество исследований в области гидродинамики с применением графических ускорителей. Однако часто исследователи концентрируются на какой-либо одной проблеме, например, турбулентности, визуализации, взаимодействии с другими телами, области сложной формы и т.д. При этом практически все эти работы [109; 133] используют достаточно примитивный, но в тоже время легко параллелизуемый метод Гаусса-Зейделя с шахматным порядком вычисления [133], либо метод простых итераций [140]. Такое ограниченное использование методов может приводить к погрешностям в решении. К тому же даже эффективная параллельная схема не может скомпенсировать медленную сходимость метода.
Однако часть исследователей [109-111; 125] используют многосеточные методы решения уравнения Пуассона. В качестве оператора сглаживания выступает метод верхней релаксации. Степень упрощения сетки обычно небольшая (2 шага), к тому же используются линейные операторы перехода между сетками. Алгоритм расчёта течения, предлагаемый авторами, использует некоторые искусственные ограничения на количество итераций, на степень сходимости, направленные на упрощение и ускорение вычислений, поскольку цель авторов - визуализация движения воздуха и частиц в режиме реального времени.
Другим примером исследования, связанного с созданием реалистичного киноизображения, является работа Д. Байли (D. Bailey) [101] по оптимизации работы с графическим ускорителем. Автором приводятся различные подходы к оптимизации доступа к памяти, разделения ресурсов, загрузки вычислительных ядер при интегрировании уравнений Пуассона и Навье - Стокса.
Интегрирование динамических уравнений
Из результатов экспериментов можно сделать вывод о том, что, как и предполагалось, прямой метод FACR является наиболее эффективным и экономичным. Его алгоритм не зависит от требуемой точности, а фактическая точность решения, как указывает Р. Хокни [93], находится в зависимости от точности представления вещественных чисел и от точности выполнения арифметических операций над ними в используемой машине и может составлять в самом лучшем случае 10 12-10"14. Незначительное различие во времени на выполнение операций при разной точности можно объяснить тем, что программа работала в многозадачной среде. Однако необходимо помнить и учитывать ограничения в применении данного метода, которые упоминались при его описании.
Особо следует отметить тот факт, что при требуемой точности решения в 10"3 использование методов верхней релаксации и Ричардсона не выгодно. При проведении численных экспериментов выяснилось, что, хотя и не происходит расхождение в решении, вычисления приходят к неверному решению, что показывает большую погрешность, вносимую данными методами.
Как видно из диаграммы (рис. 2), метод верхней релаксации является наименее эффективным. Простота реализации данного метода ни коим образом не компенсирует те чрезвычайно высокие затраты машинного времени и количество арифметических действий, требуемые для достижения необходимой точности решения, особенно по сравнению с другими методами.
Метод Ричардсона показал среднюю эффективность. Этот метод достаточно несложен в программировании. При использовании чебышевских итерационных параметров метод достаточно устойчив. Поэтому его можно использовать в тех задачах, где заранее известно, что размер сетки, наложенной на решаемую область, будет не очень высокого порядка (до 256) и требуется не очень высокая точность вычислений (до 10"9). Кроме того, этот метод можно использовать в качестве оператора сглаживания в многосеточном методе [27; 82].
В результате эксперимента выявлены высокие (и сравнимые) показатели скорости работы методов Дугласа - Писмана - Рекфорда и попеременно-треугольного. Даже при большой требуемой точности решения эти методы показали очень высокую производительность и быструю сходимость, которые можно соотнести только с прямым методом FACR. Метод Дугласа - Писмана -Рекфорда сходится несколько быстрее, чем попеременно-треугольный, но следует помнить, что он требует большего количества операций сложения и умножения на каждый узел. В то же время попеременно-треугольный метод легко может быть расширен на любое число измерений, а также на дифференциальные уравнения с переменными или разрывными коэффициентами и области сложной формы. Поэтому, если известно, что в решаемой задаче не будет вышеупомянутых изменений, то более предпочтительным по эффективности, т.е. по соотношению вычислительных затрат для достижения требуемой точности, является метод Дугласа - Писмана - Рекфорда.
Не менее интересным представляется сравнение результатов масштабируемости методов, т.е. проведение экспериментов с одинаковой заданной точностью, но на сетках разного размера. Так, испытания проводились с требуемой точностью решения 10" последовательно для двумерных квадратных сеток с количеством интервалов 32, 64, 128, 256, 512 и 1024. Для наглядности результаты приведены в виде графиков по всем методам на рис. 3.
Из графиков видно, что время выполнения почти всех методов увеличивается экспоненциально с увеличением размера расчётной сетки. Иную тенденцию показал метод верхней релаксации. Время его выполнения растёт гораздо быстрее по сравнению с другими методами.
По приведённым данным можно сделать вывод, что сложность вычислений в большинстве методов строго зависит от размерности решаемой задачи и соответственно имеется возможность строить предположения о времени выполнения вычислений на больших сетках, проведя предварительно испытания на сетках меньшей размерности. 2.5. Методы решения жёстких систем обыкновенных дифференциальных уравнений
Множество задач имитационного моделирования, химической кинетики и других областей наук требуют решения систем обыкновенных дифференциальных уравнений. Напомним, что обыкновенное дифференциальное уравнение (ОДУ) - это уравнение, содержащее функцию и её производные. В общем виде ОДУ записывается следующим образом [48; 90; 91]: Решением ОДУ (99) будет функция y(t), представляющая собой семейство решений при различных начальных условиях. В более общей ситуации имеется п неизвестных функций у,(t), і =l,...,n, для которых задано п дифференциальных уравнений и начальных условий, которые записываются в векторном виде как: Это векторное уравнение полностью описывают постановку задачи Коши для системы уравнений. Большинство алгоритмов рассчитаны на решение одного дифференциального уравнения, но в основном все они легко переносятся на случай системы. Трудно точно сказать, что такое жёсткая система ОДУ, т.к. не существует универсального определения подобной системы. Обычно жёсткие задачи описывают как задачи, моделирующие физический процесс, в котором присутствуют компоненты с несоизмеримыми временными характеристиками, т.е. когда в системе присутствуют как быстро меняющиеся, так и медленно текущие процессы. В математическом смысле это выражается в наличии малого параметра а при ряде производных [90; 122]: at где x - медленный процесс; а. у - быстрый. К сожалению, обычно невозможно явно выделить малый параметр а из уравнений. Подобные процессы наиболее часто встречаются в задачах химической кинетики, когда в реакции участвуют и активные частицы (например, ионы), и стабильные молекулы. Например, при моделировании химических реакций, процесса горения, взрывов, окисления.
Создание параллельной схемы для нескольких устройств CUDA
На рис. 8 сплошными линиями показаны вычисления коэффициентов прямой прогонки, а штриховыми линиями - вычисления значений обратной прогонки. Такой приём позволяет эффективно распараллелить прогонку по столбцам в случае, когда решаемая область распределена между процессорами по строкам.
Как и метод Ричардсона, метод FACR также легко подвергается распараллеливанию. В нем используется геометрический и конвейерный виды параллелизма. Два из трёх этапов решения, а именно вычисление БПФ по строкам матрицы, могут выполняться абсолютно независимо и параллельно. К тому же не требуется никаких передач ни до, ни после вычислений, т.к. каждый процессор хранит все необходимые данные. Единственное, что требует особого внимания, - это распараллеливание прогонки по столбцам на промежуточном (2-м) этапе вычислений, осуществляемое так же, как и в методе Дугласа - Писмена -Рекфорда.
К сожалению, эффективного способа распараллеливания попеременно-треугольного метода не удалось найти, т.к. не всегда можно построить параллельную схему для какого-либо последовательного алгоритма без его перестройки или изменения. В случае с попеременно-треугольным методом распараллеливание невозможно, поскольку невозможно разделить вычисления на одной итерации на отдельные независимые части, т.к. каждый этап вычислений зависит от предыдущего этапа и должен проводиться в строго определённом порядке. Конечно, в таких случаях можно применять подходы, в которых происходит асинхронное вычисление. В этом случае каждый этап вычислений искусственно делается независимым от предыдущих этапов, а зависит только от предыдущего временного слоя. При этом либо в конце каждой итерации по времени, либо по окончании нескольких итераций необходимо синхронизировать асинхронные значения. Однако данный подход вносит дополнительную погрешность, что снижает достижимую точность решения и сходимость метода. Кроме того, это усложняет реализацию метода. Поэтому мы не стали применять данный подход для построения параллельной схемы, ограничившись лишь другими методами.
Как уже отмечалось ранее, трёхдиагональные системы легко решаются с помощью метода прогонки [23; 87; 88]. Способ вычисления трёхдиагональных систем был подробно представлен выше при описании параллельной схемы метода Дугласа - Писмена - Рекфорда.
При интегрировании уравнений химической кинетики факторами, определяющими скорость вычислений, являются векторные и матричные операции, поскольку каждый этап алгоритма метода Гира в той или иной степени использует эти операции с векторами получаемого решения, векторами Нордсика, погрешности, поправки и т.д. При этом размерность вектора соответствует числу веществ. Поэтому основной упор в построении параллельной схемы для метода Гира делается на распараллеливание векторных операций, поскольку основная часть алгоритма имеет ветвистую структуру и частую проверку условий, что усложняет её перенос на параллельную архитектуру.
В этом случае оптимальным является разделение векторных данных и операций равномерно по всем процессорам, когда каждый из них имеет свою локальную часть общего массива данных, а общий ход алгоритма управляется одним выделенным процессором. Векторные операции можно разделить на два типа: такие, в результате которых получается новый вектор, и такие, в результате которых получается некоторый скаляр. Практически все операции над век 82 торами из первой группы могут быть выполнены каждым процессором локально, в результате чего получается новая локальная часть некоторого вектора. Для второй группы характерно проведение некоторой глобальной операции над всем массивом данных, однако при этом каждый процессор может выполнить её над своей частью данных, а общий результат получается применением операции редуцирования над этими частичными результатами. При этом каждый процессор получит значение глобального результата и сможет его использовать для своих дальнейших действий (см. рис. 9) [15; 79].
В настоящее время любой графический ускоритель реализует потоковую вычислительную модель (stream computing model) - есть потоки входных и выходных данных, состоящие из одинаковых элементов, которые могут быть обработаны независимо друг от друга. Обработка элементов осуществляется ядром (kernel) (см. рис. 10) [14; 126; 134]. где Р - время выполнения параллельной программы на N ядрах, позволяет достичь высокого ускорения при условии, что существенная часть вычислительного процесса будет выполняться на устройстве CUDA, максимально и эффективно используя его ресурсы. Кроме того, необходимо учитывать накладные расходы на работу с памятью, поскольку в некоторых случаях это может стать узким местом алгоритма. Именно поэтому крайне важно создавать хорошо распараллеленные алгоритмы, эффективно использующие все виды доступа к памяти, представляемые системой CUDA.
Модель выполнения CUDA оперирует понятиями сетка, блок и поток. Верхний уровень - сетка (grid) - соответствует ядру и объединяет все нити, выполняющие данное ядро. Сетка представляет собой одномерный или двухмерный массив блоков (block). Каждый блок (block) представляет собой одно/двух/трёхмерный массив нитей (threads). При этом нити из разных блоков не могут между собой взаимодействовать (см. рис. 11). Но в тоже время нити внутри одного блока могут взаимодействовать между собой через общую память {shared memory) и функцию синхронизации всех нитей блока {synchronize). Подобная иерархия довольно естественна - это оптимальный компромисс между управляемостью и стоимостью реализации.
Моделирование задачи химической кинетики по газофазному окислению метана
Изучение процесса окисления метана представляет собой важную практическую задачу для оптимизации технологических процессов и КПД газовых электростанций, получения жидкого топлива, для совершенствования методов химической промышленности. Существует несколько теорий и моделей, описывающих наблюдаемые явления и закономерности окисления метана. Была рассмотрена модель, предложенная в [7] и представленная в табл.5.
Как можно заметить, приведённая модель достаточно подробна. В ней присутствует 23 вещества, участвующих в 61 реакции. Таким образом, моделирование проводилось с использованием достаточно подробной модели окисления метана. Полученные результаты соответствуют результатам, полученным другими исследователями [6; 7; 19-22; 114; 124]. Пример изменения концентраций веществ в зависимости от времени приведён на рис. 37.
Ускорение получается в 4 раза при использовании одного CUDA устройства. Выигрыш не настолько значителен, как при сравнении векторных операций, но это объясняется прежде всего тем, что число задействованных веществ и реакций было не достаточно велико и не позволило полностью раскрыть потенциал системы CUDA. Требуются более сложные и подробные модели.
Разработанная программа является универсальной и может проводить интегрирование задач любой сложности. При этом её эффективность по сравнению с последовательным вариантом будет тем выше, чем более сложной является задача. Изучение окисления алканов является практически значимой задачей для химической и топливной промышленности [2; 7]. В тоже время эта задача является трудоёмкой, требующей как экспериментального, так и имитационного исследования. Предлагаемая программа позволяет сократить временные затраты на исследование различных вариантов поведения системы, различных ветвей развития химических реакций в зависимости от присутствующих катализаторов и условий протекания реакций.
В данной главе были рассмотрены возможные способы применения разработанных ускоренных методов решения уравнений гидродинамики и химической кинетики. Было показано достигаемое в каждом случае ускорение по сравнению с традиционными системами. Кроме того, результаты, полученные в данных примерах, соответствуют экспериментальным данным, полученным другими исследователями и позволяют говорить о том, что разработанные алгоритмы не вносят дополнительной погрешности в процессе вычислений. 1. Подробно исследовано уравнение Пуассона и различные методы его численного решения. Произведено сравнение методов друг с другом. Рассмотрены параллельные варианты на предмет быстроты и точности в системах MPI и CUDA. (Получено свидетельство о государственной регистрации программы.) 2. Разработаны и реализованы усовершенствованные алгоритмы решения задачи гидродинамики в переменных "Скорость - Давление" и "Вихрь -Функция тока". Предложены как двумерные, так и трёхмерные варианты. 3. Предложена методика оптимизации вычислительного процесса с использованием многосеточного подхода с функциями перехода между сетками на основе интерполяционных полиномов Лагранжа. 4. Подробно исследован метод Гира и предложена его параллельная реализация в системе CUDA, которая позволяет проводить моделирование десятков тысяч химических реакций с высокой скоростью. Достигаемое ускорение составляет более 5 раз по сравнению с традиционными системами. 5. Построен программный комплекс для решения гидродинамических задач с физико-химическими превращениями, сочетающий в себе решение уравнений Навье - Стокса, Пуассона, диффузии, химической кинетики в системе параллельного программирования CUDA. (Получено свидетельство о государственной регистрации программы.) 6. Показано применение разработанных алгоритмов для изучения течений, сопровождающихся большим количеством химических реакций. Доказана возможность применения ускоренных алгоритмов на графических ускорителях. Достигаемое ускорение по сравнению с обычными системами составляет более 20 раз. Это позволяет быстрее получать новые результаты, рассматривать больше различных вариантов, условий протекания процессов. Кроме того, становится возможным получение результатов в режиме реального времени.
