Add samples of shape broadcasting

[huningxin]

This was proposed by @wacky6 in Chromium CL review of prelu. Thanks Jiewei!

Some WebNN ops support broadcasting, including Element-wise binary operations and prelu.

Although WebNN spec refers to General Broadcasting Rules of NumPy, it would be helpful to add some samples of the acceptable combinations in the informative section.

ONNX does a great job by Broadcasting in ONNX doc.

[a-sully]

I discovered this issue after seeing @inexorabletash's comment here https://github.com/webmachinelearning/webnn/pull/523/files#r1466950307. In the spirit of #462, it would be nice to explicitly define shape broadcasting, rather than having it "implementation defined" as it is currently specced

(apologies if this is a naive question, but) is there anything preventing us from specifying broadcasting?

A spec is better than examples, though both would be best :) (ideally with the examples in the form of web platform tests!)

[a-sully]

Looking into this a bit more, this was discussed a bit in #324. That issue is mostly focused on which input layouts should be supported ("NHWC", "NCHW", both, etc). This is tangential to the question of how broadcasting should work on the various layouts.

From #324 (comment) by @wacky6

Layout support comes up in MLOperand implementation that allows data shape broadcasting. https://chromium-review.googlesource.com/c/chromium/src/+/4396686/comment/f02acaeb_3c2795f2/

Supporting both channel-first and channel-last layout will complicate spec steps and implementation because the current numpy broadcast rule implies right-most first broadcast.

Example: caller wants to apply a per-channel multiplication.

1. lhs is nchw{1,3,4,4}; caller provides rhs {3}. This will fail under the current broadcast rule. The caller will need to broadcast rhs itself.
2. lhs is nhwc{1,4,4,3}; caller provides rhs {3}. Works as intended.

My strong preference is that WebNN specifies that shape broadcasting always starts with the trailing dimension first (as per https://numpy.org/doc/stable/user/basics.broadcasting.html#general-broadcasting-rules), regardless of the layout. WebNN would be prohibited from doing anything clever (which may rely on implementation-specific details).

In the example above, this means developers will need to reshape {3} to {3, 1, 1} if they're using NCHW layout and want to multiply the channel. Fortunately this should be cheap and, as @wchao1115 eloquently put it in #324 (comment), "easily collapsible by an intelligent backend later on"

[inexorabletash]

After reviewing the CL that inspired this, the suggestion is to add test cases:

Might be worth doing a followup: adding a test suite for WebNN broadcast function. This is worth doing if say the spec formalizes a way to broadcast. Fine to wait until WG concludes how broadcast should be done.

We've formalized the way to broadcast - so let's add WPTs for unidirectional and bidirectional broadcasting.

[inexorabletash]

web-platform-tests/wpt@3a71f44 added tests:

• the element-wise binary ops (add, sub, mul, div, max, min, pow) use validateTwoInputsBroadcastable() helper which ensures errors are thrown if the inputs are not broadcastable.
• I see specific tests relying on broadcasting for:
  • element-wise binary ops: add, sub, mul, div, max, min, pow
  • element-wise logical ops: equal, greater, greaterOrEqual, lesser, lesserOrEqual
  • gemm, matmil, prelu, where
  • expand

So we may be missing cases where broadcasting is expected to fail, e.g. I don't see tests for the expand or the logical ops that expect failure.

[inexorabletash]

We can still add examples of broadcasting to the spec, though. I just think the test coverage was the original intention.

[inexorabletash]

I put https://chromium-review.googlesource.com/c/chromium/src/+/5742615 up which adds alidation broadcast coverage for the logical operators to WPT.

Expand and the rest seem to have these cases, so after that lands I think we can close this?

Edit to add: "it would be helpful to add some samples of the acceptable combinations in the informative section" still stands.

[inexorabletash]

Okay, that's in. Do we think that WPT is sufficient, or should we add some non-normative text? Here's something I sketched up. @huningxin - can you take a look?

...

The term broadcasting in this specification describes how WebNN treats tensors with different shapes during graph construction and computation. It is heavily influenced by NumPy and generally follows the [numpy-broadcasting-rule]. Loosely speaking, it allows an operation on a smaller tensor to be "broadcast" across the shape of a larger tensor, so that the same data can be applied repeatedly without making copies.

The simplest example is the application of a scalar constant to an N-dimension tensor with element-wise binary operations such as add() or mul(). Rather than needing to allocate and populate a matching N-dimensional tensor containing multiple copies of the scalar constant, these element-wise operations allow the scalar constant to be used directly, and broadcast the scalar value across the N-dimensional tensor.

The shapes of the tensors must be compatible. A tensor is unidirectionally broadcastable to another tensor if the first tensor can be "stretched" by repeating the first tensor along an axis with size 1 or repeating across new dimensions, starting from the last (rightmost) dimension. For example, a [4] tensor can be broadcast to a [5,4] tensor by repeating it 5 times. A [1] tensor can be broadcast to a [5,4] tensor by repeating it 4 times on the last dimension and 5 times on the preceding dimension. Unidirectional broadcasting is important for operations such as expand() where the target tensor shape is explicitly given.

Two tensors are bidirectionally broadcastable if they can be mutually "stretched" (repeated) across their various dimensions, starting from the last dimension. For example, a [5,1] tensor can be bidirectionally broadcast with a [1,6] tensor by repeating the first tensor 6 times in the last dimension and the second tensor 5 times in preceding dimension. The result of the operation will be a [5,6] operation. Bidirectional broadcasting is convenient for element-wise operations.

Some operations allow broadcasting with special semantics. For example, matmul() treats the last two dimensions of the input tensors as the rows and columns of the matrices, and the number of columns in the first matrix must be equal to the number of rows in the second matrix. Any additional dimensions are treated as a stack of matrices to multiply, and are bidirectionally broadcast.