Method and apparatus for distributed state-based load balancing between task queues
First Claim
Patent Images
1. A method for balancing load between task queues in a multiprocessor system, the method comprising:
- conditionally requesting load information from a number of neighboring CPUs in a neighborhood of a requesting CPU;
in response to the request, receiving load information from one or more neighboring CPUs;
calculating a neighborhood mean load based on the received load information;
if a load on the requesting CPU is below the neighborhood mean load, requesting one or more neighboring CPUs to transfer tasks to the requesting CPU;
determining a total number of tasks which are to be requested from a neighboring CPU so that, after the transfer, the load on the requested neighboring CPU is not below the neighborhood mean load;
for each neighboring CPU from the one or more neighboring CPUs, determining if a condition is satisfied to send one or more tasks from the neighboring CPU to the requesting CPU; and
if the condition is satisfied, sending the one or more tasks from the neighboring CPU to the requesting CPU, thereby balancing load between CPUs in the neighborhood.
2 Assignments
0 Petitions
Accused Products
Abstract
One embodiment of the present invention provides a system that performs load balancing between task queues in a multiprocessor system. During operation, the system conditionally requests load information from a number of neighboring CPUs in a neighborhood of a requesting CPU. In response to the request, the system receives load information from one or more neighboring CPUs. Next, the system conditionally requests one or more neighboring CPUs to transfer tasks to the requesting CPU based on the received load information, thereby balancing load between the CPUs in the neighborhood.
-
Citations
14 Claims
-
1. A method for balancing load between task queues in a multiprocessor system, the method comprising:
-
conditionally requesting load information from a number of neighboring CPUs in a neighborhood of a requesting CPU; in response to the request, receiving load information from one or more neighboring CPUs; calculating a neighborhood mean load based on the received load information; if a load on the requesting CPU is below the neighborhood mean load, requesting one or more neighboring CPUs to transfer tasks to the requesting CPU; determining a total number of tasks which are to be requested from a neighboring CPU so that, after the transfer, the load on the requested neighboring CPU is not below the neighborhood mean load; for each neighboring CPU from the one or more neighboring CPUs, determining if a condition is satisfied to send one or more tasks from the neighboring CPU to the requesting CPU; and if the condition is satisfied, sending the one or more tasks from the neighboring CPU to the requesting CPU, thereby balancing load between CPUs in the neighborhood. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for balancing load between task queues in a multiprocessor system, the method comprising:
-
receiving at a first CPU a request to transfer a number of tasks to a second CPU, wherein the request includes the number of tasks; determining whether a load on the first CPU if the number of tasks are transferred is higher than or equal to a load on the second CPU if the number of tasks are transferred, and, if so, transferring the number of tasks to the second CPU; determining whether a load on the first CPU if the number of tasks are transferred is higher than or equal to a load on the second CPU if the number of tasks are transferred, and, if so, transferring the number of tasks to the second CPU; otherwise, if the load on the first CPU if the number of tasks are transferred is lower than the load on the second CPU if the number of tasks are transferred; determining a reduced number of tasks to transfer so that the load on the first CPU if the reduced number of tasks are transferred is higher than or equal to the load on the second CPU if the reduced number of tasks are transferred; and if the reduced number of tasks is greater than or equal to a minimum number of tasks which can be transferred between CPUs, transferring the reduced number of tasks to the second CPU.
-
-
8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for balancing load between task queues in a multiprocessor system, the method comprising:
-
conditionally requesting load information from a number of neighboring CPUs in a neighborhood of a requesting CPU; in response to the request, receiving load information from one or more neighboring CPUs; calculating a neighborhood mean load based on the received load information; if a load on the requesting CPU is below the neighborhood mean load, requesting one or more neighboring CPUs to transfer tasks to the requesting CPU; determining a total number of tasks which are to be requested from a neighboring CPU so that, after the transfer, the load on the requested neighboring CPU is not below the neighborhood mean load; for each neighboring CPU from the one or more neighboring CPUs, determining if a condition is satisfied to send one or more tasks from the neighboring CPU to the requesting CPU; and if the condition is satisfied, sending the one or more tasks from the neighboring CPU to the requesting CPU, thereby balancing load between CPUs in the neighborhood. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for balancing load between task queues in a multiprocessor system, the method comprising:
-
receiving at a first CPU a request to transfer a number of tasks to a second CPU, wherein the request includes the number of tasks; determining whether a load on the first CPU if the number of tasks are transferred is higher than or equal to a load on the second CPU if the number of tasks are transferred, and, if so, transferring the number of tasks to the second CPU; otherwise, if the load on the first CPU if the number of tasks are transferred is lower than the load on the second CPU if the number of tasks are transferred; determining a reduced number of tasks to transfer so that the load on the first CPU if the reduced number of tasks are transferred is higher than or equal to the load on the second CPU if the reduced number of tasks are transferred; and if the reduced number of tasks is greater than or equal to a minimum number of tasks which can be transferred between CPUs, transferring the reduced number of tasks to the second CPU.
-
Specification