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

• US 9,170,846 B2
• Filed: 03/29/2011
• Issued: 10/27/2015
• Est. Priority Date: 03/29/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Delling, Daniel, Budiu, Mihai, Werneck, Renato F.
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): GHAFFARI, ABU Z
• Application Number:
  US13/074,006
• Publication Number:
  US 20120254597A1
• Time in Patent Office: 1,673 Days
• Field of Search: 718/104, 712/233, 712/E09.045
• US Class Current: 1/1
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks

Abstract

A distributed data-parallel execution (DDPE) system splits a computational problem into a plurality of sub-problems using a branch-and-bound algorithm, designates a synchronous stop time for a “plurality of processors” (for example, a cluster) for each round of execution, processes the search tree by recursively using a branch-and-bound algorithm in multiple rounds (without inter-processor communications), determines if further processing is required based on the processing round state data, and terminates processing on the processors when processing is completed.

Claims

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.