Proficient Cache-Supported Path Preparation on Roads

Abstract

Path planning problems greatly arise in many applications where the objective is to find the shortest path from a given source to destination. In this paper, we explore the comparison of programming languages in the context of parallel workload analysis. We characterize parallel versions of path planning algorithms, such as the Dijkstra’s Algorithm, across C/C++ and Python languages. Programming language comparisons are done to analyze fine grain scalability and efficiency using a single socket shared memory multicore processor. Architectural studies, such as understanding cache effects, are also undertaken to analyze bottlenecks for each parallelization strategy. Our results show that a right parallelization strategy for path planning yields scalability on a commercial multicore processor. However, several shortcomings exist in the parallel Python language that must be accounted for by HPC researchers.