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

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