Customizable route planning using graphics processing unit

1. A method for determining a shortest path between an origin location and a destination location, comprising:

preprocessing, at a central processing unit (CPU) of a computing device, a graph comprising a plurality of vertices and a plurality of edges to generate preprocessed data comprising a partitioned graph, wherein each edge of the plurality of edges comprises a plurality of properties, and wherein each property of the plurality of properties has a cost;

performing, at a graphics processing unit (GPU) of the computing device, metric customization using the partitioned graph to generate metric customization data for augmenting the partitioned graph with metrics encoding a cost of traversing one or more edges of the partitioned graph, wherein performing metric customization comprises:

copying a plurality of costs of a plurality of mapping arcs to an array;

determining a plurality of costs of a plurality of arcs of the graph from the array;

performing a search phase using the plurality of arcs and the determined plurality of costs of the plurality of arcs; and

computing the metric customization data comprising a plurality of costs of shortcuts using results of the search phase; and

computing, at the CPU, a shortest path between the origin location and the destination location using the preprocessed data and the metric customization data, wherein the method further comprises:

the CPU sending metric information to the GPU for use by the GPU during the metric customization; and

the CPU copying metric customization data from the GPU to memory of the CPU.

2. The method of claim 1 , wherein the preprocessing is metric-independent.

3. The method of claim 1 , further comprising:

receiving a query at the computing device, the query comprising the origin location and the destination location.

4. The method of claim 1 , wherein the array is a shortcut array, and wherein the plurality of arcs are inner arcs and init arcs.

5. The method of claim 1 , wherein for determining the plurality of costs of the plurality of arcs a single kernel is created with one thread for each arc.

6. The method of claim 1 , wherein performing metric customization comprises search-based metric customization using the GPU.

7. The method of claim 1 , wherein performing metric customization comprises contraction-based metric customization using the GPU.

8. The method of claim 1 , wherein performing metric customization comprises using microinstructions with the GPU.

9. The method of claim 8 , wherein using microinstructions with the GPU comprises storing a microinstruction array in a global memory and storing a memory array in a shared memory.

10. The method of claim 1 , wherein the graph represents a network of nodes.

11. The method of claim 1 , wherein the graph represents a road map.

12. A method of determining a shortest path between two locations, comprising:

obtaining in a computing device, a graph comprising a plurality of vertices and edges, wherein each edge of the plurality of edges comprises a plurality of properties, and wherein each property of the plurality of properties has a cost;

executing a preprocessing stage in a central processing unit (CPU) of the computing device, the preprocessing stage comprising generating preprocessed data comprising a partitioned graph;

executing a metric customization stage, in a graphics processing unit (GPU) of the computing device, to generate metric customization data for augmenting the partitioned graph with metrics encoding a cost of traversing one or more edges of the partitioned graph, wherein executing the metric customization stage comprises:

copying a plurality of costs of a plurality of mapping arcs to an array;

determining a plurality of costs of a plurality of arcs of the graph from the array;

performing a search phase using the plurality of arcs and the determined plurality of costs of the plurality of arcs; and

computing the metric customization data comprising a plurality of costs of shortcuts using results of the search phase;

computing, at the CPU, a point-to-point shortest path using the preprocessed data and the metric customization data without re-executing the preprocessing stage; and

outputting the point-to-point shortest path, by the computing device, wherein the method further comprises:

the CPU sending metric information to the GPU for use by the GPU during the metric customization; and

the CPU copying the metric customization data from the GPU to memory of the CPU.

13. The method of claim 12 , wherein executing the metric customization stage further comprises contraction-based metric customization using the GPU.

14. A system for determining a shortest path between two locations, comprising:

a central processing unit (CPU), of a computing device, that executes a preprocessing stage to generate preprocessed data comprising a partitioned graph comprising a plurality of vertices and edges, wherein each edge of the plurality of edges comprises a plurality of properties, and wherein each property of the plurality of properties has a cost; and

a graphics processing unit (GPU), of the computing device, that performs search-based metric customization using the partitioned graph to generate metric customization data for augmenting the partitioned graph with metrics encoding a cost of traversing one or more edges of the partitioned graph,

wherein the CPU is configured to:

compute the shortest path between the two locations using the preprocessed data and the metric customization data; and

output the shortest path, and

wherein the CPU sends the metric information to the GPU for use by the GPU during the metric customization, and the CPU copies metric customization data from the GPU to memory of the CPU, and wherein the GPU performing search-based metric customization comprises the GPU configured to:

copy a plurality of costs of a plurality of mapping arcs to an array;

determine a plurality of costs of a plurality of arcs of the graph from the array;

perform a search phase using the plurality of arcs and the determined plurality of costs; and

compute the metric customization data comprising a plurality of costs of shortcuts using results of the search phase.

15. The system of claim 14 , wherein the CPU is configured to set up data structures on the GPU during the preprocessing stage, for use by the GPU during the metric customization.