1 Математическое и алгоритмическое обеспечение параллельных вычислений на графических процессорах на примере задачи распознавания объектов на изображении Научн.руководитель: к.т.н., доцент, Ржеуцкая Светлана Юрьевна Капустин Дмитрий Сергеевич Специальность – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

3 Актуальность исследования (продолжение) Модели программирования графических процессоров (CUDA, OpenCL) – Дают представление о структуре вычислительных устройств – Анализ и сравнение параллельных алгоритмов с помощью экспериментов Модели параллельных вычислений (PRAM, BSP, LogP) – Множество известных параллельных алгоритмов, методов их разработки, анализа и сравнения – Не применимы для графических процессоров без учёта их существенных особенностей

4 Актуальность исследования. Вывод Не существует модели параллельных вычислений, которая учитывает основные особенности графических процессоров и позволяет разрабатывать, анализировать и сравнивать параллельные алгоритмы для них

5 Актуальность исследования. Прикладной аспект Автоматическое тестирование графических приложений – Распознавание элементов интерфейса – Множество алгоритмов обладающих параллелизмом по данным – Важна точность и скорость распознавания

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

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

8 Задачи исследования Анализ архитектурных особенностей и средств программирования графических процессоров, анализ основных моделей параллельных вычислений Разработка универсальной модели параллельных вычислений на графических процессорах, предназначенной для создания, анализа и сравнения параллельных алгоритмов Разработка методов повышения быстродействия параллельных алгоритмов на графических процессорах и их применение к задаче распознавания объектов на изображении Программная реализация параллельных алгоритмов обнаружения объектов на изображении с использованием графических процессоров и их экспериментальная проверка Решение прикладной задачи автоматического функционального тестирования интерактивных графических приложений с использованием разработанных и реализованных алгоритмов распознавания объектов на изображении

9 Абстрактные модели параллельных вычислений PRAM (Parallel Random Access Machine, S. Fortune, J. Wyllie, 1978) BSP (Bulk Synchronous Parallelism, Leslie Valiant, 1990) LogP (Latency, overhead, gap, Processors- Memory, David Culler, 1996)

10 PRAM PRAM – Parallel Random Access Machine (1978, Fortune, Wyllie) Бесконечное число процессоров Общая для всех процессоров память неограниченного объёма (разделяемая память) 123 … Общая память Процессоры

11 PRAM (продолжение) Схема алгоритма в виде ациклического ориентированного графа «операции- операнды» Размер схемы (7) Глубина элемента Глубина схемы (3)

12 PRAM (продолжение) Виды модели по стратегии разрешения конфликтов доступа к памяти: – Concurrent Read, Concurrent Write (CRCW, одновременное чтение при одновременной записи) – Concurrent Read, Exclusive Write (CREW, одновременное чтение при исключительной записи) – Exclusive Read, Concurrent Write (CRCW, исключительное чтение при одновременной записи) – Exclusive Read, Exclusive Write (CRCW, исключительное чтение при исключительной записи)

13 PRAM (продолжение) Теорема Брента: – p – число процессоров – n – размер схемы – d – глубина схемы Work-Time парадигма: N – количество элементов обрабатываемых данных W(N) – рабочая сложность алгоритма S(N) – шаговая сложность алгоритма

14 Программируемые графические процессоры. Архитектуры.

15 Программируемые графические процессоры

16 Программируемые графические процессоры

17 Уточнение и дополнение PRAM CREW (Concurrent Read Exclusive Write) Ограниченное количество процессоров, выполняющиеся по принципу горизонтального параллелизма пучками по процессоров Ограниченный объём разделяемой памяти Все процессоры работают по принципу SIMD (Single Instruction Multiple Data) с одной скоростью flops (Float Operations per Second) Дополнительная операция доступа к общей памяти графического процессора (GRAM) с задержкой flop

18 Абстрактный графический мультипроцессор (АГМ) Множество параметров, учитывающих основные характеристики реальных графических мультипроцессоров:

19 Параметрическая модель параллельных вычислений, учитывающая особенности программируемых графических процессоров R(N) – оценка сложности доступа к общей памяти графического процессора (GRAM) Асимптотическая оценка времени выполнения алгоритма на одном мультипроцессоре :

20 Оценка времени работы алгоритма на одном АГМ в секундах W 0 - рабочая сложность одного процессора R 0 - сложность доступа к GRAM одного процессора

21 Обработка больших массивов данных на графических процессорах Обрабатываемый массив разбивается на блоки, каждый из которых обрабатывается одним АГМ

22 Параметрическая модель параллельных вычислений, учитывающая особенности программируемых графических процессоров Масштабирование вычислений на мультипроцессоры: - количество данных, предназначенных для обработки на одном мультипроцессоре - оценка времени выполнения алгоритма на одном АГМ - количество мультипроцессоров - количество шагов алгоритма в зависимости от объёмов памяти GRAM и памяти констант

