close

Вход

Забыли?

вход по аккаунту

?

19 Параметрическая модель параллельных вычислений

код для вставкиСкачать
Капустин Дмитрий Сергеевич
Математическое и алгоритмическое обеспечение
параллельных вычислений на графических
процессорах на примере задачи распознавания
объектов на изображении
Специальность 05.13.11 – Математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
Научн.руководитель: к.т.н.,
доцент, Ржеуцкая Светлана
Юрьевна
1
Актуальность исследования
Особенности графических процессоров
–
–
–
–
–
2
Широкая распространённость
Параллелизм по данным
Обособленность вычислительной системы
Различные виды памяти
Большие задержки при доступе к общей
памяти графического процессора
Актуальность исследования
(продолжение)
Модели программирования графических процессоров
(CUDA, OpenCL)
–
–
Модели параллельных вычислений (PRAM, BSP,
LogP)
–
–
3
Дают представление о структуре вычислительных устройств
Анализ и сравнение параллельных алгоритмов с помощью
экспериментов
Множество известных параллельных алгоритмов, методов их
разработки, анализа и сравнения
Не применимы для графических процессоров без учёта их
существенных особенностей
Актуальность исследования.
Вывод
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, ProcessorsMemory, David Culler , 1996)
PRAM
PRAM – Parallel Random Access Machine
(1978, Fortune, Wyllie)
Процессоры
1
2
3
…
Общая память
10
Бесконечное число процессоров
Общая для всех процессоров память
неограниченного объёма (разделяемая память)
PRAM (продолжение)
Схема алгоритма в виде ациклического
ориентированного графа «операцииоперанды»
1
2
3
Размер схемы (7)
Глубина элемента
4
5
Глубина схемы (3)
6
11
7
PRAM (продолжение)
Виды модели по стратегии разрешения конфликтов
доступа к памяти:
–
–
–
–
12
Concurrent Read, Concurrent Write (CRCW, одновременное
чтение при одновременной записи)
Concurrent Read, Exclusive Write (CREW, одновременное
чтение при исключительной записи)
Exclusive Read, Concurrent Write (CRCW, исключительное
чтение при одновременной записи)
Exclusive Read, Exclusive Write (CRCW, исключительное
чтение при исключительной записи)
PRAM (продолжение)
13
Теорема Брента:
– p – число процессоров
n
T(p) O d – n – размер схемы
p
– d – глубина схемы
Work-Time парадигма:
N – количество элементов обрабатываемых данных
W(N) – рабочая сложность алгоритма
S(N) – шаговая сложность алгоритма
W(N)
T(N, p) O S(N)
p
Программируемые графические
процессоры. Архитектуры.
14
Программируемые графические
процессоры
15
Программируемые графические
процессоры
16
Уточнение и дополнение PRAM
17
CREW (Concurrent Read Exclusive Write)
Ограниченное количество процессоров p p max ,
выполняющиеся по принципу горизонтального
параллелизма пучками по p warp процессоров
Ограниченный объём разделяемой памяти M S
Все процессоры работают по принципу SIMD
(Single Instruction Multiple Data) с одной скоростью S GPU
flops (Float Operations per Second)
Дополнительная операция доступа к общей памяти
графического процессора (GRAM) с задержкой L
flop
Абстрактный графический
мультипроцессор (АГМ)
Множество параметров, учитывающих
основные характеристики реальных
графических мультипроцессоров:
{ p max , p warp , M S , S GPU , L }
18
Параметрическая модель параллельных
вычислений, учитывающая особенности
программируемых графических
процессоров
R(N) – оценка сложности доступа к общей памяти
графического процессора (GRAM)
Асимптотическая оценка времени выполнения
алгоритма на одном мультипроцессоре:
W(N) R(N)
T M (N, p) O ceil
p
19
p
p
warp
S(N)
Оценка времени работы
алгоритма на одном АГМ в
секундах
TM (N, p) W M (N) R M (N) L
S GPU p
p
ceil p
warp
W M (N) W 0 N
R M (N) R 0 N
20
W0 - рабочая сложность одного
процессора
R0 - сложность доступа к GRAM одного
процессора
Обработка больших массивов
данных на графических
процессорах
21
Обрабатываемый массив разбивается на блоки,
каждый из которых обрабатывается одним АГМ
Параметрическая модель параллельных
вычислений, учитывающая особенности
программируемых графических
процессоров
Масштабирование вычислений на
мультипроцессоры:
N TG (N) ceil TM (N' , p)
N'
P
- количество данных, предназначенных для
обработки на одном мультипроцессоре
T - оценка времени выполнения алгоритма на
одном АГМ
P - количество мультипроцессоров
B(N) f(N, M
, M ) - количество шагов алгоритма в
зависимости от объёмов памяти GRAM и памяти
констант
N'
M
22
GPU
C
Параметрическая модель параллельных
вычислений, учитывающая особенности
программируемых графических
процессоров
NHD(N) – суммарное количество входных данных алгоритма в
байтах
N (N) N (N)
B(N)
i
HD
HD
i 1
NDH(N) – суммарное количество выходных данных алгоритма
в байтах
N (N) N (N)
B(N)
i
DH
DH
i 1
Оценка времени выполнения алгоритма на GPU:
TGPU (N) N HD (N)
S HD
B(N)
TG (N) i
i 1
N DH (N)
S DH
SHD и SDH - константы скорости передачи данных между RAM
и GRAM
23
Параметрическая модель параллельных
вычислений, учитывающая особенности
программируемых графических
процессоров
Множество параметров модели, учитывающих основные
характеристики реальных графических процессоров:
{ p max , p warp , M S , S GPU , L , P , M C , M GPU , S HD , S DH }
Множество параметров алгоритмов, предназначенных для
АГМ с p процессорами, для асимптотической оценки
времени выполнения:
{W ( N ), S ( N ), R ( N )}
Множество параметров алгоритмов на графических
процессорах для временной оценки времени выполнения:
{W M ( N ), R M ( N ), N HD ( N ), N DH ( N )}
24
Метод кэширования данных параллельных
алгоритмов на программируемых графических
процессорах
Цель метода: уменьшить
количество доступов к GRAM
из мультипроцессоров (R(N))
b
b’
a
a’
n (a' a 1) (b' b 1)
25
- объём одного элемента
данных
Q a' b' - количество
элементов, которые
помещаются в разделяемую
память мультипроцессора:
M0
Q
MS
M0
Метод кэширования данных параллельных
алгоритмов на программируемых графических
процессорах
1.
K – количество доступов к GRAM для одного
элемента
R(N) K N
2.
n – количество обрабатываемых элементов
через кэш
N Q
R C (N) K n
R(N)
1
R (N)
Q
* C
Q a' b'
a a' , b b'
26
n
a' max Q
b' max Q
n max n(a'
a 1
b 1
b 1
a 1
max
)
Q (a 1) (b 1)
2
Алгоритм принятия решения о целесообразности переноса
вычислений на графический процессор и использования
разделяемой памяти мультипроцессоров для кэширования данных
Начало
TCPU – оценка времени вычисления версии
алгоритма на центральном процессоре
Оценка TCPU
TGPU – оценка времени вычисления
параллельного алгоритма на графическом
да
Условие *
нет
процессоре
параллельного алгоритма на графическом
Оценка TGPU
Оценка TGPU-C
TGPU-С – оценка времени вычисления
процессоре с кэшированием данных в
да
TGPU-C<TCPU
Расчёт на GPU
с кэш-ем
27
нет да
Расчёт на
CPU
Конец
TCPU<TGPU
нет
Расчёт на
GPU
разделяемой памяти мультипроцессоров
K n
R(N)
1
R (N)
Q
C
*
Q a' b'
a a' , b b'
Метод Viola-Jones
Вычисление интеграла изображения
Поиск объектов на интеграле с
помощью классификаторов
Группировка результатов поиска
28
Метод Viola-Jones. Интеграл
изображения
Интеграл изображения – двумерный массив сумм
интенсивностей цветов
ii ( x , y ) i( x' , y ' )
x ' x , y ' y
Сумма интенсивностей цветов в произвольном
прямоугольнике через интеграл:
ii D ii 4 ii 1 ( ii 2 ii 3 )
29
Метод Viola-Jones. Каскад
классификаторов
30
Параллельный алгоритм обнаружения объектов
на изображении по признакам Хаара с
кэшированием интеграла изображения и данных
классификаторов
Начало
Кэширование
классификаторов
K>0
да
да
Расчёт с
кэшированием
интеграла
31
i<imax
Размеры скользящего
окна:
a f w0
i
b f h0
i
нет
Конец
нет
Расчёт без
кэширования
интеграла
Максимальная
итерация:
i max
log (Q K) 4 Q K 2
2
w0
h0
2K w0
K Q
Параллельный алгоритм обнаружения объектов
на изображении по признакам Хаара с
кэшированием интеграла изображения и данных
классификаторов
Время работы по итерациям (nVIDIA
GeForce 9800 GT, 1024x1024, 838
классификаторов,w 24, h 24, f 1.2, i 5 )
0
0
max
1,4
1,2
T, c
1
0,8
0,6
Tgpu1
Tgpu2
0,4
0,2
0
0
32
2
4
6
8 10 12 14 16 18 20
Iter
Параллельный алгоритм обнаружения объектов
на изображении по признакам Хаара с
кэшированием интеграла изображения и данных
классификаторов
33
Сравнение общего времени работы
алгоритмов поиска на CPU (Intel Core
2 Duo 2.93 GHz) и GPU
Программная реализация.
Тестирование в среде CUDA Vision
Workbench
34
Программное средство автоматического
тестирования интерактивного
графического приложения. Структурная
схема
БД признаков
Модуль
автоматического
ввода
35
Модуль
распознавания
Модуль управления
Буфер экрана
БД алгоритмов
Программное средство автоматического
тестирования интерактивного
графического приложения. Результаты
тестов
Объект
Tcpu, с
Tgpu, с
0
0,002049
0,001944
meduse
73
0,291326
0,164835
shell
94
0,29962
0,199027
crab
103
0,25774
0,186871
seashell
344
0,656194
0,306906
67
0,307841
0,181418
681
1,81477
1,041001
Инициализация
star
Всего:
36
Количество
классификаторов
Научная новизна работы
37
Предложена универсальная параметрическая модель
параллельных вычислений на графических процессорах на
основе модели PRAM, дополненной множеством
существенных параметров графических процессоров
Разработан алгоритм принятия решения о целесообразности
переноса вычислений на графический процессор и
использования разделяемой памяти мультипроцессоров для
кэширования данных, основанный на оценке времени
вычислений с помощью предложенной модели
Разработан параллельных алгоритм для графических
процессоров обнаружения объектов на изображении по
признакам Хаара с кэшированием интеграла изображения и
данных классификаторов
Практическая значимость
38
Теоретические и экспериментальные результаты можно
применять при разработке, анализе и сравнении
параллельных алгоритмов для программируемых
графических процессоров различных моделей, а также
принимать решение о целевой вычислительной системе в
режиме реального времени во время работы программы
Параллельный алгоритм обнаружения объектов на
изображении по признакам Хаара с кэшированием интеграла
изображения и данных классификаторов позволяет повысить
быстродействие метода Viola-Jones на ранних итерациях
обнаружения
С помощью разработанного программного средства
автоматического тестирования интерактивных графических
приложений с приемлемым временем можно распознавать
элементы графического интерфейса, эффективно используя
ресурсы графического и центрального процессоров
Апробация и публикации
39
Внедрение:
– ООО «Плейрикс»: распознавание лиц в изображениях,
загружаемых пользователем, для web приложений
– ООО «Плейрикс»: автоматическое тестирование
графических интерактивных приложений
– ВоГТУ, кафедра АВТ: результаты используются в учебном
процессе при преподавании курсов «Параллельные
вычисления»
Опубликовано 11 печатных работ (3 в журналах,
рекомендованным ВАК)
Результаты работы
40
Проведён обзор аппаратных возможностей и средств программирования
графических процессоров.
Проведён обзор и анализ основных моделей параллельных вычислений,
используемых для разработки, анализа и сравнения параллельных
алгоритмов.
Предложена параметрическая модель параллельных вычислений на
программируемых графических процессорах, предназначенная для создания,
анализа и сравнения параллельных алгоритмов для графических
процессоров.
Проведён анализ возможностей распараллеливания и переноса алгоритмов
метода Viola-Jones для обнаружения объектов на изображении на
программируемые графические процессоры и выполнена их программная
реализация.
Выполнена экспериментальная проверка модели параллельных вычислений
на графических процессорах с помощью разработанных программных
средств.
Разработан и реализован программный комплекс автоматического
функционального тестирования интерактивных графических приложений с
использованием разработанных параллельных алгоритмов распознавания
объектов на изображении
Документ
Категория
Презентации по информатике
Просмотров
52
Размер файла
4 897 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа