Parallel dynamic programming through rank convergence
AssigneeMicrosoft Technology Licensing, LLC
InventorsTodd D. Mytkowicz, Madanlal Musuvathi, Saeed Maleki
Life of this patent
Estimating the term…
Abstract
The techniques and/or systems described herein implement parallel processing of a dynamic programming problem across stages and/or clusters by breaking dependencies between stages and/or clusters. For instance, the techniques and/or systems may identify dependencies between sub-problems of the dynamic programming problem and group the sub-problems into stages. The techniques and/or systems may also group the stages into clusters (e.g., at least two clusters to be parallel processed). Then, the techniques and/or systems generate one or more solutions to use instead of actual solutions so that the dynamic programming problem can be parallel processed across stages and/or clusters.
Claims20
A system comprising:
- one or more hardware processing units;
- memory storing instructions that, when executed by the one or more hardware processing units, cause the system to perform operations comprising:
- determining at least a first stage that includes one or more sub-problems of a dynamic programming problem;
- determining a second stage includes one or more sub-problems of the dynamic programming problem, wherein solutions to the one or more sub-problems in the second stage depend on at least one solution produced by at least one sub-problem of the one or more sub-problems included in the first stage;
- determining a first group of stages that includes the first stage;
- determining a second group of stages that includes the second stage;
- generating a solution to be used instead of the at least one solution on which the one or more sub-problems of the second stage depend;
- and
- processing the first group of stages and the second group of stages in parallel via a first hardware processing unit and a second hardware processing unit, respectively, wherein the processing of the second group of stages uses the generated solution to compute solutions to the one or more sub-problems in the second stage, one or more of the computed solutions being parallel to a true solution.
One or more computer-readable storage media comprising instructions that, when executed by one or more processors, configure a device to perform operations comprising:
- dividing a plurality of stages of a dynamic programming problem into at least a first group of stages and a second group of stages, each stage comprising one or more sub-problems individually configured to compute a solution independent of solutions computed by other sub-problems in a same stage;
- generating a solution to break a dependency between a last stage of the first group of stages and a first stage of the second group of stages;
- and
- processing the first group of stages and the second group of stages in parallel via at least a first processing unit and a second processing unit, respectively, wherein the second processing unit implements sequential processing of the stages in the second group of stages using the generated solution.
A method comprising:
- dividing sub-problems of a dynamic programming problem into multiple stages, wherein an individual stage of the multiple stages includes one or more sub-problems individually configured to compute a solution independent of solutions to other sub-problems of the one or more sub-problems in the individual stage;
- dividing the multiple stages into at least a first group and a second group separated by at least one dependent solution;
- generating one or more solutions;
- and
- processing the first group and the second group in parallel via a first hardware processing unit and a second hardware processing unit, respectively, wherein processing the second group includes computing one or more solutions using the one or more generated solutions instead of the at least one dependent solution.
Dependencies are inferred from the claim text.