Информация к зачёту (экзамену) по курсу "Суперкомпьютеры и параллельная обработка данных".
Лекторы:
- Воеводин Владимир Валентинович, voevodin@parallel.ru
- Антонов Александр Сергеевич, asa@parallel.ru
Альтернативные способы получения зачёта по курсу:
- Зачёт (экзамен) в форме беседы с преподавателем.
- Зачёт в форме электронного тестирования.
- Зачёт за выполнение практического задания.
- Конкурс изображений "Параллелизм вокруг нас".
- Конкурс выступлений в формате "Научный стенд-ап".
Зачёт (экзамен) в форме беседы с преподавателем.
- Даты зачётов (экзаменов):
-
28 декабря (комиссия) с 13:00 до 17:00 ауд. П-14
-
-
В билете два вопроса. Список вопросов к зачёту (экзамену).
-
На зачёте не разрешается пользоваться никакими материалами.
-
Те группы, учебный план которых предусматривает экзамен по этому предмету, сдают его в те же сроки и по тем же билетам, но с проставлением оценки. За другие формы сдачи экзаменационная оценка не ставится, но может быть получен объявленный "бонус" (+1 балл).
Зачёт в форме электронного тестирования.
- По результатам второго электронного тестирования зачёт (бонус на экзамене) получают:
- 323 группа:
- Мохов Марк Денисович
- 401 группа:
- Кнорре Дмитрий Дмитриевич
- Мозговых Василий Владимирович
- 402 группа:
- Горохов Сергей Александрович
- Продан Анатолий Дмитриевич
- 403 группа:
- Кирякин Максим Валерьевич
- 407 группа:
- Железанов Даниил Олегович
- 412 группа:
- Юневич Дарья Владимировна
- 413 группа:
- Асанова Илона Николаевна
- Петров Дмитрий Владимирович
- Соседов Максим Николаевич
- 414 группа:
- Закальская Ксения Вячеславовна
- Наровецкий Андрей Денисович
- Ямолдин Владимир Алексеевич
- 415 группа:
- Котельницкий Константин Александрович
- Юлдашев Кирилл Ринатович
- 416 группа:
- Карпов Кирилл Михайлович
- Пудовиков Андрей Дмитриевич
- Селюшкина Наталья Евгеньевна
- Хоружев Илья Максимович
- 417 группа:
- Грозный Сергей Вячеславович
- Дмитриев Леонид Алексеевич
- Скороходов Андрей Сергеевич
- 418 группа:
- Ахмедова Элина Эльмаровна
- Жумабай Мусахан Нуржанулы
- Орловский Ростислав Владиславович
- 419/1 группа:
- Кербер Вероника Борисовна
- Курганова Алина Владленовна
- 419/2 группа:
- Тарасов Данил Дамирович
- Харис Лаврентий Александрович
- 441/2 группа:
- Сазонов Георгий Владимирович
- Шеханов Алексей Сергеевич
- По результатам первого электронного тестирования зачёт (бонус на экзамене) получают:
- 323 группа:
- Зубков Дмитрий Алексеевич
- Майсюков Максим Арменович
- Маркин Игорь Валерьевич
- Овчинников Андрей Витальевич
- Пионткевич Анастасия Георгиевна
- Струков Павел Вячеславович
- Чернов Андрей Максимович
- 401 группа:
- Епанчинцев Владимир Викторович
- Кондратьева Александра Федоровна
- Спиридонова Алина Владиславна
- Худякова Екатерина Сергеевна
- 402 группа
- Власов Алексей Олегович
- Строков Вениамин Игоревич
- 403 группа:
- Александров Михаил Сергеевич
- Дьяченко Роман Романович
- Коваль Наталия Константиновна
- Лубянский Виктор Иванович
- Масс Илья Александрович
- Поворознюк Александра Павловна
- Роговой Сергей Анатольевич
- 404 группа:
- Алексеев Григорий Сергеевич
- Баулин Семён Денисович
- Комаров Пётр Христович
- Кузьменко Илья Дмитриевич
- Лебедева Алина Владимировна
- 405 группа:
- Кривотулов Егор Владимирович
- Петров Тимур Павлович
- Исанов Тамерлан Асхатович
- 407 группа:
- Афонина Анастасия Александровна
- Дергачев Федор Сергеевич
- Жилин Виктор Александрович
- Ковалев Кирилл Максимович
- Лунин Павел Евгеньевич
- Назаров Артём Сергеевич
- 409 группа:
- Бугрименко Артём Александрович
- Ковч Николай Сергеевич
- 411 группа:
- Аладина Екатерина Владимировна
- Бабаян Никита Вачеевич
- Доровских Дмитрий Игоревич
- Какунин Кирилл Витальевич
- Приходько Денис Николаевич
- Сиваченко Артём Дмитриевич
- Степаненко Егор Михайлович
- 412 группа:
- Бердникова Арина Игоревна
- Хатмуллин Эмир Наилевич
- Нурашева Джамиля Талгатовна
- 413 группа:
- Воронина Елизавета Юрьевна
- Кряженков Александр Павлович
- Харьковский Никита Максимович
- Эмиров Самир Магомедович
- 414 группа:
- Ищенко Юлия Антоновна,
- Макоева Лана Руслановна,
- Надольский Михаил Александрович
- Стан Илья Андреевич
- 415 группа:
- Антонов Кирилл Николаевич
- Витковская Таисия Славиевна
- Журавлева Ксения Александровна
- Преображенский Михаил Николаевич
- Сучков Денис Валерьевич
- Цуканова Валерия Сергеевна
- Чистяков Тимур Олегович
- Шеститко Александр Витальевич
- 416 группа:
- Арифуллин Артур Исхакович
- Викторов Антон Андреевич
- Кадерова Надия Ренатовна
- Ладысева Алина Александровна
- Навалихин Александр Ильич
- Рачков Денис Сергеевич
- Риве Алина Адриановна
- Хорошев Олег Евгеньевич
- Чевилев Никита Вячеславович
- Шурыгин Всеволод Евгеньевич
- 417 группа:
- Авдеев Роман Артемович
- Додонов Владислав Олегович
- Кадченко Иван Евгеньевич
- Мелихов Дмитрий Александрович
- Мельник Юрий Максимович
- Никифорова Мария Дмитриевна
- Оганов Александр Артурович
- Солдатов Владислав Денисович
- Сорокин Олег Владиславович
- Тохчуков Данил Андреевич
- Феоктистов Дмитрий Дмитриевич
- Черемискин Егор Андреевич
- 418 группа:
- Воробьева Злата Витальевна
- Иванов Андрей Александрович
- Столетний Александр Васильевич
- Тищенко Анастасия Сергеевна
- 419/1 группа:
- Иванова Ксения Юрьевна
- Фридрих Анна Андреевна
- 419/2 группа:
- Вигура Полина Андреевна
- Гекко Гарри Игоревич
- Голубева Алёна Алексеевна
- Зворыкина Полина Павловна
- Каракулев Константин Николаевич
- Каргин Макар Ильич
- Куртынов Владимир Дмитриевич
- Куц Арсений Дмитриевич
- Кучерин Георгий Дмитриевич
- Пак Юлия Руслановна
- Снисаренко Ольга
- 441/2 группа:
- Биктимиров Михаил Геннадьевич
- Гаврилов Никита Сергеевич
- Лысенко Данил Русланович
- Русанов Антон Евгеньевич
- Цветкова Вера Павловна
- Церех Дарья Александровна
- При выставлении зачётов автоматом за электронное тестирование учитывается также посещение лекций.
- Тестирование будет проводиться посредством системы http://sigma.parallel.ru
- Электронное тестирование будет проведено два раза:
- 15 декабря с 18:00 до 19:30 (тест ВМК-2023_02)
- 19 декабря с 14:35 до 16:05 (тест ВМК-2023)
- На выполнение теста даётся 1 час.
- Пароли для тестирования высланы старостам групп 8 декабря.
- Инструкция по прохождению тестирования. Обратите внимание, что в конце проведения тестирования бывает рассинхзронизация времени, поэтому не откладывайте введение ответов на потом!
- Примеры вопросов для тестирования.
- Просьба старост групп присылать на адрес asa@parallel.ru списки групп (ФИО полностью). Получены списки групп: 323, 401, 402, 403, 404, 405, 407, 409, 411, 412, 413, 414, 415, 416, 417, 418, 419/1, 419/2, 441/2, Казахстанский филиал.
Зачёт за выполнение практического задания.
- Зачёт за выполнение практического задания получают:
- Никишкина Евгения Геннадьевна, группа 417
- Матвеев Артем Сергеевич, группа 417
- Кривуля Полина Юрьевна, группа 417
- Биктимиров Михаил Геннадьевич, группа 441/2
- Шеханов Алексей Сергеевич, группа 441/2
- Задание выполняется индивидуально.
- Требуется описать в рамках энциклопедии AlgoWiki и реализовать на суперкомпьютере "Ломоносов-2" параллельную версию некоторого алгоритма. Алгоритм выбирается на основе текущей научной работы, описание алгоритма должно отсутствовать в AlgoWiki.
- В AlgoWiki требуется заполнить описание алгоритма согласно такой структуре (в описании обязательно должны остаться заголовки всех разделов!), требуемые для зачёта пункты описания: 1.1-1.9, 2.4, 2.7, 3). Студенты выполняют задание в личном пространстве (т.е. статья должна называться, например, Участник:User/Алгоритм k средних). В самом начале статьи должен быть указан её автор.
- Заявка посылается на адрес asa@parallel.ru до 10 октября. Заявка должна содержать ФИО полностью, номер группы, обоснование выбора алгоритма для параллельной реализации. На основе заявки оформляется доступ на суперкомпьютер "Ломоносов-2".
- Параллельная реализация должна быть выполнена с использованием технологий MPI, OpenMP или Cuda. Для полученной реализации нужно провести исследование сильной масштабируемости. В случае плохой масштабируемости требуется определить основные мешающие факторы.
- До 31 октября должна быть сформирована страничка с описанием алгоритма в энциклопедии AlgoWiki. К этому сроку должны быть заполнены пункты описания 1.1, 1.2 и 3. Адрес страницы нужно прислать на asa@parallel.ru.
- Отчёт по заданию посылается на адрес asa@parallel.ru. Срок представления отчёта - 5 декабря.
- Отчёт должен включать:
- обоснование выбора алгоритма для параллельной реализации;
- ссылку на описание выбранного математического алгоритма в энциклопедии AlgoWiki;
- результаты запусков на суперкомпьютере "Ломоносов-2";
- график сильной масштабируемости с пояснениями;
- объяснение полученных результатов.
- К отчёту должен прилагаться текст программы с краткими комментариями.
- Собранные результаты должны быть объяснимы и повторяемы.
- В отчёте должны содержаться сведения о программно-аппаратной среде, в которой получены результаты (компьютер, компилятор с использованными опциями оптимизации, библиотеки и т.д.)
- Каждый прогон программы с новыми параметрами рекомендуется выполнять несколько раз с последующим усреднением результата (для избавления от случайных выбросов).
- Количество процессов рекомендуется задавать в виде p=2n, n=0, 1, 2, …, k, где k определяется доступными ресурсами.
Конкурс изображений "Параллелизм вокруг нас".
Объявляется конкурс изображений "Параллелизм вокруг нас". Изображения, присылаемые на конкурс, должны демонстрировать какие-то идеи параллельных вычислений на обыденном материале, который можно найти повсюду вокруг.
Изображения на конкурс принимаются в двух номинациях:
- Собственные изображения, права на использование которых передаются организаторам конкурса.
- Найденные где-то (чужие) изображения.
В конкурсе оценивается в первую очередь идея (соответствие тематике, оригинальность, неожиданность), но и качество изображения тоже имеет значение. Идеи без визуального воплощения на конкурс не принимаются.
Для участия в конкурсе необходимо в срок до 21 ноября прислать свои варианты изображений на адрес asa@parallel.ru. К каждому изображению необходимо написать свои ФИО, номер группы, номинацию, а также прислать пояснения - какую идею из области параллельных вычислений, по мнению автора, оно демонстрирует.
Победители конкурса в каждой номинации получают зачёт автоматом. Также возможно получение большего количества зачётов автоматом, если будут представлены достойные варианты. Изображения, повторяющие идеи победителей прошлых лет, не имеют шансов на победу.
Примеры возможных изображений:
Зачёт победителям конкурса будет проставляться в день и во время первого устного зачёта.
Вне конкурса за проявленные творческие наклонности зачёт получают:
- Черникова Полина Георгиевна, 417 группа
- Кулешова Екатерина Сергеевна, Куренкова Дарья Александровна, Хлопкова Виктория Александровна, Забелло Мария Алексеевна, 412 группа
Работы, победившие в 2023 году
I номинация.
- Иртуганов Мансур Наилевич, группа 412. Радиотелескоп ДКР-1000 состоит из двух антенн - Восток-Запад(на фото) и Север-Юг. ВЗ включает в себя 37 матч, каждая из которых принимает сигнал. Идея из области параллельных вычислений - многопоточность. В данном случае она нужна для увеличения точности результата. Фото сделано летом в Пущино. Дополнительная ссылка: https://imgur.com/a/gitPgSC
- Волков Владимир Владимирович, группа 414. Лернейская Гидра была крайне эффективным орудием зла - потому что умела распределять свои ресурсы - она могла распараллелить процесс уничтожения героев, которые прибыли ее убить, постоянно имея несколько голов, и увеличивая свою производительность - на месте одной срубленной головы вырастало две. Одолел ее Геракл, остановив параллелизм. Он прижигал обрубки шей, чтобы она не могла отращивать новые, пока у Гидры не осталась только одна голова, с которой герой легко расправился! Опирался на картинку из интернета, но перерисовывал с нуля, используя частично позы с оригинальной картинки.
- Кожанов Илья Романович, группа 417. Данные изображения были сгенерированы нейросетью DALL.E. На изображении представлена большая столовая в обеденный перерыв. Мы видим несколько очередей, которые образовались перед разными станциями раздачи еды: салаты, горячие блюда, напитки и десерты. Каждая станция олицетворяет собой отдельный процессор суперкомпьютера, где работники столовой выступают в роли исполнительных ячеек, а посетители столовой - это задачи, которые нужно обработать. За каждой станцией стоят несколько работников столовой, которые параллельно раздают еду довольным посетителям. Выполнение задач разделено между работниками, каждый из которых независимо раздаёт еду гостям. Это демонстрирует параллельное выполнение задач и эффективное использование ресурсов процессора. Однако некоторые посетители получают стаканчик и хотят налить себе напиток, обнаруживая, что кулер с водой закончился. Это служит аналогией ограниченных ресурсов, которые могут привести к ситуации, когда потоки конкурируют за доступ к ним. На заднем плане мы видим работников столовой, которые занимаются разными задачами: кто-то меняет кулер, кто-то разогревает еду и вафельницу для десертов. Это демонстрирует работу программы, контролирующей раздачу ресурсов, а также планирование задач и определение приоритетов. В правом верхнем углу изображения есть светодиодный таймер, который отсчитывает оставшееся время обеденного перерыва. Это показывает состязательность разных задач, выполняемых в рамках установленного времени, и важность оптимизации процессов. Таким образом, на изображении создается визуальная аналогия между столовой и суперкомпьютером, который использует параллелизм для оптимизации своей работы и быстрого решения задач. Ситуация привлекательна, поскольку сочетает элементы из повседневной жизни, которые каждый знакомы с абстрактными идеями и терминами параллельной обработки данных.
- Сибирев Антон Павлович, группа 414. Вешалка-пианино (коммент не для конкурса: делал своими руками) состоит из параллельных реек. В такой конфигурации вешалка может выдержать гораздо большую нагрузку, чем 1 крючок.
- Шенгелия Анастасия Николаевна, группа 414. Данная картинка иллюстрирует проблему взаимной блокировки. Каждый из баранов ждёт, пока второй его пропустит. Так как никто из них не намерен уступать, участь баранов неутешительна.
- Ермакова Анна Ивановна группа 419/2. На коллаже фрагменты номера ансамбля народного танца МГУ <Весна> "Озорной перепляс". Танец передает историю 2 деревень, которые соревнуются, показывая свои умения. Каждую команду можно назвать отдельным процессом. В этом изображении Асинхронный параллелизм проявляется в том, что обе команды раскрывают разные характеры движений народного танца. Обе команды независимы. Акценты в их движениях расставлены по-разному, что позволяет использовать ограниченный ресурс времени номера, максимально показывая зрителю историю и особенности танца.
- Максименко Елизавета Андреевна, группа 401. Тема конкурса «Параллелизм вокруг нас» в моем понимании указывает на невидимость параллельных процессов, что мы не особо обращаем внимание на весь их объем, мощь, распространенность и необходимость. Картина помогает иначе взглянуть на зависимости параллельных явлений между собой и найти скрытые, что является аналогией представления информационного графа алгоритма в ярусно-параллельной форме. Девушка, обычная студентка, находится среди этого множества процессов. Как в конечном параллелизме, человеческий мозг способен независимо обрабатывать некоторое количество сигналов. Однако ресурсы ограничены, поэтому героиня надела наушники, чтобы снизить нагрузку на разум от лишних шумов и сфокусироваться только на определенных вещах, таких как просмотр лекции перед экзаменом (на компьютере слева) и параллельному общению с друзьями по сети (справа). Иначе, как свойственно всем студентам нашего поколения, она могла бы впасть в бесконечный цикл "поглощение большого потока информации -> тревожность -> поглощение большого потока информации -> … ", что соответствует состоянию deadlock. Далее, если углубляться в детали, сверху изображены параллельные процессы в лаборатории, несколько химических реакций протекают одновременно для нескольких экспериментов. Справа от них фрагмент пианино, без параллельного звучания нескольких звуков Чайковский никогда бы не сочинил столь прекрасные симфонии. Рядом также находится книжная полка. И хотя каждый фрагмент отдельно несет в себе смысл асинхронной параллельности, имеются более глубокий посыл: только при параллельном продвижении науки и духовности возможен прогресс. Здесь я хотела провести аналогию между переходом от человека к сверхчеловеку (по Ницше) и переходом от компьютера к суперкомпьютеру. Осталось два кусочка по центру и за девушкой: изображения антиутопии и утопии. Замысел заключался в том, что только параллельное существование этих концепций дает возможность взглянуть на мир трезво. Нетрудно подметить, что уж очень много параллельных линий на нескольких фрагментах, и даже отмечены соответственные углы. Эта геометрическая составляющая была добавлена для утрирования параллельности, чтобы все в картине кричало «ПАРАЛЛЕЛИЗМ!» Также можно заметить лестницы и падающие предметы с одного яруса на другой (книги, яблоки). Таким образом было создано ощущение связности между верхними ярусами и нижними, будто все является частью большого конвейера. И конвейер здесь - весь мир.
II номинация.
- Алексеев Илья Алексеевич, группа 417. На ретро фотографии запечатлены распределённые вычисления и иерархия памяти на примере живых вычислителей (human computers): в одной комнате сидят девушки с арифмометрами, которые выполняют простейшие вычисления, позади них стоят их непосредственные начальники, рядом с окнами несколько операторов сортировочных машин, а за ними - их начальники. У каждого «процессора» есть свой кэш, данные из кэша посылаются в общую память и агрегируются в конечный ответ. К тому же система из живых вычислителей имеет недостаток, который есть и в современных ЭВМ: если алгоритм требует много обменов данными, то работа сильно замедляется. Сейчас подобную распределённую систему с иерархией памяти можно встретить на любой командной олимпиаде или хакатоне, поскольку работа между участниками всегда распределена. Исторический контекст: До появления ЭВМ вычисления производились на бумаге. Что удивительно, они тоже были параллельными. Первые в мире известные распределенные вычисления произведены математиком 18-го века по имени Алекси Клод Клеро, который распределил вычисления между собой и двумя коллегами. Им удалось предсказать возвращения кометы Галлея в апреле 1759. Вплоть до середины 20-го века целые группы живых вычислителей (human computers) использовались для распределённых вычислений. Чаще всего это были женщины среднего класса с базовыми навыками в математике. Такие группы использовались в Первой и Второй мировых войнах, а также NASA. Они использовали бумагу, логарифмическую линейку, механические калькуляторы (арифмометры). С появлением первых компьютеров женщины нанимались для работы с перфокартами из-за нехватки мужчин, которые были на войне. К примеру, живые вычислители оставили след в истории метода сопряжённых градиентов: изначально он был забракован из-за большого числа пересылок между живыми процессорами, но впоследствии пережил второе рождение, когда ЭВМ научились быстро осуществлять обмен данными.
- Прокудин Дмитрий Сергеевич, группа 417. Как известно, перезарядка старинного мушкета представляет из себя достаточно сложный и долгий процесс и требует от стрелка хорошей координации. При этом во время перезарядки всё внимание стрелка занято оружием, а сам он остаётся беззащитным на длительное время. На данном изображении представлен пример интересной тактики французских солдат: процесс ведения огня и перезарядки разбивается на 4 параллельных этапа с использованием 4 мушкетов; один человек занят только своим этапом, после выполнения которого он передаёт свой мушкет на следующий этап и получает новый мушкет с предыдущего. Таким способом заметно повышается темп стрельбы (за то же время за вычетом времени обмена мушкетами обрабатывается 4 мушкета, вместо 1), каждый солдат занят только одним действием, а стрелок может оказывать постоянное прикрытие. Т.е. здесь солдаты реализуют параллельную обработку данных с передачей данных друг другу.
- Абрамов Валентин Андреевич, группа 417. Пример deadlock в классической литературе — Чичиков и Манилов «взаимно упрашивают друг друга пройти вперед».
- Макеев Сергей Михайлович, группа 417. Ситуация простоя GPU может возникнуть не только при работе в Google Colab, но и при параллельном использовании нескольких вычислительных устройств. Боттлнеком такого кластера может являться сервер, который агрегирует информацию с остальных серверов и после некоторой обработки возвращает ее обратно, остальные в это время простаивают в ожидании. Здесь такая ситуация сравнивается с широким шоссе в столице Мьянмы, Нейпьидо, у которого зачастую занята лишь одна полоса из двадцати.
- Кленин Максим Дмитриевич, группа 418. При передаче электричества через большие провода с высоким напряжением нередки случаи большой потери энергии. Чтобы избежать этого, на ЛЭП применяет расщепление фаз - использование нескольких провод меньшего размера, идущих параллельно, вместо одного большого.
- Боровко Никита Алексеевич, группа 416. Изображение иллюстрирует принцип работы компьютеров с общей памятью. Здесь мы видим группу работников, перед которыми располагается стеллаж с различными типами конфет, из которых они формируют упаковку, добавляя в нее по несколько объектов каждого типа. Таким образом, этот стеллаж представляет собой общую память, потому что каждому «компьютеру» необходимо несколько раз обратиться в разные его части за «данными» (конфетами).
Работы, победившие в 2022 году
I номинация.
- Воробьев Сергей Юрьевич, группа 417. На данном изображении показана фотография пункта оплаты трассы М11 (фото с иллюминатора самолета). Пункт оплаты в данном случае является своеобразным bottleneck-ом на трассе, так как автомобили должны существенно снизить скорость, чтобы произвести оплату. Чтобы не создавать пробки, пункты оплаты “распараллелены”. За счет этого средняя скорость прохождения данного участка остается высокой. Можно сказать, что каждый из процессов движения (один туда, другой обратно) разбивается внутри себя на большее количество нитей (потоков движения) перед узким местом, а после его прохождения возвращается в более выгодное с точки зрения ресурсов меньшее количество нитей, т.к. на дальнейшем участке дороги большое распараллеливание не принесет выигрыша в производительности из-за движения на пределе ограничения по скорости.
- Казаринов Андрей Вячеславович, группа 416. Модульное оригами - сборка фигурки из множества модулей - одинаковых частей, которые собираются по одной схеме из 1/16 листа бумаги А4. Фигурка состоит примерно из 500-1000 модулей. Данную сборку можно разбить на три параллельные операции (по человеку на операцию): 1) разрезание нужного числа листов А4 на 16 частей, 2) сборка модулей из 1/16 А4, 3) сборка фигурки из готовых модулей. Таким образом, реализуется конвейерный параллелизм.
- Дмитриева Татьяна Юрьевна, группа 417. На данной фотографии мы можем увидеть, что несколько сурикатов смотрят в одну сторону, а несколько в другую. Тем самым они разделяют между собой контроль над территорией, поделив ее на несколько подконтрольных частей. Если бы за наблюдением отвечал один сурикат, то выполнение контроля за территорией подразумевало бы постоянную смену позиции (что напоминает смену контекстов). Такое действие затрачивает много энергетических ресурсов. Тем временем если параллельное наблюдение осуществляют несколько сурикатов, которые не требуют между собой постоянной передачи информации (а только сигнал об опасности), качество работы увеличивается. Таким образом сурикаты реализуют параллельную обработку данных(об их окружении), разделяя между собой всю полученную информацию о местности.
- Солонина Елена Андреевна, группа 419/2. Попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) может привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются противоречивыми. При увеличении числа процессоров эффективность распараллеливания, как правило, уменьшается из-за роста накладных расходов. На картине это иллюстрируется в шуточной форме.
- Кузьминский Андрей Владиславович, группа 323. Набор нитей (студентов) пытаются занести свой ID (ФИО) в разделяемую память (в листочек с присутствующими) + демонстрация работы мьютексов.
II номинация.
- Пальтов Никита Сергеевич, группа 413. Иллюстрация ситуации дедлока в классическом произведении.
- Коротаев Никита Дмитриевич. Группа 419/1. Идея в том, что обручальное кольцо в наше время является индикатором, что девушка или мужчина уже женаты. А жена/муж почти всегда может быть только один. У классического мьютекса тоже есть два состояния, не заблокирован и заблокирован(когда доступ для других потоков блокируется).
- Солонина Елена Андреевна, группа 419/2. Параллелизм присутствует во многих сферах нашей жизни, однако не везде он уместен. При вождении, например, параллелизм даже опасен.
- Султонов Азамат, 403 группа. Deadlock.
- Кузнецова Мария Павловна, группа 411. Необычный храм, раньше здесь параллельно обрабатывались тысячи запросов к богу, а теперь здесь параллельно обрабатываются тысячи запросов к суперкомпьютеру.
- Пеструилова Анастасия Николаевна, группа 402. При работе множества сливов вода сбрасывается вниз быстрее и эффективнее, что демонстрирует многопоточный (также и в прямом смысле этого слова) параллелизм.
- Пеструилова Анастасия Николаевна, группа 402. Многопоточный чайник. Иногда приходится менять архитектуру программы для увеличения степени параллелизма (с обычным чайником такая параллельная работа невозможна).
Работы, победившие в 2021 году
I номинация.
-
Дединов Данзан Мингиянович, группа 406. Данное изображение демонстрирует концепцию mutex в реальной жизни. Ванная комната в общежитие представляет из себя некий общий ресурс, которым может завладеть лишь один студент блока.
II номинация
- Старикова Наталия Николаевна, группа 419/2. На изображении представлена статуя Гуаньинь, персонажа китайской мифологии. По легенде Гуаньинь поклялась не знать покоя, пока все живые существа не будут освобождены от сансары или перерождений. Несмотря на упорные усилия, она видела, что ещё очень многие несчастные существа не спасены. От стараний постичь нужды столь многих её голова раскололась на одиннадцать частей. Тогда Гуаньинь попыталась дотянуться до всех нуждающихся в помощи, но обнаружила, что её руки разрываются на части. И тогда Будда пришёл на помощь и дал ей тысячу рук. Эта история иллюстрирует горизонтальное масштабирование, производительность системы (Гуаньинь) увеличивается за счет добавления аппаратных средств (голов и рук).
-
Дербилов Александр Владимирович, группа 411. Галеры. Рабы демонстрируют слаженный параллелизм действий (хоть и не вполне добровольный) для движения судна, синхронность (и добровольность) действий регулируется надсмотрщиком.
-
Дербилов Александр Владимирович, группа 411. Люди демонстрируют конвейерный параллелизм при тушении пожара (зачерпывают воду – передают – заливают огонь).
-
Кузьмина Анастасия Андреевна, группа 402. Асинхронный параллелизм. Данный коллаж демонстрирует домашние дела, которые выполняются независимо и асинхронно по отношению друг к другу: человек запускает каждый из этих процессов (стиральная машина, мультиварка, робот-пылесос, чайник), не дожидаясь окончания предыдущего процесса.
-
Титова Любовь Дмитриевна, группа 413. Данная картинка иллюстрирует ситуацию дедлока при объяснении ситуации дедлока.
-
Долматов Александр Андреевич, группа 407. Изображение символизирует архитектуру MISD (по классификации Флинна). Воробьи прилетели в кормушку и едят хлеб (множество различных процессов обрабатывают один и тот же набор данных).
Работы, победившие в 2020 году
I номинация.
- На данном изображении мы видим как охотник осознает необходимость привлечь к решению поставленной задачи ресурсы в виде своих друзей-охотников из вне, так как добыча мамонта ему одному не под силу. Данное изображение иллюстрирует необходимость использования многопоточности при решении ресурсоемкой задачи.
- Масштабируемось вглубь и вширь на примере формы зачета
Систему зачета, при которой один преподаватель лично беседует с каждым студентом, «масштабируема вширь», так как можно увеличить количество преподавателей, принимающих зачет в форме личной беседы (то есть увеличить производительность системы (быстрее принять зачет) за счет добавления дополнительных программных или аппаратных средств), и «масштабируема вглубь», так как можно провести зачет в форме электронного тестирования (то есть заменить форму принятия зачета (платформу) на новую, обладающую большей производительностью). - Синхронный параллелизм. На фотографии изображена группа самолетов, выполняющая синхронный полет по пространственной траектории, заданной ведущим самолетом. Ведомые самолеты на основании команд ведущего, осуществляя параллельные вычисления траектории, выполняют синхронный, групповой полет.
- Изображение демонстрирует многопоточность - нагрев чайника происходит более эффективно за счет распределения потоков газа и нагревания поверхности в разных точках. Одиночную струю газа можно ассоциировать с однопоточной программой, в которой отсутствует сложность реализации алгоритма применимого для многопоточности - сетки распределения газа, накладных расходы на переключение потоков - потерь тепла уходящего в стороны. Но при этом очевидно что при данной архитектуре плиты нагрев происходит значительно быстрее как и при грамотно реализованной многопоточной программе.
- Изображение иллюстрирует смысл коммутаторов в MPI и то, каким образом процессы могут "общаться" между собой: с использованием общего коммутатора MPI_COMM_WORLD (беседа людей за одним столом) или посредством создания новых коммутаторов для обмена информацией внутри отдельных групп процессов (разговор людей за разными столами).
- "Две стратегии подготовки" демонстрирует два способа решения задачи – подготовки к контрольной/зачёту/экзамену. В первом случае студентка использует последовательную стратегию, решая задачи одну за другой: чтение учебника, обед, подготовка конспектов, практическое задание. Второй, более реалистичный случай – неразумное использование параллелизма из-за нехватки времени.
- На фото представлен старт соревнований, который схож с написанием программы с элементом распараллеливания. Изначально задается определенное количество нарезанной лыжни (количество нитей или потоков), по которым будут распределяться спортсмены (процессы).XXXXXx
II номинация
- Касатки демонстрируют совместную работу. они плывут параллельно друг другу, тем самым создавая волну, которая собьет тюленя со льдины.
- Изображение иллюстрирует поведение процессов в программах с разделяемыми ресурсами и локальными.
- Шурик и Лида демонстрируют чтение из общей памяти.
- Одна из практических проблем многопоточности - взаимная блокировка: каждый человек ожидает, когда пройдёт другой.
- Известная всем с детства басня Ивана Андреевича Крылова "Лебедь, рак и щука" демонстрирует неэффективный пример MISD классификации Флина. Здесь данные - повозка, а каждое животное имеет свою инструкцию как эту повозку везти.
- Иллюстрация векторных инструкций. На изображении рабочий за раз переносит большое количество мешков. Это олицетворяет способность процессора обработать за такт большое количество данных с помощью векторных команд.
- Трус, Балбес и Бывалый демонстрируют НЕэффективную совместную работу.
- Параллелизм на примере работы салонов красоты. Одна из самых популярных услуг — маникюр и педикюр в четыре руки, когда время посещения сокращается в два раза, а во время процедуры можно почитать или посмотреть что-то полезное.
- Когда имеется простаивающий процессор.
- В природе встречается поразительной синхронности параллелизм. Некоторые виды мелких рыб сбиваются в косяки, чтобы спастись от хищников. Они начинают синхронно плыть покругу, а когда хищник плывёт на них, расплываются в две стороны, чтобы переместиться за хищника. Плавая в плотном косяке, эти рыбки умудряются не сталкиваться друг с другом.
- Муравьи демонстрируют совместную работу для переноса веточки.
- Некоторое количество человек отправились в байдарочный поход. В день перехода им требуется доплыть от одной стоянки до другой. Все члены этой компании одновременно отплывают от берега и плывут параллельно, чтобы время, затраченное на переход всеми байдарками, примерно равнялось времени, за которое с этим справилась бы одна байдарка. Однако в данном плане есть узкое место, которое не получится распараллелить и оптимизировать: предположим, что туристы плывут по реке, и она достаточно широкая, чтобы все байдарки могли идти рядом друг с другом. Тем не менее, если на пути встретится порог, все байдарки должны будут проходить его по очереди, дабы избежать столкновений и прочих опасных ситуаций. То есть, пока одна байдарка проходит порог, другие стоят на месте и ждут (байдарка, еще не преодолевшая порог, ждёт своей очереди, а справившиеся с задачей участники команды дожидаются своих товарищей, чтобы убедиться, что никому не требуется помощь).
Работы, победившие в 2019 году
I номинация.
- Этот шуточный комикс с помощью довольно частой жизненной ситуации (хотя и утрированной) иллюстрирует тупиковую ситуацию (deadlock) при передаче сообщений в MPI вида Recv(1), Send(1) для процесса 0 и Resv(0), Send(0) для процесса 1. Оба процесса ждут получения сообщения от другого и блокируются в этом состоянии.
- Изображения символизируют классификацию Флинна по наличию параллелизма в потоках команд и данных. Музыкальный инструмент символизирует данные, а игра на нем - инструкцию. (SISD - исполнитель, играющий определенную мелодию на своем музыкальном инструменте. MISD - на одной и той же гитаре два исполнителя играют разные ноты и разные мелодии. SIMD - оркестр исполнителей, играют одно и то же, но на разных гитарах. MIMD - несколько исполнителей играют каждый свою отличающуюся партию на своем инструменте).
- Рассматривается гипотетический процесс массового производства глиняных игрушек (неавторских). Комикс нужно читать слева направо. В данной работе я хотела проиллюстрировать возможные источники параллелизма в алгоритме, а так же ‘узкое место’, которое нельзя оптимизировать средствами параллельной обработки.
II номинация
- Изображение иллюстрирует принцип распараллеливания задачи на примере поисковых миссий. Ежегодно тысячи людей пропадают без вести. При поиске потерявшихся в лесу зона практически необъятна и дорога каждая минута, поэтому все поисковые отряды действуют по принципу параллельного поиска для максимально эффективного использования сил. Поисковый отряд разбивается на небольшие группы по 2-3 человека, а зона поиска разбивается сеткой на равные квадраты, после чего поисковые группы прибывают на свой квадрат и начинают одновременно "прочёсывать". Таким образом покрывается максимальная зона за наименьшее время, и отряды не мешают друг другу и не ищут в одном месте дважды.
- Песики несут палочку. Палочку может нести и один, но помочь хотят все. В итоге эффективность процесса падает как в задаче про землекопов. Но песики все равно молодцы.
- При подготовке самолета к вылету задействовано много людей и техники. Одновременно идет посадка людей, загрузка багажа, заправка топлива, погрузка еды. Все это происходит одновременно, при этом вылет возможен только когда все процессы процессы будут завершены.
Работы, победившие в 2018 году
I номинация.
- Пример про рабочих, которые копают яму. Не всегда чем больше число процессоров, тем эффективней работа.
- Параллелизм окружает нас везде в обычной жизни - а иногда даже там, где его на самом деле нет. Идея комикса основана на шутке, возникшей в начале учебного семестра благодаря ошибке в расписании.
- Иллюстрация параллелизма. На левой фотографии представлено распараллеливание процесса "покупок". На правой иллюстрируется выполнение процесса при отсутствии параллелизма.
- Иллюстрация организации памяти. На левой фотографии представлена архитектура компьютера с общей памятью на примере одной упаковки с печеньем. На правой представлена архитектура компьютера с распределенной памятью, когда множество печенек у каждого своё.
II номинация
- Барьерная функция. Фотография иллюстрирует идею барьерной функции. Проводники, начиная с последнего вагона, выбрасывают желтый флаг. До тех пор, пока проводник первого вагона не выкинет желтый флаг, поезд не тронется.
- Конвейерность и параллелизм на примере строительства ГЗ Московского Университета. Корпуса строятся параллельно, при этом верхние этажи еще только в проекте, чуть ниже уже готов каркас, в самом низу ставят стекла и занимаются отделкой.
- Описание: модель single instruction multiple processors: командир полка 18 века отдаёт приказ открыть огонь. Из-за сильного разброса пуль для повышения вероятности поражения цели большое количество солдат стреляло одновременно, одиночные выстрелы были неэффективны, напротив одновременное поражение значительного количества солдат противника вводило оставшихся в ужас, и те отступали. Также ddos-атаки были бы неэффективны, если бы не происходили одновременно с большого количества серверов.
- Задача воспроизведения огромной анимации на трибуне стадиона распараллеливается на тысячу человек (процессов). Каждому из них необходимо в заданной последовательности поворачиваться нужной стороной, чтобы показать правильный цвет одежды. Синхронизация работы происходит при помощи звуковых сигналов. Всё работает без задержек, так как все процессы одинаково загружены и получают сигналы одновременно, а значит никого не приходится ждать. Проиллюстрирован синхронный параллелизм.
Работы, победившие в 2017 году
I номинация.
II номинация
Работы, победившие в 2016 году
I номинация.
- На картине изображены люди, подготавливающие данные, и стоящие в очереди в ожидании их загрузки. Бог мудрости Тот олицетворяет собой контролёра (ОС), позволяя параллельным процессам начать своё выполнение. Фараон (центральный узел) следит за распределением работы по рабочим-кластерам. Древнеегипетский стиль был выбран потому, что все с ним знакомы, а также он очень насыщен параллельными линиями и демонстрацией иерархичности.
- Не помню как называется такой транспорт - бар на колёсах. Предположим, где необходимая операция - передвинуться.
- Мечта любого студента — чтобы все предметы учились одновременно, и оставалось время на отдых. Но, к сожалению, не всё можно распараллелить!
II номинация
Работы, победившие в 2015 году
I номинация.
II номинация
Конкурс выступлений в формате "Научный стенд-ап".
Результаты конкурса "Научный стенд-ап" (фото1, фото2, фото3, фото4):
- 1 место - Ушаков Дмитрий Андреевич, группа 418
- 2 место - Турашев Артём Сергеевич, группа 419/2
- 3 место - Михалев Евгений Константинович, группа 418, Романюк Полина Дмитриевна, группа 419/1
- Все четыре участника получают зачёт по курсу.
Объявляется конкурс выступлений в формате "Научный стенд-ап" по материалам курса. Конкурс пройдёт на последней лекции курса. Каждый участник должен будет выступить в формате "Научный стенд-ап" продолжительностью до 10 минут. Выступление должно в яркой форме демонстрировать некоторые положения данного лекционного курса или своей научной работы в связке с некоторыми положениями данного курса. Зачёт по курсу получат те участники конкукрса, чьи выступления покажутся заслуживающими внимания лекторам (и, возможно, другим приглашённым членам жюри).
Желающие поучаствовать в конкурсе выступлений в формате "Научный стенд-ап" должны в срок до 21 ноября прислать примерные сценарии своих выступлений на адрес asa@parallel.ru. К конкурсу будет допущено до 6 выступающих, если желающих окажется больше, то будет проведён предварительный отбор на основе присланных сценариев.
Формат выступлений должен примерно соответствовать стилистиске подобного конкурса на канале "Культура".
Материалы к курсу:
- Презентация первой лекции.
- Презентация второй лекции.
- Презентация третьей лекции.
- Презентация четвёртой лекции.
- Презентация пятой лекции.
- Презентация шестой лекции.
- Презентация седьмой лекции.
- Презентация восьмой лекции.
- Презентация девятой лекции.
- Презентация десятой лекции.
- Презентация одиннадцатой лекции.
- Презентация двенадцатой лекции.
- Презентация тринадцатой лекции.