×

Dynamic load balancing among processors in a parallel computer

  • US 6,292,822 B1
  • Filed: 06/30/1998
  • Issued: 09/18/2001
  • Est. Priority Date: 05/13/1998
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for dynamically balancing a processing workload among parallel processors operating on a program, where the program comprises recursive function calls capable of being executed in parallel, the method comprising:

  • compiling both parallel and serial versions of the program, the parallel version being capable of executing in a data-parallel fashion on every processor in a team of processors and the serial version being capable of executing on a single processor;

    inserting a test function in a serial version of the program;

    upon recursive function calls of the program, subdividing each team of processors into smaller teams, with one team per recursive function call;

    when the subdividing step results in a team having only one processor, calling the serial version of the code from the parallel version of the code executing on that processor;

    executing the test function on a first processor to determine whether computational cost of a recursive function call to be executed on the first processor exceeds a threshold; and

    when the computational cost exceeds a threshold, shipping a function call to an idle processor, executing the function call on the idle processor and returning results of the function call to the first processor.

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