A new synchronization in parallel shortest paths analysis for massive road networks

To effectively solve the single-source shortest path (SSSP) problem for massive road networks in geographical information systems, a new synchronization method is proposed in the implementations of parallel SSSP algorithm. It applies spinlock by inline assembly language for the sake of small overheads of controlling the interaction of multiple threads. The performance of our method is compared with widely used Pthreads application programming interfaces and the powerful sequential solution given by DIMACS. The experimental platform is a shared address space workstation with two processors (i.e. eight cores) at a clock speed of 3 GHz. Problem instances for experiments contain a directed road networks of the USA with more than 23 million vertices and 57 million edges, and its 11 subnetworks of variant sizes. This method answers the SSSP of the USA road network in 1231 ms, while Pthreads costs 1808 ms and DIMACS sequential solution takes 4856 ms. It achieves a speedup of 3.95, which is 47% faster than Pthrea...