Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов С.М.Вишняков научный руководитель: д.т.н. А.В.Бухановский

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Актуальность работы 2009Научно-исследовательский институт наукоемких компьютерных технологий 22 BrookGPU (Stanford University, 2004) Sh Lib (Waterloo University, ) ATI Close-To-Metal/FireStream SDK (2007) nVidia CUDA (2007) OpenCL (2008) Преимущества CUDA: абстрагирование от терминологии компьютерной графики; SDK разрабатывается производителем «железа»; поддержка высокопроизводительных HPC-акселераторов (Tesla). NVidia GeForce 8800 GTX: 16 мультипроцессоров по 8 ядер 768 Mb памяти Высокоуровневые надстройки PyCUDA Jacket: A CUDA-engine for MATLAB

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Цель и задачи работы 2009Научно-исследовательский институт наукоемких компьютерных технологий 33 Изучение ключевых особенностей отображения вычислительных алгоритмов на GPU-архитектуру, выявление ряда факторов, влияющих на получаемую производительность и исследование их влияния Изучение средств отображения алгоритмов на архитектуру графических акселераторов и выбор актуальных алгоритмов, на примерах которых изучаются особенности GPU-архитектуры Отображение выбранных алгоритмов на архитектуру графических акселераторов Анализ параллельной производительности

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Архитектура GPU и отображение вычислительных задач Научно-исследовательский институт наукоемких компьютерных технологий 4 Выделение вычислительного ядра Определение конфигурации Загрузка ядра и данных в GPU 2009

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Пример 1: спектры климатического волнения 2009Научно-исследовательский институт наукоемких компьютерных технологий 5 Аппроксимация нелинейной функции нескольких аргументов – оптимизация методом линейного случайного поиска (алгоритм класса «б») Массив расчетных спектров волнения Представление спектра Аппроксимация Estimation of prevailed peak position on the data sheet directly Определение числа и положения пиков методом адаптивного случайного поиска с линейной тактикой Оценка значимости выявленных пиков Набор параметров спектров Сглаживание. Определение положения главного пика 5 Научно-исследовательский институт наукоемких компьютерных технологий

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Пример 2: выделение особых точек на изображении – SIFT Научно-исследовательский институт наукоемких компьютерных технологий 6 Применение: Склейка аэрофотосъемки Поиск образов в БД Ключевые этапы алгоритма: Построение последовательности фильтров Гаусса для изображения Поиск и уточнение экстремумов в пирамиде Вычисление ориентации особых точек Вычисление дескрипторов особых точек 2009

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Параллельная реализация аппроксимации спектров Научно-исследовательский институт наукоемких компьютерных технологий 7 Распараллеливание по данным Распараллеливание подсчета целевой функции 2009

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Параллельная реализация алгоритма SIFT Научно-исследовательский институт наукоемких компьютерных технологий Особенности параллельной реализации Ручное кэширование данных в разделяемой памяти при применении фильтра Гаусса и поиске экстремумов Использование атомарных операций (CC 1.1) Использование разделяемой памяти для хранения промежуточных данных

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Полученные результаты 9 Научно-исследовательский институт наукоемких компьютерных технологий A – распараллеливание по данным, B – распараллеливание подсчета целевой функции внутри блока, C – распараллеливание подсчета целевой функции на все потоки От каких параметров зависит эффективность параллельной реализации?

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Полученные результаты Структура модели производительности Зависимость t0(blockSize) и ее теоретический вид (а), зависимость occupancy(blockSize) (б) 10 Научно-исследовательский институт наукоемких компьютерных технологий2009

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Полученные результаты 11 Научно-исследовательский институт наукоемких компьютерных технологий2009

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов 12 Выводы Реализованы алгоритмы аппроксимации климатических спектров и поиска ключевых точек с использованием графических акселераторов, получено существенное ускорение Исследованы различные особенности архитектуры, влияющие на получаемое ускорение Предложена модель производительности, облегчающая выбор оптимальной конфигурации ядра Факультет информационных технологий и программирования2009