Многопоточный распределенный поиск в ширину с упорядоченными коммуникациями

Описывается параллельная реализация алгоритма поиска в ширину на графе, разработанная в компании Т-Платформы. Ключевой особенностью является оптимизированное внутреннее представление графа, позволяющее упорядочить коммуникации между вычислительными процессами и разделить выполнение на потоки внутри каждого из процессов. Приводится описание оптимизации по направлению и ее многопоточной имплементации. Также приведены результаты исследования производительности разработанной реализации.