26-29 октября 2010 года, Красноярск

Аникин А.С.  

Программная реализация метода случайных покрытий для задач оптимального управления с использованием технологии CUDA

Поиск глобального экстремума функционалов, определенных на траекториях нелинейных динамических систем является одной из сложнейших оптимизационных задач. В работе [1] рассматривается алгоритм поиска глобального экстремума в задаче оптимального управления, основанный на идее покрытия множества достижимости разновеликими шарами. Рассмотренная программная реализация метода, к сожалению, не позволяет использовать возможности современных многопроцессорных вычислительных систем. Применение данного метода для решения сложных прикладных задач влечет за собой достаточно большой объем вычислений, поэтому возникает необходимость их ускорения.
В настоящее время все большую популярность приобретают технологии, позволяющие проводить параллельные вычисления на графических ускорителях (GPU). Самая распространенная и технически совершенная из них – Nvidia CUDA ([2,3]). Основным достоинством применения данного подхода является высокая производительность современных графических процессоров — более 1 TFLOPS - при низкой стоимости оборудования, недостатком — сложность программирования подобных систем, и высокая их эффективность лишь при использовании одинарной (float) точности на значительной части используемого оборудования. Последнее поколение GPU от Nvidia (Fermi) имеет более совершенную архитектуру и позволяют значительно эффективнее использовать в алгоритмах двойную (double) точность представления чисел.
В работе рассматривается программная реализация метода случайных покрытий для решения невыпуклых задач оптимального управления с использованием технологии Nvidia CUDA. Первым этапом явилось создание параллельной версии уже существующего алгоритма. Дальнейшая реализация потребовала также решения ряда технических проблем, связанных с аппаратными особенностями и ограничениями современных графических процессоров - наличием различных типов памяти, необходимостью минимизации объема данных, пересылаемых между центральным и графическим процессорами, минимизацией количества ветвлений алгоритма и рядом других.
Полученная реализация протестирована в операционных системах Linux и Windows на графических адаптерах Nvidia Quadro NVS 140M и GeForce GTX 285. Результаты сравнения с расчетами, выполненными на центральном процессоре, демонстрируют значительное уменьшение времени расчетов. Проведенные вычислительные эксперименты позволяют надеяться, что современные графические процессоры, дополненные технологией уровня CUDA, смогут выступать эффективным средством ускорения вычислений при решении невыпуклых задач оптимизации динамических систем.
Работа выполнена при финансовой поддержке грантов РФФИ № 09-07-00267 и 10-01-00595.

Список литературы

  1. Горнов А.Ю., Зароднюк Т.С. Метод случайных покрытий для задачи оптимального управления // Вычислительные технологии (в печати).
  2. www.nvidia.com/object/cuda_home.html
  3. www.gpgpu.ru


К списку докладов