Секреты невозможных вычислений на GPU09.10.2018 00:02

Наш опыт использования вычислительного кластера из 480 GPU AMD RX 480 при решении математических задач. В качестве задачи мы взяли доказательство теоремы из статьи профессора Чуднова А.М. «Циклические разложения множеств, разделяющие орграфы и циклические классы игр с гарантированным выигрышем». Задача заключается в поиске минимального числа участников одной коалиции в коалиционных играх Ним-типа, гарантирующее выигрыш одной из сторон.

Развитие CPU

Первый процессор, получивший действительно массовое распространение — это 8086 от компании Intel, разработанный в 1978 году. Тактовая частота работы 8086 составляла всего 8 МГц. Спустя несколько лет появились первые процессоры внутри которых было 2, 4 и даже 8 ядер. Каждое ядро позволяло выполнять свой код независимо от других. Для сравнения — современный процессор Intel Core i9–7980XE работает на частоте 2,6 ГГц и содержит 18 ядер. Как видите — прогресс не стоит на месте!

Развитие GPU

Одновременно с развитием центральных процессоров развивались и видеокарты. В основном их характеристики важны для компьютерных игр, там новые технологии проявляются особенно красочно и рендеринг 3D картинки постепенно приближается к фотографическому качеству. В начале развития компьютерных игр расчет картинки выполнялся на CPU, но вскоре был достигнут предел изобретательности разработчиков 3D-графики, ухитрявшихся оптимизировать даже очевидные вещи (хороший пример тому — InvSqrt ()). Так, в видеокартах стали появляться сопроцессоры со специальным набором команд для выполнения 3D вычислений. Со временем число таких команд росло, что, с одной стороны, позволяло гибче и эффективнее работать с изображением, а с другой — усложнило процесс разработки.

С 1996 года начали выпускаться графические ускорители S3 ViRGE, 3dfx Voodoo, Diamond Monster и другие. В 1999 году nVidia выпустила процессор GeForce 256, введя в обиход термин GPU — графический процессор. Он уже универсальный, может заниматься геометрическими расчетами, преобразованием координат, расстановкой точек освещения и работой с полигонами. Отличие GPU от других графических чипов заключалось в том, что внутри, кроме специализированных команд, был набор стандартных команд, с помощью которых можно было реализовать свой алгоритм рендеринга. Это дало значительное преимущество, так как позволило добавлять любые спецэффекты, а не только те, которые уже запрограммированы в видеокарту. Начиная с GeForce 8000/9000 в GPU появились потоковые процессоры — уже полноценные вычислители. Их число варьировалось в зависимости от модели от 16 до 128. В современной терминологии они называются унифицированные шейдерные блоки, или просто шейдерные блоки. В производимых сегодня GPU AMD Vega 64 содержится 4096 шейдерных блока, а тактовая частота может достигать 1536 МГц!

Что содержит в себе GPU

Архитектура GPU отличается от CPU большим количеством ядер и минималистичным набором команд, направленных в основном на векторные вычисления. На уровне архитектуры решены вопросы параллельной работы большого числа ядер и одновременного доступа к памяти. Современные GPU содержат от 2-х до 4-х тысяч шейдерных блоков, которые объединены в вычислительные юниты (Compute Unit). При параллельных вычислениях особенно остро стоит проблема одновременного доступа к памяти. Если каждый из потоковых процессоров попытается выполнить запись в ячейку памяти то эти команду упрутся в блокировку и их необходимо будет поставить в очередь, что сильно снизит производительность. Поэтому потоковые процессоры выполняют команды небольшими группами: пока одна группа производит вычисления, другая загружает регистры и т.д. Также можно объединить ядра в рабочие группы, обладающие общей памятью и внутренними механизмами синхронизации.

Еще одной важной особенностью GPU является наличие векторных регистров и векторных АЛУ, которые могут выполнять операции одновременно для нескольких компонентов вектора. Это в первую очередь нужно для 3D графики, но поскольку наш мир трехмерный, ничто не мешает использовать это для многих физических вычислений. При наличии свободных векторных АЛУ их можно использовать и для вычисления скалярных величин.

Они такие разные, CPU и GPU

Для полноценной работы вычислительной системы важны оба типа устройств. К примеру, мы выполняем пошаговую программу, некий последовательный алгоритм. Там нет возможности выполнить пятый шаг алгоритма, так данные для него рассчитываются на шаге четыре. В таком случае эффективнее использовать CPU с большим кэшем и высокой тактовой частотой. Но есть целые классы задач, хорошо поддающихся распараллеливанию. В таком случае эффективность GPU очевидна. Самый частый пример — вычисление пикселей отрендеренного изображения. Процедура для каждого пикселя почти одинаковая, данные о 3D объектах и текстурах находятся в ОЗУ видеокарты и каждый потоковый процессор может независимо от других посчитать свою часть изображения.

