“Shift Homomorphism”

Consider the following fragment of HPF pseudocode:

!HPF$  TEMPLATE tx (0 :  ), ty (0 :  )
!HPF$  DISTRIBUTE tx (BLOCK (w_{x})) ONTO p
!HPF$  DISTRIBUTE ty (BLOCK (w_{y})) ONTO p
!HPF$  DIMENSION x (0 :  n - 1), y (0 :  n - 1)
!HPF$  ALIGN x (i) WITH tx (k_{x}+ s_{tx}* i)
!HPF$  ALIGN y (i) WITH ty (k_{y}+ s_{ty}* i)

x = y

By suitable composition of section and alignment parameters, possibly combined with trivial relabelling so that index ranges start at 0, any assignment between one-dimensional sections block-distributed over the same one-dimensional processor arrangement can be reduced to this case.

The arrays x and y are “shift-homomorphic” iff

s_{tx}/w_{x} = s_{ty}/w_{y}

If this condition holds the assignment of y to x can be implemented by shifting the values of y along template ty then performing a local copy.

Proof:

The element i of x is aligned with element k_{x} + s_{tx}i of template tx and the element i of y is aligned with element k_{y} + s_{ty}i of template ty.

A temporary array y' is created by shifting the values in y by amount

a = k′_{y} − k_{y}

along template ty. So element i of y' is aligned with element k′_{y} + s_{ty}i of template ty.

In particular, choose

k′_{y} = ⌊k_{x}w_{y}/w_{x}⌋

so the alignment of element i of y' is to element

k′_{y} + s_{ty}i = ⌊k_{x}w_{y}/w_{x}⌋ + s_{ty}i
= ⌊k_{x}w_{y}/w_{x} + s_{ty}i⌋
= ⌊(k_{x}w_{y} + s_{ty}w_{x}i)/w_{x}⌋

of template ty.

Now, element j_{x} of template tx is mapped to processor ⌊j_{x}/w_{x}⌋ and element j_{y} of template ty is mapped to processor ⌊j_{y}/w_{y}⌋.

So element i of x is mapped to processor

⌊(k_{x} + s_{tx}i)/w_{x}⌋

and element i of y' is mapped to processor

⌊(k′_{y} + s_{ty}i)/w_{y}⌋

But

⌊(k′_{y} + s_{ty}i)/w_{y}⌋ = ⌊⌊(k_{x}w_{y} + s_{ty}w_{x}i)/w_{x}⌋/w_{y}⌋
= ⌊(k_{x}w_{y} + s_{ty}w_{x}i)/w_{x}w_{y}⌋
= ⌊k_{x}/w_{x} + s_{ty}i/w_{y}⌋
= ⌊(k_{x} + s_{tx}i)/w_{x}⌋

In the second step we used a general property of non-negative integers:

⌊⌊l/m⌋/n⌋ = ⌊l/mn⌋

and in the last step we used the shift homomorphism condition.

This establishes that elements i of x and y' map to the same processor. Suppose this is processor n. Assuming array segments are allocated according to the template size, the local subscript in x is

l_{x} = k_{x} + s_{tx}i − n ∗ w_{x}

and the local subscript in y' is

l′_{y} = k′_{y} + s_{ty}i − n ∗ w_{y}

Using the shift homomorphism condition gives

w_{x}l′_{y} − w_{y}l_{x} = w_{x}k′_{y} − w_{y}k_{x}

or

l′_{y} = (w_{y}/w_{x})l_{x} + (k′_{y} − w_{y}k_{x}/w_{x})

as the relation between the local subscripts.