Лучше ли для каждого потока иметь собственную копию графа в параллельном алгоритме? ⇐ C++

[Anonymous]

Я пытаюсь реализовать параллельный алгоритм кратчайшего пути для всех пар, используя алгоритм Дейкстры. Цикл запускает алгоритм Дейкстры для каждой вершины графа. Этот цикл распараллеливается с помощью OpenMP #pragma omp Parallel for. В алгоритме Дейкстры нет распараллеливания для одной вершины. Граф хранится в виде списков смежности, реализованных как вектор смежные_вершины. График никогда не изменяется во время алгоритма, поэтому синхронизация кэша выполняться не должна. Что лучше: предоставить каждому потоку собственную копию графа или позволить каждому потоку использовать один общий граф?
P.S. Я не уверен, но я думаю, что если бы использовался один общий граф, промахов в кэше было бы меньше, потому что все потоки используют один диапазон адресов, и когда одному потоку нужна часть графа, она может быть уже загружена в кеш другим потоком ( по крайней мере, в L3, совместно используемом всеми ядрами).

Подробнее здесь: https://stackoverflow.com/questions/792 ... lel-algori