Методы и алгоритмы параллельного программирования

内容描述: Курс дает представление о моделировании и анализе параллельных вычислений, принципах разработки параллельных алгоритмов и программ, технологиях и системах разработки параллельных программ, параллельных численных алгоритмах. По окончании курса магистрант способен строить модель выполнения параллельных программ, оценивать эффективности параллельных вычислений, анализировать сложность вычислений и возможность распараллеливания разрабатываемых алгоритмов, оценивать основные параметры программ.

贷款数: 5

Пререквизиты:

• Современные среды и языки программирования
• Алгоритмы, структуры данных и программирование

*СomplexityDiscipline(zh-CN)*:

零件: Компонент по выбору

循环次数: Профилирующие дисциплины

Цель

• Изучении математических моделей, методов и технологий параллельного программирования для многопроцессорных вычислительных систем (МВС) в объеме, достаточном для успешного начала работ в области параллельного программирования.

Задача

• Формирование у студентов теоретических знаний и практических навыков разработки алгоритмов и программ и их реализации на (МВС) (суперкомпьютерах).

Результат обучения: знание и понимание

• Методы параллельных вычислений для задач вычислительной математики.
• Основные подходы к разработке параллельных программ

Результат обучения: применение знаний и пониманий

• Строить модель выполнения параллельных программ.
• Применять общие схемы разработки параллельных программ для реализаций собственных алгоритмов.

Результат обучения: формирование суждений

• Анализировать сложность вычислений и возможность распараллеливания разрабатываемых алгоритмов.
• Оценивать основные параметры получаемых параллельных программ, таких как ускорение, эффективность и масштабируемость.
• Способность разрабатывать и анализировать концептуальные и теоретические модели решаемых научных проблем и задач.

Результат обучения: коммуникативные способности

• Развивать коммуникативные способности, в том числе владение минимум одним иностранным языком для работы с открытыми ресурсами интернет и навыки межличностной и групповой коммуникации для делового взаимодействия в рамках ИТ проектов и других видов деятельности.

Результат обучения: навыки обучения или способности к учебе

• Навык разработки параллельных программ для МВС с применением технологий MPI, OpenMP.

*TeachingMethods(zh-CN)*

Модульно-блочные технологии. В основе модульный или циклический тип обучения, а также информационно-коммуникационный (в том числе дистанционные образовательные технологии). Ведущими формами обучения выступают лекции, а методами эвристический, программированный и объяснительно-иллюстративный. Основными средствами диагностики являются итоговые письменные работы и выполнение работ по пройденным темам и разделам.

Темы лекционных занятий

• Введение в параллельные вычисления. Архитектура ВС. Классификация вычислительных систем. Пути достижения параллелизма. Параллелизм на уровне команд, потоков, приложений. Анализ эффективности параллельных вычислений. Закон Амдала.
• Проблемы разработки параллельных приложений. Декомпозиция, выявление информационных зависимостей между подзадачами, масштабирование подзадач и балансировка нагрузки для каждого процессора.
• Работа с потоками. Создание потоков, ожидания завершения потоков. Пул потоков ThreadPool.
• Средства синхронизации. Критическая секция. Конструкция Lock. Атомарные операторы. Класс Interlocked Семафоры. Semaphore и SemaphoreSlim Классы Monitor и Mutex Сообщения ManualResetEvent, AutoResetEvent Классы SpinLock и SpinWait
• Конкурентные коллекции. Потокобезопасные коллекции пространства имен System.Collections.Concurrent.
• Работа с задачами. Основные возможности TPL: асинхронные задачи, императивный параллелизм, декларативный параллелизм Работа с задачами. Вложенные задачи. Задачи-продолжения. Обработка исключений в задачах. Механизм отмены задач
• Шаблоны параллелизма Parallel Параллельные циклы Parallel.For, Parallel.ForEach Дополнительные возможности циклов: досрочный выход из цикла, пакетная обработка диапазонов, реализация агрегированных вычислений. Методы Parallel.Invoke для реализации алгоритмов Эразделяй-и-властвуй".
• Технология PLINQ Параллелизм PLINQ-запросов. Анализ оптимальности. Вынужденный параллелизм. Упорядочивание элементов в PLINQ-запросах Разделение данных при выполнении PLINQ-запросов: разделение по диапазону, блочное разделение, хеш-секционирование. Буферизация выполнения PLINQ-запросов. Агрегированные вычисления с помощью PLINQ-запросов.
• Планировщик задач Организация планировщика: глобальная очередь задач, локальные очереди рабочих потоков. Стратегии планировщика: WorkStealing, Inlined threading, Inject threads Опции задач: LongRunning, PreferFairness.
• Типовые модели параллельных приложений Шаблон MapReduce. Реализация с помощью PLINQ-запросов. Шаблон Scan/Fold. Реализация с помощью Parallel.For. Распараллеливание рекурсивных алгоритмов.

Основная литература

• Антонов А.С. Технологии параллельного программирования MPI и Open MP: Учебное пособие для вузов. – М.: Изд-во МГУ, 2012. – 344 с.
• Старченко А.В., Данилкин Е.А., и др. Практикум по методам параллельных вычислений: Учебник. – М.: Изд-во МГУ, 2010. – 200 с.
• Волосова А.В. Параллельные методы и алгоритмы [Электронный ресурс]: учебное пособие/ А.В. Волосова. ‒ М.: МАДИ, Электронные текстовые и графические данные (5,35 Мбайт). 2020. – 176 с.
• Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ – Петербург, 2002. - 608 с.

Дополнительная литература

• Якобовский М. В. Введение в параллельные методы решения задач: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2013. – 328 с., илл
• Боресков А.В., Харламов А.А. Параллельные вычисления на GPU. Архитектура и программная модель CUDA: Учеб. пособие. – М.: Изд. МГУ, 2012. – 336 с.
• Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. – М.: ДМК Пресс, 2013.– 232 с.
• Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем: Учебник – М.: Изд-во МГУ, 2010. – 544 с
• Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. – М.: ДМК Пресс, 2011. – 231 с.
• Воеводин В.В. Вычислительная математика и структура алгоритмов: Учебник. – М.: Изд-во МГУ, 2010. – 168 с.