PARALLEL.RU - Информационно-аналитический центр по параллельным вычислениям

Информация к зачёту (экзамену) по курсу "Суперкомпьютеры и параллельная обработка данных".

---

Лекторы:

• Воеводин Владимир Валентинович, voevodin@parallel.ru
• Антонов Александр Сергеевич, asa@parallel.ru

---

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

1. Зачёт (экзамен) в форме беседы с преподавателем.
2. Зачёт в форме электронного тестирования.
3. Зачёт за выполнение практического задания.
4. Конкурс изображений "Параллелизм вокруг нас".
5. Конкурс выступлений в формате "Научный стенд-ап".

---

Зачёт (экзамен) в форме беседы с преподавателем.

• Даты зачётов (экзаменов) и аудитории:
  • 23 декабря (понедельник), ауд. П-14, порядок прихода групп (внимание, есть небольшое изменение!):
    • 9:00 - 323, 404, 405, 415, 417
    • 10:00 - М-118, 401, 402, 403, 406, 407
    • 11:00 - 416, 418
    • 14:00 - 411, 413, 414
    • 15:00 - 412, 419
  • 25 декабря (среда), ауд. П-14: второй поток с 9:00, первый поток с 14:00
  • 27 декабря (пятница), ауд. П-8 (комиссия), все с 9:00
• Вопросы к зачёту (экзамену). В каждом билете будет по 2 вопроса.
• На зачёте не разрешается пользоваться никакими материалами.
• Те группы, учебный план которых предусматривает экзамен по этому предмету, сдают его в те же сроки и по тем же билетам, но с проставлением оценки. За другие формы сдачи экзаменационная оценка не ставится, но может быть получен объявленный "бонус" (+1 балл).

---

Зачёт в форме электронного тестирования.

• По результатам электронного тестирования зачёт (+1 балл на экзамене) получают (при выставлении зачётов автоматом за электронное тестирование учитывалось также посещение лекций):

• Магистратура, М118:
  Королев Алексей Константинович
  Олохтонов Алексей Андреевич

  323 группа:
  Камалов Ирек Маратович
  Личманов Дмитрий Игоревич
  Ни Юлия Авроровна
  Питанов Елисей Сергеевич
  Тыркалов Евгений Олегович
  Шульгин Евгений Алексеевич

  401 группа:
  Артёмкин Кирилл Романович
  Бабаков Вадим Валерьевич
  Кононыхин Данил Александрович
  Косов Александр Владимирович
  Кочкарев Алексей Вячеславович
  Тихонова Варвара Андреевна

  402 группа:
  Бажитов Сергей Денисович
  Котельников Илья Александрович
  Новоселова Дарья Дмитриевна
         
  403 группа:
  Агафонов Никита Владимирович
  Карпов Егор Дмитриевич
  Титова Анастасия Ивановна

  404 группа:
  Балобанова Надежда Алексеевна
  Кислицын Виктор Алексеевич
  Кочетов Егор Владимирович
  Уваркин Илья Геннадьевич
  Филиппова Мария Анатольевна

  405 группа:
  Зайденварг Алиса Андреевна
  Панферова Ирина Андреевна

  407 группа:
  Фирсов Арсений Николаевич

  411 группа:
  Пилипенко Александр Олегович

  412 группа:
  Узакбай Каби Куанышбекулы

  413 группа:
  Зенкин Никита Николаевич
  Пешков Сергей Сергеевич

  414 группа:
  Бегишев Руслан Ренатович
  Горбатова Елена Сергеевна
  Закотенко Илья Сергеевич
  Лойко Анна Андреевна
  Полежаева Дарья Максимовна
  Полянина Виктория Валерьевна
  Хитрина Дарья Сергеевна

  415 группа:
  Зинченко Михаил Геннадьевич
  Касымов Алишер Бахытович
  Кожевец Полина Юрьевна
  Кондрашев Михаил Викторович
  Кулешов Игорь Александрович
  Наумова Арина Алексеевна
  Пак Инна Владимировна
  Садков Григорий Алексеевич

  416 группа:
  Анашкина Екатерина Андреевна
  Буланбаев Артур Ильдарович
  Гудков Иван Дмитриевич
  Имеев Мерген Анатольевич
  Камбаров Динмухаммед Кайыпбекулы
  Кинзябаев Ильяс Рустамович
  Маргасов Арсений Олегович
  Мифтяхетдинова Динара Ренатовна
  Наволоцкий Алексей Александрович
  Тимофеев Сергей Юрьевич

  417 группа:
  Кормаков Георгий Владимирович
  Королев Николай Сергеевич
  Лукьянов Павел Александрович
  Петренко Дарья Павловна
  Попов Дмитрий Олегович
  Саенко Иван Александрович
  Ташевцев Артем Евгеньевич

  418 группа:
  Ержанов Жалгас Калиевич
  Лопунов Михаил Александрович
  Макеев Сергей Данилович
  Омарова Мадина Муратовна
  Панкратов Максим Алексеевич
  Пименов Никита Владимирович
  Попков Георгий Александрович

  419 группа:
  Гуртова Кристина Сергеевна
  Дороднов Григорий Олегович
  Ергалиев Иса Гимранулы
  Лысаков Иван Вячеславович
  Панов Алексей Сергеевич
  Стрельникова Наталия Павловна
  Тхамокова Амина Анзоровна
  Шляхтина Елена Анатольевна

