Опыт использования 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 раза.

    Спасибо за внимание, буду рад ответить на вопросы. Репорты об опечатках, пропущенных зпт, требования замены дефиса на тире желательно слать в личку.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 39

      0
      На SIMD переносить пробовали?
        0
        Там не в арифметике проблема. Очень много условных ветвлений.
        +2
        У NVIDIA оптимизация OpenCL почти идентична оптимизации CUDA и соответственно отличается от оптимизаций OpenCL от AMD, ну а Intel вообще в другой плоскости мыслит :).

        Я у себя даже поиск по большой ХЕШ таблице совершаю на видеокарте, ну а с ускорением алгоритма Маркова и работы с нейронными сетями я думаю многие знают.

        Всю руки не дойдут, хочу попробовать хранить данные в виде текстуры, но с учётом что данные это CRC32 хеш, а 3-х значное поле. Если Вам попадался такой пример, то буду благодарен, если им поделитесь.
          +1
          Тогда за счёт чего ускорение на GPU? GPU не дружат с условными ветвлениями
            0
            Ну да, каждая ветка внутри блока обрабатывается отдельно, т.е. остальные ждут. Выигрыш в целом за счет количества процессоров.
              0
              У Radeon 5850 всего 18 независимых процессоров (simd cores). Учитывая их частоту в 725 MHz они едва ли выигрывают у 6-ядерного Phenom на 3.2 GHz только за счёт числа.
                0
                Ну нельзя ведь и сводить ситуацию к тому что в каждом блоке в любой момент выполняется только один поток :) Плюс переключения эти достаточно быстрые.

                Много времени также тратится на чтение из памяти.
              0
              У NVIDIA каждое ветвление обрабатывает свой Warp. При этом GeForce GTX 560 Ti содержит 384 ядра для обработки. Выигрыш за счёт массовости.
                0
                Ну не совсем так. Просто часть потоков внутри блока (warp-а) засыпает пока выполняется другая ветка.

                Поэтому желательно таким образом подбирать данные чтобы внутри одного блока все потоки попадали в одно и то же ветвление. Если получится так сделать, то да, каждый блок будет обрабатывать своё ветвление. Но это задача разработчика, а не платформы.
                  +1
                  Я приблизительно это и хотел сказать. Если внутри блока (warp-а) нет ветвления, то получаем на GeForce GTX 560 Ti 384 ядра для обработки.
              +6
              время обработки сократилось в 72 раза

              это надо большим жирным шрифтом и в заголовок )

              Истинная success story, спасибо
                +4
                время обработки сократилось в 72 раза
                Я эту фразу картинкой прочувствовал :)
                  +6
                  Ээ… Если б на бабу дули со скоростью в 72 раза превышающей номинальную (ну пускай 30 км\ч) получилась бы совсем другая картинка из цикла «рас;%дорасило» ))
                • UFO just landed and posted this here
                  +2
                  > NVIDIA не прощает ошибок.
                  сурово :)
                    0
                    Сколько занимает времени расчёт ТС с фиксированными значениями?
                    Сколько параметров ТС подбирается?
                    Расчёт идёт по тикам или барам, максимумы минимумы цены за период?

                    В нашем продукте, расчёт результатов ТС на квартальных тиковых данных с фиксированными значениями более 4 часов занимает, параллельная обработка не помогает, тики ведь нужно обрабатывать последовательно один за другим. Единственный вариант это параллельный расчёт нескольких вариантов параметров, ну и тут при достаточно сложной ТС модификации подвергаются одновременно десяток параметров, каким кластером это считать и главное как потом обрабатывать результат, выделяя «правильные»параметры для последующего тестирования на реальном рынке, вопрос.
                      0
                      1) Не могу с ходу ответить. Гляну и потом напишу.
                      2) 4 — достаточно простая система
                      3) По тикам

                      Ну квартальные это серьёзно.
                      Извиняюсь, часть информации раскрывать не могу :) Успехов вам.
                        +1
                        Я там понимаю что скорее всего это ТС по «скальпингу»,
                        обрабатываются N тиков, при превышении максимума цены, волатильности, спреда БидАска или какого то другого значения входите в сделку, потом только мониторите прибыль/убыток для выхода.
                        Это очень хорошо ускоряется в вашем случае, одновременно рассчитать финансовый результат для разных значений прибыли/убытка.

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

                        Года три назад Церих представлял свою систему тестирования ТС на CUDA, но у них другой подход они не только параметры стратегии модифицировали, но и сами исторические данные, тики, что бы максимально
                        быстро отсеять неподходящие значения ТС, или саму ТС. В случаи больших «сливов». Заявлялось ускорение в сотни раз, относительно одного ядра ЦПУ

                        Ваша статья вдохновила нас на продолжения исследования в этом направлении, спасибо.
                          +8
                          Ваша статья вдохновила нас на продолжения исследования в этом направлении, спасибо./blockquote>
                          Гендир прочитал, сделал мне выговор :)
                            0
                            В торговой платформе MetaTrader 5 для ускорение оптимизации торговых систем используется публичный MQL5 Cloud Network в дополнение в локальным ядрам и удаленным агентам.

                            Можете попробовать — скорость возрастает в десятки раз.
                              0
                              Отличная штука.

                              Параноидальные клиенты не боятся отдавать свои идеи в облако? :)
                                0
                                Не боятся, так как все программы пишутся на специальном прикладном managed MQL5 языке (безопасный вариант С++), работают внутри защищенной песочницы и никогда не записываются на диск.

                                На клаудных агентов передается уже скомпилированный код, который на целевой платформе докомпилируется в нативный 32/64 код и исполняется.

                                Кроме торговых задач можно запускать и математические вычисления. Желающие могут продавать свои ресурсы — cloud.mql5.com/ru
                                  0
                                  Скоро в MQL5 будет включена поддержка OpenCL — это позволит еще в разы/порядки поднять производительность вычислений в распределенной сети.
                          –3
                          Я бывал по обе стороны резюме. И очень настоятельно советую при описание опыта работы использовать такую схему:

                          Место работы
                          Обязанности на этой работе (что делал?)
                          Достижения (что получилось?) // очень конкретные факты, без размытых фраз и красивых словосочетаний.
                            –2
                            извини промазал
                              –2
                              Сам у себя извинения попросил, теперь нужно самого себя извинить.
                            +2
                            влепил плюс в карму за одну только иллюстрацию
                              +1
                              Если кому интересно, это Anina Schenker.
                              А подпись с gizmodo
                              0
                              >После завершения обработки всех комбинаций параметров среди результатов ищется наилучший.

                              а каким образом вы определяете, что этот результат лучший, а не другой?
                                0
                                Результат это прибыль/убыток ТС. Чем больше, тем лучше.
                                  0
                                  ну например один набор параметров у вас дал 1000 сделок и 500 прибыли, другой набор дал 400 сделок и 450 прибыли, какой из них лучше?
                                    0
                                    Комиссия учитывается при расчете PnL. Ваш вопрос был про это? :)

                                    Соответственно на ваш вопрос не могу ответить не зная какую комиссию за сделку вы подразумеваете. Если нулевую, то 500 прибыли лучше.
                                      0
                                      да пускай высчитывается, дело не в комиссии,
                                      я к тому, что пробектестированная прибыль возможно неважный способ выбора лучшего набора параметров, но если у вас реализовано так, то вопрос закрываю:)
                                        0
                                        Не, вы меня только раззадорили. Поделитесь своими идеями :)
                                          0
                                          я не знаю, выже акула фондового рынка, мне просто стало интересно ;)
                                            0
                                            иронично)
                                              0
                                              m'kay
                                  +1
                                  Применить какой-нибудь численный метод оптимизации также не получилось, т.к. у целевой функции (результата торгов) было много локальных максимумов.


                                  Вообще-то существует достаточно большое количество методов многоэкстремальной оптимизации — Пиявского, Жилинскаса, Стронгина и т.п., в т.ч. есть и многокритериальные и оптимизированные под параллельную обработку. Обычно они предполагают что имеется константа Липшица, которую можно оценить (максимальное значение производной), но в финансовых задачах всегда все функции ограничены. Использование этих методов сократит время обработки на порядки по сравнению с перебором.
                                    0
                                    Класс. Почитаю, спасибо :)

                                  Only users with full accounts can post comments. Log in, please.