ИСТИНА

We present a practical multicore solution for the classical problem of the Shortest Path Tree (SPT) search. Most of the practical graphs are relatively small and a commodity hardware can be used though a synchronization overhead is relatively huge. Computing SPT for the large graphs is slow though the multicore synchronization overhead diminishes. We propose an enhancement of the classical Bellman-Ford-Moore algorithm with aligned in memory bit arrays for the next updating vertices in order to reduce the number of cache misses. We considered IPRAN, Fat Tree, and random networks with 2000 to 500000 nodes. For our optimized parallel Bellman-Ford-Moore implementation we obtained the performance improvement $\sim 4 - 9$ times relative to the standard implementation of Dijkstra's algorithm (e.g. in Boost Graph Library). Performance improvement $>10$ times was also obtained for large, more than 50000 nodes, random graphs.