автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Модели и алгоритмы параллельных вычислений на графических процессорах и их применение в программных средствах автоматического тестирования графических приложений

На правах рукописи

Капустин Дмитрий Сергеевич

МОДЕЛИ И АЛГОРИТМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА ГРАФИЧЕСКИХ ПРОЦЕССОРАХ И ИХ ПРИМЕНЕНИЕ В ПРОГРАММНЫХ СРЕДСТВАХ АВТОМАТИЧЕСКОГО ТЕСТИРОВАНИЯ ГРАФИЧЕСКИХ ПРИЛОЖЕНИЙ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

5 ДЕК 2013

Санкт-Петербург

2013

005542778

Работа выполнена на кафедре «Автоматика и вычислительная техника» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Вологодский государственный технический университет» (ВоГТУ)

Научный руководитель - Ржеуцкая Светлана Юрьевна, кандидат

технических наук, доцент кафедры «Автоматика и вычислительная техника» ВоГТУ Официальные оппоненты - Куприянов Михаил Степанович

доктор технических наук, профессор, Заслуженный работник высшей школы РФ, декан факультета компьютерных технологий и информатики ФГБОУ ВПО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» (СПбГЭТУ) Ерофеев Сергей Анатольевич

кандидат физико-математических наук, доцент кафедры «Системы и технологии управления» Института информационных технологий и управления ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет» (СПбГПУ) Ведущая организация - Федеральное государственное автономное

образовательное учреждение высшего

профессионального образования «Северный (Арктический) федеральный университет имени М.В. Ломоносова» (САФУ) Защита диссертации состоится «27» декабря 2013 г. в 11:30 на заседании диссертационного совета Д.002.199.01 при Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Санкт-Петербургского института информатики и автоматизации Российской академии наук Автореферат разослан «26» ноября 2013 г.

Ученый секретарь

диссертационного совета Д.002.199.01

кандидат технических наук

