Введение
В последнее время активно развивается направление высокопроизводительных вычислений и, в частности, вычисления общего назначения на графических процессорах– 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для ускорения решения СЛАУ с трехдиагональными матрицами методом циклической редукции при размерностях матрицы больших 
Список литературы:
- Боресков А. В., Харламов А. А., Марковский Н. Д. и др. Параллельные вычисления на GPU. Архитектура и программная модель CUDA / А. В. Боресков и др. Предисл.: В. А. Садовничий. – М.: Изд-во Московского университета, 2012. 336 с.
- Гергель В. П., Баркалов К. А., Мееров И. Б. и др. Параллельные вычисления: технологии и численные методы: учебное пособие. В 4 т. Т. 4. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2013. 369 с.
- Мееров И. Б., Никонов А. С., Русаков А. В., Шишков А. В. Реализация одного алгоритма нахождения цены конвертируемой облигации. // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. Р. Г. Стронгина. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2008. – С. 236–241.
- Мееров И. Б., Никонов А. С., Русаков А. В., Шишков А. В. Параллельная реализация одного алгоритма нахождения цены конвертируемой облигации для систем с общей памятью // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. проф. В. П. Гергеля. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2009. – С. 287–292.
- Косяков М. С. Применение технологии CUDA для ускорения расчета цен опционов европейского типа сеточным методом / М. С. Косяков, Д. Н. Шинкарук, А. В Торопов, Ю. А. Шполянский // Известия высших учебных заведений. Приборостроение, 2012. – Т.55, вып.10. – С. 13–19.
- Косяков М.С. Анализ эффективности применения технологии CUDA для решения систем линейных уравнений с трехдиагональными матрицами в задачах расчета цен опционов / М. С. Косяков, Д. Н. Шинкарук, А. В Торопов, Ю. А. Шполянский // Известия высших учебных заведений. Приборостроение, 2012. – Т.55, вып.10. –С. 20–25.
- Параллельные вычисления CUDA [Электронный ресурс] URL: https://www.nvidia.ru/object/cuda-parallel-computing-ru.html. (дата обращения: 24.06.2015).[schema type=»book» name=»АНАЛИЗЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯТЕХНОЛОГИИ CUDA ДЛЯ ЧИСЛЕННОГО РЕШЕНИЯДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙВ ЧАСТНЫХ ПРОИЗВОДНЫХПО СХЕМЕ КРАНКА НИКОЛСОНА» description=»Приведены результаты разработки программы расчета цены конвертируемой облигации, как численного решения дифференциального уравнения в частных производных второго порядкапо схеме Кранка-Николсона с использованием метода циклической редукциинагетерогенной вычислительной системе, сочетающей в себе графический и центральный процессоры. Проведен анализ эффективности применениятехнологии CUDAдля реализации схемы Кранка-Николсона.» author=»Вахлаева Клавдия Павловна, Сынкова Дарья Александровна, Фаюстов Денис Сергеевич» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2017-02-20″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_25.07.15_07(16)» ebook=»yes» ]