# US 2008/0313484 A1 · Parallel Processing of Multi-Dimensional Data With Causal Neighborhood Dependencies

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0313484 A1
- Document ID: US20080313484A1
- Status: Published application
- Kind: A1
- Application number: 11/761,510
- Filed: 2007-06-12
- Published: 2008-12-18
- Earliest claimed: 2007-06-12
- Assignees: International Business Machines Corporation
- Inventors: Krishna Ratakonda; Deepak S. Turaga
- Web page: https://patentgrep.com/patent/US20080313484A1

## CPC

- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method (which can be computer implemented) 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, includes the steps of determining starting times for each individual one of the processors, and maintaining synchronization across the processors, while ensuring that the dependency structure is not violated. Not all the starting times are the same, and a sum of absolute differences between (i) starting times of any given processor, and (ii) that one of the processors having an earliest starting time, is minimized.

## Claims

### Claim 1

A method for assigning starting times to a plurality of parallel processors processing a plurality of rows of data units, said method comprising the steps of:
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;
in each of said rows in said group of rows except said first one of said 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;
identifying a relative right-most data unit in said relative left-most data unit set;
identifying a second given data unit in a last one of said rows in said group;
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;
identifying a relative left-most data unit in said relative right-most data unit set; and
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.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
there are N of said processors;
said group of rows comprises N rows, each with B data units;
said group of rows have inter-row dependencies spanning M rows; and
there are a plurality of N-row groups;
further comprising the additional step of computing delays for each of said N processors associated with transitioning from a first of said N-row groups to a second of said N-row groups.

### Claim 3 (depends on 2)

The method of claim 2, wherein said additional step of computing said delays for each of said N processors associated with said transitioning in turn comprises:
for a first of said N processors to finish processing said first of said N-row groups, determining said delay associated with said transitioning as a maximum of a set of differences between desired and actual processing positions of a remainder of said N processors;
for each additional one of said N processors, in an order in which they finish said processing of said first of said N-row groups, determining said delay associated with said transitioning as a maximum of a set of differences between desired and actual processing positions of a remainder of said N processors, plus said delay associated with a preceding one of said N processors to finish said processing of said first of said N-row groups.

### Claim 4 (depends on 3)

The method of claim 3, wherein M≦N, further comprising the additional step of employing said delays computed for said transitioning from said first of said N-row groups to said second of said N-row groups for additional transitions between additional ones of said N-row groups.

### Claim 5 (depends on 3)

The method of claim 3, wherein M>N, further comprising the additional step of re-computing said delays for said transitioning for additional transitions between additional ones of said N-row groups.

### Claim 6 (depends on 2)

The method of claim 2, further comprising the additional step of operating said N processors in accordance with said starting times and said delays associated with said transitioning.

### Claim 7 (depends on 2)

The method of claim 2, wherein:
N=M;
said step of identifying said relative left-most data unit on which said first given data unit is dependent, to obtain said relative leftmost data unit set, comprises determining the quantity PRkmin for k=1 to N−1:
PRkmin=max(PR0+rk, PR1min+rk−1, PR2min+rk−2, . . . , PRk−1min+r1)
wherein:
Psubscript1 comprises a position of a given data unit in a row corresponding to subscript1 and
rsubscript2 comprises a distance between a relative right-most data unit in an adjacent row that a current data unit in row subscript2depends o, and said current data unit;
said step of identifying a relative right-most data unit in said relative left-most data unit set comprises determining a relative right-most processor
O
0
=
arg


max
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
min
)
and setting
P
O
0
=

max
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
min
)
;
said step of 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, comprises determining the quantity PRkmax for k=N−2 to 0:
PRkmax=min(PrN−1−rN−1−k, PRN−2−rN−2−k, . . . , PRk+1max−r1); and
said step of identifying a relative left-most data unit in said relative right-most data unit set comprises determining a relative left-most processor
O
N
-
1
=
arg


min
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
max
)
.

### Claim 8 (depends on 7)

The method of claim 7, wherein said step of determining said starting times comprises applying, for each ith processor:
TOi=T×(PO0−POi)
wherein:
T=time required to process one data unit

### Claim 9 (depends on 7)

The method of claim 7, further comprising the additional step of:
setting PR0min=PR0=0; and
setting PRN−1max=PRN−1=PO0.

### Claim 10 (depends on 2)

The method of claim 2, wherein:
M<N;
said step of identifying said relative left-most data unit on which said first given data unit is dependent, to obtain said relative left-most data unit set, comprises determining the quantity PRkmin for k=1 to N−1:
PRkmin=max(PR0+rk, PR1min+rk−1, PR2min+rk−2, . . . , PRk−1min+r1)
wherein:
Psubscript1 comprises a position of a given data unit in a row corresponding to subscript1; and
rsubscript2 comprises a distance between a relative right-most data unit in an adjacent row that a current data unit in row subscript2 depends on, and said current data unit, rsubscript2 being set to negative infinity when data units in a row corresponding to subscript2 do not depend on data units in an adjacent row;
said step of identifying a relative right-most data unit in said relative left-most data unit set comprises determining a relative right-most processor
O
0
=
arg


max
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
min
)
and setting
P
O
0
=

max
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
min
)
;
said step of 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, comprises determining the quantity PRk for k=N−2 to 0:
PRkmax=min(PRN−1−rN−1−k,PRN−2max−rN−2−k, . . . , PRk+1max−r1); and
said step of identifying a relative left-most data unit in said relative right-most data unit set comprises determining a relative left-most processor
O
N
-
1
=
arg


min
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
max
)

### Claim 11 (depends on 2)

The method of claim 2, wherein said additional step of computing said delays for each of said N processors associated with said transitioning in turn comprises:
calculating an additional wait time for a first of said N processors to finish processing said first of said N-row groups, according to:
WSk=WO0=max(ΔSk→R0, ΔSk→R1, . . . , ΔSk→Rk−1, 0),
wherein:
ASk→Rk−1=min(B−PRk+PRk 1, B);
B=number of data elements per row;
DSk→Rk−1=rN−1; and
ΔSk→Ri=T(DSk→R1−ASk→Ri), for i=0, . . . , k−1; and
for each additional one of said N processors, in an order in which they finish said processing of said first of said N-row groups, calculating an additional wait time for each additional one of said processors according to:
WSi=WOm=max(ΔSi→R0, ΔSi→R1, . . . , ΔSi→R1−1, 0)+WOm−1,
wherein:
ASi→Ri−1=min(B−PRi+PRi−1+WOm−1T, B);
T=time required to process one data unit;
DSi→Ri−1−rN−1; and
ΔSi→RiT(DSh→R1−ASk→Ri), for i=0, . . . , k−1.

### Claim 12

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.

### Claim 13

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.

### Claim 14 (depends on 13)

The computer program product of claim 13, wherein:
there are N of said processors;
said group of rows comprises N rows, each with B data units; and
said group of rows having inter-row dependencies spanning M rows; and
there are a plurality of N-row groups;
further comprising computer usable program code for computing delays for each of said N processors associated with transitioning from a first of said N-row groups to a second of said N-row groups.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein said computer usable program code for computing said delays for each of said N processors associated with said transitioning in turn comprises:
computer usable program code for, for a first of said N processors to finish processing said first of said N-row groups, determining said delay associated with said transitioning as a maximum of a set of differences between desired and actual processing positions of a remainder of said N processors;
computer usable program code for, for each additional one of said N processors, in an order in which they finish said processing of said first of said N-row groups, determining said delay associated with said transitioning as a maximum of a set of differences between desired and actual processing positions of a remainder of said N processors, plus said delay associated with a preceding one of said N processors to finish said processing of said first of said N-row groups.

### Claim 16 (depends on 15)

The computer program product of claim 15, wherein N=M, further comprising computer usable program code for employing said delays computed for said transitioning from said first of said N-row groups to said second of said N-row groups for additional transitions between additional ones of said N-row groups

### Claim 17 (depends on 15)

The computer program product of claim 15, wherein M>N, further comprising computer usable program code for re-computing said delays for said transitioning for additional transitions between additional ones of said N-row groups.

### Claim 18 (depends on 14)

The computer program product of claim 14, further comprising computer usable program code for operating said N processors in accordance with said starting times and said delays associated with said transitioning.

### Claim 19 (depends on 14)

The computer program product of claim 14, wherein:
N=M;
said computer usable program code for identifying said relative left-most data unit on which said first given data unit is dependent, to obtain said relative left-most data unit set, comprises computer usable program code for determining the quantity PRkmin for k=1 to N−1:
PRkmin=max(PR0+rk, PRimin+rk−1, PR2min+rk−2, . . . , PRk 1min+r1)
wherein:
Psubscript1 comprises a position of a given data unit in a row corresponding to subscript1; and
rsubscript2 comprises a distance between a relative right-most data unit in an adjacent row that a current data unit in row subscript2 depends on, and said current data unit;
said computer usable program code for identifying a relative right-most data unit in said relative left-most data unit set comprises computer usable program code for determining a relative right-most processor
O
0
=
arg


max
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
min
)
and setting
P
O
0
=
max
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
min
)
;
said computer usable program code for 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, comprises computer usable program code for determining the quantity PRkmax for k=N−2 to 0:
PRkmax=min(PRN−1−rN−1−k, PRN−2max−rN−2−k, . . . , PRk+1max−r1); and
said computer usable program code for identifying a relative left-most data unit in said relative right-most data unit set comprises computer usable program code for determining a relative left-most processor
O
N
-
1
=
arg


min
j
=
0
,
1
,
…

,
N
-
1

(
P
R
j
max
)
.

### Claim 20

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.
