Хабрахабр

Секреты невозможных вычислений на GPU

Наш опыт использования вычислительного кластера из 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 вычислений. Со временем число таких команд росло, что, с одной стороны, позволяло гибче и эффективнее работать с изображением, а с другой — усложнило процесс разработки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если представить последовательность в виде списка нулей и единиц, то проверку на опорность можно реализовать логическими побитовыми операциями. С математической точки зрения это поиск опорной циклической последовательности. Самый надежный способ решения этой задачи — перебор всех вариантов за исключением невозможных по очевидным причинам. С точки же зрения программирования такая последовательность представляет собой длинный регистр, например, 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 и код был модифицирован для работы в несколько потоков. Этого удалось добиться за счет одновременной работы 4 потоков и объединения функций. В многопоточной среде скорость вычисления увеличилась в 5 раз!

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

GPU и OpenCL

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

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

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

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

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

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

Проверка решений показала, что полученные ответы достоверны и соответствуют изложенным в статье теоремам профессора Чуднова А.М. Всего через два часа работы вычислительного кластера мы получили все решения до 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 кластерам.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть