Customized architectures for faster route finding in GPS-based navigation systems

摘要: GPS based navigation systems became popular in dedicated handheld devices, and are now also found modern cell phones, other small personal devices. A key element of any system is fast effective route finding, this depends heavily on Dijkstra's shortest path algorithm. algorithm serial nature; prior efforts to accelerate it through parallel processing have had almost no success. In paper, we present a practical approach extract small-scale parallelism by shifting priority queue operations secondary tightly-coupled processor. We obtain substantial speedup real-world graphs (in particular, road maps), allowing the development that more responsive, lower total power consumption.