• Тестирование будет проводиться посредством системы http://sigma.parallel.ru
• Электронное тестирование будет проводиться 17.12 с 14:35 до 16:15.
• Пароли для тестирования 07.12.2019 уже высланы старостам групп.
• Зачёт по электронному тестированию проставляется в день и во время первого устного зачёта.
• Инструкция по прохождению тестирования. Обратите внимание, что в конце проведения тестирования бывает рассинхзронизация времени, поэтому не откладывайте введение ответов на потом!
• Примеры вопросов для тестирования.
• Просьба старост групп присылать на адрес asa@parallel.ru списки групп (ФИО полностью). Получены списки групп: 323, 341/2 М-118, 401, 402, 403, 404, 405, 406, 407, 411, 412, 413, 414, 415, 416, 417, 418, 419.

---

Зачёт за выполнение практического задания.

• По результатам выполнения практического задания зачёт по курсу получают:
  • Процеров Сергей Дмитриевич, 407 группа
  • Ашабоков Аслан Нажмудинович, 415 группа
  • Чухарев Фёдор Сергеевич, 401 группа
• Зачёт проставляется в день и во время первого устного зачёта.
• Задание выполняется индивидуально.
• Требуется описать в рамках энциклопедии AlgoWiki и реализовать на суперкомпьютере "Ломоносов" параллельную версию некоторого алгоритма. Алгоритм выбирается на основе текущей научной работы, описание алгоритма должно отсутствовать в AlgoWiki.
• В AlgoWiki требуется заполнить описание алгоритма согласно такой структуре (в описании обязательно должны остаться заголовки всех разделов!), требуемые для зачёта пункты описания: 1.1-1.9, 2.4, 2.7, 3). Студенты выполняют задание в личном пространстве (т. е. статья должна называться, например, Участник:User/Алгоритм k средних). В самом начале статьи должен быть указан её автор.
• Заявка посылается на адрес asa@parallel.ru до 1 октября. Заявка должна содержать ФИО полностью, номер группы, обоснование выбора алгоритма для параллельной реализации. На основе заявки оформляется доступ на суперкомпьютер "Ломоносов-2".
• Параллельная реализация должна быть выполнена с использованием технологий MPI, OpenMP или Cuda. Для полученной реализации нужно провести исследование сильной масштабируемости. В случае плохой масштабируемости требуется определить основные мешающие факторы.
• До 22 октября должна быть сформирована страничка с описанием алгоритма в энциклопедии AlgoWiki. К этому сроку должны быть заполнены пункты описания 1.1, 1.2 и 3. Адрес страницы нужно прислать на asa@parallel.ru.
• Отчёт по заданию посылается на адрес asa@parallel.ru. Срок представления отчёта - 3 декабря.
• Отчёт должен включать:
  • обоснование выбора алгоритма для параллельной реализации;
  • ссылку на описание выбранного математического алгоритма в энциклопедии AlgoWiki;
  • результаты запусков на суперкомпьютере "Ломоносов";
  • график сильной масштабируемости с пояснениями;
  • объяснение полученных результатов.
• К отчёту должен прилагаться текст программы с краткими комментариями.
• Собранные результаты должны быть объяснимы и повторяемы.
• В отчёте должны содержаться сведения о программно-аппаратной среде, в которой получены результаты (компьютер, компилятор с использованными опциями оптимизации, библиотеки и т.д.)
• Каждый прогон программы с новыми параметрами рекомендуется выполнять несколько раз с последующим усреднением результата (для избавления от случайных выбросов).
• Количество процессов рекомендуется задавать в виде p=2ⁿ, n=0, 1, 2, …, k, где k определяется доступными ресурсами.

