Эффективные параллельные алгоритмы: методика BSP

Общая информация
ЛекторА. В. Тискин
Семестросень 2012
Дата начала21.10.2012
Количество пар3
Язык курсарусский
Аннотация

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

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

Ваша оценка: Пусто Средняя: 3.4 (5 votes)
Share |