принципы адаптации вычислительных алгоритмов




Скачать 413.33 Kb.
Названиепринципы адаптации вычислительных алгоритмов
страница6/10
Дата22.10.2012
Размер413.33 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9   10

Выводы по главе 1


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


Глава 2. Отображение исследуемых алгоритмов на архитектуру графических акселераторов

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


Одной из особенностей этой задачи является необходимость обработки больших массивов входных данных, что с одной стороны, приводит к большой трудоемкости вычислений, а с другой, позволяет эффективно использовать распараллеливание по данным (рис. 7). При таком подходе вычислительные мощности GPU используются для подсчета значений целевой функции для набора входных данных, обрабатываемого на одном этапе работы алгоритма оптимизации N спектров, выполняющемся на CPU, что позволяет эффективно использовать вычислительные мощности GPU-устройств, поскольку для каждого набора входных данных решается одна и та же трудоемкая задача. Очевидным недостатком такого подхода является требование по наличию большого числа входных данных – для полной загрузки графического акселератора со 128 ядрами – потребуется как минимум (а на самом деле, как будет показано в следующей главе, и больше) 128 входных спектров.

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






Рис. 7. Случайный поиск на GPU: распараллеливание по данным




Рис. 8. Случайный поиск на GPU: распараллеливание подсчета целевой функции


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


При реализации первого этапа алгоритма учитывалась сепарабельность фильтра Гаусса: . Обозначим . Поскольку число пикселей в обрабатываемых изображениях (минимум 320 на 240) достаточно велико по сравнению с числом ядер в графических акселераторах, при распараллеливании данного этапа наиболее естественным является подход, когда каждый поток вычисляет значение сначала , а затем – на собственном множестве точек.

При этом для подсчета в точке необходимо получить значения на множестве точек , где r – радиус подсчета свертки (оптимальное значение r приведено в работе [19]). Аналогично, для подсчета необходимы значения  на множестве точек . Более подробно схема реализации этого этапа на GPU-устройстве приведена на рис. 9. Подсчет разностной пирамиды реализован очевидным образом – каждый поток считает для своего набора точек.



Рис. 9. GPU–реализация свертки Гаусса, использующаяся при построении пирамиды


Второй этап алгоритма реализован аналогичным образом (рис. 10). Каждый поток проверяет на экстремум собственный набор точек.



Рис. 10. GPU–реализация поиска экстремумов в разностной пирамиде

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

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

На пятом этапе очевидный подход – разделить ключевые точки между потоками и в каждом потоке подсчитывать дескриптор для одной ключевой точки – не работает. Это связано с тем, что, хранить промежуточные результаты в разделяемой памяти не получится: дескриптор представляет собой 128 чисел с плавающей точкой, занимающих 512 байт. То есть при минимальном размере блока в 32 потока будет требоваться 16 килобайт разделяемой памяти, что превышает возможности архитектуры (16 килобайт на мультипроцессор, из которых несколько десятков байт уходят на служебные данные). С другой стороны, хранение промежуточных данных в памяти GPU-устройства ведет к потерям производительности. Из-за перечисленных фактов на данном этапе используется более сложный подход: ключевые точки разделяются между блоками (размер блока фиксирован – 32 потока), по две ключевые точки на блок, или по 16 потоков на ключевую точку. При этом, поскольку происходит подсчет гистограммы, важно, чтобы между разными протоками не было коллизий при записи в одну ячейку гистограммы. Это достигается благодаря использованию особенностей структуры гистограммы: при ее подсчете окрестность ключевой точки делится на 16 областей и для каждой из областей подсчитывается распределение ориентации градиента. Таким образом, каждый обрабатывает только одну из этих шестнадцати областей, то есть участвует в построении только собственной, не зависящей от других частей, части гистограммы.
1   2   3   4   5   6   7   8   9   10

Похожие:

принципы адаптации вычислительных алгоритмов iconпринципы адаптации вычислительных алгоритмов к архитектуре графических акселераторов
Целью работы является изучение ключевых особенностей отображения вычислительных алгоритмов на gpu -архитектуру, выявление ряда факторов,...
принципы адаптации вычислительных алгоритмов iconЗадача параметрической аппроксимации двумерной функции с использованием метода случайного поиска 10
Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
принципы адаптации вычислительных алгоритмов iconОсобенности адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов
В работе обсуждаются вопросы отображения вычислительных алгоритмов на параллельную архитектуру gpu-акселератора. В качестве примера...
принципы адаптации вычислительных алгоритмов iconПрограмма вступительного экзамена в магистратуру по направлению подготовки 231000. 68 «Программная инженерия»
...
принципы адаптации вычислительных алгоритмов icon1. цели и задачи дисциплины, ее место в учебном процессе согласно гос впо в дисциплину «Вычислительные системы, сети и телекоммуникации» должно включаться
Вычислительных машин: общие принципы построения и архитектуры вычислительных машин, информационно-логические основы вычислительных...
принципы адаптации вычислительных алгоритмов iconАлгоритмы
Основы алгоритмизации. Понятие об алгоритме. Применение алгоритмов. Свойства алгоритмов. Типы алгоритмов: линейные, циклические,...
принципы адаптации вычислительных алгоритмов iconСодержание, основные понятия
Понятие алгоритма, свойства алгоритмов. Использование алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
принципы адаптации вычислительных алгоритмов iconОглавление 4
Архитектура графических акселераторов, средства отображения на них вычислительных алгоритмов и исследуемые алгоритмы 10
принципы адаптации вычислительных алгоритмов iconБилет №4
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов....
принципы адаптации вычислительных алгоритмов iconТическая логика и теория алгоритмов
Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница