Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Воротникова Дарья Геннадьевна

Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации
<
Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Воротникова Дарья Геннадьевна. Метод численного решения явных сеточных уравнений на графических процессорах и комплексы программ для его реализации: диссертация ... кандидата Технических наук: 05.13.18 / Воротникова Дарья Геннадьевна;[Место защиты: «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)»].- Самара, 2016.- 121 с.

Содержание к диссертации

Введение

1 Организация вычислений по явным разностным схемам на векторных процессорах 13

1.1 Явные разностные схемы 13

1.1.1 Разностная схема для решения уравнения теплопроводности 14

1.1.2 Разностная схема для решения уравнений Максвелла 15

1.2 Обзор векторных алгоритмов решения сеточных уравнений 19

1.2.1 SIMD-вычисления и их аппаратные реализации 19

1.2.1.1 Классификация Флинна 19

1.2.1.2 Аппаратная реализация SIMD 20

1.2.1.3 Программная и архитектурная модели CUDA

1.2.2 Реализация FDTD-метода на суперкомпьютере серии CRAY 25

1.2.3 Реализация FDTD-метода при помощи технологии SSE 28

1.2.4 CUDA-реализации FDTD-метода 32

1.2.5 CUDA-реализации разностного решения уравнения теплопроводности 35

1.3 Способы записи и модели параллельных алгоритмов 37

1.3.1 Классификация Яна Фостера 38

1.3.2 Нотация Джеймса Ортеги для векторных алгоритмов 39

1.3.3 Нотация Джина Голуба для векторных алгоритмов 40

1.3.4 Нотация А.А. Валькаре 41

1.4 Использование временной сети Петри для моделирования вычислений по векторным алгоритмам 42

1.4.1 Актуальность задачи 42

1.4.2 Модель на основе временной сети Петри для алгоритма с короткими векторами 44

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

2 Векторные алгоритмы разностного решения уравнения теплопроводности 50

2.1 Алгоритмы с короткими векторами 51

2.1.1 Описание алгоритмов 52

2.1.2 Аппаратное и программное обеспечение 53

2.1.3 Постановка вычислительных экспериментов 57

2.2 Алгоритм с длинными векторами на основе операции gaxpy 61

2.2.1 Описание алгоритма 62

2.2.2 Постановка вычислительных экспериментов 66

2.3 Алгоритм с длинными векторами, основанный на повторном использовании попарных сумм 69

2.3.1 Описание алгоритма 70

2.3.2 Постановка вычислительных экспериментов 74

2.3.3 Моделирование вычислений 77

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

3 Векторные алгоритмы разностного решения уравнений Максвелла 84

3.1 Алгоритм с длинными векторами на основе операции gaxpy 85

3.1.1 Описание алгоритма 85

3.1.2 Постановка экспериментов 90

3.2 Алгоритм с длинными векторами для уравнения Даламбера, основанный на повторном использовании попарных сумм 95

3.2.1 Разностная схема для уравнения Даламбера 96

3.2.2 Описание алгоритма 97

3.2.3 Постановка вычислительных экспериментов

3.3 Рекомендации по использованию векторного метода 104

3.4 Внедрение 108

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

Заключение 111

Список литературы

Введение к работе

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

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

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

Недавнее внедрение (в течении последних десяти лет) в широкую вычислительную практику векторных процессоров (типа SIMD по классификации Флинна), представленных графическими процессорами (GPU, подтип SIMT), обусловило актуальность разработки специализированных векторных алгоритмов для них. К сожалению, расчеты по неявным схемам, сопряженные с необходимостью решать системы линейных алгебраических уравнений (СЛАУ) с матрицами ленточного вида, векторизуются весьма сложно. Джин Голуб в фундаментальной монографии «Матричные вычисления» указывал на невозможность векторизации прямых методов решения таких систем для случая узкой ленты. Векторные алгоритмы для итерационных методов (работа Дж. Ортеги «Введение в параллельные и векторные методы решения линейных систем») также не нашли широкого применения и хотя работы в этом направлении ведутся, говорить об их окончании преждевременно.

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

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

