초록 ▼

In accordance with the principles of the invention, a method and system of multiprocessor scheduling for load sharing among multiple multiprocessors to within any given error criteria, ε>0, is disclosed. The method comprises guessing a value for an optimal load on the processors, partitio

In accordance with the principles of the invention, a method and system of multiprocessor scheduling for load sharing among multiple multiprocessors to within any given error criteria, ε>0, is disclosed. The method comprises guessing a value for an optimal load on the processors, partitioning a plurality of multi-dimensional tasks into a set of large tasks and a set of small tasks, guessing the invention of the set of small tasks and among the set of larger tasks processors which are represented as multi-dimensional bins, packing a discretized the set of large tasks, in the guessed invention space of the multi-dimensional bins determining if the small tasks can be allocated into unallocated space of the multi-dimensional bins after packing of the discretized large tasks, and iteratively repeating the guessing steps until all the tasks can be allocated within the gussed load. The method establishes a schedule of the multi-dimensional tasks which provides a maximum load among the multi-processors which is less than (1+ε) times the optimal load.

대표청구항 ▼

1. 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, ε, in which each processor is represented by a multi-dimensional bin, comprising the steps of:a. guessing a value of op

1. 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, ε, 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); andg. 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+ε) times the optimal load; otherwiseh. iteratively repeating the steps (a)-(f) if step f is not valid until the step (f) is valid. 2. The method of claim 1 wherein if the step (h) is executed further comprising the step of:increasing the guessed value of optimal load by a factor of(1+ε)for each iteration of the steps (a)-(f). 3. The method of claim 1 wherein the step (b) of partitioning includes the steps of:determining if a largest dimension is smaller than the error criteria per number of dimensions represented by δ; and determining a set of large vectors if the error criteria per number of dimensions, δ, is smaller than said largest coordinate; otherwisedetermining a set of small vectors if the error criteria per number of dimensions, δ, is greater than or equal to said largest coordinate. 4. The method of claim 1 wherein the plurality of multi-dimensional tasks is represented by a d-dimensional vector, p j , and an error criteria per number of dimensions is represented by δ, wherein the step (f) of determining includes the steps of:i. defining an integer program to actually pack the d-dimensional vectors representing the small tasks in the space of the plurality of multi-dimensional bins unallocated after step (e);j. solving the integer program by linear relaxation with a vertex solution to determine from the vertex solution d-dimensional vectors representing the small tasks which can be allocated integrally to one of the plurality of multi-dimensional bins and ddimensional vectors representing the small tasks which can be allocated fractionally; andk. if step (j) is valid, packing the d-dimensional vectors representing the small tasks determined to be allocated fractionally in a round robin greedy fashion to one of the plurality of multi-dimensional bins; orl. if step (j) is not valid reporting failure. 5. The method of claim 3 wherein the step (d) of discretizing includes the steps of:rounding dimensions of the set of large vectors which are smaller than δ 2 to zero for determining a smallest non zero coordinate from the set of large vectors;partitioning the set of large vectors into geometrically increasing intervals; androunding up non zero coordinates of each large vector in the set of large vectors up to the right end part of one the intervals of which the coordinate falls to form the discretized large tasks. 6. The method of claim 5 wherein the intervals are determined as log 1+ε 1/δ 2 intervals from δ 2 to 1. 7. The method of claim 6, wherein the step (e) of packing includes the steps of:defining a number of the large vectors to fit in each of the plurality of multidimensional bins;defining a number of types of the large vectors;assigning a capacity configuration for each of the plurality of multi-dimensional bins from the space of the plurality of mu lti-dimensional bins unallocated in step (c); anddetermining a plurality of subsets of the large vectors to fit in the assigned capacity configuration for each of the plurality of multi-dimensional bins by dynamic programming. 8. The method of claim 7 wherein the number of discretized large vectors to fit in any of said plurality of multi-dimensional bins is represented by: 2 /εwherein d is the number of dimensions. 9. The method of claim 8 wherein the number of types of the large vectors is represented by: 1+ε 1/δ 2 ) d . 10. A system for scheduling a plurality of multi-dimensional tasks on a plurality of processors to provide a maximum load among the processors within an error criteria, ε, comprising:the plurality of processors;a process scheduler;memory for storing a schedule of the plurality of multi-dimensional tasks for said process scheduler;said process scheduler adapted to establish a schedule of said multi-dimensional tasks, said process scheduler comprising:means for representing the processors as m multi-dimensional bins;first guessing means for guessing a value of an optimal load among the plurality of processors;partitioning means for partitioning the plurality of multi-dimensional tasks into a set of large tasks and a set of small tasks;second guessing means for guessing an interaction of the set of large tasks and the set of small tasks;discretizing means for discretizing said set of large tasks into a set of discretized large tasks;packing means for packing the discretized set of large tasks in the guessed interaction;determining means for determining if the set of small tasks can be allocated into space of the plurality of multi-dimensional bins unallocated by the packing means,wherein said guessing means, said partitioning means, said second guessing means, said discretizing means, said packing means and said determining means are repeatedly accessed until said small tasks can be allocated. 11. The system of claim 10 wherein the guessing means further includes:means for increasing the guessed value for said value of optimal load by a factor of (1+ε) each time said first guessing means is accessed. 12. The system of claim 10 wherein said partitioning means further comprises:means for determining if a largest dimension is smaller than said error criteria per number of dimensions represented by δ;means for determining a set of large vectors if the error criteria per number of dimensions, δ is smaller than said largest coordinate; andmeans for determining a set of small vectors if the error criteria per number of dimensions, δ, is greater than or equal to said largest coordinate. 13. The system of claim 12 wherein said discretizing means includes:means for rounding dimensions of the set of large vectors which are smaller than δ 2 to zero for determining a smallest non zero coordinate from said set of large vectors;means for partitioning said set of large vectors into geometrically increasing intervals; andmeans for rounding up mapping non zero coordinates of each large vector in the set of large vectors up to the right end part of one of the intervals of which the coordinate falls to form the discretized large tasks. 14. The system of claim 12 wherein the plurality of multi-dimensional tasks is represented by a d-dimensional vector, p j , and an error criteria per number of dimensions is represented by δ, wherein said determining means includes:means for defining an integer program to allocate d-dimensional vectors representing the small tasks in the space of the m multi-dimensional bins unallocated after allocating the set of discretized tasks;means for solving the integer program by linear relaxation to determine from the vertex solution d-dimensional vectors representing the small tasks which can be allocated integrally to one of the m multi-dimensional bins and d-dimensional vectors representing the small tasks which can be allocated fractiona lly; andmeans for packing the d-dimensional vectors representing the small tasks determined to be allocated fractionally in a round robin greedy fashion to one of said plurality of multi-dimensional bins. 15. The system of claim 13 wherein the packing means includes:means for defining a number of the large vectors to fit in each of the m multidimensional bins;means for defining a number of types of the large vectors;means for assigning a capacity configuration for each of the m multi-dimensional bins from said space of the m multi-dimensional bins unallocated by the guessed allocation of the set of small tasks; andmeans for determining a plurality of subsets of the large vectors to fit in the assigned capacity configuration for each of the plurality of multi-dimensional bins by dynamic programming.