23 Параметрическая модель параллельных вычислений, учитывающая особенности программируемых графических процессоров N HD (N) – суммарное количество входных данных алгоритма в байтах N DH (N) – суммарное количество выходных данных алгоритма в байтах Оценка времени выполнения алгоритма на GPU: S HD и S DH - константы скорости передачи данных между RAM и GRAM

24 Параметрическая модель параллельных вычислений, учитывающая особенности программируемых графических процессоров Множество параметров модели, учитывающих основные характеристики реальных графических процессоров: Множество параметров алгоритмов, предназначенных для АГМ с p процессорами, для асимптотической оценки времени выполнения: Множество параметров алгоритмов на графических процессорах для временной оценки времени выполнения:

25 Метод кэширования данных параллельных алгоритмов на программируемых графических процессорах Цель метода: уменьшить количество доступов к GRAM из мультипроцессоров (R(N)) - объём одного элемента данных - количество элементов, которые помещаются в разделяемую память мультипроцессора: a b a b

26 Метод кэширования данных параллельных алгоритмов на программируемых графических процессорах 1. K – количество доступов к GRAM для одного элемента 2. n – количество обрабатываемых элементов через кэш *

27 Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных T CPU – оценка времени вычисления версии алгоритма на центральном процессоре T GPU – оценка времени вычисления параллельного алгоритма на графическом процессоре T GPU-С – оценка времени вычисления параллельного алгоритма на графическом процессоре с кэшированием данных в разделяемой памяти мультипроцессоров Начало Оценка T CPU Оценка T GPU-C Оценка T GPU Расчёт на GPU с кэш-ем Расчёт на CPU Расчёт на GPU Конец Условие * T GPU-C

28 Метод Viola-Jones Вычисление интеграла изображения Поиск объектов на интеграле с помощью классификаторов Группировка результатов поиска

29 Метод Viola-Jones. Интеграл изображения Интеграл изображения – двумерный массив сумм интенсивностей цветов Сумма интенсивностей цветов в произвольном прямоугольнике через интеграл:

30 Метод Viola-Jones. Каскад классификаторов

31 Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с к э шированием интеграла изображения и данных классификаторов Размеры скользящего окна: Максимальная итерация: Начало K>0 Кэширование классификаторов Конец да нет i

32 Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с к э шированием интеграла изображения и данных классификаторов Время работы по итерациям (nVIDIA GeForce 9800 GT, 1024x1024, 838 классификаторов, )

33 Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с к э шированием интеграла изображения и данных классификаторов Сравнение общего времени работы алгоритмов поиска на CPU (Intel Core 2 Duo 2.93 GHz) и GPU

34 Программная реализация. Тестирование в среде CUDA Vision Workbench

35 Программное средство автоматического тестирования интерактивного графического приложения. Структурная схема

36 Программное средство автоматического тестирования интерактивного графического приложения. Результаты тестов ОбъектКоличество классификаторов Tcpu, сTgpu, с Инициализация00, , meduse730, , shell940,299620, crab1030,257740, seashell3440, , star670, , Всего:6811,814771,041001

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

38 Практическая значимость Теоретические и экспериментальные результаты можно применять при разработке, анализе и сравнении параллельных алгоритмов для программируемых графических процессоров различных моделей, а также принимать решение о целевой вычислительной системе в режиме реального времени во время работы программы Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием интеграла изображения и данных классификаторов позволяет повысить быстродействие метода Viola-Jones на ранних итерациях обнаружения С помощью разработанного программного средства автоматического тестирования интерактивных графических приложений с приемлемым временем можно распознавать элементы графического интерфейса, эффективно используя ресурсы графического и центрального процессоров

39 Апробация и публикации Внедрение: – ООО «Плейрикс»: распознавание лиц в изображениях, загружаемых пользователем, для web приложений – ООО «Плейрикс»: автоматическое тестирование графических интерактивных приложений – ВоГТУ, кафедра АВТ: результаты используются в учебном процессе при преподавании курсов «Параллельные вычисления» Опубликовано 11 печатных работ (3 в журналах, рекомендованным ВАК)

40 Результаты работы Проведён обзор аппаратных возможностей и средств программирования графических процессоров. Проведён обзор и анализ основных моделей параллельных вычислений, используемых для разработки, анализа и сравнения параллельных алгоритмов. Предложена параметрическая модель параллельных вычислений на программируемых графических процессорах, предназначенная для создания, анализа и сравнения параллельных алгоритмов для графических процессоров. Проведён анализ возможностей распараллеливания и переноса алгоритмов метода Viola-Jones для обнаружения объектов на изображении на программируемые графические процессоры и выполнена их программная реализация. Выполнена экспериментальная проверка модели параллельных вычислений на графических процессорах с помощью разработанных программных средств. Разработан и реализован программный комплекс автоматического функционального тестирования интерактивных графических приложений с использованием разработанных параллельных алгоритмов распознавания объектов на изображении