Выбор шагов дискретизации сеточной области традиционно принято производить из математических (выполнение условия устойчивости) и физических (достижение необходимой точности разностного решения) соображений. Полнота использования возможностей вычислительного комплекса, определяющаяся архитектурой видеопроцессора с одной стороны и характеристиками (в том числе и дискретизацией) векторного алгоритма с другой, также может быть принята за критерий выбора. Кроме того, подбор аппаратного обеспечения для многократного решения разностных уравнений на сеточной области с уже определенными параметрами дискретизации (если физические соображения выбора шагов оказались доминирующими), также является важной задачей при планировании вычислительных экспериментов. Например, нет нужды в финансовых тратах на последнюю видеокарту серии Tesla, если расчет за приемлемое время обеспечит несколько устаревшая видеокарта ряда GeForce. Решение обоих проблем: выбора шагов при условии достижения максимальной производительности карты или подбор видеопроцессора при условии фиксированной сеточной области, желательно производить с помощью математического моделирования, предварительно оценивая длительность вычислений по разным алгоритмам на разных аппаратных базах. Это избавит как от затрат времени на подбор шагов дискретизации в первом случае, так и от финансовых издержек при выборе видеокарты, во втором. Следовательно, проведение упомянутого моделирования также представляется актуальной задачей.

Наконец, сложно найти доказательства актуальности разработанных алгоритмов более веские, чем в ходе сравнения их реализаций с уже существующими программными пакетами. Это соображение в купе с наличием изрядного количества упомянутых пакетов (OpenCurrent, B-CALM и др.), появившихся в последнее время, свидетельствует об актуальности задачи разработки программных комплексов для реализации векторных методов решения сеточных уравнений явных разностных схем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическую значимость имеют два разработанных программных комплекса, обеспечивающих ускорение вычислений по сравнению с пакетом OpenCurrent компании Nvidia (при разностном решении уравнения теплопроводности) и пакетом B-CALM Калифорнийского технологического института (при разностном решении уравнений Максвелла).

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

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

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

  1. Аналогичный предыдущему алгоритм для разностного решения уравнения Даламбера.

  2. Векторный алгоритм разностного решения уравнений Максвелла, реализующий операции gaxpy с матрицами ленточного вида.

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

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

7. Программные комплексы, реализующие различные векторные алгорит
мы решения сеточных уравнений явных разностных схем для задач теплопро
водности и электродинамики.

Степень достоверности и апробация работы.

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

векторных алгоритмов, а также сравнением с существующими программными реализациями (OpenCurrent и B-CALM).

Результаты, полученные в диссертации, представлялись на Sino-Russia Bilateral Scientific Seminar on Diffractive Optics and Nano-Photonics (2012, Shanghai, China), 13th International Conference on Computational and Mathematical Methods in Science and Engineering (2013, Almeria, Spain), 14th International Conference on Mathematical Methods in Science and Engineering (2014, Cdiz, Spain), Национальный Суперкомпьютерный Форум (2014, Переславль-Залесский, РФ), 15th International Conference on Mathematical Methods in Science and Engineering (2015, Cdiz, Spain), Международной конференции "Информационные технологии и нанотехнологии" (2015, Самара, РФ), а так же на совместных семинарах кафедры «Техническая кибернетика» и ИСОИРАН.

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

Диссертационная работа выполнена в рамках работ по грантам РФФИ: 14-07-31178 мол_а “Разработка методов решения обратных задач дифракционной нанофотоники на гетерогенных вычислительных системах с графическими процессорами” (автор диссертации – руководитель работ), 14-01-31305 мол_а “Анализ возбуждения и распространения мод лазерного излучения в оптическом волокне” (исполнитель) и 14-07-00291 а “Разработка параллельных приложений для расчета оптических компонент телекоммуникационных систем на гетерогенных вычислительных комплексах с графическими процессорами” (исполнитель).

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

Структура и объём работы. Диссертация состоит из введения, трёх глав и заключения. Объём диссертации – 121 страница. Диссертация содержит 16 таблиц, 35 рисунков и список литературы из 103 наименований.

Разностная схема для решения уравнений Максвелла

