25 Июл

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




Номер части:
Оглавление
Содержание
Журнал
Выходные данные


Науки и перечень статей вошедших в журнал:

Введение

В последнее время активно развивается направление высокопроизводительных вычислений и, в частности, вычисления общего назначения на графических процессорах– GPGPU (General-Purposecomputingon GPU)[1]. Возможность переносить интенсивные параллельные вычисления на графический процессор, а последовательные выполнять на центральном процессоре, делает актуальной задачуразработки параллельных программ, согласованных с гетерогенной вычислительной средой, сочетающей в себе графический и центральный процессоры.В рамках данного направления необходимы новые средства разработки GPGPU-приложений. Одним из таких средств является технология CUDA (Compute Unified Device Architecture), разработанная компанией NVIDIA[7].

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

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

Постановка задачи и метод решения

Математической модельюрассматриваемой задачи является модель Блэка-Шоулза[5], представляющая собойпараболическое уравнение в частных производных относительно стоимости конвертируемой облигации. Жизненный цикл конвертируемой облигации делится на конечное число стадий или временных интервалов в соответствии с рисунком 1.

  • решить СЛАУ методом циклической редукции;
  • определитьоптимальное значение цены конвертируемой облигации по вектору .

Наиболее эффективное распараллеливание приведенного выше алгоритма можно получить, распараллелив следующие функции:

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

Особенности реализации

Кодыфункций, предназначенных для распараллеливания с применением технологии CUDA, были оформлены в виде ядер CUDA-программы(kernel) и выполнялисьна GPU как набор многих одновременно работающих нитей (threads).

Код для всех ядер CUDA-программы разрабатывался с использованием типа double, чтобы не снижать точность расчетов.Трехдиагональные матрицы и правые столбцы систем линейных алгебраических уравненийформируются непосредственно в памяти GPU. Вектор результатов копируется из памяти GPU в память центрального процессора, после чего ресурсы освобождаются.

Далее представлен фрагмент программы, содержащий ядроCycleReductionMethod_step_forward() для прямого хода циклической редукции.

__global__ void CycleReductionMethod_step_forward(double* cuda_f,

                                      double* cuda_a, double* cuda_b, double* cuda_c,

                                      int step, int start, int j, double a_0,

                                      double a_1, double a_2, int n, intelementsNum)

{

         inttid = getGlobalIdx_2D_3D();

         if (tid>= elementsNum) return;

         intblockSize = blockDim.x*blockDim.y*blockDim.z;

         if (j == 0 &&tid == 0) {

                   cuda_a[0] = a_0;

                   cuda_b[0] = a_1;

                   cuda_c[0] = a_2;

         }

         __syncthreads();

         double alpha = -cuda_a[j] / cuda_b[j];

         double beta = -cuda_c[j] / cuda_b[j];

         if (tid == 0) {

                   cuda_a[j + 1] = alpha * cuda_a[j];

                   cuda_b[j + 1] = cuda_b[j] + 2 * alpha * cuda_c[j];

                   cuda_c[j + 1] = beta * cuda_c[j];

         }

         for (inti = tid; i<elementsNum; i += blockSize) {

         int k = start * (i + 1);

         cuda_f[k] = alpha * cuda_f[k — step] + cuda_f[k] + beta * cuda_f[k + step];

         }

}

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

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

Вычислительные эксперименты проводились с использованием инфраструктуры, представленной в таблице 1. Для CUDA-программы измерялось время расчета с учетом всех накладных расходов на запуск нитей.

Таблица 1.

Тестовая инфраструктура

Центральный процессор (CPU) Intel(R) Core(TM) i5-3450 CPU @ 3.10 GHz
Память 8 ГБ
Операционная система MicrosoftWindows 7 Ultimate, 64-bit (SP1)
Среда разработки MicrosoftVisualStudio 2012
GPU NVIDIA GeForce GTX 670
Число CUDA-ядер 1344
Память GPU 2048 МБ GDDR5
Шина PCI-E 16x 3.0
Скорость передачи данных памяти 6008 МГц
Версия драйвера CUDA 347.62

