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

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Актуальность работы 2009Научно-исследовательский институт наукоемких компьютерных технологий 2 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Научно-исследовательский институт наукоемких компьютерных технологий 3 Изучение особенностей отображения вычислительных алгоритмов на GPU-архитектуру, выявление ряда факторов, влияющих на получаемую производительность и исследование их влияния Изучение средств отображения алгоритмов на архитектуру графических акселераторов и выбор актуальных алгоритмов, на примерах которых изучаются особенности GPU-архитектуры Отображение выбранных алгоритмов на архитектуру графических акселераторов Анализ параллельной производительности, изучение влияния особенностей архитектуры на получаемую производительность

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

Принципы адаптации вычислительных алгоритмов под параллельную архитектуру графических акселераторов Пример 1: спектры климатического волнения 2009Научно-исследовательский институт наукоемких компьютерных технологий Аппроксимация нелинейной функции нескольких аргументов – оптимизация методом линейного случайного поиска Массив расчетных спектров волнения Представление спектра Аппроксимация 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