Method for load balancing an n-dimensional array of parallel processing elements
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/46
G06F-015/00
G06F-015/76
출원번호
US-0689365
(2003-10-20)
등록번호
US-7472392
(2008-12-30)
우선권정보
GB-0309204.6(2003-04-23)
발명자
/ 주소
Beaumont,Mark
출원인 / 주소
Micron Technology, Inc.
대리인 / 주소
Jones Day
인용정보
피인용 횟수 :
0인용 특허 :
22
초록▼
One aspect of the present invention relates to a method for balancing the load of an n-dimensional array of processing elements (PEs), wherein each dimension of the array includes the processing elements arranged in a plurality of lines and wherein each of the PEs has a local number of tasks associa
One aspect of the present invention relates to a method for balancing the load of an n-dimensional array of processing elements (PEs), wherein each dimension of the array includes the processing elements arranged in a plurality of lines and wherein each of the PEs has a local number of tasks associated therewith. The method comprises balancing at least one line of PEs in a first dimension, balancing at least one line of PEs in a next dimension, and repeating the balancing at least one line of PEs in a next dimension for each dimension of the n-dimensional array. The method may further comprise selecting one or more lines within said first dimension and shifting the number of tasks assigned to PEs in said selected one or more lines.
대표청구항▼
What is claimed is: 1. A method for balancing the work load of an n-dimensional array of processing elements(PEs), wherein each dimension of said array includes said processing elements arranged in a plurality of lines and wherein each of said processing elements has a local number of tasks associa
What is claimed is: 1. A method for balancing the work load of an n-dimensional array of processing elements(PEs), wherein each dimension of said array includes said processing elements arranged in a plurality of lines and wherein each of said processing elements has a local number of tasks associated therewith, the method comprising: balancing a work load across at least one line of processing elements in a first dimension by redistributing the tasks amongst the processing elements in said line; balancing a work load across at least one line of processing elements in a next dimension by redistributing the tasks amongst the processing elements in said line; and repeating said balancing at least one line of processing elements in a next dimension by redistributing the task among the processing elements in said line for each dimension of said n-dimensional array until the work load is balanced across all said processing elements; and wherein said balancing a work load comprises: calculating a total number of tasks for said line, wherein said total number of tasks for said line equals the sum of said local number of tasks for each of said processing elements on said line; notifying each of said processing elements on said line of said total number of tasks for said line; calculating a local mean number of tasks for each of said processing elements on said line; calculating a local deviation from local mean number for each of said processing elements on said line; determining a first local cumulative deviation for each of said processing elements on said line; determining a second local cumulative deviation for each of said processing elements on said line; and redistributing tasks among said processing elements on said line in response to at least one of said first local cumulative deviation and said second local cumulative deviation. 2. The method of claim 1 wherein two or more lines in at least one of said first dimension and said next dimension are balanced in parallel. 3. The method of claim 1 wherein said calculating a total number of tasks for said line comprises sequentially summing said local number of tasks for each of said processing elements on said line from a first end of said line to a second end of said line. 4. The method of claim 1 wherein said calculating said total number of tasks for said line includes solving the equation where V represents said total number of tasks for said line, N represents the number of processing elements on said line, and vi represents said local number of tasks for a local PEr on said line. 5. The method of claim 1 wherein said notifying step includes passing said total number of tasks from a second end of said line to a first end of said line. 6. The method of claim 1 wherein said calculating a local mean number of tasks includes solving the equation Mr=Trunc((V+Er)/N), where Mr represents said local mean for a local processing element PEr on said line, N represents the total number of PEs on said line, V is the total number of tasks, and Er is a number in the range of 0 to (N-1). 7. The method of claim 6 wherein each processing element has a different Er value. 8. The method of claim 6 wherein said Trunc function is responsive to Er such that said total number of tasks for said line is equal to the sum of the local mean number of tasks for each processing element on said line. 9. The method of claim 6 wherein said local mean Mr=Trunc((V+Er)/N) for each local PEr on said line is equal to either X or (X+1), where X is equal to local mean. 10. The method of claim 1 wherein said calculating a local deviation for each processing element on said line includes finding a difference between said local number of tasks for each PEr and said local mean number of tasks for each PEr. 11. The method of claim 1 wherein said determining a first local cumulative deviation includes sequentially summing said local deviations for each PEr from a first end of said line to an adjacent upstream PEr-1 on said line. 12. The method of claim 1 wherein said determining a second local cumulative deviation includes finding a difference between the negative of said local deviation for each PEr and said first local cumulative deviation for each PEr. 13. The method of claim 1 wherein said redistributing tasks among said processing elements on said line comprises: transferring a task from a local PEr to a left-adjacent PEr-1 if said first local cumulative deviation for said local PEr is a negative value; and transferring a task from said local PEr to a right-adjacent PEr+1 if said second local cumulative deviation for said local PEr is a negative value. 14. The method of claim 1 wherein said redistributing tasks among said processing elements on said line comprises: transferring a task from a local PEr to a left-adjacent PEr-1 if said second local cumulative deviation for said local PEr is a positive value; and transferring a task from said local PEr to a right-adjacent PEr+1 if said first local cumulative deviation for said local PEr is a positive value. 15. The method of claim 1 wherein said calculating a local mean number of tasks; said calculating a local deviation; said determining a first local cumulative deviation; said determining a second local cumulative deviation; and said redistributing tasks are completed in parallel for each processing element on said line. 16. The method of claim 15 wherein said calculating a local mean number of tasks; said calculating a local deviation; said determining a first local cumulative deviation; said determining a second local cumulative deviation; and said redistributing tasks are completed in parallel for each line in a selected dimension. 17. The method of claim 1 wherein said calculating a local deviation, said determining a first local cumulative deviation, said determining a second local cumulative deviation, and said redistributing tasks among said processing elements are repeated until said local deviation, said first local cumulative deviation, and said second local cumulative deviation for each of said processing elements is zero. 18. A method for balancing a work load across one dimension of an n-dimensional array of processing elements(PEs), wherein each of said n-dimensions is traversed by a plurality of lines and wherein each of said lines has a plurality of processing elements with a local number of tasks associated therewith, the method comprising: balancing said plurality of lines in one dimension by redistributing tasks amongst the processing elements in each of said plurality of lines; balancing said plurality of lines in a next higher dimension; repeating said balancing said plurality of lines in a next higher dimension for each remaining dimension of said n-dimensional array, wherein each of said balanced lines includes PEs with either a number of local tasks equal to X or a number of local tasks equal to (X+1), where X equals a local mean; substituting the value zero (0) for each processing element having X local number of tasks; substituting the value one (1) for each processing element having (X+1) local number of tasks; and shifting said values for each processing element within said balanced lines until a sum of said processing elements relative to a second dimension has only two different values, wherein shifting said values represents moving a task. 19. The method of claim 18 wherein said balancing said plurality of lines in one dimension comprises: calculating a total number of tasks present within at least one of said lines; notifying each processing element on said line of said total number of tasks for said line; determining each processing element's share of said total number of tasks on said line; calculating a local deviation from said previous steps; determining a first local cumulative deviation for each processing element on said line using said local deviation; determining a second local cumulative deviation for each processing element on said line using said local deviation; and redistributing tasks among each processing element on said line in response to at least one of said first local cumulative deviation and said second local cumulative deviation. 20. The method of claim 19 wherein said notifying each processing element comprises: serially summing said total number of tasks present on said line; and transmitting said total number of tasks to each processing element on said line. 21. The method of claim 19 wherein said determining each processing element's share of said total number of tasks comprises: calculating a local mean number of tasks for each processing element on said line; and calculating a local deviation from said local mean number of tasks for each processing element on said line by finding the difference between said local number of tasks and said local mean number of tasks for each processing element on said line. 22. The method of claim 21 wherein said calculating a local mean number of tasks for each processing element on said line comprises using a rounding function Mr=Trunc((V+Er)/N), where Mr represents said local mean of a local processing elements PEr, N represents the total number of processing elements on said line, V is the total number of tasks, and Er represents a number in the range of 0 to (N-1). 23. The method of claim 22 wherein said Trunc function is responsive to Er such that said total number of tasks for said line is equal to the sum of the local mean number of tasks for each of said processing elements in said line. 24. The method of claim 22 wherein said local mean Mr=Trunc((V+Er)/N) for each local processing element on said line is equal to either X or (X+1), where X is equal to a local mean. 25. The method of claim 19 wherein said determining a first local cumulative deviation for each processing element on said line includes summing said local deviations for each upstream processing element on said line. 26. The method of claim 19 wherein said determining a second local cumulative deviation for each processing element on said line includes finding the difference between the negative of said local deviation and said first local cumulative deviation for each processing element on said line. 27. The method of claim 19 wherein said redistributing tasks among each processing element on said line in response to at least one of said first local cumulative deviation and said second local cumulative deviation comprises: transferring a task from a first processing element on said line to a second processing element on said line if said first local cumulative deviation for said first processing element is a negative value; and transferring a task from said second processing element on said line to said first processing element on said line if said first local cumulative deviation for said second processing element is a positive value. 28. The method of claim 19 wherein said redistributing tasks among each processing element on said line in response to at least one of said first local cumulative deviation and said second local cumulative deviation comprises: transferring a task to a first processing element on said line from a second processing element on said line if said second local cumulative deviation for said first processing element is a negative value; and transferring a task to said second processing element on said line from said first processing element on said line if said second local cumulative deviation for said second processing element is a positive value. 29. The method of claim 21 wherein said calculating a local deviation, said determining a first local cumulative deviation, said determining a second local cumulative deviation, and said redistributing tasks among said processing elements are repeated until said local deviation, said first local cumulative deviation, and said second local cumulative deviation for each of said processing elements is zero. 30. A computer memory storing a set or instructions which, when executed, perform method for balancing a work load across one dimension of an n-dimensional array of processing elements(PEs), wherein each of said n-dimensions is traversed by a plurality of lines and where each of said lines has a plurality processing elements with a local number of tasks associated therewith, the method comprising: balancing said plurality of lines in one dimension by redistributing tasks amongst the processing elements in each of said plurality of lines; balancing said plurality of lines in a next higher dimension; repeating said balancing said plurality of lines in a next higher dimension for each remaining dimension of said n-dimensional array, wherein each of said balanced lines includes PEs with either a number of local tasks equal to X or a number of local tasks equal to (X+1), where X equals a local mean; substituting the value zero (0) for each processing element having X local number of tasks; substituting the value one (1) for each processing element having (X+1) local number of tasks; and shifting said values for each processing element within said balanced lines until a sum of said processing elements relative to a second dimension has only two different values, wherein shifting said values represents moving a task.
Hartung Michael H. (Tucson AZ) Nolta Arthur H. (Tucson AZ) Reed David G. (Tucson AZ) Tayler Gerald E. (Tucson AZ), Load balancing in a multiunit system.
Glover Michael A. (10 Hemlock Way Durham NH 03824), Massively parallel SIMD processor which selectively transfers individual contiguously disposed serial memory elements.
David Karger ; Eric Lehman ; F. Thomson Leighton ; Matthew Levine ; Daniel Lewin ; Rina Panagrahy, Method and apparatus for distributing requests among a plurality of resources.
Vignes Jean P. (Rueil-Malmaison FRX) Ung Vincent (La Varenne FRX), Method and apparatus of providing a result of a numerical calculation with the number of exact significant figures.
Eilert, Catherine K.; Kubala, Jeffrey P.; Nick, Jeffrey M.; Yocom, Peter B., Method, system and program products for managing central processing unit resources of a computing environment.
Harrison R. Loyd (Fullerton CA) Davies Steven P. (Ontario CA), Modular array processor architecture having a plurality of interconnected load-balanced parallel processing nodes.
Hinsley Christopher Andrew,GBX, Operating system for use with computer networks incorporating two or more data processors linked together for parallel processing and incorporating improved dynamic load-sharing techniques.
Bahr James E. (Rochester MN) Corrigan Michael J. (Rochester MN) Knipfer Diane L. (Rochester MN) McMahon Lynn A. (Rochester MN) Metzger Charlotte B. (Elgin MN), Process for dispatching tasks among multiple information processors.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.