Аппаратная реализация SIMD Хронологический обзор векторных вычислительных систем и технологий, основанных на модели SIMD, начнем с компьютера ILLIAC IV [40] (1966 - 1971 г) - первого векторного процессора, состоящего из 64 64-битных исполнительных устройств с общей памятью. За ним следовал знаменитый Cray-1 [61] (1975 г.) -первый матричный процессор, содержащий функциональные модули, объединенные в 12 параллельно работающих узлов. Каждый узел управляется одним устройством управления с варьирующимся количеством АЛУ внутри одного узла. Внутри узла исполнительные устройства оперируют над общей памятью, обмен данными между узлами при выполнении одной задачи не предусматривался.

Далее следует выделить MMX [59] (1996 г) — MultiМedia Extensions, программно-аппаратное расширение процессоров серии Pentium MMX. Добавляется восемь 64-битных регистров общего пользования, работающих с 64-разрядными целочисленными данными, а также с данными, упакованными в группы (векторы) общей длиной 64 бита. Расширение определяет 57 инструкций, позволяющих параллельно обрабатывать несколько элементов векторов. Особенностью является запрет на одновременное исполнение команд математического сопроцессора и MMX.

Расширение SSE [97] (1999 г) - Streaming SIMD Extensions, Развитие технологии MMX. Впервые реализовано в Intel Pentium III. Добавляет восемь 128-битных регистров, каждый регистр может хранить числа с четырьмя 32-битными значениями с плавающей точкой одинарной точности. Включает 70 команд для векторной обработки данных. Работает только с числами с плавающей точкой. Позволяет одновременное использование команд сопроцессора и SSE. Его развитием являются SSE2 [87] (2001г.), SSE3 [91] (2004 г.) и SSE4 (2007 г.), характеризующиеся большим набором инструкций (добавлены, соответственно 144, 13 и 54 команды для работы с векторами).

Интерес к организации векторных вычислений на видеокартах возник еще в конце прошлого века, серьезное внедрение видеопроцессоров в широкую вычислительную практику началось с технологии CUDA (2007 г.) [94] - Compute Unified Device Architecture. Она позволяет организовывать доступ к набору инструкций графического ускорителя фирмы NVIDIA и управлять его памятью. Содержит набор расширений языка C, позволяющих выражать как параллелизм данных, так и параллелизм задач на уровне мелких и крупных структурных единиц. Поддерживает только одинарную точность. Современный вариант CUDA 7.5 (2015) [50] реализует динамический параллелизм (потоки GPU могут динамически порождать новые потоки, позволяя GPU адаптироваться к новым данным), работает и с двойной точностью.

Технология ОpenCL (2009 год) [60] - Open Computing Language, фреймворк написания параллельных программ на различных GPU и CPU. Представляет собой расширения языка С, использующие модель SIMD и поддерживающие Task Parallel programming model – модель, когда одновременно могут выполняться различные ядра (kernal). Основное достоинство — кроссплатформенность, способность исполнять код как на GPU, так и на CPU, поддержка стандарта целым рядом компаний: Apple, AMD, Intel, NVIDIA и некоторыми другими. Производительность на видеокартах NVIDIA на несколько десятков процентов уступает работе с использованием CUDA.

OpenACC (2012 г.) [100] - программный стандарт для параллельного программирования, разрабатываемый фирмами Cray, CAPS, Nvidia и PGI, представляет собой набор директив компилятора, аналогичный OpenMP, предназначенных для упрощения создания гетерогенных параллельных программ, работающих как с центральным, так и графическим процессорами

Термин GPU впервые был использован компанией NVIDIA в 1999 году, когда она представила новый продукт из линейки GeForce - GeForce 256 [84], графический процессор, который впервые мог независимо от CPU производить вычисление геометрических преобразований. Начиная с этого момента графический ускоритель, ранее использовавшийся только для вывода и ускорения 3D графики, начали использовать для решения более широкого круга задач (GPGPU [98] - General-purpose computing for graphics processing units). На сегодняшний день программирование на GPU занимает существенную долю высокопроизводительных вычислений. Оно применяется от моделирования физических процессов [64] до кодирования видео и рендеринга трехмерных сцен [14]. С появлением технологий NVidia CUDA стало возможным относительно просто писать программы, использующие вычислительные возможности GPU, именно NVidia CUDA обеспечила рост популярности GPGPU за счет облегчения процесса создания GPGPU приложений. На сегодняшний день, наиболее популярная технология для работы с видеокартами - технология CUDA от фирмы NVIDIA. Если смотреть на список самых мощных суперкомпьютеров 2015 года [103], то 56 из 90 используют чипсеты NVIDIA.

