Distributed Encoding Explanation

[jeromeku]

Can someone step through how the distributed encoding data to thread layout is derived?

Distributed encodings have a layout function that is entirely characterized
by a d-dimensional tensor L. Note that L doesn't need to have the same shape
(or even the same rank) as the tensor it is encoding.

The layout function \mathcal{L} of this layout is then defined, for an
index `i` \in R^D, as follows:

\mathcal{L}(A)[i_d] = L[(i_d + k_d*A.shape[d]) % L.shape[d]] \forall k_d such as i_d + k_d*A.shape[d] < L.shape[d]

For example, for a tensor/layout pair
A = [x  x  x  x  x  x  x  x]
    [x  x  x  x  x  x  x  x]
L = [0  1  2  3 ]
    [4  5  6  7 ]
    [8  9  10 11]
    [12 13 14 15]

Then the data of A would be distributed as follow between the 16 CUDA threads:
L(A) = [ {0,8} , {1,9} , {2,10}, {3,11}, {0,8} , {1, 9} , {2, 10}, {3, 11},
         {4,12}, {5,13}, {6,14}, {7,15}, {4,12}, {5, 13}, {6, 14}, {7, 15} ]
  }];

That is, can someone step through an example calculation of an entry of $L(A)$?

[HydraQYH]

I want to know about it too.

[JensenFire]

d means the i-th dimension (is equal to 0 or 1). i_d means the specific coordinate/index in matrix A (row_index when d = 0, column_index when d=1). k_d means the specific coordinate/index in matrix L . We need to figure out all k_d that meet the layout function. In this case, 0<=i_0<=1, 0<=k_0<=3, 0<=i_1<=7, 0<=k_1<=3.

Take A(1,0) as an example: i_0 = 1, i_1 = 0, A.shape = [2,8], L.shape = [4,4] ,

since 0<=k_0<=3,

(i_0 + k_0 * A.shape[0]) % L.shape[0] = 1 or 3, and (i_1 + k_1 * A.shape[1]) % L.shape[1] = 0

Then the element A(1,0) can be accessed by the thread L(1,0)= 4, and L(3,0) = 12

I think we can close the discussion.