Содержание к диссертации
Введение
Глава 1. Анализ абстрактных моделей параллельных вычислений с учетом особенностей графических процессоров 13
1.1. Анализ абстрактных моделей параллельных вычислений 13
1.1.1. Модель PRAM 14
1.1.2. Модель BSP 20
1.1.3. Модель LogP 23
1.2. Анализ особенностей структур программируемых графических процессоров общего назначения 26
1.2.1. Особенности структуры графических процессоров NVIDIA 27
1.2.2. Особенности структуры графических процессоров ATI 31
1.3. Анализ математических моделей графических процессоров и возможностей применения абстрактных моделей параллельных вычислений к графическим процессорам 35
1.4. Анализ возможностей использования графических процессоров в программных средствах автоматического тестирования приложений через интерфейс пользователя 38
Основные выводы 44
Глава 2. Разработка параметрической модели параллельных вычислений на графических процессорах 47
2.1. Параметрическая модель графического мультипроцессора на основе PRAM модели 47
2.2. Разработка модели абстрактного графического процессора 55
2.3. Разработка модели параллельных вычислений на графических процессорах 59
2.4. Использование модели для разработки, анализа и сравнения параллельных алгоритмов на графических процессорах 63
2.4.1. Разработка параллельных алгоритмов 64
2.4.2. Анализ параллельных алгоритмов 66
2.4.3. Сравнение параллельных алгоритмов 69
2.5. Применение модели в средствах программирования графических процессоров 71
2.5.1. Использование модели в CUDA 71
2.5.2. Использование модели в OpenCL 73
2.5.3. Использования модели для принятия решения об используемой вычислительной системе 74
Основные выводы 75
Глава 3. Разработка методов повышения производительности параллельных алгоритмов за счет эффективного использования объединенных ресурсов центрального и графического процессоров 77
3.1. Анализ возможностей кэширования данных в различных видах памяти графического процессора 77
3.2. Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных 81
3.3. Применение полученных результатов к задаче фильтрации изображений 86
Основные выводы 93
Глава 4. Разработка программного компонента распознавания элементов интерфейса пользователя в средстве автоматического тестирования графических приложений 94
4.1. Средство автоматического тестирования графических приложений 94
4.2. Разработка и реализация параллельного алгоритма вычисления интегрального представления изображения 96
4.3. Разработка и реализация параллельного алгоритма поиска объектов на интегральном представлении изображения 110
4.4. Разработка и реализация параллельного алгоритма группировки результатов поиска объектов по положению и размеру 124
4.5. Анализ результатов экспериментов 126
4.6. Реализация программного компонента для распознавания произвольных элементов интерфейса пользователя с использованием графического процессора и результаты его работы 127
Основные выводы 130
Заключение 131
Список сокращений и условных обозначений 132
Список терминов 133
Список литературы 134
Приложения 146
- Особенности структуры графических процессоров NVIDIA
- Разработка модели параллельных вычислений на графических процессорах
- Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных
- Разработка и реализация параллельного алгоритма поиска объектов на интегральном представлении изображения
Введение к работе
Актуальность темы исследования. Современные программируемые графические процессоры общего назначения (GPU) спроектированы таким образом, чтобы выполнять не только графические вычисления, но и вычисления общего назначения. Графические адаптеры обычно имеют в своем составе несколько сотен скалярных процессоров, частота которых сравнима с частотой ядер центральных процессоров (CPU), а также собственную память с иерархической организацией. Таким образом, GPU представляют собой мощное дополнение CPU, но для того, чтобы эффективно использовать их возможности в процессе разработки программного обеспечения, нужно учитывать существенные особенности GPU.
Во-первых, графические процессоры обладают параллелизмом по данным, т.е. все скалярные процессоры выполняют параллельно одинаковые инструкции над различными данными. Перенос на графический процессор алгоритмов, не допускающих распараллеливания по данным, не даст ощутимого повышения производительности. Во-вторых, при переносе вычислений на графический процессор необходимо учитывать пропускную способность различных видов памяти GPU и рационально использовать каждый вид памяти в целях повышения производительности.
В силу указанных особенностей перенос вычислений на GPU требует серьезной проработки на алгоритмическом уровне. В настоящее время существует несколько моделей программирования графических процессоров (CUDA, OpenCL), однако в доступных источниках информации не имеется сведений о математических моделях, с помощью которых можно разрабатывать, сравнивать и анализировать параллельные алгоритмы для GPU без их трудоемкой программной реализации. Безусловно, разработка алгоритмов для графических процессоров может быть значительно упрощена при использовании опыта распараллеливания вычислений для центральных процессоров на основе известных моделей. К сожалению, ни одна из них не может быть применена к графическим процессорам напрямую в силу значительных отличий архитектур CPU и GPU. Исходя из вышеизложенного, актуальной является задача адаптации известных моделей параллельных вычислений к специфике GPU.
Графические процессоры позволяют эффективно решать многие вычислительно ёмкие задачи. Одна из таких задач обозначилась в последние годы в связи с появлением многочисленных программных средств, предназначенных для автоматизации тестирования программных продуктов. В процессе автоматического тестирования приложений через графический интерфейс пользователя программное средство должно имитировать действия человека-оператора, выполняющего «ручное» тестирование, на основе распознаваемых экранных объектов (элементов интерфейса). При этом время, затрачиваемое средством на получение этих данных и принятие решения, должно быть не больше среднего времени реакции человека в приложении.
Современные средства автоматического тестирования имеют в своем составе программный компонент для распознавания элементов интерфейса пользователя, однако в подавляющем большинстве случаев он позволяет распознавать только стандартные интерфейсные элементы (кнопки, поля ввода и т.д.). В последние годы появились программные средства для распознавания произвольных графических экранных объектов (Sikuli, eggPlant), но эта функция выполняется с ощутимым замедлением, что не позволяет выполнить полноценное автоматическое тестирование графических приложений с большим количеством элементов интерфейса. Принимая во внимание высокую трудоемкость алгоритмов распознавания образов и потенциальную возможность их распараллеливания по данным, актуальной является задача разработки быстродействующего программного компонента для распознавания произвольных элементов интерфейса пользователя, реализующего алгоритмы параллельных вычислений на GPU.
Развитию существующих моделей параллельных вычислений посвящены работы S. Fortune, J. Wyllie, L. Valiant, B.B. Воеводина, B.C. Любченко. Специфика вычислений на графических процессорах представлена в работах S. Hong, H.Kim, А. Берилло, В. Фролова. Вопросы автоматического тестирования программ рассмотрены в работах И.В. Винниченко, В.В. Липаева, Г.Л. Гриппы.
Объектом диссертационного исследования являются параллельные вычисления на программируемых графических процессорах общего назначения.
Предметом диссертационного исследования являются модели, методы и алгоритмы эффективных параллельных вычислений на графических процессорах.
Цель диссертационного исследования заключается в повышении производительности параллельных вычислений за счет эффективного использования объединенных ресурсов центрального и графического процессоров применительно к задаче распознавания элементов пользовательского интерфейса в процессе автоматического тестирования графических приложений.
Основные задачи исследования:
-
Разработка модели параллельных вычислений на графических процессорах, предназначенной для разработки, анализа и сравнения алгоритмов.
-
Разработка методов повышения быстродействия параллельных алгоритмов на графических процессорах и их применение к задаче распознавания произвольных графических элементов интерфейса пользователя.
-
Программная реализация параллельных алгоритмов распознавания элементов интерфейса пользователя с использованием GPU и их экспериментальная проверка.
-
Применение реализованных алгоритмов в программных средствах автоматического тестирования графических приложений.
Методы исследования. При выполнении работы использованы методы математического анализа и линейной алгебры, теории множеств, теории параллельных вычислений, теории графов, методы анализа алгоритмов.
Положения, выносимые на защиту:
1. Параметрическая модель параллельных вычислений на графических
процессорах, представляющая собой уточнение и дополнение известной модели
параллельных вычислений PRAM в соответствии с существенными особенностями
графических процессоров.
2. Алгоритм принятия решения о целесообразности переноса вычислений на
графический процессор и использования разделяемой памяти мультипроцессоров для
кэширования данных.
-
Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием данных классификаторов и интегрального представления изображения в памяти графического процессора.
-
Программный компонент для средств автоматического тестирования графических приложений, выполняющий распознавание произвольных элементов пользовательского интерфейса с использованием графических процессоров.
Научная новизна работы.
-
Предложена параметрическая модель параллельных вычислений на графических процессорах на основе модели PRAM, учитывающая все основные параметры графических процессоров. В отличие от известных моделей программирования графических процессоров данная модель позволяет выполнять анализ алгоритмов для графических процессоров без их программной реализации, используя опыт распараллеливания вычислений на основе PRAM-модели.
-
Разработан алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных, основанный на оценке времени вычислений с помощью предложенной модели. Принятие решения о переносе вычислений может быть выполнено в автоматическом режиме.
-
Разработан параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием данных классификаторов и интегрального представления изображения в памяти графического процессора, позволяющий сократить время обнаружения объектов по сравнению с известными алгоритмами метода Viola-Jones.
-
Разработан быстродействующий программный компонент для распознавания элементов графического интерфейса пользователя, позволяющий существенно расширить круг графических приложений, которые могут быть протестированы в автоматическом режиме.
Обоснованность и достоверность полученных результатов обеспечивается корректностью применяемого математического аппарата, строгими доказательствами предложенных утверждений, результатами вычислительного эксперимента.
Практическая значимость работы заключается в том, что теоретические и экспериментальные результаты можно применять в целях упрощения и ускорения процессов разработки, анализа и сравнения параллельных алгоритмов для программируемых графических процессоров различных моделей, а также принимать решение об используемой вычислительной системе в автоматическом режиме непосредственно во время работы программы. Разработанный программный компонент для распознавания элементов графического интерфейса пользователя, включающий в себя параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием данных классификаторов и интегрального представления изображения, позволяет повысить производительность средств автоматического тестирования графических приложений, эффективно используя объединенные ресурсы графического и центрального процессоров.
Реализация результатов исследования. Теоретические и практические результаты диссертационной работы используются в программных средствах ООО «Плейрикс» и НИП «Адрэм», что подтверждено актами о внедрении. Кроме того, результаты работы используются в учебном процессе кафедры «Автоматика и вычислительная техника» Вологодского государственного технического университета при преподавании курса «Структуры и алгоритмы обработки данных».
Материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы в рамках проектов «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры» и «Методология построения интеллектуальных агентно-ориентированных комплексов для многоуровневой подготовки специалистов технического профиля».
Апробация результатов исследования. Основные результаты работы докладывались и получили положительную оценку на следующих конференциях, симпозиумах и семинарах: Всероссийская научно-практическая конференция «Информационно-телекоммуникационные технологии» (Москва, 2010 г.), Всероссийская научная конференция студентов и аспирантов «Молодые исследователи - регионам» (Вологда, 2008, 2009 гг.), Всероссийская конференция «Вузовская наука - региону» (Вологда, 2008, 2009, 2010 гг.), семинар вологодского отделения РАН по искусственному интеллекту (Вологда, 2010 г.), городской семинар «Информатика и компьютерные технологии» (Санкт-Петербург, 2012 г.).
Публикации. По материалам диссертационного исследования опубликовано 11 печатных работ, из них три в журналах, включенных в перечень ВАК.
Структура диссертационной работы. Работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений. Текст изложен на 146 страницах, содержит 36 рисунков и 2 таблицы. Библиографический список включает 105 наименований. В приложениях представлены акты о внедрении результатов диссертационной работы.
Особенности структуры графических процессоров NVIDIA
Впервые архитектура G80 была представлена в ноябре 2006 года [84] и получила распространение сразу в нескольких вариантах графических процессоров, отличающихся количеством устанавливаемых на них мультипроцессоров [10]. Мультипроцессор состоит из следующих компонентов (рисунок 1.3) [56]:
1) 8 унифицированных скалярных процессоров (SP, Stream Processor), позволяющих выполнять как операции над целыми числами, так и над числами с плавающей запятой;
2) 2 блока для вычисления трансцендентных функций с одинарной точностью (SFU, Super Function Unit);
3) блок разделяемой памяти;
4) блок управления потоками
5) кэш-память констант;
6) регистры общего назначения (RF, Register File).
Все скалярные процессоры работают в режиме SIMD, выполняя при этом блок потоков (в G80 количество потоков в блоке равно 32), называемые warp (пучок). При этом за 4 такта мультипроцессора обрабатываются сразу все потоки пучка при исполнении операций с плавающей запятой, с двойной точностью - за 32 такта, и трансцендентных функций - за 16 тактов. Количество потоков на мультипроцессор ограничено. Чтобы синхронизировать потоки, разработаны специальные инструкции, прерывающие выполнение пучка и запускающие следующие пучки в очереди, до тех пор, пока не прервутся все пучки. За счёт такого механизма достигается пороговая синхронизация с минимальными затратами времени. Обычно она предназначена для коммуникации скалярных процессоров через разделяемую память.
При вычислениях на мультипроцессоре, кроме данных из глобальной памяти, используется два дополнительных вида памяти: память констант и разделяемая память. Память констант предназначена только для чтения. Она хранится в видеопамяти и кэшируется на мультипроцессоре по 8 Кб (общий объём для всех мультипроцессоров ограничен и составляет 64 Кб; для всех мультипроцессоров память констант одинакова). Задержка при обращении к ней может составлять такое же время, как и при обращении к глобальной памяти при кэш-промахе, но, если есть кэш-попадание, то операция обращения к памяти будет осуществлена за 2 такта мультипроцессора [48]. Разделяемая память предназначена для чтения /записи и организована в виде банков памяти (по 16 или 32), к каждому из которых может быть произведено обращение за 2 такта. Запрос на обращение к общей памяти получает весь пучок. При этом могут возникнуть запросы сразу к одному банку разделяемой памяти, что повлечёт за собой возникновение конфликта и упорядочивание запросов в очередь с увеличением времени обращения к данным банков для всего пучка. Поэтому важно при создании алгоритмов учитывать когерентность запросов [1]. Объём разделяемой памяти также ограничен (16 Кб), но в более поздних версиях графических процессоров (Compute Compatibility 2.x) его можно настраивать в зависимости от задачи. В процессе исследования различных видов доступа к кэш-памяти было выявлено, что необходимое количество тактов может серьёзно варьироваться [105].
Мультипроцессоры стали основным компонентом структур следующих поколений графических процессоров NVIDIA (GT200 [85], Fermi [86])
Для программирования графических процессоров NVIDIA используется гетерогенная модель CUDA [34, 87]. CUDA включает модель программирования параллельных вычислений на суперскалярных архитектурах, а также библиотеки, компилятор и расширения для нескольких языков высокого уровня. Общая схема работы CUDA представлена на рисунке 1.5.
Если в качестве Device выступает графический процессор, то на размеры раздела и блоков накладываются ограничения. Каждый блок выполняется на отдельном мультипроцессоре независимо от других блоков. Поэтому ширина и высота блока определяются максимальным количеством одновременно обрабатываемых потоков на мультипроцессоре. В свою очередь при выполнении блоки разбиваются на пучки по 32 потока, запускаемые в соответствии с командами блока управления потоками мультипроцессора. Коммуникация между потоками в блоке осуществляется с помощью разделяемой памяти и барьерной синхронизации потоков.
Разработка модели параллельных вычислений на графических процессорах
Модель абстрактного графического процессора позволяет создавать параллельные алгоритмы для существующих графических процессоров, а также оценивать время их выполнения с учётом существенных особенностей графических процессоров. Тем не менее, графические процессоры - это только вычислительные устройства, которые не могут работать без управляющих команд. Роль управляющего устройства в большинстве случаев выполняет центральный процессор компьютера (CPU). Основными функциями CPU являются:
1) инициализация графического процессора, к которым относятся действия, связанные с получением информации о графическом процессоре, его основных характеристиках, в том числе введенных в качестве параметров модели абстрактного мультипроцессора и графического процессора. Эти функции необходимо производить в начале выполнения программы, использующей графические процессоры в качестве вычислительного устройства. Время выполнения этих функций не существенно для оценки в модели, поэтому они не включены в неё;
2) копирование исходных данных в графический процессор. Копирование необходимо производить в связи с тем, что скалярные процессоры не могут напрямую обращаться к оперативной памяти компьютера, а только к глобальной памяти и памяти констант графического процессора;
3) копирование данных результата вычислений в оперативную память компьютера. Данная функция также необходима CPU, т.к. результаты вычислений на графическом процессоре не могут быть напрямую записаны в другой вид памяти, отличный от глобальной памяти графического процессора;
4) инициализация и запуск ядра. К инициализации относится компилирование исходного кода ядра, если он не представлен в байт-коде, разбиение вычислений на этапы и разбиение каждого этапа на вычислительные блоки, выполняемые на отдельных мультипроцессорах. Запуск ядра производится для конкретного этапа параллельного алгоритма с конкретными данными о вычислительных блоках.
Вследствие введения управляющего устройства в виде центрального процессора, модель параллельных вычислений на графических процессорах должна иметь гетерогенную структуру, учитывающую не только особенности графического процессора, но и центрального процессора, на котором тоже могут быть выполнены аналогичные параллельные вычисления в виде последовательного выполнения потоков.
Для вычислений на графическом процессоре необходимо передать исходные данные, произвести сами вычисления и получить данные результатов из глобальной памяти графического процессора. Все эти три этапа требуют определённого времени. Поэтому, чтобы учесть центральный процессор в модели, необходимо ввести дополнительные параметры:
1) скорость работы центрального процессора. Данный параметр необходим для оценки времени выполнения последовательной версии алгоритма на CPU. Существует довольно много вариантов оценок времени работы алгоритма на центральных процессорах [33], которыми можно воспользоваться для оценки TS(N) на CPU. В данной модели основной единицей измерения скорости вычислений является число элементарных операций в секунду, что позволяет провести оценку времени выполнения в секундах на основе количества совершаемых элементарных операций над числами с плавающей запятой одинарной точности. Поэтому целесообразно скорость работы центрального процессора выразить в количестве элементарных операций в секунду. Обозначим эту скорость как Scpu ;
2) скорость передачи данных из оперативной памяти компьютера в глобальную память графического процессора. Данный параметр отвечает за пропускную способность передачи данных с host на device. Поэтому обозначим его как SHD байт/с;
3) скорость передачи данных из глобальной памяти графического процессора в оперативную память компьютера. Данный параметр отвечает за пропускную способность передачи данных с device на host. Поэтому обозначим его как SDft байт/с. Не смотря на то, что данные передаются по одной и той же шине, связывающей CPU и GPU, значения в прямом и в обратном направлении могут различаться на некоторых архитектурах, поэтому его необходимо ввести в модель.
Структурная схема модели параллельных вычислений на графических процессорах представлена на рисунке 2.3.
Предложенная модель не является исчерпывающей по отношению к центральным процессорам, т.к. направлена на оценку времени вычислений на графических процессорах. Поэтому в ней не учитывается количество ядер центрального процессора, уровни кэширования и пропускная способность оперативной памяти. Все эти факторы должны быть отражены в параметрах Scm , SHD viSDH. При малых объёмах данных или при других условиях, ограничивающих применение всех скалярных процессоров графического адаптера, вычисление на центральном процессоре может оказаться быстрее, чем на графическом процессоре. Поэтому важна предварительная верхняя оценка времени работы параллельного алгоритма на графическом процессоре в среде CPU-GPU.
Таким образом, модель параллельных вычислений на графических процессорах содержит множество параметров самой системы и параллельных алгоритмов, выполняемых на ней. Для анализа и сравнения таких алгоритмов требуется сравнение оценок времени работы как последовательной реализации на CPU, так и параллельной на GPU.
Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных
Объём глобальной памяти графического процессора и памяти констант определяют количество этапов параллельного алгоритма (см. 2.4.1), поэтому стратегия использования данных видов памяти должна быть заложена программистом изначально при проектировании алгоритма. Однако для любого этапа этого параллельного алгоритма эффективное использование разделяемой памяти мультипроцессоров может дать существенный выигрыш в производительности этапа, независимо от разбиения этого алгоритма на этапы. Рассмотрим обобщённый метод кэширования данных для разделяемой памяти АГМ, который позволяет повысить производительность вычислений на мультипроцессорах за счёт уменьшения количества обращений к глобальной памяти графического процессора при общих исходных данных. Этот метод используется во многих параллельных алгоритмах для графических процессоров, но обычно параметры подбираются экспериментальным путём [80]. При рассмотрении метода сделан акцент на оценку времени выполнения этапа алгоритма, что позволяет в режиме реального времени принимать решение о выборе алгоритма с кэшированием данных в разделяемой памяти или алгоритма без кэширования.
При разбиении параллельного алгоритма для графического процессора па этапы одним из условий является возможность реализации каждого этапа на одном мультипроцессоре, который последовательно обрабатывает блоки исходных данных. Организация и структура самих исходных данных зависит от программиста, но в рассмотренных средствах программирования графических процессоров особое внимание уделяется матричному представлению данных, т.к. с его помощью можно представить линейную область данных, а также достаточно легко перейти к трёхмерному представлению данных. Это объясняется тем, что изначально графические процессоры хранили данные в двумерных и трёхмерных текстурах, которые представляют собой матричные массивы данных. Поэтому предпочтительным методом хранения, перемещения и копирования данных в глобальной памяти графического процессора является матричная форма, которую можно представить в виде двумерного массива в памяти. Аналогично, можно представить данные разделяемой памяти мультипроцессора. Тогда рассмотрим общий случай использования разделяемой памяти для кэширования исходных данных из глобальной памяти графического процессора.
Допустим, что один скалярный процессор вычисляет один элемент на основе одного массива исходных данных. Вследствие того, что все массивы исходных данных на графическом процессоре являются двумерными, то требуемую для вычисления такого элемента область памяти исходных данных произвольной формы в двумерном массиве можно ограничить прямоугольной областью с размерами а х Ъ, где а - ширина этой области, а Ъ - высота. Допустим, что для расчета одного элемента данных требуется К произвольных обращений к памяти в этой области, то общее число операций обращения к памяти для обработки N элементов данных
Если количество требуемых для вычисления элементов будет кратно максимальному количеству элементов (или программно увеличено до нужного количества за счёт пустых данных), которые можно вычислить с помощью кэшированной области, то формулу (3.5) можно свести к упрощённому виду
Таким образом, количество обращений к GRAM из АГМ в версии с кэшированием, где происходит копирование двумерного массива GRAM в двумерный массив разделяемой памяти с помощью всех процессоров АГМ, должно быть меньше количества обращений в версии без кэширования, а объём кэшированной области должен быть меньше объёма разделяемой памяти мультипроцессора.
Из системы равенств и неравенств (3.7) можно найти значения а и Ь , при котором достигается максимальное значение количества обрабатываемых элементов птах. Для этого выразим из (3.3) значение Ь и подставим в (3.4)
Система равенств и неравенств (3.7) является критерием принятия решения о целесообразности использования кэширования на каждом этапе параллельного алгоритма для графического процессора. Тем не менее, для принятия решения об используемой вычислительной системе необходимо оценивать время выполнения этапа параллельного алгоритма с учётом (3.5). Алгоритм принятия решения о целесообразности переноса вычислений алгоритма на графический процессор с учётом описанного метода кэширования данных в разделяемой памяти мультипроцессора изображён на рисунке 3.3.
Замечание 3.1. Представленный метод предполагает использование исходных данных в виде двумерных массивов. Переход к одномерной версии может быть осуществлён путём приравнивания высоты b к 1. Трёхмерная версия метода может быть расценена как двумерная с одним элементом данных в виде массива элементов исходных данных.
Замечание 3.2. Если для обработки одного элемента требуется большее количество матриц исходных данных, то необходимо проверить критерий (3.7) для каждой из них с учётом объёма разделяемой памяти, которая должна вместить все кэшируемые данные всех матриц. Если для какой-либо матрицы критерий соблюдаться не будет, то необходимо корректировать параллельный алгоритм для АГМ, убирая кэширование данной матрицы.
Разработка и реализация параллельного алгоритма поиска объектов на интегральном представлении изображения
Оценим время работы алгоритма на каждой из вычислительных систем (CPU, GPU, GPU с кэшированием в разделяемой памяти):
а) Оценка времени выполнения алгоритма поиска объектов на интегральном представлении изображения на CPU
Основу поиска объектов на изображении по методу Viola-Jones составляют признаки Хаара прямоугольной формы. Для вычисления одного такого признака требуется нахождение трёх интенсивностей прямоугольников пикселей, умноженных на весовой коэффициент:
Далее признаки Хаара формируют собой каскад, который уже определяет, находится ли объект в заданной области или не находится. При обучении каскада у каждого признака Хаара есть свой порог срабатывания, при котором к сумме каскада суммируется дополнительная величина в зависимости от значения признака (при этом само значение порога умножается на коэффициент светокоррекции [52]):
Таким образом, для вычисления каскада классификаторов необходимо выполнить 12 стах сложений, 4 стах умножений и стад сравнений. Затем данная сумма сравнивается с пороговым значением каскада, и если она больше его, то делается вывод о том, что каскад обнаружил объект. Последовательность таких каскадов позволяет определить сложные объекты на изображении. Если общее число признаков Хаара во всех каскадах обозначить как стах, то в совокупности для них требуется 21 сшк элементарных операций (при условии, что на одно умножение требуется 2 элементарных операции). Тогда общее количество операций, требуемых для обнаружения объекта по интегральному представлению изображения при условии, что в каждом скользящем окне будет обнаружен объект, можно оценить по следующей формуле:
Графики теоретической и экспериментальной оценки времени приведены на рисунке 4.11 (размер скользящего окна w0 - 24 на /г0=24, коэффициент масштабирования / = 1.2, стах=2913 классификаторов). На изображении размерами 1024 на 1024 всего было обнаружено 637 возможных областей нахождения объекта. Именно поэтому график экспериментальной оценки находится намного ниже теоретической, т.к. на практике количество положительных результатов поиска объектов на изображении очень мало по сравнению с количеством обрабатываемых скользящих окон, и заранее предсказать количество найденных объектов невозможно. Тем не менее, для сравнения производительности алгоритмов необходимо рассчитывать максимально возможную оценку времени выполнения, т.е. такую, при которой каждое скользящее окно будет считаться возможной областью нахождения объекта. Именно она отображает пиковую производительность рассматриваемого алгоритма.
Оценка времени выполнения алгоритма поиска объектов на интегральном представлении изображения на GPU без кэширования
При реализации параллельного алгоритма поиска объектов на интегральном представлении изображения очевидным решением является перенос обработки каждого скользящего окна на отдельный скалярный процессор, т.е. один АГМ может обработать максимально рта окон, при этом рабочая сложность будет равна WM{N) = 17 р-стгх (на умножение и сложение требуется одна элементарная операция). Однако графический процессор не умеет работать с динамическими массивами данных, поэтому требуется способ передачи результатов обработки на центральный процессор. Это достигается за счёт использования дополнительного массива, каждый элемент которого представляет собой простое битовое значение, в которое записывается 1 при обнаружении объекта в данном скользящем окне и 0 при отсутствии его. Далее этот массив на каждой итерации передаётся на центральный процессор, который уже составляет массив результатов обработки аналогичный массиву результатов при обработке на CPU. Таким образом, объёмы передачи данных между RAM и GRAM при условии, что интегральное представление изображения уже находится в GRAM, будут равны NHD(N) = 0,NDH(N) = I-wh-M0.
Основной проблемой, влияющей на производительность параллельного поиска объектов на АГМ, является обращение к памяти. Действительно, если каждый признак требует 4 обращения к интегральному представлению изображения, 5 обращений к данным прямоугольников (координаты и вес), 1 - к пороговому значению и 2 - к взвешенным суммам, то для всего классификатора требуется 30 обращений к GRAM. В итоге, для обработки спшх классификаторов требуется RM (N) = 30 р стах обращений к GRAM, что уже значительно больше, чем рабочая сложность алгоритма с учётом задержки обращения к памяти. Для оценки времени работы алгоритма на одном АГМ можно воспользоваться формулой:
Т.к. результаты обработки требуется передавать обратно в RAM на каждой итерации, то количество этапов алгоритма будет B(N) = I. Следовательно, для оценки времени выполнения алгоритма поиска объектов на интегральном представлении изображения в системе CPU-GPU можно воспользоваться формулой:
Графики теоретической и экспериментальной оценки времени для р = 256 процессоров с тем же изображением и каскадами классификаторов, что и в эксперименте с CPU, приведены на рисунке 4.12.
Из рисунка видно, что, как и в случае с CPU, график теоретической оценки намного выше экспериментальной, т.к. количество обнаруженных объектов намного меньше рассчитываемых. Тем не менее, сравнивая теоретическую оценку для GPU с теоретической оценкой для CPU можно сделать вывод о том, что у GPU в данном случае будет большая производительность, чем у CPU. Результат эксперимента же показывает обратное - производительность GPU в данном случае ниже CPU. Это можно объяснить тем, что пучки обрабатывают один и тот же код, но на разных данных. Когда большинство скалярных процессоров АГМ получают отрицательный результат и прекращают работать, то остальные процессоры продолжают, вынуждая простаивать закончившие работу процессоры. На центральном процессоре такого не происходит, и он продолжает обрабатывать данные. На рисунке 4.13 приведены графики теоретической и экспериментальной оценки ускорения для CPU и GPU. Таким образом, одним из недостатков данной модели является отсутствие оценки простоя закончивших работу скалярных процессоров АГМ.
Оценка времени выполнения алгоритма поиска объектов на интегральном представлении изображения на GPU с кэшированием классификаторов
Как отмечалось в главе 2, память констант целесообразно использовать для данных, которые являются общими для всех мультипроцессоров. В алгоритме поиска объектов на интегральном представлении изображения такими данными являются каскады классификаторов, поэтому их кэширование должно повысить производительность вычислений на GPU. Объём памяти констант небольшой, тем не менее, для вычислений необходимо, чтобы в неё помещался как минимум один каскад классификаторов. Для хранения одного классификатора требуется 72 байта в 32 разрядной системе (координаты прямоугольников и их веса в 3 признаках Хаара, пороговое значение и два взвешенных коэффициента). Таким образом, максимальное количество классификаторов, которое может быть кэшировано в памяти констант определяется по формуле:
Тогда, если все каскады классификаторов по объёму укладываются в память констант, то из оценки количества обращений к GRAM можно убрать обращения к классификаторам, оставив только обращения к интегральному представлению изображения: RM (N) = 12 cmax. Временем копирования классификаторов в память констант также можно пренебречь при условии, что размеры изображения будут существенно больше числа классификаторов. Общая блок-схема алгоритма поиска объектов с кэшированием классификаторов представлена на рисунке 4.14, при этом количество обращений к памяти констант для доступа к данным классификаторов, которое должно быть оценено на каждом этапе, обозначено как К.
Похожие диссертации на Модели и алгоритмы параллельных вычислений на графических процессорах и их применение в программных средствах автоматического тестирования графических приложений
