Patent ID: 6779183
Filing Date: 2004-08-17
Classification: G06F

Abstract:
A method of scheduling a plurality of multi-dimensional tasks on a plurality of processors for load sharing among said plurality of processors to within an error criteria, &egr;, in which each processor is represented by a multi-dimensional bin, comprising the steps of:a. guessing a value of optimal load among said plurality of processors; b. partitioning the plurality of multi-dimensional tasks into a set of large tasks and a set of small tasks; c. guessing an interaction of the set of large tasks and of the set of small tasks to determine a configuration of multi-dimensional bins; d. discretizing the set of large tasks into a set of discretized large tasks; e. packing the discretized set of large tasks in the guessed interaction; f. determining if the set of small tasks can be allocated into space of the multi-dimensional bins unallocated after step (e); and g. establishing if step (f) is valid, thereby determining a schedule of the multi-dimensional tasks from the bin configuration of the set of discretized tasks and the bin configuration of the set of small tasks which has a maximum load less than (1+&egr;) times the optimal load; otherwise h. iteratively repeating the steps (a)-(f) if step f is not valid until the step (f) is valid.