Нестерук Филипп Геннадьевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Современные программируемые графические процессоры общего назначения (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, А. Берилло, В. Фролова. Вопросы автоматического тестирования программ рассмотрены в работах И.В. Винниченко, В.В. Липаева, Г.Л. Гриппы.

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

Предметом диссертационного исследования являются модели, методы и алгоритмы эффективных параллельных вычислений на графических процессорах.

Цель диссертационного исследования заключается в повышении производительности параллельных вычислений за счет эффективного использования объединенных ресурсов центрального и графического процессоров применительно к задаче распознавания элементов пользовательского интерфейса в процессе автоматического тестирования графических приложений.

Основные задачи исследования:

1. Разработка модели параллельных вычислений на графических процессорах, предназначенной для разработки, анализа и сравнения алгоритмов.

2. Разработка методов повышения быстродействия параллельных алгоритмов на графических процессорах и их применение к задаче распознавания произвольных графических элементов интерфейса пользователя.

3. Программная реализация параллельных алгоритмов распознавания элементов интерфейса пользователя с использованием GPU и их экспериментальная проверка.

4. Применение реализованных алгоритмов в программных средствах автоматического тестирования графических приложений.

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

Положения, выносимые на защиту:

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

2. Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных.

3. Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием данных классификаторов и интегрального представления изображения в памяти графического процессора.

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

Научная новнзна работы.

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

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

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

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

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

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

Реализация результатов исследования. Теоретические и практические результаты диссертационной работы используются в программных средствах ООО «Плейрикс» и НИП «Адрэм», что подтверждено актами о внедрении. Кроме того, результаты работы используются в учебном процессе кафедры «Автоматика и вычислительная техника» Вологодского государственного технического университета при преподавании курса «Структуры и алгоритмы обработки данных».

Материалы работы использованы в Федеральной целевой программе «Научньт и научно-педагогические кадры инновационной России» на 2009-2013 годы в рамках проектов «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры» и «Методология построения интеллектуальных агентно-ориентированных комплексов для многоуровневой подготовки специалистов технического профиля».

Апробация результатов исследования. Основные результаты работы докладывались и получили положительную оценку на следующих конференциях, симпозиумах и семинарах: Всероссийская научно-практическая конференция «Информационно-телекоммуникационные технологии» (Москва, 2010 г.), Всероссийская научная конференция студентов и аспирантов «Молодые исследователи - регионам» (Вологда, 2008, 2009 гг.), Всероссийская конференция «Вузовская наука - региону» (Вологда, 2008, 2009, 2010 гг.), семинар вологодского отделения РАН по искусственному интеллекту (Вологда, 2010 г.), городской семинар «Информатика и компьютерные технологии» (Санкт-Петербург, 2012 г.).

Публикации. По материалам диссертационного исследования опубликовано 11 печатных работ, из них три в журналах, включенных в перечень ВАК.

Структура диссертационной работы. Работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений. Текст изложен на 146 страницах, содержит 36 рисунков и 2 таблицы. Библиографический список включает 105 наименований. В приложениях представлены акты о внедрении результатов диссертационной работы.

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

В первой главе выполнена постановка задач исследования. В начале главы проведён обзор основных моделей параллельных вычислений. Основой этих моделей является абстрактная модель PRAM (Parallel Random Access Machine), описанная в 1978 году S.Fortune и J.Wyllie. Она представляет собой идеализированную модель синхронной машины с бесконечным числом процессоров и разделяемой памятью, к которой они имеют доступ. Введем несколько определений.

Если размер входных данных алгоритма равен N, то количество шагов (тактов) PRAM машины S(N), необходимых для его исполнения, называют шаговой сложностью алгоритма. Рабочей сложностью параллельного алгоритма W(N) называется количество элементарных операций, выполняемых всеми процессорами на всех шагах алгоритма:

где (Ы) - количество параллельных элементарных операций на шаге <.

Шаговая и рабочая сложность являются характеристиками параллельного алгоритма и не зависят от количества процессоров (оно не ограничено). Чтобы оценить время выполнения алгоритма для входных данных размера N на РЯАМ-машине с р процессорами, используется теорема Брента, которая дает верхнюю оценку временной сложности алгоритма с шаговой сложностью 5(Л0 и рабочей сложностью IV(Ы):

где О - верхняя асимптотическая оценка трудоёмкости алгоритма.

Для анализа алгоритмов на PRAM целесообразно представить их вычисления в виде ациклического ориентированного графа «операции-операнды», по которому можно оценить рабочую и шаговую сложности алгоритма, а также ускорение, определяемого отношением верхней оценки временной сложности последовательной версии алгоритма к верхней оценке временной сложности параллельного алгоритма, и эффективность, определяемую отношением оценки ускорения к числу процессоров в PRAM-машине.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

W(N)= ^ЩЮ,

(1)

В диссертации рассмотрены основные виды (субмодели) PRAM, связанные с различными вариантами обращения к ячейкам разделяемой памяти. Сделан вывод о том, что данная модель подходит для реализации алгоритмов, использующих параллелизм по данным, следовательно, методы, используемые для анализа и оценки параллельных алгоритмов PRAM модели, могут быть применены и для графических процессоров.

Кратко рассмотрены модели параллельных вычислений на центральных процессорах, созданные на основе PRAM: модель массового синхронного параллелизма BSP и LogP, которая описывает распределённые параллельные вычисления. Делается вывод, что ни одна из этих моделей не подходит для разработки эффективных параллельных алгоритмов на графических процессорах.

Выполнен обзор современных программируемых графических процессоров различных архитектур от компаний NVIDIA и ATI, представлены общий принцип работы и средства программирования CUD A, OpenCL. Данные средства являются также и моделями программирования графических процессоров, которые дают представление о структуре GPU, но с их помощью можно разрабатывать, анализировать и сравнивать параллельные алгоритмы для графических процессоров только путем их программной реализации и вычислительного эксперимента.

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

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

Основными структурными элементами программируемого графического процессора являются мультипроцессоры, которые содержат множество скалярных процессоров и разделяемую память (Shared Memory) ограниченного размера. Имеется также общая (глобальная) оперативная память графического процессора (GRAM), в которую могут быть переданы данные из оперативной памяти (RAM). Обращение к GRAM занимает от 300 до 600 тактов скалярного процессора, обращение к Shared Memory выполняется в несколько раз быстрее. Также GPU имеет память констант, которую можно использовать для кэширования глобальных неизменяемых данных.

Учитывая сходство графического мультипроцессора и PRAM машины, в работе представлено параметрическое описание работы графического мультипроцессора на основе PRAM модели с учётом следующих уточнений и дополнений:

1. Все процессоры могут одновременно считывать данные из разделяемой памяти, но запись должна быть монопольной, т.к. порядок изменения ячейки разделяемой памяти при обращении на запись из нескольких скалярных процессоров не определён. Такой вид PRAM называется CREW (Concurrent Read Exclusive Write);

2. Количество скалярных процессоров в графическом мультипроцессоре ограничено сверху (рт„ процессоров). Для выполнения большего числа потоков используется система горизонтального параллелизма, аналогичная горизонтальной структуре в модели BSP: генерируется расписание последовательного исполнения потоков, разбитых на пучки по pwarp скалярных процессоров;

3. Размер разделяемой памяти мультипроцессора ограничен - Ms байт;

4. Все скалярные процессоры работают с одинаковой скоростью по принципу SIMD (Single Instruction, Multiple Data) со скоростью Sapu элементарных операций в секунду;

5. Введена дополнительная операция - обращение к оперативной памяти GRAM графического процессора на чтение или запись. Задержка при обращении L определяется количеством элементарных операций, требуемых при обращении к одному числу одинарной точности в глобальной памяти графического процессора.

Предложенная модель графического мультипроцессора является общей для всех моделей графических процессоров, поэтому она названа абстрактным графическим мультипроцессором (АГМ). Таким образом, для АГМ имеем следующее множество параметров {pm„>Pwarp,Ms,Sam,L}, учитывающих основные

характеристики реальных графических мультипроцессоров. Для разработки параллельного алгоритма под предложенную модель можно воспользоваться тем же методом создания расписания, который применяется в обычной PRAM модели, учитывая изложенные выше уточнения и дополнения. Однако необходимо скорректировать формулу (2) для верхней оценки временной сложности алгоритма на PRAM машине. Т.к. PRAM модель теперь представлена в виде одного АГМ, на котором все скалярные процессоры работают пучками по принципу горизонтального параллелизма, то верхнюю оценку временной сложности алгоритма следует производить по следующей формуле:

T(N,p) = О ( tV(N) _cgjy / \ Р \ + S(N)

1 Р ч РwarP , 7

где ceil - функция округления числа до ближайшего большего целого,

Р Ртах " количество используемых в параллельном алгоритме скалярных процессоров.

г \ \

ceil Р + S(N) (4)

ч Pwarp J J

, Чтобы учесть операции обращения к глобальной памяти графического процессора, необходимо ввести дополнительный параметр алгоритма - сложность обращения к глобальной памяти графического процессора R(N) - это суммарное количество обращений на чтение и запись из глобальной памяти графического процессора, требуемое для обработки N элементов данных. Данный вид операций обязательно присутствует в любом параллельном алгоритме для графических процессоров, который обрабатывает входные данные. Вследствие того, что процессоры работают в режиме SIMD и выполняют команды последовательно пучками по принципу горизонтального параллелизма, формула верхней оценки временной сложности параллельного алгоритма на одном АГМ имеет вид:

I р

Исходя из этой формулы, при прочих равных условиях производительнее будет тот алгоритм, который совершает меньшее количество обращений к GRAM.

Для верхней оценки времени выполнения алгоритма в секундах на одном АГМ

можно воспользоваться следующей формулой:

+ (5)

SGPu'P \ P~»rP J

где WK,(N) - количество элементарных операций одного процессора в PRAM;

RM (N) - количество обращений к GRAM из одного процессора в PRAM.

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

1) М'ари < Мс„,, где Мсри - фактический, а М'ат - объём требуемой глобальной памяти графического процессора для вычисления на / -м этапе алгоритма;

2) М'с < Мс, где Мс - фактический, а М'с - объём требуемой памяти констант для вычисления на / -м этапе алгоритма;

3) между АГМ не требуется синхронизации;

