초록 ▼

A method for balancing the load of a parallel processing system having parallel processing elements (PEs) linked serially in a line with first and second ends, wherein each of the PEs has a local number of tasks associated therewith, the method comprising determining a total number of tasks present

A method for balancing the load of a parallel processing system having parallel processing elements (PEs) linked serially in a line with first and second ends, wherein each of the PEs has a local number of tasks associated therewith, the method comprising determining a total number of tasks present on the line; notifying each of the PEs of the total number of tasks, calculating a local mean number of tasks for each of the PEs, and calculating a local deviation for each of the PEs. The method also comprises determining a first local cumulative deviation for each of the PEs, determining a second local cumulative deviation for each of the PEs, and redistributing tasks among the PEs in response to the first local cumulative deviation and the second local cumulative deviation.

대표청구항 ▼

What is claimed is: 1. A method for balancing the load of a parallel processing system having a plurality of parallel processing elements linked serially in a line with first and second ends, wherein each of said plurality of processing elements (PEr) has a local number of tasks associated therewit

What is claimed is: 1. A method for balancing the load of a parallel processing system having a plurality of parallel processing elements linked serially in a line with first and second ends, wherein each of said plurality of processing elements (PEr) has a local number of tasks associated therewith, the method comprising: determining a total number of tasks present on said line; notifying each of said plurality of processing elements of said total number of tasks; calculating a local mean number of tasks for each of said plurality of processing elements; calculating a local deviation from said local mean number for each of said plurality of processing elements; determining a first local cumulative deviation for each of said plurality of processing elements by summing the local deviations associated with upstream processing elements; determining a second local cumulative deviation for each of said plurality of processing elements; and redistributing tasks among said plurality of processing elements in response to said first local cumulative deviation and said second local cumulative deviation. 2. The method of claim 1 wherein said determining a total number of tasks present on said line comprises sequentially summing said local number of tasks associated with each of said plurality of PE's from said first end of said line to said second end of said line. 3. The method of claim 1 wherein said determining said total number of tasks present on said line includes solving the equation where V represents said total number of tasks present on said line, N represents the number of processing elements in said line, and vi represents said local number of tasks associated with a local PEr. 4. The method of claim 1 wherein said notifying step includes passing said total number of tasks from said second end to said first end. 5. The method of claim 1 wherein said calculating a local mean number of tasks for each of said plurality of processing elements further includes solving the equation Mr=Trunc((V+Er)/N), where Mr represents said local mean for a PEr, N represents the total number of processing elements in said line, V represents the total number of tasks, and Er is a number in the range of 0 to (N-1). 6. The method of claim 5 wherein each PE has a different Er value. 7. The method of claim 5 wherein said Trunc function is responsive to the value of 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 plurality of processing elements in said line. 8. The method of claim 5 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 the local mean. 9. The method of claim 1 wherein said calculating a local deviation for each of said plurality of processing elements includes finding the difference between said local number of tasks and said local mean number of tasks for each PEr. 10. The method of claim 1 wherein said determining a second local cumulative deviation includes finding a difference between the negative of said local deviation and said first local cumulative deviation for each PEr. 11. The method of claim 1 wherein said redistributing tasks among said plurality of processing elements 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; transferring a task from said local PEr to a right-adjacent PE,r+1 if said second local cumulative deviation for said local PEr is a negative value. 12. The method of claim 1 wherein said redistributing tasks among said plurality of processing elements 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; 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. 13. The method of claim 1 wherein said calculating a local mean number of tasks for each of said plurality of processing elements; said calculating a local deviation from said local mean number of tasks for each of said plurality of processing elements; said determining a first local cumulative deviation; said determining a second local cumulative deviation; and said redistributing tasks are completed in parallel for each of said plurality of processing elements. 14. The method of claim 1 wherein said calculating a local deviation for each of said plurality of processing elements, determining a first local cumulative deviation for each of said plurality of processing elements, determining a second local cumulative deviation for each of said plurality of processing elements, and redistributing tasks among said plurality of processing elements in response to said first local cumulative deviation and said second local cumulative deviation are repeated until said local deviation, said first local cumulative deviation, and said second local cumulative deviation for each of said plurality of processing elements is zero. 15. A method for assigning tasks associated with a parallel processing element (PEr) within a line of processing elements, said PEr being serially connected to at least one other PE in said line and said PEr having a local number of tasks associated therewith, the method comprising: notifying said PEr of a total number of tasks associated with said line; determining said PEr's associated share of said total number of tasks; determining a first local cumulative deviation for said PEr by summing the local deviations associated with upstream processing elements; determining a second local cumulative deviation for said PEr; redistributing tasks with said at least one other connected parallel processing element in response to at least one of said first local cumulative deviation and said second local cumulative deviation. 16. The method of claim 15 wherein said notifying said PEr comprises: serially summing said local number of tasks present on said line; and transmitting said total number of tasks to said PEr. 17. The method of claim 15 wherein said determining said PEr's associated share of said total number of tasks comprises: calculating a local mean number of tasks for said PEr, said local mean number of tasks being equal to Mr=Trunc((V+Er)/N), where Mr represents said local mean of said local PEr, N represents the total number of processing elements in said line, V represents the total number of tasks and Er represents a number in the range of 0 to (N-1); and calculating a local deviation from said local mean number of tasks for PEr by finding the difference between said local number of tasks and said local mean number of tasks for PEr. 18. The method of claim 17 wherein each processing element in said line has a different Er value. 19. The method of claim 15 wherein said Trunc function is responsive to the value of 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. 20. The method of claim 17 wherein 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 the local mean. 21. The method of claim 15 wherein said determining a second local cumulative deviation for said PEr includes finding the difference between the negative of said local deviation and said first local cumulative deviation for said PEr. 22. The method of claim 15 wherein said redistributing tasks with said at least one other parallel processing element comprises: transferring a task to said at least one other parallel processing element from said PEr if at least one said first local cumulative deviation is a negative value and if said second local cumulative deviation is a negative value; and transferring a task from said at least one other parallel processing element to said PEr if at least one said first local cumulative deviation is a positive value and if said second local cumulative deviation is a positive value. 23. The method of claim 15 wherein said determining a first local cumulative deviation step, determining a second local cumulative deviation step, and said redistributing tasks step continue until said first local cumulative deviation and said second local cumulative deviation for said PEr is zero. 24. A computer readable memory device carrying a set of instructions which, when executed, perform a method comprising: determining a total number of tasks present on a line of parallel processing elements; notifying each of said plurality of processing elements of said total number of tasks; calculating a local mean number of tasks for each of said plurality of processing elements; calculating a local deviation from said local mean number for each of said plurality of processing elements; determining a first local cumulative deviation for each of said plurality of processing elements by summing the local deviations associated with upstream processing elements; determining a second local cumulative deviation for each of said plurality of processing elements; and redistributing tasks among said plurality of processing elements in response to said first local cumulative deviation and said second local cumulative deviation.