Title :
Customized architectures for faster route finding in GPS-based navigation systems
Author :
Loew, Jason ; Ponomarev, Dmitry ; Madden, Patrick H.
Author_Institution :
Binghamton Comput. Sci. Dept., SUNY, Binghamton, NY, USA
Abstract :
GPS based navigation systems became popular in dedicated handheld devices, and are now also found in modern cell phones, and other small personal devices. A key element of any navigation system is fast and effective route finding, and this depends heavily on Dijkstra´s shortest path algorithm. Dijkstra´s algorithm is serial in nature; prior efforts to accelerate it through parallel processing have had almost no success. In this paper, we present a practical approach to extract small-scale parallelism by shifting priority queue operations to a secondary tightly-coupled processor. We obtain a substantial speedup on real-world graphs (in particular, road maps), allowing the development of navigation systems that are more responsive, and also lower in total power consumption.
Keywords :
Global Positioning System; mobile handsets; parallel processing; queueing theory; GPS-based navigation systems; cell phones; customized architectures; dedicated handheld devices; parallel processing; priority queue operations; real-world graphs; route finding; shortest path algorithm; small-scale parallelism; tightly-coupled processor; Acceleration; Cellular phones; Computer architecture; Data structures; Global Positioning System; Hardware; Multicore processing; Navigation; Parallel processing; Roads;
Conference_Titel :
Application Specific Processors (SASP), 2010 IEEE 8th Symposium on
Conference_Location :
Anaheim, CA
Print_ISBN :
978-1-4244-7953-5
DOI :
10.1109/SASP.2010.5521148