文章基本信息

标题：A new synchronization in parallel shortest paths analysis for massive road networks
本地全文：下载
作者：Yuefeng HUANG ; Ershun ZHONG
期刊名称：Geo-spatial Information Science
印刷版ISSN：1009-5020
电子版ISSN：1993-5153
出版年度：2012
卷号：15
期号：1
页码：43-49
DOI：10.1080/10095020.2012.708157
出版社：Taylor and Francis Ltd
摘要：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 Pthreads with the speedup of 2.69. When the size of instance is larger, our method achieves a better performance.
关键词：parallel shortest path; Pthreads; multiple threads; synchronization