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

Задача о динамической связности является одной из фундаментальных задач в теории графов. Большое число задач в теоретической информатике, например, связанных с социальными сетями или с сетевыми соединениями, имеют графовые модели, для которых задача поддержания компонент связности при добавлениях и удалениях ребер возникает естественно. Эта задача хорошо изучена как с теоретической, так и с практической стороны для однопоточного случая. Однако, на момент написания диплома не найдено многопоточного и масштабируемого алгоритма, который решает задачу динамической связности. Данная работа заполняет этот пробел и предлагает многопоточное обобщение классического однопоточного алгоритма, сохраняющее при этом теоретическую эффективность. Основу масштабируемости многопоточной версии алгоритма составляют три оптимизации. Первая заключается в использовании тонкой блокировки для компонент связности, что позволяет естественным образом распараллелить работу над разными компонентами. Вторая делает операции проверки связности, которые превалируют в реальных сценариях использования, неблокирующими. Последняя оптимизация развивает идею неблокирующих операций, позволяя выполнять большинство модификаций (не меняющих внутреннее представление компонент связности) без захвата блокировок. Для подтверждения высокой производительности алгоритма конструируется серия многопоточных экспериментов на различных реалистичных и искусственных графах с различными профилями нагрузки. Полученные результаты показывают эффективность каждой из предложенных оптимизаций. В среднем предложенный многопоточный алгоритм позволяет получить выигрыш в 4-8 раз по сравнению с алгоритмом с грубой блокировкой при малом числе операций проверки связности, и до 40 раз при их доминировании. Ключевые слова: многопоточность, графовые алгоритмы, задача о динамической связности, масштабируемость, неблокирующие операции.