Patent ID: 7472392

Claim:
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.