  In this paper, we study how the Pruned Landmark Labeling (PPL) algorithm can
be parallelized in a scalable fashion, producing the same results as the
sequential algorithm. More specifically, we parallelize using a Vertex-Centric
(VC) computational model on a modern SIMD powered multicore architecture. We
design a new VC-PLL algorithm that resolves the apparent mismatch between the
inherent sequential dependence of the PLL algorithm and the Vertex- Centric
(VC) computing model. Furthermore, we introduce a novel batch execution model
for VC computation and the BVC-PLL algorithm to reduce the computational
inefficiency in VC-PLL. Quite surprisingly, the theoretical analysis reveals
that under a reasonable assumption, BVC-PLL has lower computational and memory
access costs than PLL and indicates it may run faster than PLL as a sequential
algorithm. We also demonstrate how BVC-PLL algorithm can be extended to handle
directed graphs and weighted graphs and how it can utilize the hierarchical
parallelism on a modern parallel computing architecture. Extensive experiments
on real-world graphs not only show the sequential BVC-PLL can run more than two
times faster than the original PLL, but also demonstrates its parallel
efficiency and scalability.