Использование временной сети Петри для моделирования вычислений по векторным алгоритмам

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

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

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

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

Исследователь, специализирующийся на параллельных вычислениях для ЭВМ типа MIMD (по классификации Флинна) отметит важность выбора декомпозиции сеточной области для явных схем, вспомнит правило перехода «от поверхности к объему», особенности применения этого правила при разных моделях коммуникаций. С юмором отзовется о работе Фостера, где упомянутое правило иллюстрировалось неуместным рисунком, перекочевавшим затем в учебные пособия отечественных авторов.

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

Наиболее естественным приемом векторизации алгоритмов решения сеточных уравнений явных схем представляется работа с векторами, длина которых совпадает с дискретизаций сеточной области по выбранному пространственному направлению. Впредь будем называть такие алгоритмы «коротковекторными», или «алгоритмами с короткими векторами». Их построение представляется наиболее естественным, с них и начнем. 2.1.1 Описание алгоритмов

В предыдущей Главе (пункт 1.4.2) в качестве иллюстрации авторской методики моделирования векторных вычислений на GPU был предложен алгоритм 1.5 решения сеточных уравнений схемы (2) для задачи (1). Он основан на операциях сложения векторов и saxpy в их столбцовых вариантах.

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

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

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

Повторное использование найденных величин безусловно является общим приемом при модификации численных методов с целью снижения их вычислительной сложности. Однако, пищу для размышлений автору диссертации дало высказанное Дж. Ортегой в [23] предложение, которое, впрочем, касалось не дифференциального шаблона, а относилось к модификации методов Якоби и Гаусса-Зайделя для решения СЛАУ. Будучи весьма изящным, но приложенным несколько неудачно (перечисленные итерационные методы в большинстве случаев сходятся медленно и в широкой вычислительной практике применяются, как правило, в методических целях) оно не получило распространения даже в выбранной Дж. Ортегой предметной области. В частности, не было перенесено на неявные разностные схемы для решения нестационарных задач математической физики. Здесь упомянутая идея повторного использования данных, полученных в ходе расчета значения сеточной функции по дифференциальному шаблону, впервые применяется к методу решения уравнений явных схем и для нестационарных задач. Следуя одному из замыслов диссертации (переходу от матричных алгоритмов к векторным) в данном параграфе далее сформулируем новый векторный алгоритм, реализующий такое повторное использование.

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

Рассмотрим новый способ организации массива, хранящего значения сеточной функции. Пусть V – это одномерный массив длины (N+2)2, содержащий упомянутые значения на текущем временном слое, хранящиеся по строкам, как показано на рис. 2.9. В отличие от ранее введённого Un (в пункте 1.1.1) в V входят граничные значения.

Рисунок 2.9 - Схема хранения в виде одномерного массива V и попарные суммы Разностной схеме (2) для уравнения теплопроводности при вычислении лапласиана соответствует дифференциальный шаблон «крест». На рис. 2.8 обозначены светло- и тёмно-серым выделением элементы вектора V, участвующие в расчёте новых значений V(N+4) и V(2N+7) (U1k,1 и U2k,2 на рис. 2.1) соответственно. Очевидно, что попарная сумма значений U1k,2 и U2k,1 (рис. 2.1), переобозначенных как V(N+5) и V(2N+6) и показанная на рис. 2.8 двунаправленной стрелкой, подсчитывается дважды в алгоритмах из 2.1. и 2.2, так как используется для нахождения двух разных значений сеточной функции. Благодаря новому варианту алгоритма с длинными векторами, мы можем сократить общее число операций, необходимое для расчёта значений сеточной функции, путём введения вспомогательного вектора T размерности (N+2)(N+1)+1, который будет хранить в себе результаты попарного сложения.

