Массивно-параллельное программирование на CUDA

Преподаватель: Перепёлкин Евгений Евгеньевич
доктор физико-математических наук, профессор кафедры квантовой статистики и теории поля

Общая информация

Курс предназначен для разработчиков и исследователей, желающих познакомиться с основами программирования графических процессоров (GPU) NVIDIA в целях ускорения решаемых задач. Слушателям будут даны основы программирования с использованием технологии CUDA, приведены сведения о типах памяти GPU, будут рассмотрены библиотеки и инструменты, входящие в комплект разработчика CUDA Toolkit, вопросы отладки, профилирования и оптимизации CUDA-программ. Также будет рассмотрен стандарт параллельного программирования OpenACC и особенности программирования многопроцессорных систем с несколькими GPU.

Приблизительная программа курса

Лекция 1

Проблемы повышения частоты центральных процессоров (CPU) и перехода на низший техпроцесс. Графический процессор как массивно-параллельная архитектура. Тандем CPU-GPU. Задачи, решаемые на GPU: астрофизика, био-информатика (анализ ДНК, секвенирование генома, скручивание белков), молекулярная динамика, ускорительная физика, обработка данных в реальном времени (big data, data-mining, on-line обработка экспериментальных данных), гидрогазодинамика, нефтегазовая промышленность (каротаж скважин), финансовая индустрия (рынок акций, опционы, бонды, капитализация), задачи распознавания (программа «безопасный город», глубокое обучение (deep learning)), компьютерная графика, шоу бизнес и многое другое

Лекция 2

Гибридная модель вычислений. Типы вычислительных архитектур. Архитектура графического процессора (GPU). Высокоскоростное внутреннее соединение NVIDIA NVLink обмена данными между GPUs

Лекция 3

Программная модель CUDA. Гибридная модель программного кода. Понятие потока, блока, сети блоков. Функция – ядро как параллельный код на GPU.

Лекция 4

Иерархия памяти на GPU. Регистры и локальная память. Register spilling. L1 и Read Only Data Cache. Глобальная память и L1, L2. Шаблон работы с глобальной памятью.

Лекция 5

Компиляция кода на GPU. Средства разработки MS Visual Studio, NVIDIA Profiler, NVIDIA Parallel Nsight.
Задача. Простейший алгоритм параллельного вычисления значений функции на GPU. Сравнение времени копирования данных между «host» / «device» и времени вычислений на GPU.

Лекция 6

Compute Capability видеокарты. Объединение запросов при доступе в глобальную память (Coalescing). Использование L1 cash и _ldg при работе с глобальной памятью.
Задача. Пример параллельного алгоритма решения системы линейных алгебраических уравнений (СЛАУ). Оптимизация доступа в глобальную (coalescing, L1 cash, _ldg ) память в алгоритме решения СЛАУ.

Лекция 7

Параллельный алгоритм решения задачи многих тел (N-body) с использованием глобальной памяти.
Задача. Гравитационное и электрическое взаимодействие. Оценка эффективности.

Лекция 8

Pinned-память. Оптимизация копирования данных с «host» на «device» с использованием pinned-памяти.
Задача. Использование pinned-памяти в алгоритме вычисления значений функции (лекция 4) и решения СЛАУ.

Лекция 9

Понятие CUDA-потока (CUDA-Streams). Асинхронное выполнение функции-ядра и асинхронное копирование данных между «host» и «device».
Задача. Пример использование CUDA-потоков и pinned-памяти в алгоритме обработке массивов данных. Оценка времени копирования данных, вычислений на GPU, загрузки шины PCI-E

Лекция 10

Шаблон работы с глобальной памятью. Массивы с выравниванием. Двумерные массивы в глобальной памяти GPU.
Задача. Пример параллельного алгоритма перемножения матриц.

Лекция 11

Разделяемая память (shared memory) и L1-cache. Шаблон работы с разделяемой памятью.
Задача. Параллельный алгоритм решения задачи многих тел (N-body) с использованием разделяемой памяти.

