Алгоритм поиска параллельного соединения

Question

Мне нужно распараллелить алгоритм kruskal, в серийной версии использовался алгоритм поиска соединения для обнаружения цикла в неориентированном графе. Есть ли способ распараллеливать эту часть кода?

Answer 1

Ну, это может быть распараллелено до некоторой степени. Он выглядит следующим образом:

Первоначально все ребра сортируются в порядке возрастания. Существует main thread, который фактически сканирует каждое ребро с самого начала и решает, добавляет ли текущий край цикл. Наша главная цель в параллелизации алгоритма состоит в том, чтобы сделать эти проверки параллельными.

Здесь мы используем worker threads. Каждому потоку задано определенное количество ребер для проверки, где в каждом потоке проверяется, образуют ли его ребра цикл с текущим представлением после каждой итерации (итерация означает, что основной поток добавляет новый край). Поскольку основной поток продолжает добавлять ребра, некоторые потоки видят, что определенные ребра уже формируют цикл с текущим представлением.

Такие края обозначены как discarded. Когда основной поток достигает таких краев, он просто переходит к следующему, не делая никаких проверок на нем.

Таким образом, мы проверили эти проверки параллельно, что означает, что алгоритм работает быстро, повышая эффективность.

Фактически, существует nice paper, который использует ту же идею, что и описанную выше.

EDIT:

Если вы в значительной степени обеспокоены бегущего времени все более-алгоритма, вы можете даже использовать алгоритм параллельной сортировки сначала как @ jarod42 предложил.