Patent ID: 7373645

Claim:
A method for balancing the load of a parallel processing system having a plurality of parallel processing elements arranged in a loop, wherein each processing element (PE r ) has a local number of tasks associated therewith, wherein r represents the number for a selected processing element, and wherein each of said processing elements is operable to communicate with a clockwise adjacent processing element and with an anti-clockwise adjacent processing element, the method comprising: determining a total number of tasks present within said loop; 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 running partial deviation sum for each of said plurality of processing elements using said local deviation; determining a clockwise transfer parameter and an anti-clockwise transfer parameter for each of said plurality of processing elements from said running partial deviation sums; and redistributing tasks among said plurality of processing elements using said clockwise transfer parameter and said anti-clockwise parameter for each of said plurality of processing elements.