---

Конкурс изображений "Параллелизм вокруг нас".

Победители конкурса в 2019 году

I номинация.

• Купраш Екатерина Дмитриевна, 418 группа. Этот шуточный комикс с помощью довольно частой жизненной ситуации (хотя и утрированной) иллюстрирует тупиковую ситуацию (deadlock) при передаче сообщений в MPI вида Recv(1), Send(1) для процесса 0 и Resv(0), Send(0) для процесса 1. Оба процесса ждут получения сообщения от другого и блокируются в этом состоянии.
• Купраш Екатерина Дмитриевна, 418 группа. Изображения символизируют классификацию Флинна по наличию параллелизма в потоках команд и данных. Музыкальный инструмент символизирует данные, а игра на нем - инструкцию. (SISD - исполнитель, играющий определенную мелодию на своем музыкальном инструменте. MISD - на одной и той же гитаре два исполнителя играют разные ноты и разные мелодии. SIMD - оркестр исполнителей, играют одно и то же, но на разных гитарах. MIMD - несколько исполнителей играют каждый свою отличающуюся партию на своем инструменте).
• Абрамова Варвара Владимировна, 415 группа. Рассматривается гипотетический процесс массового производства глиняных игрушек (неавторских). Комикс нужно читать слева направо. В данной работе я хотела проиллюстрировать возможные источники параллелизма в алгоритме, а так же ‘узкое место’, которое нельзя оптимизировать средствами параллельной обработки.

I I номинация

• Купраш Екатерина Дмитриевна, 418 группа. Изображение иллюстрирует принцип распараллеливания задачи на примере поисковых миссий. Ежегодно тысячи людей пропадают без вести. При поиске потерявшихся в лесу зона практически необъятна и дорога каждая минута, поэтому все поисковые отряды действуют по принципу параллельного поиска для максимально эффективного использования сил. Поисковый отряд разбивается на небольшие группы по 2-3 человека, а зона поиска разбивается сеткой на равные квадраты, после чего поисковые группы прибывают на свой квадрат и начинают одновременно "прочёсывать". Таким образом покрывается максимальная зона за наименьшее время, и отряды не мешают друг другу и не ищут в одном месте дважды.
• Толкачев Олег Григорьевич, 414 группа. Песики несут палочку. Палочку может нести и один, но помочь хотят все. В итоге эффективность процесса падает как в задаче про землекопов. Но песики все равно молодцы.
• Демин Дмитрий Андреевич, 416 группа. При подготовке самолета к вылету задействовано много людей и техники. Одновременно идет посадка людей, загрузка багажа, заправка топлива, погрузка еды. Все это происходит одновременно, при этом вылет возможен только когда все процессы процессы будут завершены.

Объявляется конкурс изображений "Параллелизм вокруг нас". Изображения, присылаемые на конкурс, должны демонстрировать какие-то идеи параллельных вычислений на обыденном материале, который можно найти повсюду вокруг.

Изображения на конкурс принимаются в двух номинациях:

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

В конкурсе оценивается в первую очередь идея (соответствие тематике, оригинальность, неожиданность), но и качество изображения тоже имеет значение. Идеи без визуального воплощения на конкурс не принимаются.

Для участия в конкурсе необходимо в срок до 19 ноября прислать свои варианты изображений на адрес asa@parallel.ru. К каждому изображению необходимо написать свои ФИО, номер группы, номинацию, а также прислать пояснения - какую идею из области параллельных вычислений, по мнению автора, оно демонстрирует.

Победители конкурса в каждой номинации получают зачёт автоматом. Также возможно получение большего количества зачётов автоматом, если будут представлены достойные варианты. Авторы некоторого количества работ могут быть поощрены "бонусом на зачёте" (получат зачёт, если будет немного не хватать баллов на электронном тестировании, а также получат условный +1 балл на устном зачёте). Изображения, повторяющие идеи победителей прошлых лет, не имеют шансов на победу.

Примеры возможных изображений:

• иллюстрация конвейерного параллелизма;
• иллюстрация совместной работы;
• асинхронный параллелизм.

Зачёт победителям конкурса будет проставляться в день и во время первого устного зачёта.

Работы, победившие в 2018 году

