Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов С.В. Ковальчук, С.М. Вишняков, А.С. Мордвинцев НИИ НКТ СПбГУ ИТМО

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Антикризисное предложение 2008Научно-исследовательский институт наукоемких компьютерных технологий за GFlop

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Почувствуйте разницу 2008Научно-исследовательский институт наукоемких компьютерных технологий 3

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Решенные задачи 2008Научно-исследовательский институт наукоемких компьютерных технологий 4 Аппроксимация климатических спектров волнения Выделение особых точек на изображении – SIFT (Scale- invariant feature transform) Построение пирамиды Гаусса для изображения Поиск и уточнение экстремумов в пирамиде Вычисление ориентации особых точек Вычисление дескрипторов особых точек Воксели ???

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Пример: климатические спектры волнения 2008Научно-исследовательский институт наукоемких компьютерных технологий 5 Аппроксимация нелинейной функции нескольких аргументов – оптимизация методом линейного случайного поиска (алгоритм класса «б») Массив расчетных спектров волнения Представление спектра Аппроксимация Estimation of prevailed peak position on the data sheet directly Определение числа и положения пиков методом адаптивного случайного поиска с линейной тактикой Оценка значимости выявленных пиков Набор параметров спектров Сглаживание. Определение положения главного пика

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Результаты Получаемая производительность зависит не только от реализации алгоритма, но и от загрузки GPU 2008Научно-исследовательский институт наукоемких компьютерных технологий 6

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Выделение особых точек на изображении – SIFT 2008Научно-исследовательский институт наукоемких компьютерных технологий 7

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Результаты 2008Научно-исследовательский институт наукоемких компьютерных технологий 8

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов CUDA 2008Научно-исследовательский институт наукоемких компьютерных технологий 9

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов

CUDA 2008Научно-исследовательский институт наукоемких компьютерных технологий 11

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов CUDA BrookGPU (Stanford University, 2004) Sh Lib (Waterloo University, ) ATI Close-To-Metal/FireStream SDK (2007) NVidia CUDA (2007) Преимущества CUDA: абстрагирование от терминологии компьютерной графики; SDK разрабатывается производителем «железа»; поддержка высокопроизводительных HPC-акселераторов (Tesla). NVidia GeForce 8800 GTX: 16 мультипроцессоров по 8 ядер 768 Mb памяти 2008Научно-исследовательский институт наукоемких компьютерных технологий 12

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов CUDA BrookGPU (Stanford University, 2004) Sh Lib (Waterloo University, ) ATI Close-To-Metal/FireStream SDK (2007) NVidia CUDA (2007) Преимущества CUDA: абстрагирование от терминологии компьютерной графики; SDK разрабатывается производителем «железа»; поддержка высокопроизводительных HPC-акселераторов (Tesla). NVidia GeForce 8800 GTX: 16 мультипроцессоров по 8 ядер 768 Mb памяти 2008Научно-исследовательский институт наукоемких компьютерных технологий 13

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Конфигурация GPU-устройства 2008Научно-исследовательский институт наукоемких компьютерных технологий 14 Программное ядро Элементы конфигурации Блок Поток Warp

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Отображение вычислительной задачи на GPU 2008Научно-исследовательский институт наукоемких компьютерных технологий 15 Выделение вычислительного ядра Определение конфигурации Загрузка ядра и данных в GPU

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Пример: климатические спектры волнения 2008Научно-исследовательский институт наукоемких компьютерных технологий 16 Аппроксимация нелинейной функции нескольких аргументов – оптимизация методом линейного случайного поиска (алгоритм класса «б») Массив расчетных спектров волнения Представление спектра Аппроксимация Estimation of prevailed peak position on the data sheet directly Определение числа и положения пиков методом адаптивного случайного поиска с линейной тактикой Оценка значимости выявленных пиков Набор параметров спектров Сглаживание. Определение положения главного пика

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Перенос алгоритма на архитектуру GPU Распараллеливание по данным Вычислительное ядро реализует подсчет целевой функции в заданной точке 2008Научно-исследовательский институт наукоемких компьютерных технологий 17

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Измерение производительности Получаемая производительность зависит не только от реализации алгоритма, но и от загрузки GPU 2008Научно-исследовательский институт наукоемких компьютерных технологий 18

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Элементы времени работы Получаемый характер зависимости производительности определяется временем работы ядра 2008Научно-исследовательский институт наукоемких компьютерных технологий 19

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Исследование производительности 2008Научно-исследовательский институт наукоемких компьютерных технологий 20

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Исследование производительности 2008Научно-исследовательский институт наукоемких компьютерных технологий 21

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов «Конвейерный» эффект Отрезки графика, на которых время работы постоянно обусловлены: «конвейерным» эффектом, компенсирующим задержки при чтении данных из памяти устройства; «конвейерным» эффектом, компенсирующим ожидание при чтении из регистра. 2008Научно-исследовательский институт наукоемких компьютерных технологий 22

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Модель производительности Скачки на графике обусловлены «переполнением» ресурсов GPU: 2008Научно-исследовательский институт наукоемких компьютерных технологий 23 nblocks – общее число блоков в конфигурации blockSize – размер блока согласно конфигурации warpSize – размер warpa, зависит от архитектуры M – число мультипроцессоров GPU mWarps – максимальное число warpов, которое может быть одновременно запущено на мультипроцессоре occupancy – определяет максимальное число одновременно работающих warpов, обусловленное распределением ресурсов GPU между потоками

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Модель производительности Рассчитать значение occupancy для ядра можно при помощи CUDA Occupancy Calculator. 2008Научно-исследовательский институт наукоемких компьютерных технологий 24

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Проверка модели производительности 2008Научно-исследовательский институт наукоемких компьютерных технологий 25

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Определение времени t Научно-исследовательский институт наукоемких компьютерных технологий 26

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Итоги Адаптация алгоритма параметрической оптимизации к архитектуре GPU позволяет получить ускорение более 30 раз по сравнению с реализацией без использования GPU Построена модель производительности, позволяющая предсказывать время выполнения ядра Открытые вопросы: расхождение модели с результатами измерений при четном числе warpов в блоке. 2008Научно-исследовательский институт наукоемких компьютерных технологий 27

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Актуальные направления исследований Уточнение и приведение к универсальному виду модели производительности Анализ особенностей адаптации различных классов алгоритмов Исследование методов балансировки при адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Построение сложных вычислительных архитектур с использованием графических акселераторов

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Параллельный алгоритм трассировки лучей для гетерогенных Грид-архитектур, использующих вычислительные акселераторы

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Постановка задачи Перенос вычислительного алгоритма на архитектуру GPU Построение вычислительной системы на основе Грид- архитектуры, использующей вычислительные ресурсы GPU Адаптация алгоритма для Грид-архитектуры Анализ эффективности функционирования вычислительной системы Цель: Определение основных аспектов переноса вычислительных алгоритмов под параллельную Грид- архитектуру, использующую графические акселераторы

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Обратная трассировка лучей Учитывает физические свойства сцены Позволяет неограниченно увеличивать качество получаемой картинки Требует больших вычислительных затрат

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Реализация Для программирования GPU используется высокоуровневое API – CUDA На GPU производится только расчет пересечения луча с объектами vs Алгоритм трассировки лучей полностью переносится на GPU Использование Грид-архитектуры для организации распределенных вычислений Среда: PEG 2 (Parallel Execution GPE)

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Работа распределенного алгоритма

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Балансировка нагрузки при вычислениях на GPU с использованием CUDA

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Проблема GPU изначально предназначены для однородных вычислений над большими объемами данных (трансформация вершин, растеризация примитивов) Для этого идеально подходят SIMD процессоры А как эффективно решать неоднородные задачи?

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Отсутствие балансировки

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

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Проблемы балансировки Требуется когерентность между потоками, работающими в одном warp'е SIMD-процессора Нет асинхронного обмена сообщениями между потоками Сложность синхронизации между потоками, работающими на разных процессорах Атомарные функции появились только начиная с CUDA 1.1, и недоступны на Geforce 8800 GTX и Ultra

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

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Простейшая стратегия балансировки для GPU

Особенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Текущие задачи Реализация алгоритма «глобальной» балансировки (на CPU) Реализация алгоритма «локальной» балансировки (на GPU) Построение теоретической модели времени работы, учитывающей балансировку