Вот пример современной задачи — обучение нейронной сети. Большое количество одинаковых нейронов необходимо обучить, то есть поменять весовые коэффициенты каждого нейрона. После таких изменений нужно пропустить через нейросеть тестовые последовательности для обучения и получить вектора ошибок. Такие вычисления хорошо подходят для GPU. Каждый потоковый процессор может вести себя как нейрон и при вычислении не придется выстраивать решение последовательным образом, все наши вычисления будут происходить одновременно. Другой пример — расчет аэродинамических потоков. Необходимо выяснить возможное поведение проектируемого моста под воздействием ветра, смоделировать его аэродинамическую устойчивость, найти оптимальные места установки обтекателей для корректировки воздушных потоков или рассчитать устойчивость к ветровому резонансу. Помните знаменитый «танцующий мост» в Волгограде? Думаю, что никто не хотел бы оказаться в тот момент на мосту…

Поведение воздушного потока в каждой точке можно описать одинаковыми математическими уравнениями и решать эти уравнения параллельно на большом количестве ядер.

GPU в руках программистов

Для выполнения вычислений на GPU используется специальный язык и компилятор. Существует несколько фреймворков для выполнения общих вычислений на GPU: OpenCL, CUDA, С++AMP, OpenACC. Широкое распространение получили первые два, но использование CUDA ограничено только GPU от компании nVidia.

OpenCL был выпущен в 2009 году компанией Apple. Позднее корпорации Intel, IBM, AMD, Google и nVidia присоединились к консорциуму Khronos Group и заявили о поддержке общего стандарта. С тех пор новая версия стандарта появляется каждые полтора-два года и каждый привносит все более серьезные улучшения.

На сегодняшний день язык OpenCL C++ версии 2.2 соответствует стандарту C++14, поддерживает одновременное выполнение нескольких программ внутри устройства, взаимодействие между ними через внутренние очереди и конвейеры, позволяет гибко управлять буферами и виртуальной памятью.

Реальные задачи

Интересная задача из теории игр, в решении которой мы принимали участие — доказательство теоремы из статьи профессора Чуднова А.М. «Циклические разложения множеств, разделяющие орграфы и циклические классы игр с гарантированным выигрышем». Задача заключается в поиске минимального числа участников одной коалиции в коалиционных играх Ним-типа, гарантирующее выигрыш одной из сторон.

С математической точки зрения это поиск опорной циклической последовательности. Если представить последовательность в виде списка нулей и единиц, то проверку на опорность можно реализовать логическими побитовыми операциями. С точки же зрения программирования такая последовательность представляет собой длинный регистр, например, 256 бит. Самый надежный способ решения этой задачи — перебор всех вариантов за исключением невозможных по очевидным причинам.

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

Сложность решения этой задачи в переборе огромного числа вариантов. Например, если мы ищем решение для n=25, то это 25 бит, а если n=100, то это уже 100 бит. Если взять количество всех возможных комбинаций, то для n=25 это 2^25=33 554 432, а для n=100 это уже 2^100=1 267 650 600 228 229 401 496 703 205 376 комбинаций. Возрастание сложности просто колоссальное!

Такая задача хорошо распараллеливается, а значит она идеально подходит для нашего GPU кластера.

Программисты vs математики

Изначально математики решали эту задачу на Visual Basic в Excel, так удалось получить первичные решения, но невысокая производительность скриптовых языков не позволила продвинуться далеко вперед. Решение до n=80 заняло полтора месяца… Склоняем голову перед этими терпеливыми людьми.

Первым этапом мы реализовали алгоритм задачи на языке Си и запустили на CPU. В процессе выяснилось, что при работе с битовыми последовательностями многое можно оптимизировать.
Далее мы оптимизировали область поиска и исключили дублирование. Также хороший результат дал анализ генерируемого компилятором ассемблерного кода и оптимизация кода под особенности компилятора. Всё это позволило добиться существенного прироста скорости вычислений.

Следующим этапом оптимизации стало профилирование. Замер времени выполнения различных участков кода показал, что в некоторых ветках алгоритма сильно возрастала нагрузка на память, а также выявилось излишнее ветвление программы. Из-за этого «маленького» недочёта почти треть мощности CPU была не задействована.

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

Вот и наступил этап подготовки программы для решения на GPU и код был модифицирован для работы в несколько потоков. Управляющая программа теперь занималась диспетчеризацией задач между потоками. В многопоточной среде скорость вычисления увеличилась в 5 раз! Этого удалось добиться за счет одновременной работы 4 потоков и объединения функций.

На этом этапе решение производило верные расчеты до n=80 за 10 минут, тогда как в Exсel«e эти расчеты занимали полтора месяца! Маленькая победа!

GPU и OpenCL

Было принято решение использовать OpenCL версии 1.2, чтобы обеспечить максимальную совместимость между различными платформами. Первичная отладка производилась на CPU от Intel, потом на GPU от Intel. Уже потом перешли на GPU от AMD.

В версии стандарта OpenCL 1.2 поддерживаются целочисленные переменные размерностью 64 бита. Размерность в 128 бит ограничено поддерживается AMD, но компилируется в два 64-х битных числа. Из соображений совместимости и для оптимизации производительности было решено представлять число размерностью 256 бит как группу 32-х битных чисел, логические побитовые операции над которыми производятся на внутреннем АЛУ GPU максимально быстро.
Программа на OpenCL содержит ядро — функцию, которая является точкой входа программы. Данные для обработки загружаются с CPU в ОЗУ видеокарты и передаются в ядро в виде буферов — указателей на массив входных и выходных данных. Почему массив? Мы же выполняем высокопроизводительные вычисления, нам нужно много задач, выполняемых одновременно. Ядро запускается на устройстве во множестве экземпляров. Каждое ядро знает свой идентификатор и берет именно свой кусочек входных данных из общего буфера. Тот случай, когда самое простое решение — самое эффективное. OpenCL — это не только язык, но и всеобъемлющий фреймворк, в котором досконально продуманы все мелочи научных и игровых вычислений. Это здорово облегчает жизнь разработчику. Например, можно запустить много потоков, диспетчер задач разместит их на устройстве сам. Те задачи, которые не встали на немедленное исполнение, будут поставлены в очередь ожидания и запущены по мере освобождения вычислительных блоков. У каждого экземпляра ядра есть свое пространство в выходном буфере, куда он и помещает ответ по завершению работы.

Основная задача диспетчера OpenCL — обеспечить параллельное выполнение нескольких экземпляров ядра. Здесь применён накопленный десятилетиями научный и практический опыт. Пока часть ядер загружает данные в регистры, другая часть в это время работает с памятью или выполняет вычисления — в результате ядро GPU всегда полностью загружено.
Компилятор OpenCL хорошо справляется с оптимизацией, но разработчику влиять на быстродействие проще. Оптимизация под GPU идет в двух направлениях — ускорение выполнения кода и возможность его распараллеливания. Насколько хорошо распараллеливается код компилятором зависит от нескольких вещей: количество занимаемых scratch регистров (которые располагаются в самой медленной памяти GPU — глобальной), размер скомпилированного кода (надо поместиться в 32 кб кэша), количество используемых векторных и скалярных регистров.

ComBox A-480 GPU или один миллион ядер

Эта самая интересная часть проекта, когда от Excel мы перешли на вычислительный кластер состоящий из 480 видеокарт AMD RX 480. Большого, быстрого, эффективного. Полностью готового к выполнению поставленной задачи и получению тех результатов, которых мир еще никогда не видел.

Хочется отметить что на всех этапах совершенствования и оптимизации кода мы запускали поиск решения с самого начала и сравнивали ответы новой версии с предыдущими. Это позволяло быть уверенными, что оптимизация кода и доработки не вносят ошибки в решения. Тут нужно понимать, что правильных ответов в конце учебника нет, и никто в мире их не знает.
Запуск на кластере подтвердил наши предположения по скорости решений: поиск последовательностей для n>100 занимал около часа. Было удивительно видеть как на кластере ComBox A-480 новые решения находились за минуты, в то время как на CPU это занимало многие часы.

Всего через два часа работы вычислительного кластера мы получили все решения до n=127. Проверка решений показала, что полученные ответы достоверны и соответствуют изложенным в статье теоремам профессора Чуднова А.М.

Эволюция скорости

Если посмотреть прирост производительности в ходе решения задачи, то результаты были примерно такими:

полтора месяца до n=80 в Excel;
час до n=80 на Core i5 с оптимизированной программой на С++;
10 минут до n=80 на Core i5 с использованием многопоточности;
10 минут до n=100 на одном GPU AMD RX 480;
120 минут до n=127 на ComBox A-480.

Перспективы и будущее

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

Возможные области применения параллельных вычислений:

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

Отдельное направление — облачные вычисления на GPU. Например, такие гиганты как Amazon, IBM и Google сдают свои вычислительные мощности на GPU в аренду. Сегодня с уверенностью можно сказать что будущее высокопроизводительных параллельных вычислений будет принадлежать GPU кластерам.