Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Эффективные параллельные алгоритмы: методика BSP
Санкт-Петербург / осень 2012, посмотреть все семестры

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

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

Дата и время Занятие Место Материалы
21 октября
11:15–12:50
Лекция, Лекция ПОМИ РАН видео
21 октября
13:00–14:35
Лекция, Лекция ПОМИ РАН видео
21 октября
15:35–17:10
Лекция, Лекция ПОМИ РАН видео