Broadcasting

Array API specification for broadcasting semantics.

Overview

Broadcasting refers to the automatic (implicit) expansion of array dimensions to be of equal sizes without copying array data for the purpose of making arrays with different shapes have compatible shapes for element-wise operations.

Broadcasting facilitates user ergonomics by encouraging users to avoid unnecessary copying of array data and can potentially enable more memory-efficient element-wise operations through vectorization, reduced memory consumption, and cache locality.

Algorithm

Given an element-wise operation involving two compatible arrays, an array having a singleton dimension (i.e., a dimension whose size is one) is broadcast (i.e., virtually repeated) across an array having a corresponding non-singleton dimension.

If two arrays are of unequal rank, the array having a lower rank is promoted to a higher rank by (virtually) prepending singleton dimensions until the number of dimensions matches that of the array having a higher rank.

The results of the element-wise operation must be stored in an array having a shape determined by the following algorithm.

  1. Let A and B both be arrays.

  2. Let shape1 be a tuple describing the shape of array A.

  3. Let shape2 be a tuple describing the shape of array B.

  4. Let N1 be the number of dimensions of array A (i.e., the result of len(shape1)).

  5. Let N2 be the number of dimensions of array B (i.e., the result of len(shape2)).

  6. Let N be the maximum value of N1 and N2 (i.e., the result of max(N1, N2)).

  7. Let shape be a temporary list of length N for storing the shape of the result array.

  8. Let i be N-1.

  9. Repeat, while i >= 0

    1. Let n1 be N1 - N + i.

    2. If n1 >= 0, let d1 be the size of dimension n1 for array A (i.e., the result of shape1[n1]); else, let d1 be 1.

    3. Let n2 be N2 - N + i.

    4. If n2 >= 0, let d2 be the size of dimension n2 for array B (i.e., the result of shape2[n2]); else, let d2 be 1.

    5. If d1 == 1, then set the ith element of shape to d2.

    6. Else, if d2 == 1, then

      • set the ith element of shape to d1.

    7. Else, if d1 == d2, then

      • set the ith element of shape to d1.

    8. Else, throw an exception.

    9. Set i to i-1.

  10. Let tuple(shape) be the shape of the result array.

Examples

The following examples demonstrate the application of the broadcasting algorithm for two compatible arrays.

 A      (4d array):  8 x 1 x 6 x 1
 B      (3d array):      7 x 1 x 5
---------------------------------
 Result (4d array):  8 x 7 x 6 x 5
 A      (2d array):  5 x 4
 B      (1d array):      1
 -------------------------
 Result (2d array):  5 x 4
 A      (2d array):  5 x 4
 B      (1d array):      4
 -------------------------
 Result (2d array):  5 x 4
 A      (3d array):  15 x 3 x 5
 B      (3d array):  15 x 1 x 5
 ------------------------------
 Result (3d array):  15 x 3 x 5
 A      (3d array):  15 x 3 x 5
 B      (2d array):       3 x 5
 ------------------------------
 Result (3d array):  15 x 3 x 5
 A      (3d array):  15 x 3 x 5
 B      (2d array):       3 x 1
 ------------------------------
 Result (3d array):  15 x 3 x 5

The following examples demonstrate array shapes which do not broadcast.

A      (1d array):  3
B      (1d array):  4           # dimension does not match

A      (2d array):      2 x 1
B      (3d array):  8 x 4 x 3   # second dimension does not match

A      (3d array):  15 x 3 x 5
B      (2d array):  15 x 3      # singleton dimensions can only be prepended, not appended

In-place Semantics

As implied by the broadcasting algorithm, in-place element-wise operations (including __setitem__) must not change the shape of the in-place array as a result of broadcasting. Such operations should only be supported in the case where the right-hand operand can broadcast to the shape of the left-hand operand, after any indexing operations are performed.

For example:

x = empty((2, 3, 4))
a = empty((1, 3, 4))

# This is OK. The shape of a, (1, 3, 4), can broadcast to the shape of x[...], (2, 3, 4)
x[...] = a

# This is not allowed. The shape of a, (1, 3, 4), can NOT broadcast to the shape of x[1, ...], (3, 4)
x[1, ...] = a