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

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

---

Лекторы:

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

---

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

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

---

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

• Даты зачётов (экзаменов):
  • 27.12 все группы приходят к 10:00, ауд. П-6
• Порядок прихода групп на зачёт будет определён позже.
• В билете два вопроса. Список вопросов к зачёту (экзамену).
• На зачёте не разрешается пользоваться никакими материалами.
• Те группы, учебный план которых предусматривает экзамен по этому предмету, сдают его в те же сроки и по тем же билетам, но с проставлением оценки. За другие формы сдачи экзаменационная оценка не ставится, но может быть получен объявленный "бонус" (+1 балл).

---

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

• По результатам второго электронного тестирования зачёт (бонус на экзамене) получают:
• 323 группа:
  • Агаджанян Грант Минасович
  • Алексеев Никита Константинович
• 402 группа:
  • Сапрончев Андрей Михайлович
  • Шаргаровский Михаил Денисович       
• 403 группа:
  • Балашов Георгий Сергеевич
  • Бондаренко Анна Игоревна
  • Закс Роберт Тамазович
  • Папикян Тамара Вагеевна
  • Печеный Денис Васильевич
  • Подлесов Егор Анатольевич
  • Протопопов Михаил Андреевич
• 405 группа:
  • Дьяков Ярослав Андреевич
• 407 группа:
  • Ефремов Сергей Александрович
  • Родина Дарья Олеговна
  • Рыбинскова Юлия Олеговна
  • Селюцкая Лина Юрьевна
• 409 группа:
  • Романова Юлия Антоновна
  • Васильченко Дмитрий Дмитриевич
• 411 группа:
  • Титушин Александр Дмитриевич
  • Тишина Ульяна Кирилловна
• 412 группа:
  • Зайцева Ирина Владимировна
  • Москалев Артем Романович
• 414 группа:
  • Батушин Антон Александрович
• 415 группа:
  • Анашкина Анастасия Алексеевна
  • Гольдфайн Андрей Александрович
• 416 группа:
  • Анохин Владислав Андреевич
  • Евстигнеева Екатерина Сергеевна
  • Замятин Андрей Иванович
  • Зубков Даниил Константинович
  • Измайлов Александр Айратович
  • Исмаилов Элвин Велиевич
  • Котова Анна Игоревна
  • Куринов Юрий Наранович
  • Малахов Александр Андреевич
  • Островский Алексей Дмитриевич
  • Хайретинов Григорий Маратович
  • Шеряев Антон Владимирович
• 417 группа:
  • Аристархов Данила Дмитриевич
  • Брескану Никита
  • Елисова Анастасия Алексеевна
  • Зыков Валерий Павлович
  • Каратыщев Дмитрий Иванович
  • Карпинская Анна Викторовна
  • Лапиков Владислав Андреевич
  • Максимова Яна Дмитриевна
  • Федоров Артем Максимович
• 419/1 группа:
  • Диденко София Максимовна
  • Кирюткина Арина Владимировна
  • Лаврова Екатерина Игоревна
  • Левин Алексей Александрович
  • Хуанфу Линфэй
• 419/2 группа:
  • Альтерман Лев Михайлович 
• 441/2 группа:
  • Орлова Екатерина Михайловна
• Казахстанский филиал:
  • Баяков Тамерлан Маратулы
  • Жан-Юль-Ян Азель Максатовна
  • Исанбеков Дамир Александрович
  • Искакова Аружан Армановна
  • Ковшов Илья Владимирович
  • Мухамеджанова Томирис Ойратовна
  • Сембина Карина Ерлановна
  • Хангельдин Ансар Рахимович
  • Швец Игорь Станиславович

 

• По результатам первого электронного тестирования зачёт (бонус на экзамене) получают:
• 323 группа:
  • Акопян Микаэла Тиграновна
  • Горина Елизавета Сергеевна
  • Демина Мария Александровна
  • Майстренко Марат Алексеевич
  • Мальцев Егор Станиславович
  • Рудченко Арсений Олегович
