Transportation network micro-simulation with pre-emptive decomposition

1. A parallel computing method performed by a parallel computing system comprising a plurality of central processing units (CPUs), the parallel computing method comprising:

executing a main process;

executing a task priority queue update process to maintain a task priority queue that ranks tasks for a current execution point whose results will be needed with non-zero probability by the main process wherein the task priority queue update process comprises:

identifying the tasks whose results will be needed with non-zero probability by the main process based on the current execution point in the main process,

for each identified task, assigning a probability that the task result will be needed by the main process based on the current execution point in the main process, a time limit for the task relative to the current execution point in the main process, and a score for the task that is computed based on the probability and time limit, and

ranking the identified tasks in the task priority queue in accordance with the assigned scores;

executing tasks in parallel with the executing of the main process on CPUs not used in executing the main process and with execution order of the tasks being in accordance with the task priority queue; and

storing, in a completed task results cache, results of tasks whose execution is completed on CPUs not used in executing the main process;

wherein the main process is configured to retrieve completed task results from the completed task results cache when needed by the main process.

2. The parallel computing method of claim 1 wherein the executing of tasks comprises:

(1) selecting the top-ranked task in the task priority queue that is suspended or not yet started; and

(2) executing the selected task on an idle CPU if an idle CPU is available.

3. The parallel computing method of claim 2 wherein the executing of tasks further comprises:

(3) if no idle CPU is available, and further conditional upon identifying a task that is of lower rank in the task priority queue than the selected task and that is currently executing on a working CPU, pre-empting execution of the identified task and executing the selected task on the working CPU.

4. The parallel computing method of claim 3 wherein the executing of tasks further comprises repeating the operations (1), (2), and (3) for each next-highest-ranked task in the task priority queue until a task is selected in operation (1) that is not executed in operation (2) and is not executed in operation (3).

5. The parallel computing method of claim 1 wherein the time limit for each task is quantified as one of:

(a) time when the result of the task will be used by the main process, and

(b) task execution start time in order for the result of the task to be available in the completed task results cache when the result of the task will be used by the main process,

and the time limit is measured in one of time units and instruction cycles.

6. The parallel computing method of claim 1 wherein, for at least one identified task, the probability that the task result will be needed by the main process is assigned further based on a parameter value of the executing main process.

7. The parallel computing method of claim 1 further comprising:

removing from the completed task results cache the result of any task for which the probability that the task result will be needed by the main process is zero.

8. The parallel computing method of claim 1 wherein the main process comprises a transportation network simulation process and the tasks include trip planning tasks for individual vehicles or travelers.

9. A non-transitory storage medium storing instructions executable by a parallel computing system comprising a plurality of central processing units (CPUs) to perform a parallel computing method comprising:

executing a main process;

while executing the main process, executing a task priority queue update process to maintain a task priority queue that, for a current execution point in the main process, ranks tasks whose results will be needed with non-zero probability by the main process at an execution point in the main process that is later than the current execution point; and

executing tasks in parallel with the executing of the main process on CPUs not used in executing the main process and with the executing of tasks being initiated in accordance with the task priority queue, the executing of tasks including storing results of completed tasks in a completed task results cache;

wherein the task priority queue update process includes:

from vantage point of the current execution point in the main process, identifying the tasks whose results will be needed with non-zero probability by the main process,

for each identified task, assigning a probability that the task result will be needed by the main process based on the current execution point in the main process, a time limit for the task relative to the current execution point in the main process, and a score for the task that is computed based on the probability and time limit, and

ranking the identified tasks in the task priority queue in accordance with the assigned scores; and

wherein the main process is configured to retrieve completed task results from the completed task results cache when needed by the main process.

10. The non-transitory storage medium of claim 9 wherein the executing of tasks comprises:

(1) selecting the top-ranked task in the task priority queue that is suspended or not yet started;

(2) executing the selected task on an idle CPU if an idle CPU is available;

(3) if no idle CPU is available, and if a task is identified that is of lower rank in the task priority queue than the selected task and that is currently executing on a working CPU, pre-empting execution of the identified task and executing the selected task on the working CPU; and

repeating the operations (1), (2), and (3) for each next-highest-ranked task in the task priority queue until a task is selected in operation (1) that is not executed in operation (2) and is not executed in operation (3).

11. The non-transitory storage medium of claim 9 wherein the parallel computing method further comprises:

removing from the completed task results cache the result of any task for which, from the vantage point of the current execution point in the main process, the probability that the task result will be needed by the main process is zero.

12. The non-transitory storage medium of claim 9 wherein the main process comprises a main simulation process and the tasks include micro-simulations whose results are used by the main simulation process.

13. The non-transitory storage medium of claim 12 wherein the main simulation process comprises a transportation network simulation process and the micro-simulations include trip simulations for individual vehicles or travelers.

14. An electronic data processing system comprising:

a non-transitory storage medium as set forth in claim 9 ; and

a parallel computing system comprising a plurality of central processing units (CPUs), the parallel computing system operatively connected with the non-transitory storage medium to read and execute the instructions stored on the non-transitory storage medium.

15. A parallel computing method performed by a parallel computing system comprising a plurality of central processing units (CPUs), the parallel computing method comprising:

executing a main process;

executing tasks in parallel with the main process on CPUs not used in executing the main process, and storing results of completed tasks in a completed task results cache from which the main process retrieves completed task results when needed by the main process;

in executing tasks, controlling the initiation of task execution in accord with a task priority queue that ranks tasks for a current execution point whose results will be needed with non-zero probability by the main process; and

updating the task priority queue with advancement of the current execution point as the main process executes wherein the updating includes:

identifying the tasks whose results will be needed with non-zero probability by the main process based on the current execution point in the main process,

for each identified task, assigning a probability that the task result will be needed by the main process based on the current execution point in the main process, a time limit for the task relative to the current execution point in the main process, and a score for the task that is computed based on the probability and time limit, and

ranking the identified tasks in the task priority queue in accordance with the assigned scores.

16. The parallel computing method of claim 15 wherein controlling the initiation of task execution includes:

pre-empting an executing task by a task having higher priority in the priority ranking of tasks if no idle CPU is available for initiation of execution of the task having higher priority in the priority ranking of tasks.

17. The parallel computing method of claim 15 further comprising:

removing the result of a completed task from the completed task results cache in response to the probability going to zero that the result of the completed task will be needed by the main process as the priority ranking is updated with advancement of the current execution point.

18. The parallel computing method of claim 15 wherein the main process comprises a main simulation process and the tasks include micro-simulations whose results are used by the main simulation process.