WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

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

ГРАФИЧЕСКИХ ПРОЦЕССОРАХ И ИХ ПРИМЕНЕНИЕ В

ПРОГРАММНЫХ СРЕДСТВАХ АВТОМАТИЧЕСКОГО

ТЕСТИРОВАНИЯ ГРАФИЧЕСКИХ ПРИЛОЖЕНИЙ

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

АВТОРЕФЕРАТ

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

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

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

Научный руководитель Ржеуцкая Светлана Юрьевна, кандидат технических наук, доцент кафедры «Автоматика и вычислительная техника» ВоГТУ

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

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

Ведущая организация Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Северный (Арктический) федеральный университет имени М.В. Ломоносова» (САФУ)

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

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





Автореферат разослан «26» ноября 2013 г.

Ученый секретарь диссертационного совета Д.002.199. кандидат технических наук, доцент Нестерук Филипп Геннадьевич

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

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

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

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

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

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

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

тестирование, на основе распознаваемых экранных объектов (элементов интерфейса).

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





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

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

Берилло, В. Фролова. Вопросы автоматического тестирования программ рассмотрены в работах И.В. Винниченко, В.В. Липаева, Г.Л. Гриппы.

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

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

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

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

исследования:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выполнен обзор современных программируемых графических процессоров различных архитектур от компаний NVIDIA и ATI, представлены общий принцип работы и средства программирования CUDA, 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. Количество скалярных процессоров в графическом мультипроцессоре ограничено сверху ( pmax процессоров). Для выполнения большего числа потоков используется система горизонтального параллелизма, аналогичная горизонтальной структуре в модели BSP: генерируется расписание последовательного исполнения потоков, разбитых на пучки по p warp скалярных процессоров;

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

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

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

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

где ceil - функция округления числа до ближайшего большего целого, p pmax - количество используемых в параллельном алгоритме скалярных процессоров.

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

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

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

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

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

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

M GPU M GPU, где M GPU - фактический, а M GPU - объём требуемой глобальной памяти графического процессора для вычисления на i -м этапе алгоритма;

констант для вычисления на i -м этапе алгоритма;

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

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

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

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

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

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

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

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

S HD S DH

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

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

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

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

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

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

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

S HD S DH

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

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

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

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

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

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

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

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

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

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

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

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

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

TGPU-CTCPU TCPUTGPU

Рисунок 2 – Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для TCPU - время вычисления на центральном процессоре, TGPU - время вычисления на графическом процессоре без кэширования данных, TGPU-C - время вычисления на Рисунок 3 – Структурная схема программного средства автоматического На практике для многих приложений со сложным графическим интерфейсом производительность известных программных средств распознавания изображений оказывается недостаточной, чтобы обеспечить приемлемое время распознавания.

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

Рассмотрены и другие алгоритмы метода: вычисление интегрального представления изображения с помощью параллельного алгоритма для PRAM (алгоритм scan) и группировка результатов поиска по положению и размерам. Эти алгоритмы тоже могут быть перенесены на GPU для повышения скорости вычислений.

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

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

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

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

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

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

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

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

Рисунок 6 – Сравнение быстродействия метода Viola-Jones на CPU и GPU Параллельные алгоритмы для графических процессоров, предложенные в данной главе, позволяют повысить производительность методов распознавания элементов графического интерфейса на экране. В таблице 1 представлено среднее время работы алгоритма распознавания для пяти элементов интерфейса пользователя различной сложности на изображении размером 0.25 Mpx (мегапикселей), генерируемом графическим приложением, в процессе его автоматического тестирования. Характеристики компьютера такие же, что и в тестировании алгоритмов обнаружения объектов.

Таблица 1 – Среднее время выполнения алгоритма распознавания Как видно из данной таблицы, модуль распознавания за счёт использования ресурсов графического процессора позволяет каждую секунду определять ситуацию в графическом приложении, отслеживая положения объектов, принадлежащих пяти различным видам графических элементов, что сравнимо со средним временем реакции человека в процессе ручного тестирования для данного приложения.

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

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

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

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

10. Капустин Д.С. Объектно-ориентированный подход к программированию шейдеров / Д.С.

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

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

Издательский центр ВИРО, 2008. – С. 129 – 134.

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

ГРАФИЧЕСКИХ ПРОЦЕССОРАХ И ИХ ПРИМЕНЕНИЕ В

ПРОГРАММНЫХ СРЕДСТВАХ АВТОМАТИЧЕСКОГО

ТЕСТИРОВАНИЯ ГРАФИЧЕСКИХ ПРИЛОЖЕНИЙ

Текст автореферата размещен на сайтах:

Высшей аттестационной комиссии Министерства образования и науки Федерального государственного бюджетного учреждения науки Санкт-Петербургского института информатики и автоматизации Российской академии наук (СПИИРАН) http://www.spiiras.nw.ru/DissSovet/Templates/PhDSchedule.htm _ Подписано в печать 18.11.2013. Формат 60 84 1/ _ Отпечатано: РИО, ВоГУ 160000, г. Вологда, ул. Ленина,

 
Похожие работы:

«Грибанова Екатерина Борисовна АЛГОРИТМЫ И КОМПЛЕКС ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ОБЪЕКТОВ ПРИКЛАДНОЙ ЭКОНОМИКИ Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Томск – D Работа выполнена в Томском государственном университете систем управления и радиоэлектроники. Научный руководитель : доктор технических наук, профессор Мицель Артур...»

«АЛТЫНБАЕВ Равиль Биктимурович ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ УПРАВЛЕНИЯ АВИАЦИОННЫМИ РАБОТАМИ ПО ТЕРРИТОРИАЛЬНОМУ РАСПРЕДЕЛЕНИЮ АКТИВНЫХ ВЕЩЕСТВ НА ОСНОВЕ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ (НА ПРИМЕРЕ АГРОПРОМЫШЛЕННОГО КОМПЛЕКСА) Специальность: 05.13.06 Автоматизация и управление технологическими процессами и производствами (в промышленности) АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Уфа – Работа выполнена в ФГБОУ ВПО Оренбургский государственный...»

«Жериков Андрей Валерьевич ПРИМЕНЕНИЕ КВАЗИГИДРОДИНАМИЧЕСКИХ УРАВНЕНИЙ ДЛЯ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ТЕЧЕНИЙ ВЯЗКОЙ НЕСЖИМАЕМОЙ ЖИДКОСТИ 05.13.18 – Математические моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук. Москва, Работа выполнена на...»

«ЗАГРЕБНЕВА Анна Дмитриевна СТРУКТУРООБРАЗОВАНИЕ В ПОПУЛЯЦИОННЫХ СИСТЕМАХ, ОБУСЛОВЛЕННОЕ ЯВЛЕНИЕМ ТАКСИСА 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Ростов-на-Дону 2010 Работа выполнена в отделе математических методов в экономике и экологии НИИ механики и прикладной математики им. Воровича И.И. Южного федерального университета, г. Ростов-на-Дону Научный...»

«Максаков Алексей Владимирович ПОВЫШЕНИЕ РЕЛЕВАНТНОСТИ ПЕРИОДИЧЕСКОГО ТЕМАТИЧЕСКОГО ПОИСКА ИНФОРМАЦИИ В WEB Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук МОСКВА 2007 Работа выполнена на кафедре автоматизации...»

«Сачкова Елена Федоровна Методы, алгоритмы и программы приближенного решения задачи управления 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 05.13.01 Системный анализ, управление и обработка информации (технические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Переславль-Залесский 2009 г....»

«Фиалко Надежда Сергеевна МОДЕЛИРОВАНИЕ ПЕРЕНОСА ЗАРЯДА В ДНК Специальность: 05.13.18 – математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Пущино 2007 Работа выполнена в Институте математических проблем биологии РАН (г. Пущино) Научный руководитель : доктор физико-математических наук, профессор Лахно Виктор Дмитриевич Официальные доктор физико-математических наук,...»

«СТАРОДУБЦЕВ Игорь Юрьевич МОДЕЛИ И МЕТОДЫ МНОГОЦЕЛЕВЫХ ЗАДАЧ СЕТЕВОГО ПЛАНИРОВАНИЯ В УСЛОВИЯХ НЕЧЕТКОЙ НЕОПРЕДЕЛЕННОСТИ ПРОДОЛЖИТЕЛЬНОСТЕЙ ОПЕРАЦИЙ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Воронеж – 2012 Работа выполнена в ФГБОУ ВПО Воронежский государственный университет Научный руководитель : Артемов Михаил Анатольевич доктор...»

«Ляпунова Ирина Артуровна РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛЕЙ ПРОСТРАНСТВЕННО НЕОДНОРОДНЫХ ГЕННОМОДИФИЦИРОВАННЫХ ПОПУЛЯЦИЙ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Таганрог – 2013 2 Работа выполнена в Южном федеральном университете в г. Таганроге. Научный руководитель : Сухинов Александр Иванович доктор физико-математических наук, профессор, ФГАОУ...»

«Половнев Антон Леонидович Оптимизация плана эксперимента в задаче определения координат места пробоя гермооболочки пилотируемого космического аппарата Специальность: 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Москва 2011 Работа выполнена в открытом акционерном обществе Ракетнокосмическая корпорация Энергия имени С.П.Королёва. кандидат технических наук...»

«Гильмуллин Ринат Абрекович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В МНОГОЯЗЫКОВЫХ СИСТЕМАХ ОБРАБОТКИ ДАННЫХ НА ОСНОВЕ АВТОМАТОВ КОНЕЧНЫХ СОСТОЯНИЙ 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Казань – 2009 Работа выполнена на кафедре теоретической кибернетики государственного образовательного учреждения высшего профессионального...»

«МАЛКОВ Артемий Сергеевич МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ РАЗВИТИЯ АГРАРНЫХ ОБЩЕСТВ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2005 Работа выполнена в Ордена Ленина Институте прикладной математики им. М.В. Келдыша Российской академии наук Научные...»

«Крылов Андрей Серджевич МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И КОМПЬЮТЕРНЫЙ АНАЛИЗ ЖИДКИХ МЕТАЛЛИЧЕСКИХ СИСТЕМ Специальность 05.13.18 математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва 2009 Диссертационная работа выполнена на кафедре математической физики факультета...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.