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

• Автор: Капустин, Дмитрий Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Вологда
• Количество страниц: 150 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. Анализ абстрактных моделей параллельных вычислений с учетом особенностей графических процессоров

1.1. Анализ абстрактных моделей параллельных вычислений

1.1.1. Модель PRAM

1.1.2. Модель BSP

1.1.3. Модель LogP

1.2. Анализ особенностей структур программируемых графических процессоров общего назначения

1.2.1. Особенности структуры графических процессоров NVIDIA

1.2.2. Особенности структуры графических процессоров ATI

1.3. Анализ математических моделей графических процессоров и возможностей применения абстрактных моделей параллельных вычислений к графическим процессорам
1.4. Анализ возможностей использования графических процессоров в программных средствах автоматического тестирования приложений через интерфейс пользователя
Основные выводы
ГЛАВА 2. Разработка параметрической модели параллельных вычислений на графических процессорах
2.1. Параметрическая модель графического мультипроцессора на основе PRAM модели
2.2. Разработка модели абстрактного графического процессора
2.3. Разработка модели параллельных вычислений на графических процессорах

2.4. Использование модели для разработки, анализа и сравнения
параллельных алгоритмов на графических процессорах
2.4.1. Разработка параллельных алгоритмов
2.4.2. Анализ параллельных алгоритмов
2.4.3. Сравнение параллельных алгоритмов
2.5. Применение модели в средствах программирования графических
процессоров
2.5.1. Использование модели в ССГОА
2.5.2. Использование модели в ОрепСЬ
2.5.3. Использования модели для принятия решения об используемой вычислительной системе
Основные выводы
ГЛАВА 3. Разработка методов повышения производительности параллельных алгоритмов за счет эффективного использования объединенных ресурсов центрального и графического процессоров
3.1. Анализ возможностей кэширования данных в различных видах памяти графического процессора
3.2. Алгоритм принятия решения о целесообразности переноса вычислений на графический процессор и использования разделяемой памяти мультипроцессоров для кэширования данных
3.3. Применение полученных результатов к задаче фильтрации изображений
Основные выводы
ГЛАВА 4. Разработка программного компонента распознавания
элементов интерфейса пользователя в средстве автоматического
тестирования графических приложений
4.1. Средство автоматического тестирования графических
приложений

4.2. Разработка и реализация параллельного алгоритма вычисления интегрального представления изображения
4.3. Разработка и реализация параллельного алгоритма поиска объектов на интегральном представлении изображения
4.4. Разработка и реализация параллельного алгоритма группировки результатов поиска объектов по положению и размеру
4.5. Анализ результатов экспериментов
4.6. Реализация программного компонента для распознавания произвольных элементов интерфейса пользователя с использованием графического процессора и результаты его работы
Основные выводы
ЗАКЛЮЧЕНИЕ
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ
СПИСОК ТЕРМИНОВ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ

группы разбиваются на меньшие группы - пучки (wavefront) и выполняются согласно расписанию. Таким образом, модели CUDA и OpenCL похожи друг на друга.
1.3. Анализ математических моделей графических процессоров и возможностей применения абстрактных моделей параллельных вычислений
к графическим процессорам
Рассмотренные выше модели параллельного программирования предназначены в первую очередь для того, чтобы программист имел представление об основных структурных элементах графических процессоров, к которым можно отнести память и вычислительные элементы, и связях между ними. Кроме того, и в CUDA и в OpenCL имеется некоторая абстракция алгоритма, в которой предполагается, что входные и выходные данные представлены в виде массива элементов, каждый из которых обрабатывается независимо друг от друга, за счёт чего достигается параллелизм по данным. Выделим основные недостатки данных моделей:
1) отсутствует математическое описание абстрактной модели графического процессора, поэтому невозможно оценить время работы конкретного алгоритма на разных графических процессорах;
2) не акцентированы существенные параметры параллельных алгоритмов, благодаря которым можно анализировать и сравнивать эти алгоритмы по времени выполнения на графическом процессоре с определённой конфигурацией;
3) не смотря на то, что модели являются гетерогенными (т.е. они учитывают не только графические процессоры, но и центральные) в них не реализованы методы принятия решения об используемой вычислительной системе;
4) для таких моделей не разработаны общие принципы оптимизации параллельных вычислений (в [87, 41] приводятся методы оптимизации под конкретную платформу, но не под модель);
5) нет общей методологии разработки параллельных алгоритмов.