Patent ID: 7437729
Filing Date: 2008-10-14
Classification: G06F

Abstract:
1. 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 within each processing element a total number of tasks present within said loop; calculating a local mean number of tasks within each of said plurality of processing elements; calculating a local deviation from said local mean number within each of said plurality of processing elements; determining a sum deviation from said local deviations within each of said processing elements for one-half said loop in an anti-clockwise direction, said one-half of said loop being relative to each of said selected processing elements; determining a sum deviation from said local deviations within each of said processing elements for one-half said loop in a clockwise direction, said one-half of said loop being relative to each of said selected processing elements; determining a clockwise transfer parameter and an anti-clockwise transfer parameter from said sum deviations within each of said processing elements; and redistributing tasks among said plurality of processing elements using said clockwise transfer parameters and said anti-clockwise parameters within each of said plurality of processing elements.