• 401 группа:
  • Краснова Светлана Максимовна
  • Матвеева Софья Вячеславовна
  • Николаев Глеб Витальевич
• 402 группа:
  • Артемов Арсений Александрович       
• 403 группа:
  • Бурцев Леонид Андреевич
  • Таумурзаев Ахматали Канаматович
• 405 группа:
  • Радаева Карина Владиславовна
• 407 группа:
  • Кыштымова Анна Юрьевна
  • Пахнушев Андрей Вадимович
• 409 группа:
  • Огородников Даниил Михайлович
• 411 группа:
  • Володин Платон Олегович
• 412 группа:
  • Баймашева(Мокиевская) Лейсан Равилевна
  • Рождественский Артем Дмитриевич
  • Слович Марко Драгишевич
  • Цянь Люмуси
• 413 группа:
  • Хазиахметов Азат Айдарович
  • Шамина Арина Алексеевна
• 414 группа:
  • Берочкина Вероника Алексеевна
  • Дорохин Александр Владимирович
  • Кочура Тимофей Сергеевич
  • Цыбина Ольга Алексеевна
• 416 группа:
  • Гервиц Виктория Александровна
  • Гореленкова Анастасия Петровна
  • Гринченко Егор Дмитриевич
  • Гулевская Софья Олеговна
  • Задворный Даниэль Сергеевич
  • Манджиев Улан Викторович
  • Торбин Николай Викторович
  • Шахраманьян Михаил Андреевич
• 417 группа:
  • Богачев Владимир Александрович
  • Глазырина Светлана Евгеньевна
  • Иванов Егор Романович
  • Смирнова Виктория Станиславовна
  • Суржанский Александр Сергеевич
• 418 группа:
  • Голобоков Дмитрий Иванович
  • Гребенкин Сергей Дмитриевич
  • Золкина Екатерина Максимовна
  • Колесникова Наталия Сергеевна
  • Сергеев Максим Денисович
• 419/1 группа:
  • Аталаева Марьям Гитиномагомедовна
  • Мурадян Давид Каренович
• 419/2 группа:
  • Гмыриков Константин Константинович
  • Дыскина Мария Алексеевна
  • Ильина Дарья Дмитриевна
  • Камловская Надежда Олеговна
  • Медведев Георгий Михайлович
  • Минц Александр Артурович
  • Михеев Егор Михайлович
  • Прокопьев Андрей Александрович
  • Скиц Никита Александрович
  • Шереметьева Анастасия Александровна 
• 441/2 группа:
  • Панкина Алина Алексеевна
  • Плотников Алексей Сергеевич
• Казахстанский филиал:
  • Абдикашева Вилена Ринатовна
  • Алдабергенов Руслан Даниярович
  • Арзуманьян Андрей Эдуардович
  • Бежнар Артем Иванович
  • Воробьев Егор Александрович
  • Досай Даулетбек Олжасулы
  • Жуматай Арсен Мерейулы
  • Нукешова Индира Досжановна
  • Саликов Амир Жанатович
  • Шаку Жангирхан Жусипулы

 

• При выставлении зачётов автоматом за электронное тестирование учитывается также посещение лекций.
• Тестирование будет проводиться посредством системы http://sigma.parallel.ru
• Даты проведения электронного тестирования: 10 декабря 14:35 - 16:05, 17 декабря 14:35 - 16:05.
• На выполнение теста даётся 1 час.
• Пароли для тестирования будут высланы старостам групп.
• Инструкция по прохождению тестирования. Обратите внимание, что в конце проведения тестирования бывает рассинхзронизация времени, поэтому не откладывайте введение ответов на потом!
• Примеры вопросов для тестирования.
• Просьба старост групп присылать на адрес 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, Казахстанский филиал.

---

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

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

---

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

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

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

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

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

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

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

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

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

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

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

I номинация.

• Левыкин Александр Михайлович, группа 417

Картинки с коллажа были сгенерированы нейросетью Kandinsky 3.1. Пчелиный улей ярко демонстрирует многие идеи параллельных вычислений:

1. На 1-й картинке коллажа рядом с пчелиным ульем можно увидеть муравьев. Известно, что в природе муравьи могут как уничтожать ульи, так и жить в симбиозе, что демонстрирует идею Конкурентного и кооперативного планирования задач (Cooperative vs. Competitive Multitasking): когда муравьи и пчелы живут в симбиозе, они извлекают выгоду из общего пространства, не мешая друг другу. Это похоже на кооперативную многозадачность, когда процессы делят ресурсы без конфликтов: например, когда GPU и CPU работают в одной системе, дополняя друг друга. Если же муравьи начинают нападать на пчел, они становятся конкурентами за ресурсы, что приводит к разрушению всей системы (улья), что похоже на конкурентную многозадачность или конфликты за ресурсы. Это может привести к снижению производительности системы или даже к "взаимной блокировке" (deadlock).

2. Разделение задач (Task Parallelism):  На картинках 2, 3, 4 коллажа мы видим, что пчелы выполняют различные задачи — уход за личинками (картинка 2), полёты за нектаром (картинка 3), защита и укрепление улья (картинка 4), — так и в параллельных вычислениях разные потоки могут работать над различными частями одной большой задачи.

3. Коммуникация (Communication and Synchronization): Пчелы взаимодействуют через "танцы" и феромоны, что похоже на синхронизацию процессов в кластерах, где важна быстрая передача данных между вычислительными узлами.

4. Отказоустойчивость (Fault Tolerance): Если какая-то пчела погибает или выпадает из работы, другие продолжают выполнять её задачи, что напоминает механизмы дублирования и восстановления в вычислительных системах.

• Романенко Александр Евгеньевич, филиал МГУ в г.Саров, группа ВМ-124

Ситуация представляет собой самый доступный и безопасный способ прочувствовать deadlock на себе. Сначала ребята встают в круг друг за другом, а потом каждый садится на колени к сзади стоящему, получаем ситуацию deadlock. Теперь, чтобы Вам встать, нужно подождать пока встанет человек, сидящий у Вас на коленях, но так как все сидят на коленях друг у друга «по кругу» встать не может никто – остаётся только падать (я в серой куртке спереди).

• Морозов Иван Дмитриевич, группа 417

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

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

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

• Пименова Светлана Ильинична, филиал МГУ в г.Саров, группа СКТ-124

Многозадачность. Изображение человека, который пытается выполнять сразу несколько  дел — готовиться к экзамену, слушать музыку, работать за компьютером, заполнять ежедневник — приводит к тому, что ни одно дело не выполняется качественно. Это символизирует перегрузку задач и потерю эффективности.  

II номинация.

• Бородинов Владислав Михайлович, группа 402

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

• Сержантов Артемий Вячеславович, филиал МГУ в г.Саров, группа ВМ-124

Параллелизм встречается в очень многих сферах нашей жизни, но особенно часто в коллективной работе над одной огромной задачей. Именно здесь кроются действительно невероятные возможности применения параллелизма. На картинке изображено сооружение моста в Китае, в городе Пекине. Была задействована коллективная работа 116 экскаваторов. Мост был построен всего за каких-то 43 часа. Это кажется просто немыслимым! Ведь при стандартном выполнении такого проекта могут уйти целые годы. Данная картинка иллюстрирует параллелизм по данным (однотипная обработка большого объема данных, оптимальное распределение по процессам).

• Брылев Роман Дмитриевич, филиал МГУ в г.Саров, группа СКТ-124

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

• Буян Кирилл Игоревич, группа 403

На данной картинке изображена плесень Physarum polycephalum. Интересной особенностью данного организма является его способ поиска еды: поначалу он начинает разрастаться во все стороны, как бы параллельно рассматривая все возможные пути. Когда же один из путей приводит к еде, он сосредотачивается лишь на тех отростках, которые образуют кратчайший путь до питательных веществ. Таким образом, данный организм решает задачу поиска кратчайшего пути, используя синхронное распараллеливание.

• Солодухов Тимофей Олегович, группа 404

Демонстрация проблемы с критическим ресурсом при параллелизме.

 

