×

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
First Claim
Patent Images

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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×