Parallel Processing of Multi-Dimensional Data With Causal Neighborhood Dependencies

A method for processing a plurality of adjacent rows of data units, using a plurality of parallel processors, given (i) a predetermined processing order, and (ii) a specified inter-row dependency structure, said method comprising the steps of:

• determining starting times for each individual one of said processors;
• and
• maintaining synchronization across said processors, while ensuring that said dependency structure is not violated;
• wherein:
• not all said starting times are the same;
• and
• a sum of absolute differences between (i) starting times of any given processor, and (ii) that one of said processors having an earliest starting time, is minimized.

A computer program product comprising a computer useable medium including computer usable program code for assigning starting times to a plurality of parallel processors processing a plurality of rows of data units, said computer program product including:

• computer usable program code for, within a group of rows having inter-row dependencies, identifying a first given data unit in a first one of said rows in said group;
• computer usable program code for, in each of said rows in said group of rows except said first one of rows, identifying a relative left-most data unit on which said first given data unit is dependent, to obtain a relative left-most data unit set;
• computer usable program code for identifying a relative right-most data unit in said relative left-most data unit set;
• computer usable program code for identifying a second given data unit in a last one of said rows in said group;
• computer usable program code for, in each of said rows in said group except said last one of said rows, identifying a relative right-most data unit that is dependent on said second given data unit, to obtain a relative right-most data unit set;
• computer usable program code for identifying a relative left-most data unit in said relative right-most data unit set;
• and
• computer usable program code for determining said starting times based, at least in part, on said relative right-most data unit in said relative left-most data unit set and said relative left-most data unit in said relative right-most data unit set.

A computer program product comprising a computer useable medium including computer usable program code for processing a plurality of adjacent rows of data units, using a plurality of parallel processors, given (i) a predetermined processing order, and (ii) a specified inter-row dependency structure, said computer program product including:

• computer usable program code for determining starting times for each individual one of said processors;
• and
• computer usable program code for maintaining synchronization across said processors, while ensuring that said dependency structure is not violated;
• wherein:
• not all said starting times are the same;
• and
• a sum of absolute differences between (i) starting times of any given processor, and (ii) that one of said processors having an earliest starting time, is minimized.