Лекция 12

Оптимизация работы с разделяемой памятью. Понятие банков. Понятие банк- конфликтов.
Задача. Параллельный алгоритм перемножения матриц с использованием разделяемой памяти (оптимизация банк-конфликтов, параллелизм по нитям (TLP), параллелизм по инструкциям (ILP) )

Лекция 13

Разделяемая память.
Задача. Оптимизация алгоритма задачи многих тел (N-body) с использованием разделяемой памяти.

Лекция 14

Статические переменные. Константная память. Текстурная память. Конвейеры текстурной памяти: фильтрация, переадресация. Нормализованные и целочисленные координаты.
Задача. Параллельный алгоритм вычисление свертки функций с использованием текстурной и разделяемой памяти в задачах обработки сигнала (изображения).

Лекция 15

Режим фильтрации в текстурной памяти. Вычисления конечно-разностных производных.
Задача. Интерполяция конечно-разностной функции при переходе из одной системы координат в другую.

Лекция 16

Алгоритм параллельной редукции с использованием разделяемой памяти. Оптимизация алгоритма редукции (ветвления в варпах (warps), банк-конфликты (bank-conflict), развертка циклов).
Задача. Параллельное суммирование рядов на GPU.

Лекция 17

Свободные параллельные библиотеки на GPU. Библиотека линейной алгебры CUBLAS. Библиотека быстрого преобразования Фурье CUFFT.
Задача. Задача о нахождении электрического поля, создаваемого плотность электрического заряда. Уравнение Пуассона. Быстрое преобразование Фурье.

Лекция 18

Свободные параллельные библиотеки на GPU. Библиотека генератора псевдо-случайных чисел CURAND. Библиотека для работы с разряженными матрицами CUSPARS. Библиотека шаблонов STL – Thrust. Библиотека примитивов NPP.
Задача. Задача вычисления интеграла методом Монте-Карло.

Лекция 19

Параллельный алгоритм решения системы нелинейных алгебраических уравнений. Непрерывный аналог метода Ньютона. Понятие производной Фреше. Оптимизация доступа в память.
Задача. Реализация алгоритма решения СНАУ

Лекция 20

Уравнения гидрогазодинамики (Навье-Стокса). Параллельный алгоритм численного моделирования течения несжимаемой жидкости на GPU. Схема расщепления, метод прогонки, оптимизация доступа в глобальную память. Оценка производительности.

Лекция 21

Задача трассировки лучей (Ray Tracing). Текстурная память. Компьютерная графика. Создание фотореалистичных изображений. Алгоритмы Boundary Volume Hierarchy (BVH) и kd-деревьев. Оценка эффективности алгоритмов.

Лекция 22

Использование метода трассировки лучей (Ray Tracing) в ускорительной физике при оценке потерь частиц пучка на структурных элементах установки (триангуляционный подход). Оптимизация, использование разделяемой памяти.

Лекция 23

Стандарт OpenMP. Основные директивы OpenMP. Использование OpenMP при распараллеливании на центральном процессоре (CPU): обработка данных, перемножение матриц, задача многих тел.

Лекция 24

Стандарт OpenACC для кросс-платформенных приложений. Описание стандарта OpenACC. Основные директивы OpenACC. Процесс компиляции приложения в OpenACC (оценка эффективности распараллеливания).
Задача. Сравнение эффективности параллельных реализаций на CPU OpenMP, на GPU OpenACC и на GPU CUDA: обработка данных, перемножение матриц, задача многих тел.

Лекция 25

Задача электростатики. Постановка задачи, численный метод и параллельный алгоритм реализации на GPU. 3D- моделирование распределения электрического поля банчера, инфлектора, дуантов, дефлектора в циклотроне.

Лекция 26

Задача магнитостатики. Постановка задачи, численный метод и параллельный алгоритм реализации на GPU. Моделирование распределения магнитного поля на примере установки ATLAS LHC CERN.

Лекция 27

Метод массивно-параллельной архитектуры GPU в задачах моделирования динамики пучка в ускорительной физике.
Задача. Параллельные алгоритмы трассировки частиц, оценки потерь частиц, оценки эффекта пространственного заряда пучка.

Лекция 28

Примеры оптимизация параметров циклотрона: AVF RIKEN Cyclotron (Japan).

Лекция 29

Примеры оптимизация параметров циклотронов: VINCY Cyclotron (Serbia), Custom Cyclotron (USA)

Лекция 30

Коллективные методы ускорения (В.И. Векслер). Постановка задачи, численные методы. Учѐт собственного электрического и магнитного поля пучка. Параллельный алгоритм на GPU для моделирования коллективных методов ускорения частиц на установке CUSP.

Лекция 31

Уравнение Кардара-Паризи-Жанга. Скейленговая гипотеза. Скейленговая функция и скейлинговый параметр. TASEP (Total Asymmetric Exclusion Process). Параллельный алгоритм на GPU оценки скейленговой функции и скейленгового параметра для TASEP.

Лекция 32

Вычисления в режиме Multi-GPU. Использование нескольких графических процессоров GPU на одном узле. Обмен данными между GPU (Direct 2.0). Использование интерфейсов NVLink и PCI-E. Унифицированное адресное пространство (Unified Virtual Addressing). Оптимизация нагрузки между GPU.

Лекция 33

Распараллеливание нейро-сетевых алгоритмов. Обучение нейро-сети на GPU.
Глубокое обучение (Deep Learning). Библиотеки, алгоритмы. Задача распознавания образов.

Аннотация курса

Развитие Web-технологий является следствием и движущей силой стремительного прогресса глобальной сети. Web-технологии, являясь основой для создания инструментов кросплатформенного и кроссбраузерного доступа пользователей к ресурсам глобальной сети, во многом определяют приближённый к человеческим потребностям характер представления информации и пользовательский интерфейс современных web-сайтов.

Знакомство с ними, изучение лежащих в их основе принципов и базовых понятий, получение практических знаний в данной области, представляется достаточно интересным для начинающих исследователей в области естественных наук.  Также курс может служить основой для самостоятельного углублённого изучения отдельных технологий  для задач разработки сайтов и программных продуктов -  как создания образовательных и научных web-ресурсов, так и в интересах сторонних заказчиков.

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

Основное содержание курса включает в себя знакомство с основами HTML, CSS и отработку практических навыков программирования на языках PHP и JavaScript. Кроме того, слушатель изучит возможности имеющихся средств визуализации (HTML5, PHP, R) на примерах, связанных с задачами реализации численных экспериментов.

Также будут рассмотрены основы работы с базами данных (на примере MySQL), и практические приёмы их использования как средства хранения информации в задачах web-программирования.

Помимо этого, будут затронуты вопросы клиент-серверного взаимодействия,  удалённого хранения данных, и построения систем удалённых вычислений.

Введение

В качестве серверной операционной системы в настоящее время наиболее популярной является ОС Linux, ядро которого начал разрабатывать студент Университета Хельсинки Линус Торвальдс в 1991 г.

Открытость исходного кода системы, открытость всего процесса разработки системы сделали её привлекательной для как сообщества разработчиков, так и для ряда крупных IT-корпораций. За время существования системы, она была портирована на большинство существующих аппаратных платформ, было написано большое количество прикладных программ.  Всё это обусловило значительный рост популярности системы в последние годы, прежде всего как серверной ОС (60% интернет-серверов на 2014г.), особенно для суперкомпьютеров (97% на  2014г.). Также большую популярность в последние годы получила система Android, основанная на ядре Linux (более 60% мобильных устройств на 2012г.).

Преимуществами использования системы Linux для задач создания web-ресурсов является её бесплатность, наличие специализированных и мощных серверных пакетов (web-сервера apache, nginx), стабильность системы и простота настройки. По всем аспектам использования системы можно легко найти справочную информацию в открытых источниках. Кроме того, значительным преимуществом является наличие большого числа прикладных программ, большинство из которых также распространяется бесплатно.

Именно поэтому система Linux(Ubuntu) является основой для изучения web-технологий и выполнения практических задач в данном курсе.

Язык HTML был разработан британским учёным Тимом Бернерсом-Ли приблизительно в 1986—1991 годах в стенах Европейского Центра ядерных исследований в Женеве (Швейцария). HTML создавался как язык для обмена научной и технической документацией, пригодный для использования людьми, не являющимися специалистами в области вёрстки. В ходе развитии сети Интернет (WWW) язык HTMLстал основой для оформления гипертекстовых web-страниц.

С течением времени язык HTMLсовершенствовался (HTML5), получили широкое распространение технологии для оформления web-страниц (CSS, каскадные таблицы стилей), для создания динамических страниц на уровне клиента  (язык JavaScript, Ajax), а также языки разработки серверной части web-систем (PHP). Ядром большинства современных сайтов являются системы управления контентом (Content Management Systems, CMS), на основе связки PHPи СУБД (например, MySql).

Приобретаемые знания и умения

В результате прохождения курса обучающийся должен приобрести пользовательские навыки и освоить приёмы программирования в Linux, принципы работы сетевых сервисов Linux, изучить основы языков HTML, JavaScript (Ajax, jQuery), PHP, SQL, CSS-верстки web-страниц, принципы построения систем клиент-серверного обмена информацией, систем удалённых вычислений, приёмы визуализации и представления данных на wеb-страницах.

Образовательные технологии

Материалы курса по мере его прохождения будут доступны в электронном виде на сайте distant.msu.ru в формате дистанционного курса. Взаимодействие с преподавателем, помимо аудиторного общения, может осуществляться в дистанционной форме. Практические занятия проходят в компьютерном классе.

Каждый обучающийся получает отдельную учетную запись на виртуальной машине с установленной операционной системой Linux.

Формат курса

Курс предполагает сочетание лекций и самостоятельной практической работы. Обучающийся имеет возможность выполнять практические задания как в компьютерном классе, и удалённо (например, из дома), подключаясь к учебной виртуальной машине по RDPили SSH.

Зачёт в конце 3 семестра ставится с учётом текущей успеваемости/посещаемости, а также по результатам своевременного выполнения практических задач.

В 4 семестре обучающийся получает индивидуальное задание, которое рассматривается как курсовая работа. Выбор задания происходит с учётом мнения обучающегося. Курсовая работа предполагает использование изученных технологий и навыков для разработки клиент-серверного web-приложения, обеспечивающего проведение численного эксперимента или функционирования системы обработки экспериментальных данных.

Аннотация курса

Операционная система Linux, Являясь по своей природе открытой системой со свободно-распространяемыми исходными кодами,  стала de-facto основой вычислительной инфраструктуры подавляющего большинства университетов и вычислительных лабораторий во всем мире. Ее внедрение не требует никаких лицензионных отчислений кому бы то ни было. Поэтому, для современного ученого владение навыками работы в этой системе становятся жизненно необходимым, и важным конкурентным преимуществом на мировом рынке занятости. В данном практическом спецкурсе рассматриваются пользовательские приемы работы в ОС Linux, подробно изучается интерфейс командной строки, приемы автоматизации работы и пакетной обработки данных, верстки научных статей,  а также особенности разработки ПО с использованием встроенного инструментария. Также рассматривается система кросс-платформенного объектно-ориентированного программирования графического интерфейса QT, и дается краткое введение в мат. моделирование и математический пакет matlab. и издательский пакет Latex

Введение

Первая версия ядра операционной системы Linux была написана более 20 лет назад таким же студентом, как ты, в качестве курсовой работы по программированию на втором курсе. К тому моменту, как этот студент, Линус Торвальдс, окончил Хельсинский Политехнический институт, практически все ведущие производители оборудования и программного обеспечения уже заявили о своей поддержке этой ОС. Сегодня - Linux является основной платформой для научных вычислений, коммерческих серверных приложений, мобильных устройств, встраиваемых систем реального времени, а также стандартной основой рабочих мест во многих отраслях, будь то 3D-анимация, нефтеразведка, или обычный учебный класс в вузе или школе.

Причинами столь впечатляющего успеха являются не только следование общепринятым мировым стандартам в области ПО (POSIX), стремление к максимально возможной совместимости с существующим апаратным и программным обеспечением, но и беспрецендентая открытость процесса разработки. С момента первого сообщения о создании новой операционной системы, и по сегодняшний день любой желающий может принять участие в ее разработке и тестировании, и результат его труда увидят все остальные разработчики и пользователи. Благодаря этому, ОС Linux сегодня поддерживает рекордное количество аппаратных архитектур, устройств и файловых систем, и является ведущей площадкой для тестирования и внедрения последних инноваций в области IT.

Приобретаемые знания и умения

В результате обучающийся должен освоить приемы и навыки работы в ОС Linux, познакомиться с интерфейсом командной строки Linux, научиться использовать встроенных инструментарий для разработки ПО, и научиться писать программы с графическим интерфейсом, необходимые для написания курсовой работы.

Образовательные технологии

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

Программное обеспечение

• OS Linux, gcc 4.3 и выше

Контроль успеваемости

• Промежуточная аттестация проводится на 8 неделе, про итогам текущей успеваемости. Критерии формирования оценки – выполненные практические задания, подготовленные доклады и рефераты
• Текущая аттестация проводится еженедельно. Критерии формирования оценки – посещаемость занятий, активность студентов на семинарах, уровень подготовки к семинарам, выполнение домашних заданий

Программа курса

3 семестр:

• Устройство и архитектура ОС Linux
• Использование консольного интефейса командной строки, автоматизация работы (скрипты bash)
• Основные команды и утилиты командной строки (включая grep, sed, awk, ImageMagik, т.д.)
• Консольные текстовые редакторы (vi, Emacs)
• Управление удаленной системой (ssh, X11, VNC)
• Консольные и графические инструменты разработки на С/С++ (gcc, make, cmake, gdb, ddd, eclipse, QTCreator)

 4 семестр:

• Использование библиотеки QT для создания кроссплатформенных приложений с богатым графическим интерфесом,
• Многопотоковое и сетевое программирование средствами QT
• Основы компьютерной физики (мат. моделирование, анализ данных эксперимента)
• Прикладные пакеты математического программирования  (octave, matlab)
• Прикладные математические библиотеки C++ (Eigen), основы параллельного программирования (OpenMP)

Спецкурс не предусматривает изучения приемов системного администрирования, и не специализируется на каком-либо конкретном дистрибутиве.

 Литература

• Керниган Б. „UNIX. Программное окружение“.
• Робачевский А.М. „Операционная система Unix Издание 2“.
• Баррет Даниэл „Linux. Основные команды. Карманный справочник“.
• Секунов Н. „Программирование на C++ в Linux“.
• Чеботарев А. В. „Библиотека Qt 4. Создание прикладных приложений в среде Linux“.

Аннотация

Учебный курс посвящен основным принципам, методам и технологиям параллельного программирования, ориентированных на решение ресурсоёмких задач физически и нелинейной оптики в частности. В курсе будут подробно разобраны такие популярные технологии параллельного программирования как OpenMP и MPI. Практические занятия будут проводиться на базе выделенного учебного кластера, содержащего 14 процессоров Intel Xeon.

Завершающим этапом курса является работа над индивидуальным заданием, охватывающим весь материал курса. Курс открывает широкие возможности дальнейшего развития на переднем крае науки.

Введение

Современные научные и прикладные исследования в физике часто требуют проведения масштабных ресурсоемких вычислений. Стремительный рост производительности современных вычислительных систем достигается  за счет использование параллельно работающих процессоров или многоядерных систем. Традиционные суперкомпьютеры с оригинальной архитектурой значительно повышают производительность вычислений, однако имеют существенный недостаток – большую цену, чем серьёзно уступают кластерным системам. При существенном снижении стоимости производительность кластерной системы в большом классе задач остается весьма высокой. Так, согласно последнему списку наиболее мощных компьютеров мира (www.top500.org), 81% самых производительных вычислительных систем в мире выполнены по кластерной технологии с использованием стандартных вычислительных узлов.  В тоже время стандартный вычислительный узел уже давно не является однопроцессорной машиной, и эффективность использования многопроцессорной/многоядерной архитектуры для решения одной ресурсоемкой задачи зависит от применяемых средств разработки и методов распараллеливания. Технологией ставшей де-факто стандартной в научных ресурсоёмких приложениях является OpenMP, поддерживаемая всеми современными разработчиками компиляторов

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

Приобретаемые знания и умения

В результате курса слушатели получают знания об популярных технологиях параллельного программирования; знания о современных высокопроизводительных вычислительных системах и практические навыки работы на них.

Образовательные технологии

Курс имеет электронную версию учебных материалов. Практические занятия проводятся с использованием современного сетевого и проекционного оборудования.

Программное обеспечение и ресурсы в интернете

• C ++, Fortran, библиотеки Cluster OpenMP*, MPI-2.0
• http://www.mpi-forum.org/
  
• http://www.intel.com/cd/software/products/emea/rus/379901.htm

Контроль успеваемости

• Промежуточная аттестация проводится на 8 неделе в форме проверки решения тестовых задач с оценкой. Критерии формирования оценки – уровень знаний пройденной части курса.
• Текущая аттестация проводится еженедельно. Критерии формирования оценки – посещаемость занятий, активность студентов на практических занятиях, уровень подготовки к семинарам.

Программа курса

Литература

• Немнюгин С.А., Стесик О.Л. "Параллельное программирование для многопроцессорных вычислительных систем.", СПб, издательство "Петербург", 2002.
• Калиткин Н.Н. "Численные методы.", Москва, издательство Наука, 1978.
• Воеводин В.В. "Параллельные структуры алгоритмов и программ.", Москва, издательство ОВМ АН СССР, 1987.
• Букатов А.А., Дацюк В.Н., Жегуло А.И. "Программирование многопроцессорных вычислительных систем.", Ростов-на-Дону, издательство ООО «ЦВВР», 2003.
• Антонов А.С. "Параллельное программирование с использованием технологии MPI", Москва, издательство Московского университета, 2004.
• Корнеев В.Д. "Параллельное программирование в MPI", издательство "Регулярная и хаотическая динамика", 2003.
• Эндрюс Г.Р. "Основы многопоточного, параллельного и распределенного программирования", издательство "Вильямс", 2003.
• Богачев К.Ю. "Основы параллельного программирования",  Москва, издательство "Бином. Лаборатория знаний", 2003.
• Буравлёв А., Чельдиев М., Барыбин А. и др. "Масштабируемые мультипроцессорные вычислительные системы высокой производительности." // Современные технологии автоматизации (СТА), № 3, с.72-77, 2009.
• Boyde L., Chalut K.J. and Guck J. "Near- and far-field scattering from arbitrary three-dimensional aggregates of coated spheres using parallel computing" // Phys. Rev. E, v. 83, p. 026701, 2011.
• Fujisawa A., Shimizu A., Itoh K., et al. "Wavelet analyses using parallel computing for plasma turbulence studies." // Phys. Plasmas, v. 17, p. 104503, 2010.
• Chou Yu-Ch., Nestinger S.S., Cheng H.H. "MPI: Interpretive Parallel Computing in C" // Comput. Sci. Eng., v. 12, p. 54, 2010.
• Raghunathan S. "Parallel Computing Algorithms and Applications: Scientific Parallel Computing" // Comput. Sci. Eng., v. 9, p. 64, 2007.