PATH CALCULATION DEVICE, PATH CALCULATION METHOD AND PROGRAM

• US 20160253773A1
• Filed: 10/30/2014
• Published: 09/01/2016
• Est. Priority Date: 10/30/2013
• Status: Abandoned Application

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: SUZUKI, Jun, KAN, Masaki, HAYASHI, Yuki
• Application Number:
  US15/030,738
• Publication Number:
  US 20160253773A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

Provided is a path calculation device including a calculation unit for performing assigned processing in parallel using a plurality of threads, and a control unit for controlling the calculation unit. The control unit divides nodes that are included in a graph which is object of path calculation, into groups in accordance with distances from a start node. And The control unit causes the calculation unit to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively short and thereafter to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively long.

Claims

1. A path calculation device, comprising:

a calculation unit that is configured to perform assigned processing in parallel using a plurality of threads; and

a control unit that is configured to control the calculation unit,

wherein the control unit;

divides nodes that are included in a graph which is object of path calculation, into groups in accordance with distances from a start node; and

causes the calculation unit to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively short and thereafter to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively long.

2. The path calculation device according to claim 1, wherein

the control unit divides nodes included in the graph into different groups for each integer multiple of a predetermined parameter in accordance with distances from the start node.

3. The path calculation device according to claim 1, wherein

depending on whether or not the number of nodes, to which distances from the start node are to be updated among nodes included in the graph, is greater than or equal to a predetermined number, the control unit, causes the calculation unit either to generate threads that update distances from the start node to all nodes included in the graph, or to generate threads that update distances from the start node to nodes to which distances from the start node have a possibility of being updated.

4. The path calculation device according to claim 3, wherein

the control unit predicts the number of nodes to which distances from the start node are to be updated, on the basis of a processing time taken to perform the previous round of update processing.

5. The path calculation device according to claim 1, further comprising:

a plurality of the calculation unit,

wherein the control unit;

divides the graph into a plurality of regions by a number greater than the number of the plurality of the calculation unit;

allocates the plurality of regions to the plurality of the calculation unit at random; and

causes the plurality of the calculation unit to perform path calculations between nodes included in the region(s) allocated thereto and the start node.

6. The path calculation device according to claim 5, wherein

the control unit divides nodes included in each of the plurality of regions into groups in accordance with distances from the start node thereto, and causes the plurality of the calculation unit to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively short, and thereafter to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively long.

7. The path calculation device according to claim 6, wherein

the control unit divides nodes included in each of the plurality of regions into different groups for each integer multiple of a predetermined parameter in accordance with distances from the start node.

8. The path calculation device according to claim 5, wherein

the control unit causes the plurality of the calculation unit to exchange with each other pieces of information which indicates whether or not distances from the start node to nodes included in the region(s) allocated to the plurality of the calculation unit have been updated in the middle of path calculations.

9. A path calculation device, comprising:

a calculation unit that is configured to perform assigned processing in parallel using a plurality of threads; and

a control unit that is configured to control the calculation unit,

wherein depending on whether or not the number of nodes, to which distances from a start node are to be updated among nodes included in a graph which is object of path calculation, is greater than or equal to a predetermined number, the control unit causes the calculation unit either to generate threads that update distances from the start node to all nodes included in the graph, or to generate threads that update distances from the start node to nodes to which distances from the start node have a possibility of being updated.

10. The path calculation device according to claim 9, wherein

the control unit predicts the number of nodes to which distances from the start node are to be updated, on the basis of a processing time taken to perform a previous round of update processing.

11. A path calculation method comprising:

by a control means that is configured to control a calculation means that is configured to perform assigned processing in parallel using a plurality of threads, dividing nodes that are included in a graph which is object of path calculation into groups in accordance with distances from a start node; and

causing, by the control means, the calculation means to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively short and thereafter to perform path calculations between the start node and nodes belonging to a group of nodes to which distances from the start node are relatively long.