City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Efficient parallel algorithms: BSP method
Saint Petersburg / autumn 2012, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Параллельные вычисления стремительно входят в мейнстрим современной computer science. Новый уровень сложности, привносимый параллелизмом в вычислительный процесс, создает потребность в его теоретическом осмыслении. Одна из самых интересных идей, выдвинутых в этой направлении - модель блочно-синхронного параллелизма (bulk-synchronous parallelism, BSP), предложенная Лесли Вэлиантом (Leslie Valiant) в 1990 г. Наряду с временем, затраченным на собственно вычисления, модель BSP рассматривает в качестве ограниченных ресурсов также межпроцессорную коммуникацию и синхронизацию. Вычислительный процесс BSP представляет из себя последовательность блоков асинхронных локальных вычислений, чередующихся с блоками коммуникации и барьерной синхронизации. Вэлиант доказал, что такой ограниченный класс параллельных вычислений может быть эффективно реализован при помощи чрезвычайно простого вероятностного алгоритма маршрутизации. При этом данный класс достаточно широк, чтобы служить основой для разработки эффективных параллельных алгоритмов. Мы изучим основные принципы разработки BSP алгоритмов на примере нескольких классических задач: сортировка, быстрое преобразование Фурье, ранжирование списка, вычисления на решетке, умножение матриц, решение системы линейных уравнений, поиск кратчайших путей в графе. Для большинства этих задач возможно наивное распараллеливание вычислений, однако оптимальные решения (с учетом времени на коммуникацию и синхронизацию) зачастую нетривиальны и поучительны.

Date and time Class|Name Venue|short Materials
21 October
11:15–12:50
Лекция, Lecture ПОМИ РАН video
21 October
13:00–14:35
Лекция, Lecture ПОМИ РАН video
21 October
15:35–17:10
Лекция, Lecture ПОМИ РАН video