Apparatus and method for efficiently partitioning a weighted array

A computing apparatus for generating a pre-processing data structure configured for ordering array elements of a data array, comprising:

• temporary division means for determining a temporary division of a two or more-dimensional array in memory of data into a plurality of blocks such that each of said plurality of blocks has a weight of at least approximately two times a desired maximum weight;
• rectangle determining computing means for determining, within each block, rectangles containing array elements greater than or equal to an arbitrary value;
• independent rectangle computing determining means for determining for each block, from among said rectangles determined by said means for determining, a largest set of rectangles which are independent;
• and
• partition definition computing means for defining partitions of said two or more-dimensional array of data corresponding to sides of said largest set of rectangles which are independent for each blocks;
• wherein said pre-processing data structure is applied to one of a load balancing, scheduling, data layout, video compression and image processing settings.

A computer readable storage medium having stored thereon a computer program for implementing a method of partitioning a two or more-dimensional array of data based on a weight given to any one block in said two or more-dimensional array, said computer program comprising a set of instructions for:

• temporarily dividing said two or more-dimensional array into a plurality of blocks such that each of said plurality of blocks has a weight of at least approximately two times a desired maximum weight;
• determining, within each block, a largest set of independent rectangles containing array elements greater than or equal to an arbitrary value;
• and
• defining partitions of said two or more-dimensional array corresponding to sides of said largest set of independent rectangles for each block.