Работы, победившие в 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 номинация.

• Никитченко Никита Николаевич, группа 416. В вычислительных системах значительное увеличение числа процессоров может привести к уменьшению итоговой производительности вследствие накладных расходов. Аналогии можно наблюдать и в природе. Каждый гусь, взмахивая своими крыльями, обеспечивает подъем для птицы, которая летит непосредственно за ним. И за счет построения стаи в клин гусь экономит до 25% энергии на перелёте, при этом скорость полета стаи увеличивается на 70%, по сравнению с отдельно летящей птицей. Однако значительное увеличение числа одновременно летящих птиц приводит к уменьшению скорости выполнения задачи перелета в теплые края. Стая на фото справа, слишком велика: птицы сталкиваются, мешают друг-другу, тем самым скорость их полета уменьшается, а накладные расходы растут.

• Дединов Данзан Мингиянович, группа 406. Данное изображение демонстрирует концепцию mutex в реальной жизни. Ванная комната в общежитие представляет из себя некий общий ресурс, которым может завладеть лишь один студент блока.

II номинация

• Старикова Наталия Николаевна, группа 419/2. На изображении представлена статуя Гуаньинь, персонажа китайской мифологии. По легенде Гуаньинь поклялась не знать покоя, пока все живые существа не будут освобождены от сансары или перерождений. Несмотря на упорные усилия, она видела, что ещё очень многие несчастные существа не спасены. От стараний постичь нужды столь многих её голова раскололась на одиннадцать частей. Тогда Гуаньинь попыталась дотянуться до всех нуждающихся в помощи, но обнаружила, что её руки разрываются на части. И тогда Будда пришёл на помощь и дал ей тысячу рук. Эта история иллюстрирует горизонтальное масштабирование, производительность системы (Гуаньинь) увеличивается за счет добавления аппаратных средств (голов и рук).

• Дербилов Александр Владимирович, группа 411. Галеры. Рабы демонстрируют слаженный параллелизм действий (хоть и не вполне добровольный) для движения судна, синхронность (и добровольность) действий регулируется надсмотрщиком.

• Дербилов Александр Владимирович, группа 411. Люди демонстрируют конвейерный параллелизм при тушении пожара (зачерпывают воду – передают – заливают огонь).

• Кройчук Павел, группа 418. В командной гребле очень важна синхронная работа. В идеальном исполнении командная байдарка обгонит одиночную байдарку (как обычно параллельные программы обгоняют линейные), но если гребцы будут мешать друг другу, цепляться веслами (лезть в чужую область памяти, дедлочить), то командная байдарка не сдвинется с места, может даже перевернуться, когда как одиночная уйдет спокойной дальше.

• Кузьмина Анастасия Андреевна, группа 402. Асинхронный параллелизм. Данный коллаж демонстрирует домашние дела, которые выполняются независимо и асинхронно по отношению друг к другу: человек запускает каждый из этих процессов (стиральная машина, мультиварка, робот-пылесос, чайник), не дожидаясь окончания предыдущего процесса.

• Будак Алексей Сергеевич, группа 414. Многопоточность и параллелизм. Можно сказать, что данный пример иллюстрирует параллелизм не столько "вокруг", сколько внутри нас. Для обмена веществ артерии разветвляются на множество капилляров, за счет чего увеличивается площадь сосудов. Это позволяет напрямую проводить обмен веществ с большим числом клеток, что повышает его эффективность.

• Титова Любовь Дмитриевна, группа 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 номинация

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

---

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

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

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

Формат выступлений должен примерно соответствовать стилистиске подобного конкурса на канале "Культура".

---

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

• Презентация первой лекции.
• Презентация второй лекции.
• Презентация третьей лекции.
• Презентация четвёртой лекции.
• Презентация пятой лекции.
• Презентация шестой лекции.
• Презентация седьмой лекции.
• Презентация восьмой лекции.
• Презентация девятой лекции.
• Презентация десятой лекции.
• Презентация одиннадцатой лекции.
• Презентация двенадцатой лекции.
• Презентация тринадцатой лекции.