Вычислительная модель BSP (bulk-synchronous parallelism), предложенная и
теоретически проанализированная Leslie Valiant, в последние годы стала
широко использоваться в разработке параллельного программного
обеспечения (MapReduce, Pregel, Spark). Простота и элегантность BSP
достигается тем, что параллельное вычисление рассматривается в первом
приближении как последовательное - а конкретнее, состоящее из
последовательности асинхронных супершагов (раундов). На первый взляд
неочевидно, что многие нетривиальные задачи могут быть решены эффективно
за количество супершагов, не зависящее от размера входных данных, а
зависящее только от количества процессоров p. В докладе будет дан
краткий обзор алгоритмических задач, для которых известны "почти
асинхронные" эффективные BSP-алгоритмы, то есть алгоритмы, вычисляющие
решение всего за S = O(log p) супершагов без потери эффективности от
распараллеливания. В частности, широко известны алгоритмы с S = O(1) для
быстрого преобразования Фурье, сортировки, вычисления двумерной и
трехмерной выпуклой оболочки. Относительно недавно автором были
предложены алгоритмы с S = O(log log p) для вычисления суффиксного
массива строки и для выборки порядковой статистики последовательности, а
также неожиданные алгоритмы с S = O(log p) для определения всех попарных
кратчайших расстояний в графе и для вычисления наибольшей общей
подпоследовательности пары строк. Будет приведена попытка вычленить
общие подходы к разработке таких "почти асинхронных" алгоритмов, хотя в
настоящий момент это по-прежнему скорее искусство, чем точная наука.

Доклад будет продолжением выступления докладчика на конференции по
машинному обучению и анализу алгоритмов 18 декабря 2017 г., однако все
необходимые определения будут даны заново и знакомство с предыдущим
выступлением не требуется.