Matrix-based dynamic programming

A computer program product for solving a dynamic programming problem, the computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising computer readable program code configured to:

• represent the dynamic programming problem as a matrix F of cells, each cell representing an intermediate score to be calculated, the matrix having a form:
• F(i,j)=G(F(i−1, j−1), F(i, j−1), F(i−1, j), c(i,j)),
• wherein i is a row index of the matrix F, wherein j is a column index of the matrix F, i and j respectively being larger than or equal to 0, wherein G is an optimization function and c is a cost function;
• provide a mapping, the mapping assigning cells of the matrix to elements of a result container data structure;
• provide the result container data structure for storing cells of the matrix F to elements of the result container data structure in accordance with the mapping;
• calculate intermediate scores of all cells F(i,j) of the matrix, whereby intermediate scores of some of the cells of the matrix are stored to a respectively assigned element of the result container data structure in accordance with the mapping;
• during the calculation of the intermediate scores, dynamically update the assignment of cells and elements in the mapping such that:
• that first ones of the cells of the matrix are assigned to elements of the result container data structure respectively not having stored any intermediate score or having stored an intermediate score of second ones of the cells of the matrix, the first cells being calculated at a later moment in time than the second cells;
• that any intermediate scores of the second cells being overwritten by the intermediate scores of the first cells will not be required as input by any other ones of the matrix cells not having been calculated yet;
• and
• wherein the number of elements of the data structure is smaller than the number of cells of the matrix;
• and
• assemble a final result of the dynamic programming problem from the intermediate scores stored in the result container data structure.

A computer system comprising:

• a processor;
• a global memory having stored therein a result container data structure and a mapping;
• computer-readable non-transitory storage medium comprising instructions, wherein the processor executing the instructions is adapted for solving a dynamic programming problem, the processor being adapted for:
• representing the dynamic programming problem as a matrix F of cells, each cell representing an intermediate score to be calculated, the matrix having a form:
• F(i,j)=G(F(i−1, j−1), F(i, j−1), F(i−1, j), c(i,j)),
• wherein i is a row index of the matrix F, wherein j is a column index of the matrix F, i and j respectively being larger than or equal to 0, wherein G is an optimization function and c is a cost function;
• providing a mapping, the mapping assigning cells of the matrix to elements of a result container data structure;
• providing the result container data structure for storing cells of the matrix F to elements of the result container data structure in accordance with the mapping;
• calculating intermediate scores of all cells F(i,j) of the matrix, whereby intermediate scores of some of the cells of the matrix are stored to a respectively assigned element of the result container data structure in accordance with the mapping;
• during the calculation of the intermediate scores, dynamically updating the assignment of cells and elements in the mapping such that:
• that first ones of the cells of the matrix are assigned to elements of the result container data structure respectively not having stored any intermediate score or having stored an intermediate score of second ones of the cells of the matrix, the first cells being calculated at a later moment in time than the second cells;
• that any intermediate scores of the second cells being overwritten by the intermediate scores of the first cells will not be required as input by any other ones of the matrix cells not having been calculated yet;
• and
• wherein the number of elements of the data structure is smaller than the number of cells of the matrix;
• and
• assembling a final result of the dynamic programming problem from the intermediate scores stored in the result container data structure.

A computer system comprising:

• a first processing unit;
• a plurality of second processing units, each of the second processing units having assigned a respective local memory;
• a global memory being accessible by any of second the processing units;
• wherein the first processing unit is adapted for solving a dynamic programming problem by:
• representing the dynamic programming problem as a matrix F of cells, each cell representing an intermediate score to be calculated, the matrix having the form:
• F(i,j)=G(F(i−1, j−1), F(i, j−1), F(i−1, j), c(i,j)),
• wherein i is a row index of the matrix F, wherein j is a column index of the matrix F, i and j respectively being equal than or larger than 0, wherein the row index is incremented from top to bottom of the matrix and wherein the column index is incremented from the left to the right side of the matrix, wherein G is an optimization function and wherein c is a cost function;
• specifying a constant S;
• dividing all cells of the matrix into a grid g(y, x) of non-overlapping, adjacent cell groups, wherein each cell group g(y,x) comprises a left upper starting cell F(i,j) and is specifiable by:
• selecting a cell F(i,j) of the matrix as the left upper starting cell of said cell group;
• selecting all cells of row i lying within the matrix and having a column index j within the range [j−a+0, j−a+1, . . . , j−a+(S−1)] to get S cells, wherein a=0;
• and
• repeating the selecting a cell F(i,j), wherein in each repeat the row index i is incremented by 1 and wherein a is incremented by 1, said repeat being executed until a is equal to S−1, thereby selecting S cells in each of S rows for said cell group altogether;
• wherein the left upper starting cell of at least one of the cell groups has row index i=0 and column index j=0, and wherein each of the matrix cells belongs to exactly one cell group of the grid of cell groups;
• and
• assigning each of the cell groups to one of the second processing units, wherein each of the second processing units is adapted for executing one of the cell groups concurrently, thereby filling each cell of said cell group with a calculated intermediate score, wherein the execution of the plurality of cell groups is coordinated in a way ensuring that the execution of any of the cell groups is started only in case an execution of an adjacent left cell group and an adjacent upper cell group is already finished or if said adjacent left cell group or adjacent upper cell group does not exist, and wherein the first processing unit is further adapted for:
• storing, based on calculation of a result of the execution of any of the cell groups, said result to a result container data structure, the result container data structure being stored in the global memory;
• and
• providing the results of each of the cell groups for assembling a final result of the dynamic programming problem.

A computer-implemented method for solving a dynamic programming problem, the method comprising:

• representing the dynamic programming problem as a matrix F of cells, each cell representing an intermediate score to be calculated, the matrix having the form:
• F(i,j)=G(F(i−1, j−1), F(i, j−1), F(i−1, j), c(i,j)),
• wherein i is a row index of the matrix F, wherein j is a column index of the matrix F, i and j respectively being larger than or equal to 0, wherein the row index is incremented from top to bottom of the matrix and wherein the column index is incremented from the left to the right side of the matrix, wherein G is an optimization function and wherein c is a cost function;
• specifying a constant S;
• dividing all cells of the matrix into a grid g(y, x) of non-overlapping, adjacent cell groups, wherein each cell group g(y,x) comprises a left upper starting cell F(i,j) and is specified by:
• selecting a cell F(i,j)of the matrix as the left upper starting cell of said cell group;
• selecting all cells of row i lying within the matrix and having a column index j within the range [j−a+0, j−a+1, . . . , j−a+(S−1)] to get S cells, wherein a=0;
• and
• repeating the selecting a cell F(i,j), wherein in each repeat the row index i is incremented by 1 and wherein a is incremented by 1, said repeat being executed until a is equal to S−1, thereby selecting S cells in each of S rows for said cell group altogether;
• wherein the left upper starting cell of at least one of the cell groups has row index i=0 and column index j=0, and wherein each of the matrix cells belongs to exactly one cell group of the grid of cell groups;
• assigning each of the cell groups to one of a plurality of processing units;
• executing, by each of the processing units, one of the cell groups concurrently, thereby filling each cell of said cell group with a calculated intermediate score, wherein the execution of the plurality of cell groups is coordinated in a way ensuring that the execution of any of the cell groups is started only in case an execution of an adjacent left cell group and an adjacent upper cell group is already finished or if said adjacent left cell group or adjacent upper cell group does not exist;
• based on calculating a result of the execution of any of the cell groups, storing said result to a result container data structure, the result container data structure being stored in a global memory, the global memory being accessible by any one of the processing units;
• and
• providing the results of each of the cell groups for assembling a final result of the dynamic programming problem.