4) все АГМ должны работать со своим участком глобальной памяти графического процессора.

Т.е. количество этих этапов может варьироваться в зависимости от размера обрабатываемых данных и объёмов глобальной памяти и памяти констант графического процессора:

B = f(N,MOPV,Mc). (6)

Для верхней оценки время выполнения этапа необходимо воспользоваться формулой:

n(N) = ceilf^yT:,(N\p), (7)

где N' - размер данных, предназначенных для обработки на одном АГМ;

Р - количество АГМ графического процессора;

Т'м - верхняя оценка времени выполнения i -го этапа алгоритма на одном АГМ по формуле (5).

Кроме введенных параметров алгоритмов часто требуется ещё два параметра, существенно влияющих на время работы алгоритма в сравнении со временем работы алгоритма на одном ядре центрального процессора: объём входных данных этапа в байтах Nhd' и объём выходных данных этапа в байтах NDH'. Тогда общее время работы этапа можно вычислить по формуле:

= + + (8) ■-*//£) DU

где SHa и SD„ - константы скорости передачи данных между RAM и GRAM (байт/с).

Для анализа и сравнения параллельных алгоритмов с помощью предложенной модели необходимо использовать суммарные параметры алгоритма:

1) суммарная шаговая сложность S(N) :

вт

S{N)=Y.S\N)- (9)

