САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П. КОРОЛЕВА (национальный исследовательский университет) Якимов Павел Юрьевич, кафедра общей информатики СГАУ 16 марта 2011, Казань Рекуррентная обработка изображений в массивно-многопоточной среде CUDA Применение CUDA для цветовой коррекции и восстановления изображений

Современные параллельные вычислительные системы с общей памятью Использование графических процессоров для вычислений Сравнение кластерных и GPU систем Концепция массивно-многопоточных систем Использование CUDA для задач обработки и анализа изображений Алгоритмы цветовой коррекции и восстановления изображений План доклада 2

Профессиональные системы Многопроцессорные системы с общей памятью (Cray) Кластерные системы с распределенной памятью на основе SMP узлов Персональные системы ПК на основе многоядерных CPU Системы на основе GPU и гибридные CPU/GPU системы Облачные вычислительные системы и GRID Параллельные вычислительные системы 3

Разделяемые между процессами данные Пакет OpenMP для многоядерных систем и суперкомпьютеров Unified Parallel C (George Washington University) – расширение языка С для SMP и NUMA архитектур Intel Thread Building Block – для многоядерных систем Intel Передача сообщений между процессами Библиотека MPI (Message Passing Interface) Библиотека PVM (Parallel Virtual Mashines) Классические парадигмы параллельного программирования 4

Распределенная общая память – Distributed Shared Memory sDSM – распределенная общая память построенная по аналогии с виртуальной памятью RDMA – удаленный прямой доступ к памяти, поддерживается аппаратно в технологии Infiniband Общая память в кластерных системах 5 Платформы с поддержкой DSM – UPC, Cluster Open MP (Intel)

Два уровня параллелизма – параллельные ядра на каждом узле, параллельные узлы Два уровня памяти – «быстрая» память узла на котором выполняется поток; более медленная DSM память на удаленных узлах. Архитектура кластерной системы с многоядерными узлами 6 … Узел 1Узел N … … Потоки узла 1 Потоки узла N … Выч. группа 1 … … Выч. элементы группы 1 Выч. группа N Выч. элементы группы N

General Purpose computation on Graphic Processing Units – Вычисления общего назначения выполняемые на графических процессорах GPGPU 7

На GPU выполняются параллельно десятки тысяч потоков и тысячи из них - одновременно CPU и GPU образуют гибридную систему с обменом данными по шине PCI Express Потоки на GPU группируются в блоки, каждый из которых имеет свою «быструю» разделяемую память Блоки объединяются в сетку (grid) Обмен данными между блоками возможен посредством «медленной» глобальной памяти Все потоки разделяют один код – функцию kernel 8 Основные характеристики GPU как высокопроизводительной системы

OpenCL- Общая парадигма для многопоточных CPU и GPU систем. Основные понятия OpenCL и их CUDA аналоги: OpenCL – обобщение CUDA 9 Понятие параллельной программы OpenCL CUDA эквиалент Ядро (kernel) Хост программа Индексное пространство (NDRange)Сетка (grid) Вычислительный элемент (work item)Нить (thread) Вычислительная группа (work group)Блок (block) Появление: декабрь 2008 в MacOS (Apple и Khronos Group) Текущая аппаратная поддержка: GPU: Nvidia, ATI, S3; встраиваемые CPU VIA, ZiiLabs; Intel Graphics HD, Apple.

Кластерные системы с распределенной общей памятью и GPU системы являются массивно- многопоточными системами (аналогия с OpenCL) Массивно-многопоточные системы 10 Основные элементы: - Вычислительный элемент (поток) - Вычислительная группа (узел или блок) - Индексное пространство (кластер, сетка) … Выч. группа 1 … … Выч. элементы группы 1 Выч. группа N Выч. элементы группы N

Параллельные вычисления в массивно-многопоточных системах 11 Наиболее пригодные для решения задачи с внутренним параллелизмом данных, в частности поэлементная обработка данных (изображений) алгоритмы линейной алгебры сеточные методы и метод конечных элементов рандомизированные и эволюционные алгоритмы mapreduce алгоритмы «Неудобные» задачи: рекурсивные алгоритмы задачи с глобальными зависимостями в данных параллелизм задач возможен на кластере, но не возможен на GPU (пока)

