Параллельные вычисления

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

Департамент прикладной математики

Статус:

Курс обязательный

Когда читается:

5-й курс, 1, 2 модуль

Преподаватель

Тимофеев Алексей Владимирович

Программа дисциплины

Аннотация

Настоящая дисциплина относится к циклу дисциплин математических и естественно-научных и блоку дисциплин, обеспечивающих подготовку специалиста. Для этой специализации настоящая дисциплина является базовой. Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: • Языки программирования, • Аппаратные средства вычислительной техники, • Методы программирования, • Операционные системы, • Сети и системы передачи информации, • Математическая логика и теория алгоритмов. Дисциплина реализуется в он-лайн формате

Цель освоения дисциплины

• Формирование представления об основных технологиях параллельных вычислений.
• Ознакомление с методами и принципа создания параллельных алгоритмов.
• Освоение технологий параллельного программирования для дальнейшего использования при решении ресурсоёмких вычислительных задач математического анализа, компьютерной безопасности, защиты информации и других направлений.
• Формирования базовых знаний в области оптимизации и ускорения ресурсоёмких компьютерных вычислений.

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

• Пишет простые программы с использованием технологии MPI для запуска на кластере. Может оценить вычислительную мощность суперкомпьютера.
• Создаёт параллельный код с использованием MPI для часто используемых алгоритмов. Проводит анализ эффективности параллельных алгоритмов.
• Создаёт параллельный код с использованием OpenMP, PosixThreads, автоматического распараллеливания.
• Создаёт параллельный код с использованием CUDA, OpenACC.

Содержание учебной дисциплины

• Обзор суперкомпьютерных технологий. Введение в Linux, bash, работу на суперкомпьютере. Основы MPI. Двухточечные и коллективные обмены.
  Зачем нужны суперкомпьютеры? Задачи, требующие больших вычислений. Обзор рейтинга Тор-500. Метод классической молекулярной динамики и Монте-Крало: история, область применения, преимуществ, недостатки, положение среди других вычислительных методов. Примеры актуальных задач физики конденсированного вещества и неидеальной плазмы с демонстрацией результатов МД моделирования. Linux. Основные понятия. Навигация, основные команды. Создание, удаление и копирование файлов. Каталоги. Понятие учётной записи. Права доступа в Linux. Процессы в Linux. Понятие скриптов в Unix-системах. Интерпретаторы скриптов. Командная оболочка bash. Особенности работы. Программирование для Bash: переменные, ветвление, циклы. Арифметические операторы. Работа с файлами: перенаправление ввода и вывода, конвейерная обработка данных (pipes), регулярные выражения. Работа с аргументами командной строки. Оптимизация рутинных задач. Компиляция и запуск программ. Представление о работе компиляторов (для C/C++ - объектные файлы и библиотеки, заголовочные файлы, система сборки, зависимости). Текстовые редакторы (vim, …). Обзор основных возможностей gnuplot. Использование скриптов. Последовательная и параллельная модели программирования. Парадигмы параллельного программирования и соответствующие программные средства. Программная реализация MPI. Типовые схемы организации параллельных MPIпрограмм и их структура. Компиляция и запуск MPI-программ. Проблема поиска ошибок. Исследование вычислительного кластера с помощью средств MPI и Bash. Оценка производительности многопроцессорных вычислительных систем. Организация двухточечных обменов. Блокирующие операции: режимы, реализация в MPI, примеры. Стандартный обмен, обмен с буферизацией, обмен “по готовности”. Проблемы при организации двухточечных обменов. Неблокирующие операции. Широковещательная рассылка. Операции распределения и сбора данных, опреация приведения. Синхронизация в параллельном программировании. Средства синхронизации в MPI.
