В этой статье я вкратце описываю свой опыт оптимизации одной задачи перебора, начиная от однопроцессорного алгоритма к многопроцессорному и к версии на OpenCL.
Один из проектов (C#), над которыми я работаю, предназначен для финансового анализа и моделирования. Он позволяет пользователю на некотором «птичьем» языке описывать входные параметры и последовательность алгоритмов обработки финансовой информации (котировок и других данных по финансовым инструментам). Одной из задач, решаемых с помощью приложения, является оптимизация параметров торговой системы (ТС).
У ТС есть набор параметров, которые определяют её поведение во время торгов. Внутри торгового дня часть параметров меняется, т.е. ТС подстраивается под текущий рынок. Задача состояла в определении оптимальных параметров ТС путём ретроспективного анализа котировок (бэктестинга) за указанный пользователем период времени.
К сожалению, единственным путём нахождения оптимума оказался полный перебор.
После реализации алгоритма и получения первых полезных (для конечного пользователя) результатов оказалось, что работает данный перебор очень медленно.
Перебор выполнялся последовательно в одном потоке и загрузка 4 ядер процессора была достаточно низкой. Сразу же пришла в голову мысль что неплохо бы распараллелить обработку.
Распределение по потокам было реализовано с использованием Parallel.ForEach над набором параметров ТС.
Но после замера производительности выигрыш оказался ничтожным. Получилось это из-за накладных расходов на переключение потоков. Т.е. время обработки одного набора параметров незначительно отличалось от времени, необходимого на инициализацию потока.
Я разделил весь набор параметров на примерно равные по размеру блоки. Количество блоков задал равным количеству доступных ядер процессора.
В данной реализации ядра загружались равномерно до 99-100% и время работы сократилось почти в 4 раза, ведь это практически идеальная задача для параллельной обработки.
Пользователь был подобному ускорению очень рад.
Но через пару дней он поставил другую задачу и она увеличила объём перебора в сотни раз. Решение новой задачи на биржевой информации за 2 недели торгов считалось почти день. В принципе, пользователя это устраивало, но мне это казалось неадекватным.
Упростить алгоритм не получалось — он был сокращен до строго необходимого набора операций, профайлер не показывал явных проблем.
Применить какой-нибудь численный метод оптимизации также не получилось, т.к. у целевой функции (результата торгов) было много локальных максимумов. Проход по параметрам с широким шагом мог просто пропустить глобальный максимум.
Мне просто нужно было больше вычислительной мощности.
О вычислениях на GPU я имел достаточно общее представление. Конечно, я читал статьи о том, как это здорово, но об ограничениях технологий не имел представления.
В итоге я решил, что стоит разобраться в данной теме. Если даже не получится перенести алгоритм, то всё равно узнаю что-нибудь полезное.
Я выкачал в iTunes стэнфордский курс по CUDA и начал смотреть лекции. Лекции хороши в том плане, что дают общее представление об архитектуре. В принципе, мне хватило базы из 5 первых лекций, чтобы понять что мне нужно делать. Вот только реализовывать я решил не на CUDA, а на OpenCL. Так уж получилось, что дома у меня видеокарты AMD, а на работе NVIDIA.
Насмотревшись лекций и вооружившись словариком для перевода терминов CUDA в OpenCL, я за четыре часа написал первую реализацию. Для работы с OpenCL я использовал OpenCL.Net.
На видеокарту перекидывались преобразованные данные о котировках и наборы параметров ТС. Каждая комбинация параметров обрабатывалась отдельным потоком. Т.е. поток на старте считывал свои параметры ТС и далее перебирал всю историю котировок. После обработки всех комбинаций с видеокарты забирались результаты работы.
И тут я начал набивать шишки:
В принципе, после этого было ещё несколько итераций по доводке, в том числе я познакомился с 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 раза.
Спасибо за внимание, буду рад ответить на вопросы. Репорты об опечатках, пропущенных зпт, требования замены дефиса на тире желательно слать в личку.
Преамбула
Один из проектов (C#), над которыми я работаю, предназначен для финансового анализа и моделирования. Он позволяет пользователю на некотором «птичьем» языке описывать входные параметры и последовательность алгоритмов обработки финансовой информации (котировок и других данных по финансовым инструментам). Одной из задач, решаемых с помощью приложения, является оптимизация параметров торговой системы (ТС).
У ТС есть набор параметров, которые определяют её поведение во время торгов. Внутри торгового дня часть параметров меняется, т.е. ТС подстраивается под текущий рынок. Задача состояла в определении оптимальных параметров ТС путём ретроспективного анализа котировок (бэктестинга) за указанный пользователем период времени.
Алгоритм
К сожалению, единственным путём нахождения оптимума оказался полный перебор.
- Составляется набор комбинаций параметров ТС, удовлетворяющих заданным пользователем ограничениям. Есть ограничения между самими параметрами, которые позволяют отбросить значительный объём перебора. Параметры перебираются внутри границ с некоторым шагом. Чем меньше шаг, тем выше точность, но и соответственно больше рассматриваемых вариантов. Подобный набор комбинаций для удобства можно представить в виде n-мерной разреженной матрицы, но алгоритму от этого пользы никакой, поэтому данный набор представлял собой простой связанный список структур параметров.
- Для каждой комбинации параметров выполняется эмуляция работы ТС.
ТС проходит по всему набору котировок и при выполнении условий фиксирует совершение сделок покупки/продажи. При этом подсчитывается общий финансовый результат работы ТС. После завершения эмуляции финансовый результат сохраняется.
- После завершения обработки всех комбинаций параметров среди результатов ищется наилучший. По наилучшей комбинации параметров выполняется ещё одна эмуляция, но на этот раз уже с отображением всех сделок и результатов пользователю.
Первая рабочая версия
После реализации алгоритма и получения первых полезных (для конечного пользователя) результатов оказалось, что работает данный перебор очень медленно.
Перебор выполнялся последовательно в одном потоке и загрузка 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.
На видеокарту перекидывались преобразованные данные о котировках и наборы параметров ТС. Каждая комбинация параметров обрабатывалась отдельным потоком. Т.е. поток на старте считывал свои параметры ТС и далее перебирал всю историю котировок. После обработки всех комбинаций с видеокарты забирались результаты работы.
И тут я начал набивать шишки:
- Алгоритм что-то считал, но считал не то. Результаты совсем не совпадали с эталонными.
После длительной отладки оказалось, что я неверно думал о том что bool занимает 1 байт. По спецификации он разворачивается на устройстве в int и занимает 4 байта. Для устранения неоднозначности я просто поменял тип передаваемых данных на int. - Алгоритм начал выдавать «почти такие же» результаты. И результаты были стабильно немного лучше чем в CPU-версии. Я в очередной раз пересмотрел cl-код и не нашел ошибки. Пришлось перепроверять CPU-версию, и да, ошибка была там. Оказалось, что в процессе оптимизации я отбрасывал вроде бы лишние варианты, которые на самом деле иногда оказывались не лишними. После удаления «оптимизации» из CPU-версии результаты начали совпадать.
- До этого все эксперименты я проделывал на домашнем компе. При проверке на работе оказалось, что приложение умирает после нескольких запусков из-за нехватки памяти. При этом дома всё работало нормально. Выяснилось, что я действительно не освобождал память, но при этом реализация 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 раза.
Спасибо за внимание, буду рад ответить на вопросы. Репорты об опечатках, пропущенных зпт, требования замены дефиса на тире желательно слать в личку.