Применение GPU в задачах обработки и анализа изображений 12 Целесообразно применять GPU для решения следующих задач: обработка большеформатных изображений (ДСЗ, полиграфия) обработка нескольких потоков видео в реальном времени сжатие изображений и видео Сложные алгоритмы анализа изображений: идентификация моделей регистрации и воспроизведения изображений поиск ключевых точек с использованием NP полных алгоритмов (таких как RANSAC) рекурсивная обработка в реальном времени системы автоматической навигации с распознаванием

Ретушь большеформатных изображений 13 Задача – коррекция точечных артефактов (блики, пыль) на большеформатных изображениях в полиграфии. Алгоритм поиска артефактов основан на вычислении характеристик изображения в локальном окне. Рекуррентная схема: Обработка по столбцам:Обработка по строкам:

Согласованный доступ к глобальной памяти – нити одного блока обращаются к соседним ячейкам глобальной памяти Потоки группируются в блоки по 32 потока, общее число блоков равно N/32. Каждый поток последовательно читает данные из соседних столбцов изображения. За одну итерацию все блоки обрабатывают 32 строки изображения, формируя в общей памяти фрагмент изображения размерностью 32*N. 14 Схема GPU рекуррентной обработки строк

thread 1 thread 2 thread Пример разбиения на блоки block 1 block N block 3 block 2

Тип алгоритмаm = 5m = 9m = CPU, не рекуррентный283 мс922 мс2 531 мс 2. CPU, рекуррентный142 мс297 мс733 мс 3. GPU, не рекуррентный78 мс262 мс473 мс 4. GPU, рекуррентный (NVIDIA SDK)23 мс25 мс27 мс 5. GPU, рекуррентный с оптимизацией обращений к памяти 12 мс Время работы различных алгоритмов для разных размеров окна (m). 16 Результаты оптимизации обработки изображения скользящим окном

17 Интерфейс программного комплекса

БИХ фильтрация изображений 18 Общий вид БИХ фильтра: БИХ фильтр применим для восстановления и цветовой коррекции изображений. Часть фильтра, зависящая только от входа реализуется по схеме обработки скользящим окном.

GPU реализация рекуррентной части БИХ фильтра 19 Рекурсивная часть БИХ фильтра: Движение блоков по строкам … … Блок выполняет вычисления сдвигаясь вдоль столбца изображения, за одну итерацию обрабатывается одна строка Потоки блока выполняют каскадное суммирование Потоки каждого блока вычисляют выходное значение фильтра выполняя каскадное суммирование

Теоретическая оценка: 20 Ускорение рекурсивной обработки на GPU Скорость обработки видеопотока: Количество и размер кадров видеопотока Время вычислений (мс) для: Intel Core 2 duo E7500 Intel Core 2 quad Q8600 Nvidia GeForce GT 9500 Nvidia GTX x 2Mpix x 2Mpix

Латентность шины PCI Express определяющий фактор при обмене данными м/у CPU и GPU. 21 Обмен между CPU и GPU в задачах обработки видеоданных Оптимизация скорости передачи Режим передачи данных между оперативной памятью CPU и глобальной памятью GPU. Время передачи (мс) для различных размеров (Мб) передаваемого блока 1 Мб50Мб100 Мб 200 Мб400 Mб Синхронный режим, выгружаемая память Синхронный режим, не выгружаемая память Асинхронный режим, выгружаемая память Асинхронный режим, не выгружаемая память

Заключение 22 Использование GPU позволяет получить существенное ускорение для многих алгоритмов обработки изображений Наиболее эффективно применение GPU в задачах с параллелизмом данных Для задач с рекурсивными зависимостями также может быть получена эффективная GPU реализация GPU системы и кластерные системы с распределенной общей памятью имеют общую массивно-многопоточную природу