• Теоретические и практические основы параллельных алгоритмов.
  Теория функциональных устройств. Понятия загруженности, производительности и ускорения. Эффективность распараллеливания, законы Амдала. Информационная зависимость операций, графы исполнения. Параллельная форма алгоритма. Модель вычислений в виде графа "операции – операнды". Основные показатели качества параллельных методов — ускорение, эффективность (efficiency), стоимость (cost) и масштабируемость (scalability) вычислений. Базовые принципы разработки параллельных алгоритмов. Основные понятия, все этапы создания и анализа параллельных алгоритмов. Постановка задачи и последовательный алгоритм ее решения. Методы разделения матрицы между процессорами вычислительной системы, которые необходимы для параллельной реализации матричных операций. Три возможных подхода к параллельной реализации алгоритма умножения матрицы на вектор. Возможные подходы к параллельной реализации алгоритма умножения матриц и наиболее широко известные алгоритмы: алгоритм, основанный на ленточной схеме разделения данных, алгоритм Фокса (Fox) и алгоритм Кэннона (Cannon). Задача решения систем линейных уравнений. Необходимые определения и постановка задачи. Последовательный и параллельный варианты одного из прямых методов решения линейных систем общего вида – метода Гаусса. Описание последовательного и параллельного алгоритмов, реализующих итерационный метод сопряженных градиентов. Эффективность распараллеливания, законы Амдала. Закон ГуставсонаБарсиса. Модель вычислений в виде графа "операции – операнды". Основные показатели качества параллельных методов — ускорение, эффективность (efficiency), стоимость (cost) и масштабируемость (scalability) вычислений. Анализ влияния расчётов, передачи информации и вывода данных на общее время расчёта. Составление формул, оценка основных констант, сравнение с практическими результатами.
• Основы параллелизации с помощью технологий OpenMP, PosixThreads, автоматического распараллеливания.
  Процессы и потоки. Создание многопоточных приложений. Объекты синхронизации потоков: критическая секция, взаимное исключение, семафор, событие. Тупики (deadlocks). Проблемы недостаточной и избыточной синхронизации. Компиляция и запуск программ. Принципы параллелизации. Методы распараллеливания циклов. Отладка параллельных приложений. Примеры программ для OpenMP. Примеры программ для PosixThreads. Практика.
• Основы использования графических ускорителей с помощью технологий CUDA, OpenACC и др.
  Применение GPU для вычислений, не связанных с обработкой графических изображений. Архитектура GPU, выпускаемых ведущими производителями. Ключевое значение параллелизма по данным. Организация памяти и избежание задержек, связанных с обращением к памяти. Средства разработки программ для GPU. Кластеры на основе гибридных систем, включающих GPU. Примеры программ для CUDA, OpenACC. Практика.

Элементы контроля

• Занятие
• Тесты
• Задание
• Экзамен
  На зачете/экзамене студент может получить дополнительный вопрос (теоретический вопрос, дополнительную практическую задачу, домашнее задание), ответ на который оценивается в 1 балл.
• Занятие
• Тесты
• Задание
• Экзамен
  На зачете/экзамене студент может получить дополнительный вопрос (теоретический вопрос, дополнительную практическую задачу, домашнее задание), ответ на который оценивается в 1 балл.

Промежуточная аттестация

• Промежуточная аттестация (2 модуль)
  0.36 * Задание + 0.12 * Занятие + 0.12 * Тесты + 0.4 * Экзамен

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

Рекомендуемая основная литература

• Антонов А.С. - Параллельное программирование с использованием технологии MPI - Национальный Открытый Университет "ИНТУИТ" - 2016 - 83с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100359
• Малявко А. А. - ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ НА ОСНОВЕ ТЕХНОЛОГИЙ OPENMP, MPI, CUDA 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 129с. - ISBN: 978-5-534-11827-8 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/parallelnoe-programmirovanie-na-osnove-tehnologiy-openmp-mpi-cuda-446247

Рекомендуемая дополнительная литература

• Гергель В.П. - Теория и практика параллельных вычислений - Национальный Открытый Университет "ИНТУИТ" - 2016 - 500с. - ISBN: 978-5-94774-645-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100527
• Левин М.П. - Параллельное программирование с использованием OpenMP - Национальный Открытый Университет "ИНТУИТ" - 2016 - 133с. - ISBN: 978-5-94774-857-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100358
• Модели параллельного программирования: Практическое пособие / Федотов И.Е. - М.:СОЛОН-Пр., 2017. - 392 с.: 60x88 1/8. - (Библиотека профессионала) ISBN 978-5-91359-222-4
• Туральчук К.А. - Параллельное программирование с помощью языка C# - Национальный Открытый Университет "ИНТУИТ" - 2016 - 189с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100360
• Энтони Уильямс - Параллельное программирование на C++ в действии. Практика разработки многопоточных программ - Издательство "ДМК Пресс" - 2012 - 672с. - ISBN: 978-5-94074-448-1 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/4813