(=i

2) суммарная рабочая сложность W(N) :

BIN)

(Ю)

i=]

3) суммарная сложность обращения к глобальной памяти графического процессора !l(N):

«(ЛГ)

R(N)= (11)

4) суммарный объём данных, передаваемых между оперативной памятью компьютера и глобальной памятью графического процессора NHD(N) и NDH (М):

B(N)

NHD{N) = YN'HD(N),

вт (12)

i=l

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

N (N) "Ж> N (N)

= + (13)

В работе представлено обоснование всех приведенных выше зависимостей.

В третьей главе представлен алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных, представленных в виде двумерных массивов (например, изображения).

Вследствие того, что массивы исходных данных для обработки изображений на графическом процессоре являются двумерными, то требуемую для вычисления одного элемента область памяти исходных данных произвольной формы в этом массиве можно ограничить прямоугольной областью размерами а на Ь, где а -ширина области, а Ь - высота. Если для расчета одного элемента данных требуется К обращений к памяти в этой области, то общее число операций обращения к памяти для обработки N элементов:

Я(Ы) = К-М. (14)

Поскольку для обработки одного элемента данных требуется прямоугольная область размерами а на Ь, то область кэширования тоже можно представить в виде прямоугольной области размерами а' на Ь' (на рисунке 1 область кэширования обозначена толстой сплошной линией, а обрабатываемые с помощью этой области элементы - пунктирной), где а' - ширина этой области, а Ь' - высота. Если М0 -объём одного элемента данных, и доступную разделяемую память необходимо использовать полностью, то:

2 = ^', (15)

^ М.

где 2 < —— - количество элементов, которые помещаются в разделяемую память

М0

мультипроцессора.

С помощью этой кэшированной области памяти можно обработать число элементов, вычисляемое по формуле:

