초록 ▼

A parallel programming system implements dynamic load balancing to distribute processing workload to available processors in a parallel computer. A preprocessor in the system converts a nested parallel program into sequential code executable on processors of the parallel computer and calls to a mess

A parallel programming system implements dynamic load balancing to distribute processing workload to available processors in a parallel computer. A preprocessor in the system converts a nested parallel program into sequential code executable on processors of the parallel computer and calls to a message passing interface for inter-processor communication among the processors. When processing a nested parallel program, the preprocessor inserts a test function to evaluate the computational cost of a function call. At runtime, processors evaluate the test function to determine whether to ship a function call to another processor. This approach enables processors to offload function calls to other available processors in cases where it is more efficient to incur the cost of shipping the function call and receiving the results than it is to process the function call on the original processor.

대표청구항 ▼

[ I claim:] [1.]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,

[ I claim:] [1.]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; andwhen 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.