I номинация.

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

II номинация

• Барьерная функция. Фотография иллюстрирует идею барьерной функции. Проводники, начиная с последнего вагона, выбрасывают желтый флаг. До тех пор, пока проводник первого вагона не выкинет желтый флаг, поезд не тронется.
• Конвейерность и параллелизм на примере строительства ГЗ Московского Университета. Корпуса строятся параллельно, при этом верхние этажи еще только в проекте, чуть ниже уже готов каркас, в самом низу ставят стекла и занимаются отделкой.
• Описание: модель single instruction multiple processors: командир полка 18 века отдаёт приказ открыть огонь. Из-за сильного разброса пуль для повышения вероятности поражения цели большое количество солдат стреляло одновременно, одиночные выстрелы были неэффективны, напротив одновременное поражение значительного количества солдат противника вводило оставшихся в ужас, и те отступали. Также ddos-атаки были бы неэффективны, если бы не происходили одновременно с большого количества серверов.
• Задача воспроизведения огромной анимации на трибуне стадиона распараллеливается на тысячу человек (процессов). Каждому из них необходимо в заданной последовательности поворачиваться нужной стороной, чтобы показать правильный цвет одежды. Синхронизация работы происходит при помощи звуковых сигналов. Всё работает без задержек, так как все процессы одинаково загружены и получают сигналы одновременно, а значит никого не приходится ждать. Проиллюстрирован синхронный параллелизм.

Работы, победившие в 2017 году

I номинация.

• Фигуры, собранные из магнитного конструктора "Неокуб", иллюстрируют некоторые примеры топологий компьютерных сетей. Магнитные шарики здесь играют роль узлов сети.

II номинация

• Два типа параллельных архитектур.
• Многопоточность в природе.
• Иллюстрация функции барьер.

Работы, победившие в 2016 году

I номинация.

• На картине изображены люди, подготавливающие данные, и стоящие в очереди в ожидании их загрузки. Бог мудрости Тот олицетворяет собой контролёра (ОС), позволяя параллельным процессам начать своё выполнение. Фараон (центральный узел) следит за распределением работы по рабочим-кластерам. Древнеегипетский стиль был выбран потому, что все с ним знакомы, а также он очень насыщен параллельными линиями и демонстрацией иерархичности.
• Не помню как называется такой транспорт - бар на колёсах. Предположим, где необходимая операция - передвинуться.
• Мечта любого студента — чтобы все предметы учились одновременно, и оставалось время на отдых. Но, к сожалению, не всё можно распараллелить!

II номинация

• Многопоточный параллелизм.
• Изображение иллюстрирует совместную работу.

Работы, победившие в 2015 году

I номинация.

• Параллелизм и независимость. Распараллеливание. Взаимодействие параллельных процессов и управление ими.

II номинация

• Параллельность. Ожидание и реальность.
• Конвейер. Параллелизм и независимость. Совместная работа.

---

Конкурс выступлений в формате "Научный стенд-ап".

Объявляется конкурс выступлений в формате "Научный стенд-ап" по материалам курса. Конкурс пройдёт на последней лекции курса. Каждый участник должен будет выступить в формате "Научный стенд-ап" продолжительностью до 10 минут. Выступление должно в яркой форме демонстрировать некоторые положения данного лекционного курса или своей научной работы в связке с некоторыми положениями данного курса. Зачёт по курсу получат те участники конкукрса, чьи выступления покажутся заслуживающими внимания лекторам (и, возможно, другим приглашённым членам жюри).

Желающие поучаствовать в конкурсе выступлений в формате "Научный стенд-ап" должны в срок до 19 ноября прислать примерные сценарии своих выступлений на адрес asa@parallel.ru. К конкурсу будет допущено до 6 выступающих, если желающих окажется больше, то будет проведён предварительный отбор на основе присланных сценариев.

Формат выступлений должен примерно соответствовать стилистиске подобного конкурса на канале "Культура", пример: https://tvkultura.ru/video/show/brand_id/62329/episode_id/1657831/video_id/1781186/.

---

Материалы к курсу:

• Первая лекция
• Вторая лекция
• Третья лекция
• Четвёртая лекция
• Пятая лекция
• Шестая лекция
• Седьмая лекция
• Восьмая лекция
• Девятая лекция
• Десятая лекция
• Одиннадцатая лекция
• Двенадцатая лекция
• Тринадцатая лекция
• Четырнадцатая лекция