IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
UP-0013498
(2004-12-15)
|
등록번호 |
US-7665092
(2010-04-04)
|
발명자
/ 주소 |
|
출원인 / 주소 |
|
대리인 / 주소 |
Park, Vaughan & Fleming LLP
|
인용정보 |
피인용 횟수 :
18 인용 특허 :
4 |
초록
▼
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 requ
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.
대표청구항
▼
What is claimed is: 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 on
What is claimed is: 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. The method of claim 1, wherein the size of the neighborhood is defined in terms of number of hops separating CPUs. 3. The method of claim 1, wherein conditionally requesting load information from the neighboring CPUs involves: determining whether the load of the requesting CPU is below a threshold; and if so, requesting load information from the neighboring CPUs. 4. The method of claim 3, wherein the threshold is determined based on a delay involved in requesting and receiving load information from a neighboring CPU and a delay involved in requesting and receiving tasks from a neighboring CPU. 5. The method of claim 1, wherein determining the total number of tasks which are to be requested from the neighboring CPUs involves selecting the larger of: the amount by which the neighborhood mean load is larger than the load on the requesting CPU, and a minimum number of tasks which can be transferred between CPUs. 6. The method of claim 1, wherein determining the number of tasks which are to be requested from a neighboring CPU involves: ranking the neighboring CPUs in decreasing order with respect to their load; and determining the number of tasks which are to be requested from each neighboring CPU, starting from the highest-loaded CPU, until the total number of tasks which are to be requested from the neighboring CPUs is satisfied. 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. 9. The computer-readable storage medium of claim 8, wherein the size of the neighborhood is defined in terms of number of hops separating CPUs. 10. The computer-readable storage medium of claim 8, wherein conditionally requesting load information from the neighboring CPUs involves: determining whether the load of the requesting CPU is below a threshold; and if so, requesting load information from the neighboring CPUs. 11. The computer-readable storage medium of claim 10, wherein the threshold is determined based on a delay involved in requesting and receiving load information from a neighboring CPU and a delay involved in requesting and receiving tasks from a neighboring CPU. 12. The computer-readable storage medium of claim 8, wherein determining the total number of tasks which are to be requested from the neighboring CPUs involves selecting the larger of: the amount by which the neighborhood mean load is larger than the load on the requesting CPU, and a minimum number of tasks which can be transferred between CPUs. 13. The computer-readable storage medium of claim 8, wherein determining the number of tasks which are to be requested from a neighboring CPU involves: ranking the neighboring CPUs in decreasing order with respect to their load; and determining the number of tasks which are to be requested from each neighboring CPU, starting from the highest-loaded CPU, until the total number of tasks which are to be requested from the neighboring CPUs is satisfied. 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.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.