Patent ID: 7430742

Claim:
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 (PE r ) 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.