п = (а-а + 1) • (Ь'-Ь + 1). (16)

III 1

1 1 1 1 Ь'

— 1

I

£

1—

— — — — £_ —

1

1

1 1

4-►

а'

Рисунок 1 — Область кэширования массива обрабатываемых элементов

Таким образом, можно рассчитать количество обращений к памяти при обработке N элементов данных с использованием кэширования:

N-О

RC(N) =-(17)

п

Для того чтобы такое кэширование повысило производительность вычислений, необходимо, чтобы выполнялись следующие условия:

' R(N)

RC(N) ~~ Q . Q = a'-b' (18)

a<a',b<b'

Из системы равенств и неравенств (18) можно найти значения а' и 6', при котором достигается максимальное значение птах:

= Ф'«J = Ш- №-1)-(Ь-1)У-

На основе формул (19) можно принимать решение о выборе того или иного PRAM алгоритма на каждом этапе вычислений в автоматическом режиме из D алгоритмов, разработанных для / -го этапа.

Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных изображён на рисунке 2.

В четвертой главе показано применение предложенной модели параллельных вычислений на графических процессорах и метода кэширования данных в разделяемой памяти мультипроцессоров при разработке быстродействующего программного компонента для распознавания элементов интерфейса пользователя в процессе автоматического тестирования приложений со сложным графическим интерфейсом. Структурная схема типового программного средства автоматического тестирования графических приложений представлена на рисунке 3.

Модуль (программный компонент) распознавания элементов интерфейса обращается к буферу экрана для доступа к текущему изображению экрана исполняемой программы. После распознавания элементов пользовательского интерфейса он посылает информацию о найденных объектах модулю управления, который, в свою очередь, на основе БД алгоритмов совершает необходимые запросы по автоматическому вводу данных в процессе тестирования (события мыши и клавиатуры). Для того, чтобы автоматическое тестирование выполнялось с той же

скоростью, что и взаимодействие человека с приложением, процесс распознавания и принятия решения о вводе должен выполняться за время не большее времени реакции человека в данном приложении.

Вычисления на Вычисления Вычисления на

вРи с кэш-ем на СРи ори

Конец

Рисунок 2 — Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для

кэширования данных: Т(ти - время вычисления на центральном процессоре, ТОРи - время вычисления на графическом процессоре без кэширования данных, Тори с - время вычисления на графическом процессоре с кэшированием данных

Модуль автоматического ввода

Модуль распознавания

Модуль управления

Рисунок 3 — Структурная схема программного средства автоматического тестирования графического приложения

На практике для многих приложений со сложным графическим интерфейсом производительность известных программных средств распознавания изображений оказывается недостаточной, чтобы обеспечить приемлемое время распознавания.

В целях повышения производительности выбранного метода распознавания Viola-Jones автором предложен модифицированный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием данных классификаторов и интегрального представления изображения в памяти графического процессора. Рассмотрены и другие алгоритмы метода: вычисление интегрального представления изображения с помощью параллельного алгоритма для PRAM (алгоритм scan) и группировка результатов поиска по положению и размерам. Эти алгоритмы тоже могут быть перенесены на GPU для повышения скорости вычислений.

При детектировании объектов вычисляется каскад классификаторов, представляющих собой признаки Хаара прямоугольной формы, в области, называемой скользящим окном — прямоугольная область изображения, размеры и координаты которой меняются дискретно на определённое число пикселей, покрывая при этом всевозможные области нахождения объектов на изображении. Очевидным решением при распараллеливании этого алгоритма на GPU является перенос вычисления каждого скользящего окна на отдельный процессор в PRAM. Но во время работы такого алгоритма производится множество обращений к памяти GRAM, что существенно снижает быстродействие алгоритма. Поэтому для повышения производительности можно воспользоваться памятью констант для кэширования данных классификаторов, и разделяемой памятью мультипроцессора для кэширования данных интегрального представления изображения. Пусть размеры скользящего окна на итерации i определяются выражениями:

где - начальные размеры окна в пикселях;

/ - коэффициент масштабирования.

Подставляя эти значения в первую формулу системы равенств и неравенств (18), можно вычислить итерацию, на которой будет минимальный прирост производительности за счёт кэширования интегрального представления изображения в разделяемой памяти мультипроцессоров:

w' = f -№„,

K = f-K

(20)

\

XQ-K)1 +4QK2 —2-+AT-S

L, <i°g

2-K-w0

\

где К рассчитывается на каждой итерации кэширования классификаторов.

Алгоритм обнаружения объектов на итерации 1 с помощью кэширования классификаторов и интегрального представления изображения показан на рисунке 4.

Рисунок 4 - Блок-схема алгоритма обнаружения объектов с помощью кэширования данных классификаторов и интегрального представления изображения на GPU

Сравнительные результаты работы алгоритмов обнаружения объектов представлены на рисунке 5 (размер скользящего окна 24 на 24 пикселя, коэффициент масштабирования 1.2, 10056 классификаторов). Тестирование проводилось на компьютере с внешней видеокартой nVIDIA GeForce 9800 GT (14 мультипроцессоров с тактовой частотой 1.35 GHz) и процессором Intel Core 2 Duo 2.93 GHz (было задействовано одно ядро).

0 1 2 3 4 5

Мрх

-CPU----GPU

Рисунок 5 - Сравнение быстродействия алгоритмов обнаружения объектов на CPU и GPU

Если переносить вычисления каждого этапа метода на GPU, то происходит повышение быстродействия всего метода. Результаты работы метода Viola-Jones на CPU и GPU представлены на рисунке 6.

CPU----GPU

Рисунок 6 - Сравнение быстродействия метода Viola-Jones на CPU и GPU

Параллельные алгоритмы для графических процессоров, предложенные в данной главе, позволяют повысить производительность методов распознавания элементов графического интерфейса на экране. В таблице 1 представлено среднее время работы алгоритма распознавания для пяти элементов интерфейса пользователя различной сложности на изображении размером 0.25 Мрх (мегапикселей), генерируемом графическим приложением, в процессе его автоматического тестирования. Характеристики компьютера такие же, что и в тестировании алгоритмов обнаружения объектов.

Таблица 1 - Среднее время выполнения алгоритма распознавания экранных объектов

Объект Изображение Количество классификаторов Tcpu, с Tgpu, с

Инициализация 0 0,002 0,002

Meduse 73 0,291 0,165

Shell 94 0,3 0,199

Crab tí 103 0,258 0,187

Seashell 344 0,656 0,307

Star 67 0,308 0,181

Всего: 681 1,815 1,041

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

графическом приложении, отслеживая положения объектов, принадлежащих пяти различным видам графических элементов, что сравнимо со средним временем реакции человека в процессе ручного тестирования для данного приложения.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Разработан алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных.

4. Проведён анализ возможностей распараллеливания и переноса алгоритмов метода Viola-Jones для обнаружения объектов на изображении на программируемые графические процессоры и выполнена их программная реализация.

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК России:

1. Капустин Д.С. Использование модели параллельных вычислений на графических процессорах в задаче обнаружения объектов по методу Viola-Jones / Д.С. Капустин // Системы управления и информационные технологии, №3(41). - Москва-Воронеж: Научная книга, 2010.-С. 87-91.

2. Капустин Д.С. Оценка производительности параллельных вычислений на графических процессорах на примере алгоритмов машинного зрения / Д.С. Капустин, С.Ю. Ржеуцкая // Системы управления и информационные технологии, 1.1(43). - Москва-Воронеж: Научная книга, 2011. - С. 194-198.

3. Капустин Д.С. Модификация абстрактной модели параллельных вычислений PRAM с уетом существенных особенностей графических процессоров / Д.С. Капустин, С.Ю. Ржеуцкая // Естественные и технические науки, №5(55). - М.: Спутник+, 2011. - С. 336-342.

Другие статьи и материалы конференции:

4. Капустин Д.С. Использование графических процессоров для распознавания объектов с помощью алгоритма Viola-Jones / Д.С. Капустин, С.Ю. Ржеуцкая // Информационные технологии моделирования и управления, №1(60). - Воронеж: Научная книга, 2010.-С.9-15.

5. Капустин Д.С. Использование общей памяти графических процессоров для ускорения параллельных вычислений алгоритмов машинного зрения / Д.С. Капустин // Материалы восьмой всероссийской научно-технической конференции «Вузовская наука -региону». В 2-х т. - Вологда: ВоГТУ, 2010. -Т.1.- С. 84-86.

6. Капустин Д.С. Использование графических процессоров для параллельных вычислений / Д.С. Капустин // Материалы седьмой всероссийской научно-технической конференции «Вузовская наука - региону». В 2-х т. - Вологда: ВоГТУ, 2009. - Т. 1. - С. 58-60.

7. Капустин Д.С. Параллельные алгоритмы для графических процессоров в задачах обработки массивов данных / Д.С. Капустин // Сборник тезисов всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области информационно-телекоммуникационных технологий». — М: Департамент развития информационно-коммуникационных технологий Министерства образования и науки РФ, 2010. -С.69-70

8. Капустин Д.С. Использование графических процессоров для задач распознавания текста / Д.С. Капустин // Материалы всероссийской научной конференции «Молодые исследователи - регионам». В 2-х т. - Вологда: ВоГТУ, 2009. - Т. 1. - с. 72-73.

9. Капустин Д.С. Развитие технологий программирования трёхмерной компьютерной графики / Д.С. Капустин // Материалы шестой всероссийской научно-технической конференции «Вузовская наука - региону». Т. 1,- Вологда: ВоГТУ, 2008. - С. 94-96.

10. Капустин Д.С. Объектно-ориентированный подход к программированию шейдеров / Д.С. Капустин // Материалы всероссийской научной конференции студентов и аспирантов «Молодые исследователи - регионам». В 2-х т. - Вологда: ВоГТУ, 2008. - Т. 1 -С. 86-87.

11. Капустин Д.С. Повышение качества трехмерной визуализации в САПР / Д.С. Капустин // Материалы межрегиональной научно-практической конференции «Развитие деревянного домостроения в Вологодской области. Проблемы и практические решения». -Вологда: Издательский центр ВИРО, 2008.-С. 129- 134.

Подписано в печать 18.11.2013. Формат 60 х 84 V|6 Бумага офисная. Печать офсетная. Усл.-п.л. 1,0. Тираж 100 экз. Заказ № 484

Отпечатано: РИО, ВоГУ 160000, г. Вологда, ул. Ленина, 15

Вологодский государственный технический университет

04201450654

На правах рукописи

Капустин Дмитрий Сергеевич

МОДЕЛИ И АЛГОРИТМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА ГРАФИЧЕСКИХ ПРОЦЕССОРАХ И ИХ ПРИМЕНЕНИЕ В ПРОГРАММНЫХ СРЕДСТВАХ АВТОМАТИЧЕСКОГО ТЕСТИРОВАНИЯ ГРАФИЧЕСКИХ

ПРИЛОЖЕНИЙ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель -доцент, кандидат технических наук Ржеуцкая Светлана Юрьевна

Вологда - 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.................................................................................5

ГЛАВА 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. Использование модели в CUD А.......................................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

ВВЕДЕНИЕ

Программируемые графические процессоры (GPU) в настоящее время представляют собой мощный и гибкий инструмент для выполнения вычислений общего назначения. Графические адаптеры обычно имеют в своем составе несколько сотен скалярных (потоковых) процессоров, частота которых сравнима с частотой ядер центральных процессоров (CPU), объединенных в блоки, называемые мультипроцессорами. Каждый мультипроцессор имеет собственную память, разделяемую скалярными процессорами, кроме того, GPU имеет общую (глобальную) память (GRAM) и память для хранения неизменяемых данных. Таким образом, GPU можно позиционировать в качестве дополнения вычислительных мощностей CPU при решении задач общего назначения. Однако, для того, чтобы эффективно использовать возможности GPU в процессе разработки программного обеспечения, нужно учитывать их существенные особенности [59, 81].

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

В силу указанных особенностей, перенос вычислений на GPU требует серьезной проработки на алгоритмическом уровне индивидуально для каждой решаемой задачи. В настоящее время существует несколько моделей программирования графических процессоров (CUDA, OpenCL), однако в доступных источниках информации не имеется сведений о математических моделях, с помощью которых можно разрабатывать, сравнивать и анализировать

параллельные алгоритмы для GPU без их трудоемкой программной реализации. Безусловно, разработка алгоритмов для графических процессоров может быть значительно упрощена при использовании опыта распараллеливания вычислений для центральных процессоров на основе известных моделей [3, 26]. К сожалению, ни одна из них не может быть применена к графическим процессорам напрямую в силу значительных отличий архитектур CPU и GPU. Исходя из вышеизложенного, актуальной является задача адаптации известных моделей параллельных вычислений к специфике GPU.

Графические процессоры позволяют эффективно решать многие вычислительно ёмкие задачи. Одна из таких задач обозначилась в последние годы в связи с появлением многочисленных программных средств, предназначенных для автоматизации тестирования программных продуктов [10]. В процессе автоматического тестирования приложений через графический интерфейс пользователя программное средство должно имитировать действия человека-оператора, выполняющего «ручное» тестирование, на основе распознаваемых им экранных объектов (элементов интерфейса). При этом время, затрачиваемое программным средством на получение этих данных и принятие решения, должно быть не больше среднего времени реакции человека, работающего с тестируемым приложением.

Современные средства автоматического тестирования имеют в своем составе программный компонент для распознавания элементов интерфейса пользователя, однако в подавляющем большинстве случаев он позволяет распознавать только стандартные интерфейсные элементы (кнопки, поля ввода и т.д.). В последние годы появились программные средства для распознавания произвольных графических экранных объектов (Sikuli, eggPlant), но эта функция выполняется с видимым замедлением, что не позволяет выполнить полноценное автоматическое тестирование графических приложений с большим количеством элементов интерфейса. Принимая во внимание высокую трудоемкость алгоритмов распознавания образов и потенциальную возможность их распараллеливания по данным, актуальной является задача разработки быстродействующего

программного компонента для распознавания произвольных элементов интерфейса пользователя, реализующего алгоритмы параллельных вычислений на GPU.

Развитию существующих моделей параллельных вычислений посвящены работы S. Fortune, J. Wyllie, L. Valiant, В.В. Воеводина, B.C. Любченко. Специфика вычислений на графических процессорах представлена в работах S. Hong, H.Kim, А. Берилло, В. Фролова. Вопросы автоматического тестирования программ рассмотрены в работах И.В. Винниченко, В.В. Липаева, Г.Л. Гриппа.

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

Предметом диссертационного исследования являются модели, методы и алгоритмы эффективных параллельных вычислений на графических процессорах.

Цель диссертационного исследования заключается в повышении производительности параллельных вычислений за счет эффективного использования объединенных ресурсов центрального и графического процессоров применительно к задаче распознавания элементов пользовательского интерфейса в процессе автоматического тестирования графических приложений.

Основные задачи исследования

1. Разработка модели параллельных вычислений на графических процессорах, предназначенной для разработки, анализа и сравнения алгоритмов.

2. Разработка методов повышения быстродействия параллельных алгоритмов на графических процессорах и их применение к задаче распознавания произвольных графических элементов интерфейса пользователя.

3. Программная реализация параллельных алгоритмов распознавания элементов интерфейса пользователя с использованием GPU и их экспериментальная проверка.

4. Применение реализованных алгоритмов в программных средствах автоматического тестирования графических приложений.

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

На защиту выносятся следующие результаты:

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

2. Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных.

3. Параллельный алгоритм обнаружения объектов на изображении по признакам Хаара с кэшированием интегрального представления изображения и данных классификаторов в памяти графического процессора.

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

Научная новизна работы.

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

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

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

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

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

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

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

Реализация результатов исследования. Теоретические и практические результаты диссертационной работы используются в программных средствах ООО «Плейрикс» и НИП «Адрэм», что подтверждено актами о внедрении (см. Приложение 1, 2). Кроме того, результаты работы используются в учебном

процессе кафедры «Автоматика и вычислительная техника» Вологодского государственного технического университета при преподавании курса «Структуры и алгоритмы обработки данных» (см. Приложение 3).

Материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы в рамках проектов «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры» и «Методология построения интеллектуальных агентно-ориентированных комплексов для многоуровневой подготовки специалистов технического профиля» (см. Приложение 4).

Апробация результатов исследования. Основные результаты работы докладывались и получили положительную оценку на следующих конференциях, симпозиумах и семинарах: Всероссийская научно-практическая конференция «Информационно-телекоммуникационные технологии» (Москва, 2010 г.), Всероссийская научная конференция студентов и аспирантов «Молодые исследователи - регионам» (Вологда, 2008, 2009 гг.), Всероссийская конференция «Вузовская наука - региону» (Вологда, 2008, 2009, 2010 гг.), семинар вологодского отделения РАН по искусственному интеллекту (Вологда, 2010 г.), городской семинар «Информатика и компьютерные технологии» (Санкт-Петербург, 2012 г.).

Публикации. По материалам диссертационного исследования опубликовано 11 печатных работ, из них три в журналах, включенных в перечень ВАК.

Структура диссертационной работы. Работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений. Текст изложен на 146 страницах, содержит 36 рисунков и 2 таблицы. Библиографический список включает 105 наименований

Во введении обоснована актуальность темы диссертации, сформулированы цель и задачи работы, научная новизна, практическая значимость, указаны основные положения, выносимые на защиту.

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