PDC

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

О курсе

Курс читается для студентов 3-го курса ПМИ ФКН ВШЭ специализации "Распределенные системы" в 1-2 модулях.

Лектор: Сухорослов Олег Викторович

Семинаристы: Протасов Станислав Игоревич, Смирнов Сергей Андреевич, Сухорослов Олег Викторович

Полезные ссылки

Актуальная программа курса

Репозиторий с материалами курса

Страница курса в Anytask

Канал для объявлений

Группа для обсуждений

Правила выставления оценок

Текущий контроль проводится в форме практических домашних заданий. Всего будет 6 заданий. Каждое домашнее задание оценивается по 10-балльной шкале. Оценки выставляются в Anytask.

Итоговая оценка вычисляется на основе оценки за работу в семестре и оценки за экзамен:

Oитог = 0.8 * Oнакопл + 0.2 * Оэкз

Накопленная оценка вычисляется как среднее по всем практическим заданиям. Дополнительно предусмотрены бонусные баллы за работу на семинарах, которые семинарист может добавить к оценке в конце семестра.

Накопленная и итоговая оценки округляются арифметически.

Правила сдачи заданий

За каждый день просрочки после мягкого дедлайна снимается 2 балла. После жёсткого дедлайна решения не принимаются.

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

При наличии уважительной причины дедлайн по домашнему заданию может быть перенесён на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.

Лекции

Неделя Дата Темы
1 07.09.2018 Введение в параллельные вычисления. Параллельные вычислительные системы.
2 14.09.2018 Многопоточное программирование.
3 21.09.2018 Многопоточное программирование (ч.2). Альтернативные модели программирования.
4 28.09.2018 Теоретические основы параллельных вычислений. Типовые структуры параллельных алгоритмов.
5 05.10.2018 Принципы разработки параллельных алгоритмов. Методология PCAM.
6 12.10.2018 Введение в вычисления на GPU.
7 19.10.2018 Шаблоны вычислений на GPU.
8 02.11.2018 Параллельное программирование на MPI.
9 09.11.2018 Параллельное программирование на MPI (ч.2).
10 16.11.2018 Введение в распределенные вычисления.
11 23.11.2018 Отказы, репликация и согласованность.
12 30.11.2018 (Лекции не будет)
13 07.12.2018 Распределенная обработка больших данных.
14 14.12.2018 Облачные вычисления.

Семинары

Неделя Темы
1 Профилирование программ.
2 C++ thread support library. Отладка многопоточных программ. Предотвращение взаимной блокировки. Атомарные инструкции и низкоуровневые эффекты.
3 Условная синхронизация. Асинхронные вычисления. Пул потоков.
4 Знакомство с технологией OpenMP.
5 Знакомство с технологией OpenMP (часть 2). Разбор ДЗ 1.
6 Знакомство с CUDA C.
7 Знакомство с CUDA C (часть 2). Разбор ДЗ 2.
8 Знакомство с MPI.
9 Знакомство с MPI (часть 2). Разбор ДЗ 3.
10 Взаимодействие удаленных процессов.
11 Взаимодействие удаленных процессов (часть 2). Разбор ДЗ 4.
12 Практикум по работе с сетевыми сервисами.
13 Платформа Apache Hadoop. Реализация MapReduce-программ на Hadoop Streaming.
14 Разбор ДЗ 5-6.

Домашние задания

Для каждого задания предоставляется ссылка на сервис, содержащий описание задания и реализующий тестирование решений. Данные сервисы размещаются на платформе Everest (см. далее).

Задание Мягкий дедлайн Жесткий дедлайн
1 Обедающие философы 3 октября 00:00 MSK 5 октября 00:00 MSK
2 Метод k-средних 17 октября 00:00 MSK 19 октября 00:00 MSK
3 Умножение матриц на GPU 8 ноября 00:00 MSK 9 ноября 00:00 MSK
4 MPI Heat 2D 21 ноября 00:00 MSK 23 ноября 00:00 MSK
5 Мастер-рабочие 5 декабря 00:00 MSK 7 декабря 00:00 MSK
6 Мастер-рабочие 2 12 декабря 00:00 MSK 14 декабря 00:00 MSK

Тестирование решений

На странице каждого сервиса содержится описание задания и выполняемых тестов. Данные тесты могут не покрывать все возможные ошибки и не заменяют самостоятельное тестирование своих решений. Тем не менее, результаты тестов позволяют составить представление о работе вашей программы и используются при проверке решений преподавателями.

