1. A program product including a non-transitory computer readable medium including programmed instructions, wherein the instructions, when executed by a computer, comprise instructions for causing the computer to perform:
inputting a sequential program to be converted that includes a loop, loop division information indicating that a process within the loop is to be divided into a first process and a second process, loop control information comprising termination control information and indicating that at least one of the first process and the second process includes a loop control statement of the loop, and change information indicating that at least one of the first process and the second process executes a change process that changes data to be referred to in a process subsequent to the loop; and
parallelizing, in which the loop is divided into the first process and the second process according to the loop division information and a parallelized program is created, which is to run on a computer including a plurality of cores or processors or on a plurality of computers, from the first process and the second process obtained by dividing the loop, wherein
the loop control information indicates that the first process includes the loop control statement, and the change information indicates that the second process includes the change process,
the parallelizing inserts a determination process into the first process, the determination process determining whether or not the second process is terminated at execution of an (n\u22121)th loop iteration (n is an integer of 2 or more) when the second process is subsequent to the first process in the program to be converted, or determining whether or not the second process is terminated at execution of an nth loop iteration when the second process precedes the first process in the program to be converted, and notifying the second process of a result of the determination, and
the parallelizing inserts a control process into the second process, the control process controlling execution of the second process based on the result of determination notified by the determination process.
2. A program parallelization device, comprising:
an input unit configured to input a sequential program to be converted that includes a loop, loop division information indicating that a process within the loop is to be divided into a first process and a second process, loop control information comprising termination control information and indicating that at least one of the first process and the second process includes a loop control statement of the loop, and change information indicating that at least one of the first process and the second process executes a change statement that changes data to be referred to in a process subsequent to the loop;
a loop parallelizing unit configured to divide the loop into the first process and the second process according to the loop division information and create a parallelized program, which is to run on a computer including a plurality of cores or processors or on a plurality of computers, from the first process and the second process obtained by dividing the loop; and
a processor for executing at least the loop parallelizing unit, wherein
the loop control information indicates that the first process includes the loop control statement, and the change information indicates that the second process includes the change statement,
the loop parallelizing unit inserts a determination process into the first process, the determination process determining whether or not the second process is terminated at execution of an (n\u22121)th loop iteration (n is an integer of 2 or more) when the second process is subsequent to the first process in the program to be converted, or determining whether or not the second process is terminated at execution of an nth loop iteration when the second process precedes the first process in the program to be converted, and notifying the second process of a result of the determination, and
the loop parallelizing unit inserts a control process into the second process, the control process controlling execution of the second process based on the result of determination notified by the determination process.
3. The device according to claim 2, wherein
the loop division information indicates that the loop is to be divided into the first process, the second process and a third process that handles only data referred to within the loop,
the loop parallelizing unit inserts a second determination process into the first process, the second determination process ensuring execution up to the (n\u22121)th iteration of the third process and determining whether or not to terminate a process of execution subsequent to the (n\u22121)th iteration when the third process is subsequent to the first process in the program to be converted, or ensuring execution at least up to the nth iteration of the third process and determining whether or not to terminate a process of execution subsequent to the nth iteration, and notifying the third process of a result of the determination of the second determination process, and
the loop parallelizing unit inserts a second control process, into the third process, the second control process controlling execution of the third process based on the result of determination notified by the second determination process.
4. The device according to claim 2, wherein
when a loop control statement of the loop is not executed within the loop,
the loop parallelizing unit converts the loop into a loop into which a conditional statement for executing a loop control statement of the loop is inserted and which exits when a condition according to the conditional statement is met.
5. The device according to claim 4, wherein
when the conditional statement of the loop includes the loop control statement of the loop,
the loop parallelizing unit converts the loop into a loop in which a conditional statement for executing the loop control statement of the loop is contained and the number of iterations is not defined.
6. The device according to claim 4, wherein
when an exception handling including the entire loop is set,
the loop parallelizing unit converts the loop into a loop in which a syntax for detecting an exception is set for a process within the loop where an exception may occur and which exits when an exception is detected by the syntax.
7. The device according to claim 2, wherein
the loop control information includes at least one of:
first loop control information indicating terminating a loop when a condition is met in the first process;
second loop control information indicating terminating a function including a loop when a condition is met in the first process;
third loop control information indicating resuming a process from a specified part outside of a loop when a condition is met in the first process; and
fourth loop control information indicating terminating a process at an m-th loop iteration (m is an integer of 1 or more) at which a condition is met in the first process and executing a process at an (m+1)th loop iteration.
8. The device according to claim 2, wherein
the loop parallelizing unit outputs a program having a data structure including first data indicating that a condition to execute the loop control statement is met in the first process and second data indicating the number of iterations of the first process including the loop control statement, and
the parallelized program created by the loop parallelizing unit notifies all threads of whether a loop is terminated and the number of iterations using the data structure.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method for improving positional accuracy of a receiver that receives satellite signals for navigation, the method comprising:
deriving an initial location from a navigation satellite system (NSS) data received at a GPS receiver, wherein the initial location is determined to be within an area of interest;
receiving selective cartography information from a location-aiding device coupled to the receiver, wherein the selective cartography information includes attributes of one or more geographic objects within the area of interest;
overlaying the initial location onto the selective cartography information;
deriving positional correction from the NSS data and the selective cartography information, wherein the deriving of the positional correction includes determining whether a radial positional correction, a perpendicular positional correction, or a combination thereof is applicable based on a proximity of the initial location with respect to the attributes of the one or more geographic objects;
applying the derived positional correction to the initial location to determine a corrected location of the receiver; and
outputting the corrected location of the receiver.
2. The method of claim 1, wherein the location-aiding device is one or more of a remote server, and, an on-board computer external to a navigation device containing the receiver but located within a moving object that includes the navigation device.
3. The method of claim 1, wherein the attributes of the one or more geographic objects comprises one or more attributes including: line segments along roads, intersection points where two roads cross each other; connection points where a multi-lane road meets with another single or multi-lane road; end points where a road or a lane terminates; width of roads; number of lanes on a road; designated traffic direction of a road; width of each lane on a road; radial dimension of a traffic circle with connection points where corresponding roads connect with the traffic circle; and center-to-peripheral or corner-to-corner distance of a polygonal traffic plaza with connection points where corresponding roads connect with the traffic plaza.
4. The method of claim 1, wherein the positional correction to be applied is based on one or more metrics including: the initial location; uncertainty in the initial location; perpendicular distance between the initial location and a selected line segment; radial distance between the initial location and a selected intersection point; radial distance between the initial location and a selected connection point; heading direction; uncertainty in heading direction; velocity; uncertainty in velocity; width of lanes; uncertainty in the width of lanes; width of roads; and uncertainty in the width of roads.
5. The method of claim 1, wherein width-indicator index depends on a number of lanes on a road.
6. The method of claim 1, wherein the area of interest includes geographic regions where acquiring NSS signal is difficult due to one or more obstructions in an environment surrounding the receiver.
7. The method of claim 1, wherein the method further comprises:
receiving navigation state information of the receiver; and
using the navigation state information in conjunction with the NSS data and the selective cartography information to derive the positional correction.
8. The method of claim 7, wherein the navigation state information comprises one or more parameters of the receiver including a position, a heading direction, a velocity, and an altitude.
9. The method of claim 1, wherein a width-indicator index is assigned to intersection points, connection points, or end points of two or more roads or lanes and is stored as an attribute of the corresponding intersection point, connection point, or end point.
10. The method of claim 9, wherein a variance associated with the positional correction to be applied to the initial location is based on the width-indicator index.
11. The method of claim 1, wherein a width-indicator index is assigned to line segments along different roads and lanes, and is stored as an attribute of the corresponding road or lane.
12. The method of claim 11, wherein a variance associated with the positional correction to be applied to the initial location is based on the width-indicator index.
13. The method of claim 1, wherein the method further comprises:
using a navigational routine to correlate selective cartography information with the initial location derived from the NSS data while deriving the positional correction.
14. The method of claim 13, wherein the navigational routine uses one or more following techniques: least-squares combiner, Kalman filter, maximum likelihood estimator, particle filter, neural networks, and Bayesian estimator.
15. The method of claim 1, wherein the step of receiving selective cartography information comprises:
pre-storing cartography information about one or more areas of interests in a database at the location-aiding device, wherein each said area of interest includes said one or more geographic objects;
assigning attributes to the one or more geographic objects within each said area of interest;
partitioning each said area of interest into units of cartography information including corresponding attributes of one or more of the geographic objects;
using a map-matching algorithm to associate one or more units of cartography information with the determined initial location;
retrieving the one or more associated units of cartography information from the location-aiding device; and
extracting selective cartography information from the associated units of cartography information.
16. The method of claim 15, wherein the map-matching algorithm uses predetermined thresholds, including one or more of a perpendicular distance threshold, and a road segment azimuth threshold to select the associated units of cartography information.
17. The method of claim 15, where the map-matching algorithm further uses navigation state information to select the associated units of cartography information.
18. The method of claim 17, wherein the navigation state information comprises one or more parameters of the receiver including a position, a heading direction, a velocity, and an altitude.
19. The method of claim 1, wherein the step of deriving the positional correction comprises:
determining whether the initial location is closest to an intersection point, a connection point, or an end point, or closest to a line segment along a road.
20. The method of claim 19, wherein if it is determined that the initial location is closest to the intersection point, the connection point, or the end point, the method further comprises:
applying a positional correction based on a radial distance of the initial location from the intersection point, the connection point, or the end point, and a variance assigned for the intersection point, connection point, or the end point.
21. The method of claim 19, wherein if it is determined that the initial location is closest to the line segment along the road, the method further comprises:
applying a positional correction based on a perpendicular distance of the initial location from the line segment, and a variance assigned for the line segment.
22. The method of claim 19, wherein if it is uncertain whether the initial location is closest to the intersection point, the connection point, or the end point, or, closest to the line segment along the road, the method further comprises:
calculating respective radial positional corrections based on corresponding radial distances of the initial location from one or more of the closest intersection points, connection points, and end points, and, respective variances assigned to the closest intersection points, the connection points, and the end points;
calculating respective perpendicular positional corrections based on corresponding perpendicular distances of the initial location from one or more of the closest line segments along roads, and respective variances assigned to the line segments; and
calculating a final positional correction combining the respective radial positional corrections and the respective perpendicular positional corrections.
23. A system for improving positional accuracy of a receiver that receives satellite signals for navigation, wherein the system comprises:
a navigation device containing the receiver; and
a location-aiding device for pre-storing units of cartography information associated with an area of interest, from which selective cartography information is extracted, wherein the location-aiding device comprises one or more of a remote server, and, an on-board computer external to the navigation device but located within a moving object that includes the navigation device,
wherein the navigation device determines whether a radial positional correction, a perpendicular positional correction, or a combination thereof is applicable to improve the positional accuracy of an initial location calculated from the received satellite signals, the determination being based on a proximity of the initial location with respect to attributes of one or more geographic objects included in the extracted selective cartography information.