Distributed data-parallel execution engines for user-defined serial problems using branch-and-bound algorithm

1. A method for a distributed data-parallel execution (DDPE) system, the method comprising:

deriving a computational problem from a user-defined serial problem;

splitting the computational problem into a plurality of sub-problems using a branch-and-bound algorithm, wherein each sub-problem of the plurality of sub-problems maintains root-to-leaf information;

designating a synchronous stop time for a plurality of processors;

distributing the synchronous stop time and the plurality of sub-problems to the plurality of processors;

conducting a round of processing on the plurality of processors for the plurality of sub-problems by recursively using the branch-and-bound algorithm until the stop time and without inter-processor communications during the round;

receiving processing round state data from the plurality of processors indicating whether there are any open sub-problems remaining that require further processing, wherein the processing round state data comprises root-to-leaf information for each open sub-problem;

determining if further processing is required based on the processing round state data and:

if further processing is required, then until further processing is not required:

redesignating the synchronous stop time;

redistributing the synchronous stop time and any open sub-problems to at least one processor from among the plurality of processors; and

repeating the conducting, receiving, and determining; and

if further processing is not required, then terminating processing on the plurality of processors.

2. The method of claim 1 , wherein a number of sub-problems split from the computational problem is substantially larger than a number of processors in the plurality of processors.

3. The method of claim 1 :

wherein distributing further comprises evenly and randomly distributing the plurality of sub-problems to the plurality of processors; and

wherein redistributing further comprises evenly and randomly distributing the plurality of sub-problems to the plurality of processors.

4. The method of claim 3 , wherein for the redistributing, each processor from among the plurality of processors independently redistributes its open sub-problems evenly and randomly to the plurality of sub-processors.

5. The method of claim 1 :

wherein splitting further comprises calculating of a global state of processing the computational problem;

wherein distributing further comprises distributing the global state to the plurality of processors;

wherein the processing round state data further comprises, for each processor from among the plurality of processors, a local state;

wherein determining further comprises updating the global state based on the processing round state data; and

wherein redistributing further comprises redistributing the global state to the plurality of processors.

6. The method of claim 5 , wherein the plurality of processors utilize the global state to prune a subset of sub-problems from among the plurality of sub-problems during the round of processing while utilizing the branch-and-bound algorithm.

7. The method of claim 6 :

wherein each processor from among the plurality of processors calculates its local state;

wherein each processor from among the plurality of processors updates its local state upon receipt of the global state;

wherein each processor from among the plurality of processors updates its local state during utilization of the branch-and-bound algorithm; and

wherein the processing round state data comprises the local state received from each processor from among the plurality of processors.

8. The method of claim 5 , wherein for the determining and based on the branch-and-bound algorithm, further processing is required when the number of open sub-problems is greater than zero, and further processing is not required when the number of open sub-problems is equal to zero.

9. The method of claim 8 , further comprising determining a global stop condition where further processing is not required even if the number of open sub-problems is greater than zero.

10. The method of claim 1 , wherein the user-defined serial problem is expressed in SQL.

11. The method of claim 1 , wherein for the designating and recursively redesignating the synchronous stop time, providing a duration for each round of processing.

12. The method of claim 1 :

wherein distributing further comprises distributing root-to-leaf information for each sub-problem along with that particular sub-problem to a destination processor from among the plurality of processors.

13. The method of claim 12 , wherein redistributing further comprises redistributing root-to-leaf information for each open sub-problem along with that sub-problem to a destination processor from among the plurality of processors.

14. A system for distributed computation comprising:

a plurality of processors constituting a distributed data-parallel execution (DDPE) system; and

a first processor that:

derives a computational problem from a serial-processing problem;

splits the computational problem into a plurality of sub-problems using a branch-and-bound algorithm, wherein each sub-problem of the plurality of sub-problems maintains root-to-leaf information;

designates a synchronous stop time for the plurality of processors;

distributes the synchronous stop time and the plurality of sub-problems to the plurality of processors;

receives processing round state data from the plurality of processors indicating whether there are any open sub-problems remaining that require further processing, wherein the processing round state data comprises root-to-leaf information for each open sub-problem; and

determines if further processing is required based on the processing round state data and:

if further processing is required, then until further processing is not required:

redesignates the synchronous stop time;

distributes the synchronous stop time to the plurality of processors; and

repeats the receiving and determining elements herein; and

if further processing is not required, then distributes to the plurality of processors a terminate command and returns a result to the computational problem.

15. The system of claim 14 , wherein each processor from among the plurality of processors:

receives the synchronous stop time and at least one sub-problem from among the plurality of sub-problems;

processes recursively the at least one sub-problem using the branch-and-bound algorithm until the stop time without inter-processor communications;

sends processing round state data to the first processor; and

receives from the first processor either a terminate command or an update to the synchronous stop time, and:

if a terminate command is received, then terminates processing; and

if a synchronous stop time is received, then redistributes any open sub-problems to at least one other processor from among the plurality of processors.

16. The system of claim 15 , wherein the plurality of processors comprise at least two core processors constituting a single multicore processing unit, and wherein the plurality of processors comprise processors for at least two stand-alone computers.

17. The system of claim 14 , wherein the serial-processing problem is expressed in SQL.

18. A storage memory comprising computer readable instructions for a distributed data-parallel execution (DDPE) system, the computer readable instructions comprising instructions for:

distributing a synchronous stop time for a plurality of processors and a plurality of sub-problems of a computational problem to the plurality of processors, the computational problem having been automatically derived from a user-defined serial problem, wherein each sub-problem of the plurality of sub-problems maintains root-to-leaf information;

conducting a round of processing on the plurality of processors for the plurality of sub-problems by recursively using a branch-and-bound algorithm until the stop time;

receiving processing round state data from the plurality of processors indicating whether there are any open sub-problems remaining that require further processing, wherein the processing round state data comprises root-to-leaf information for each open sub-problem;

determining if further processing is required based on the processing round state data and:

if further processing is required, then until further processing is not required: redesignating the synchronous stop time;

redistributing the synchronous stop time and any open sub-problems to at least one processor from among the plurality of processors; and

repeating the conducting, receiving, and determining elements.

19. The storage memory of claim 18 , further comprising instructions for serializing data pertaining to the plurality of sub-problems.

20. The storage memory of claim 18 , further comprising instructions for synchronizing the synchronous stop time to each processor comprising the plurality of processors.