High performance
7 November 2011

Опыт использования GPU для финансового моделирования

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




Преамбула


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

У ТС есть набор параметров, которые определяют её поведение во время торгов. Внутри торгового дня часть параметров меняется, т.е. ТС подстраивается под текущий рынок. Задача состояла в определении оптимальных параметров ТС путём ретроспективного анализа котировок (бэктестинга) за указанный пользователем период времени.

Алгоритм


К сожалению, единственным путём нахождения оптимума оказался полный перебор.
  1. Составляется набор комбинаций параметров ТС, удовлетворяющих заданным пользователем ограничениям. Есть ограничения между самими параметрами, которые позволяют отбросить значительный объём перебора. Параметры перебираются внутри границ с некоторым шагом. Чем меньше шаг, тем выше точность, но и соответственно больше рассматриваемых вариантов. Подобный набор комбинаций для удобства можно представить в виде n-мерной разреженной матрицы, но алгоритму от этого пользы никакой, поэтому данный набор представлял собой простой связанный список структур параметров.
  2. Для каждой комбинации параметров выполняется эмуляция работы ТС.
    ТС проходит по всему набору котировок и при выполнении условий фиксирует совершение сделок покупки/продажи. При этом подсчитывается общий финансовый результат работы ТС. После завершения эмуляции финансовый результат сохраняется.
  3. После завершения обработки всех комбинаций параметров среди результатов ищется наилучший. По наилучшей комбинации параметров выполняется ещё одна эмуляция, но на этот раз уже с отображением всех сделок и результатов пользователю.

Первая рабочая версия


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

Параллельная обработка на CPU


Распределение по потокам было реализовано с использованием Parallel.ForEach над набором параметров ТС.

Parallel.ForEach(counters, counter => Process(points, counter));

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

Parallel.For(0, processorCount, i => Process(points, block[i]));

В данной реализации ядра загружались равномерно до 99-100% и время работы сократилось почти в 4 раза, ведь это практически идеальная задача для параллельной обработки.

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

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

Перенос на GPU


О вычислениях на GPU я имел достаточно общее представление. Конечно, я читал статьи о том, как это здорово, но об ограничениях технологий не имел представления.
В итоге я решил, что стоит разобраться в данной теме. Если даже не получится перенести алгоритм, то всё равно узнаю что-нибудь полезное.

Я выкачал в iTunes стэнфордский курс по CUDA и начал смотреть лекции. Лекции хороши в том плане, что дают общее представление об архитектуре. В принципе, мне хватило базы из 5 первых лекций, чтобы понять что мне нужно делать. Вот только реализовывать я решил не на CUDA, а на OpenCL. Так уж получилось, что дома у меня видеокарты AMD, а на работе NVIDIA.

Насмотревшись лекций и вооружившись словариком для перевода терминов CUDA в OpenCL, я за четыре часа написал первую реализацию. Для работы с OpenCL я использовал OpenCL.Net.

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

И тут я начал набивать шишки:
  1. Алгоритм что-то считал, но считал не то. Результаты совсем не совпадали с эталонными.
    После длительной отладки оказалось, что я неверно думал о том что bool занимает 1 байт. По спецификации он разворачивается на устройстве в int и занимает 4 байта. Для устранения неоднозначности я просто поменял тип передаваемых данных на int.
  2. Алгоритм начал выдавать «почти такие же» результаты. И результаты были стабильно немного лучше чем в CPU-версии. Я в очередной раз пересмотрел cl-код и не нашел ошибки. Пришлось перепроверять CPU-версию, и да, ошибка была там. Оказалось, что в процессе оптимизации я отбрасывал вроде бы лишние варианты, которые на самом деле иногда оказывались не лишними. После удаления «оптимизации» из CPU-версии результаты начали совпадать.
  3. До этого все эксперименты я проделывал на домашнем компе. При проверке на работе оказалось, что приложение умирает после нескольких запусков из-за нехватки памяти. При этом дома всё работало нормально. Выяснилось, что я действительно не освобождал память, но при этом реализация OpenCL от AMD обрабатывала данный косяк программиста нормально. Реализация OpenCL от NVIDIA не прощает ошибок.

В принципе, после этого было ещё несколько итераций по доводке, в том числе я познакомился с Kernel Analyzer, но в целом это было уже готовое решение.

Итоги


Пользователь после получения новой версии был очень доволен. Даже на его слабеньком Radeon 5450 (80 универсальных процессоров) расчёты ускорились в десятки раз.
Он сразу же начал меня пытать о том, насколько мощную карту можно поставить в его комп (я не смог адекватно ответить из-за трудностей удаленной диагностики его БП и МП), сколько вообще видеокарт можно воткнуть в один системник (тут было желание отправить ему ссылки на geek-porn с фотографиями bitcoin-ферм), и можно ли распараллелить сразу на несколько машин с видеокартами.

Перед завершением хотелось бы привести время решения одной и той же задачи (анализ биржевых данных за 2 дня):
1) AMD Phenom II X6 1090T (6 ядер, 100% загрузка) — 4 часа 48 минут (288 минут)
2) Radeon 5850 (1440 универсальных процессоров, примерно 50% загрузка) — 4 минуты
т.е. время обработки сократилось в 72 раза.

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

+91
7.3k 122
Comments 39