Таким образом, алгоритм подсчёта сеточной функции на каждом n+1-ом временном шаге можно записать в следующем виде [6]: векторные операции данного алгоритма – saxpy и векторные сложения. В результате его выполнения экономится одна операция сложения при вычислении каждого значения сеточной функции по дифференциальному шаблону (т. е. 14% скалярных операций). Однако приходится использовать дополнительную память для хранения вспомогательного вектора T. Переход к работе с длинными векторами по сравнению с коротковекторным вариантом из 2.1 позволил отказаться от цикла, повторяющегося N раз (количество столбцов матрицы), в котором выполняется 3 операции векторного сложения и одна операция типа saxpy с векторами длины N, ради двух операций сложения векторов длины (N+1)(N+2)-2 и одной saxpy для векторов длины N(N+2)-1, что (как будет показано далее) приводит к более полному использованию аппаратных возможностей видеокарты и, как следствие, ускорению вычислений.

По сравнению с предыдущим длинновекторным алгоритмом из 2.2, характеризовавшимся 9 векторными операциями (5 покомпонентных умножений и 4 сложения) в случае шаблона с произвольными коэффициентами и 5 операциями (1 покомпонентное умножение и 4 сложения) для схемы (2), количество векторных операций сократилось до трех. Как уже отмечалось, при таком сравнении важна не столько длина векторов (ее изменение незначительно влияет на длительность вычислений), сколько число операций. По этому критерию можно ожидать ускорения вычислений в 1,7 раз.

Недоумение может вызвать тот факт, что 14% сокращение числа скалярных операций приводит к более чем полуторакратному снижению количества векторных (при том, что длина векторов почти не отличается). Действительно, выигрыш обусловлен не только повторным использованием попарных сумм, но и изменением структуры алгоритма - задействованием операции saxpy, в которой скалярных операций втрое больше, чем в сложении или покомпонентном произведении векторов.

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

Рисунок 2.11 — Блок-схема алгоритма 2.3 Возможность приведенного анализа обычно сильно затруднена в силу отсутствия общепринятой нотации для записи алгоритмов решения сеточных уравнений явных разностных схем. Более того, в известной автору литературе ни матричные ни векторные алгоритмы не записываются вовсе. Изложение сопровождается исключительно скалярной нотацией с упоминанием ее дальнейшей программной реализации на матрице вычислительных потоков GPU. Сравнение же программ, даже в случае открытого кода, во-первых, крайне затруднительно, а во-вторых, больше расскажет об искусстве кодирования группы разработчиков (и интерпретации кода субъектом сравнения), чем о математических особенностях реализованных алгоритмов. Таким образом, использование выбранной в 1.3.3 нотации актуально и уместно.

Рекомендации по использованию векторного метода

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

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

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

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

Задействованные сеточные функции будут входить в разные конечные разности с разными коэффициентами. Это приведет к значительному усложнению длинновекторного алгоритма второго типа (как в 2.3, 3.2 и 3.3), в котором придется отказаться от использования операций saxpy и перейти к набору векторных сложений и покомпонентных произведений. При записи алгоритма на основе gaxpy, указанная неоднородность легко учитывается в коэффициентах матрицы при записи канонической формы, что не приводит ни к трансформации самого алгоритма, ни к отказу от свойственных ему векторных операций. Даже количество таких операций (но не вычислительная вычислительная сложность относительно операций со скалярами) останется прежним.

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

Переход к трехмерному случаю представляет еще больший интерес для векторизации, чем двумерный, хотя и понятно, что без детального рассмотрения последнего обойтись было нельзя в силу его методической ценности. Очевидна несостоятельность коротко-векторного подхода в трехмерном случае, обусловленная ограниченностью памяти GPU по сравнению с объемом оперативной памяти мощного вычислительного кластера (на персональной ЭВМ такие задачи решают редко). Сотня-другая узлов по одному пространственному направлению — вот максимальная длина вектора, очевидно не обеспечивающая сколь-нибудь значимую загрузку видеопроцессора.

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

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

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

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