Основная вычислительная сложность схемы Кранка-Николсона определяется трудоемкостью методов решенияСЛАУ. Результаты исследования зависимости времени выполнения программ, применяющихметод циклической редукции, на CPUи с использованием GPUот размерности трехдиагональной матрицы приведены в таблице 2.

Таблица 2.

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

J Время работы реализации на CPU (сек) Время работы реализации с использованием GPU (сек)
128 0.017 1.127
512 0.039 1.030
1024 0.113 1.323
2048 0.130 1.422
4096 0.255 1.673
16384 1.056 2.654
32768 2.574 3.805
65536 5.647 5.878
131072 10.503 10.002
262144 28.954 18.331
524288 52.856 33.426
1048576 123.336 66.078

Как видно, начиная с 131072, которому соответствует 17, реализация метода циклической редукции с применением CUDA показывает лучшее время решения.

Заключение

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

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

 

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

  1. Боресков А. В., Харламов А. А., Марковский Н. Д. и др. Параллельные вычисления на GPU. Архитектура и программная модель CUDA / А. В. Боресков и др. Предисл.: В. А. Садовничий. – М.: Изд-во Московского университета, 2012. 336 с.
  2. Гергель В. П., Баркалов К. А., Мееров И. Б. и др. Параллельные вычисления: технологии и численные методы: учебное пособие. В 4 т. Т. 4. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2013. 369 с.
  3. Мееров И. Б., Никонов А. С., Русаков А. В., Шишков А. В. Реализация одного алгоритма нахождения цены конвертируемой облигации. // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р. Г. Стронгина. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2008. – С. 236–241.
  4. Мееров И. Б., Никонов А. С., Русаков А. В., Шишков А. В. Параллельная реализация одного алгоритма нахождения цены конвертируемой облигации для систем с общей памятью // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. В. П. Гергеля. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2009. – С. 287–292.
  5. Косяков М. С. Применение технологии CUDA для ускорения расчета цен опционов европейского типа сеточным методом / М. С. Косяков, Д. Н. Шинкарук, А. В Торопов, Ю. А. Шполянский // Известия высших учебных заведений. Приборостроение, 2012. – Т.55, вып.10. – С. 13–19.
  6. Косяков М.С. Анализ эффективности применения технологии CUDA для решения систем линейных уравнений с трехдиагональными матрицами в задачах расчета цен опционов / М. С. Косяков, Д. Н. Шинкарук, А. В Торопов, Ю. А. Шполянский // Известия высших учебных заведений. Приборостроение, 2012. – Т.55, вып.10. –С. 20–25.
  7. Параллельные вычисления CUDA [Электронный ресурс] URL: http://www.nvidia.ru/object/cuda-parallel-computing-ru.html. (дата обращения: 24.06.2015).
    АНАЛИЗЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯТЕХНОЛОГИИ CUDA ДЛЯ ЧИСЛЕННОГО РЕШЕНИЯДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙВ ЧАСТНЫХ ПРОИЗВОДНЫХПО СХЕМЕ КРАНКА НИКОЛСОНА
    Приведены результаты разработки программы расчета цены конвертируемой облигации, как численного решения дифференциального уравнения в частных производных второго порядкапо схеме Кранка-Николсона с использованием метода циклической редукциинагетерогенной вычислительной системе, сочетающей в себе графический и центральный процессоры. Проведен анализ эффективности применениятехнологии CUDAдля реализации схемы Кранка-Николсона.
    Written by: Вахлаева Клавдия Павловна, Сынкова Дарья Александровна, Фаюстов Денис Сергеевич
    Published by: БАСАРАНОВИЧ ЕКАТЕРИНА
    Date Published: 02/20/2017
    Edition: ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_25.07.15_07(16)
    Available in: Ebook