Для тестирования решения необходимо перейти во вкладку Submit Job, загрузить требуемые файлы и нажать кнопку Submit. При этом происходит перенаправление на страницу нового задания (job), где можно отслеживать его состояние. Информация на странице обновляется автоматически. После окончания выполнения задания (состояние DONE или FAILED) становится доступной вкладка Outputs, где можно увидеть вывод с результатами тестирования.

Время выполнения тестов обычно составляет несколько минут, однако при большом количестве одновременных запросов к сервису время ожидания увеличивается. Поэтому лучше не откладывать тестирование на последний момент. Число попыток при тестировании не ограничено.

Сдача решений

Сдача решений происходит через систему Anytask. Страница курса: https://anytask.org/course/367. Инвайт будет разослан отдельно.

Для сдачи решения надо перейти в раздел Задачи, нажать Сдать напротив нужного задания и отправить текст, содержащий:

  • краткое описание вашего решения (основная идея, особенности реализации, соответствие условиям задания и т.д.), которое бы позволило проверяющему быстрее разобраться в нём (приветствуются также комментарии в коде),
  • ссылку на результаты тестирования вашего решения в Everest вида https://everest.distcomp.org/jobs/JOB_ID. Ваша программа доступна во вкладке Inputs на Everest, поэтому её не требуется отдельно загружать в Anytask.

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

Проверка решений

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

Каждое задание оценивается по 10-балльной шкале. За каждый день просрочки после мягкого дедлайна снимается 2 балла. После жёсткого дедлайна решения не принимаются.

Everest

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

Для получения доступа к сервисам надо выполнить следующие действия:

  • Зайдите на Everest и зарегистрируйте нового пользователя (ccылка Sign Up в правом верхнем углу)
  • Зайдите под своим пользователем
  • Вступите в группу pdc-hse2018

При работе с Everest рекомендуется использовать свежие версии браузеров Chrome или Firfeox. Обязательно следует включить выполнение JavaScript.

Экзамен

Экзамен устный. Выдается один вопрос из списка. Для подготовки ответа дается время, можно пользоваться любыми источниками. В случае Oнакоп < 6, после ответа на основной вопрос задается дополнительный вопрос без времени на подготовку. Автомат за экзамен возможен при Oнакоп ≥ 8.

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

Архитектура компьютера

Многопоточное программирование и concurrency

  • Anthony Williams. C++ Concurrency in Action: Practical Multithreading. Manning, 2012. (Перевод на русский: Энтони Уильямс. Параллельное программирование на C++ в действии: Практика разработки многопоточных программ. ДМК Пресс, 2012.)
  • Paul Butcher. Seven Concurrency Models in Seven Weeks: When Threads Unravel. Pragmatic Bookshelf, 2014.
  • Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2012 (Revised Reprint).

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

  • Peter Pacheco. An Introduction to Parallel Programming. Morgan Kaufmann, 2011.
  • G. Barlas. Multicore and GPU Programming: An Integrated Approach. Morgan Kaufmann, 2014.
  • Foster I. Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley, 1995. http://bit.ly/2vfOkO6
  • Tim Mattson. Introduction to OpenMP, 2013. http://tinyurl.com/OpenMP-Tutorial
  • David B. Kirk, Wen-mei W. Hwu. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann, 2016 (3rd edition).
  • W. Gropp, E. Lusk, A. Skjellum. Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press, 2014 (3rd edition).

Распределенные системы

  • George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Blair. Distributed Systems: Concepts and Design. Addison Wesley, 2011 (5th edition). http://www.cdk5.net/
  • Andrew S. Tanenbaum, Maarten van Steen. Distributed Systems: Principles and Paradigms. Pearson, 2007 (2nd edition). (Перевод на русский 1-го издания: Э. Таненбаум, М. ван Стеен. Распределенные системы. Принципы и парадигмы. - СПб.: Питер, 2003.)
  • Martin Kleppmann. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media, 2017.

Обработка больших данных

  • Jimmy Lin, Chris Dyer. Data-Intensive Text Processing with MapReduce, 2010. http://lintool.github.io/MapReduceAlgorithms/
  • Martin Kleppmann. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media, 2017.
  • Nathan Marz, James Warren. Big Data: Principles and best practices of scalable realtime data systems. Manning Publications, 2015. (Перевод на русский: Натан Марц, Джеймс Уоррен. Большие данные. Принципы и практика построения масштабируемых систем обработки данных в реальном времени. - М.: Вильямс, 2016.)
  • Tom White. Hadoop: The Definitive Guide: Storage and Analysis at Internet Scale. O'Reilly Media, 2015 (4th edition). (Перевод на русский: Том Уайт. Hadoop. Подробное руководство. - СПб.: Питер, 2013.)