# US 2012/0254597 A1 · Branch-and-bound on distributed data-parallel execution engines

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254597 A1
- Document ID: US20120254597A1
- Status: Published application
- Kind: A1
- Application number: 13/074,006
- Filed: 2011-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-29
- Assignees: Microsoft Corporation
- Inventors: Daniel Delling; Mihai Budiu; Renato F. Werneck
- Web page: https://patentgrep.com/patent/US20120254597A1

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- 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)}
- G06F 2209/5017: Task decomposition
- H04L 67/1001: for accessing one among a plurality of replicated servers
- H04L 67/1031: Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests
- H04L 67/104: Peer-to-peer [P2P] networks
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 1

A method for a distributed data-parallel execution (DDPE) system, the method comprising:
splitting a computational problem into a plurality of sub-problems using a branch-and-bound algorithm;
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 a branch-and-bound algorithm until the stop time and without inter-processor communications;
receiving processing round state data from the plurality of processors;
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 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 1)

The method of claim 1:
wherein splitting further comprises the calculating of a global state;
wherein distributing further comprises distributing the global state to the plurality of processors;
wherein 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 a global state to the plurality of processors.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 6)

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 processing round state data comprises the local state received from each processor from among the plurality of processors.

### Claim 8 (depends on 5)

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.

### Claim 9 (depends on 8)

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

### Claim 10 (depends on 1)

The method of claim 1, wherein the computational problem comprises a parallel processing optimization problem that was derived from a user-defined serial problem.

### Claim 11 (depends on 1)

The method of claim 1, wherein the synchronous stop time is designated and recursively redesignated to provide a substantially long duration for each round of processing.

### Claim 12 (depends on 1)

The method of claim 1:
wherein root-to-leaf information is maintained for each sub-problem;
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; and
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.

### Claim 13 (depends on 12)

The method of claim 12, wherein processing round state data comprises root-to-leaf information for each open sub-problem in the plurality of processors.

### Claim 14

A system for distributed computation comprising:
a plurality of processors constituting a distributed data-parallel execution (DDPE) system; and
a first processor that:
receives a computational problem;
splits the computational problem into a plurality of sub-problems using a branch-and-bound algorithm;
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; 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 receive and determines 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 14)

The system of claim 14, further comprising an application program interface for receiving a serial-processing problem and transforming it into a parallel-processing problem.

### Claim 18

A computer-readable medium 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;
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;
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 any open sub-problems to at least one processor from among the plurality of processors; and
repeating the conducting, receiving, and determining elements.

### Claim 19 (depends on 18)

The computer-readable medium of claim 18, further comprising instructions for serializing data pertaining to the plurality of sub-problems.

### Claim 20 (depends on 18)

The computer-readable medium of claim 18, further comprising instructions for synchronizing the synchronous stop time to each processor comprising the plurality of processors.
