[cfe-dev] Matrix Support in Clang

[Florian Hahn via cfe-dev]

Hi,

> On Mar 18, 2020, at 20:38, Richard Smith <richard at metafoo.co.uk> wrote:
> 
> Thanks. I'm concerned about the inconsistency between * and the / and % operators, but other than that I think this proposal looks good.


Thank you very much for taking a look! I’ve responded inline. 

As next step I am planning on putting a patch up with the draft specification (that should make it easier to keep track of additional comments about formulation details) and get the clang operator patches ready.

> 
> Below is a proposal for matrix type element access & binary operators:
> 
> Matrix Type Element Access Operator
> 
> An expression of the form `postfix-expression [expression][expression]` where the postfix-expression is of matrix type is a matrix element access expression. expression shall not be a comma expression, and shall be a prvalue of unscoped enumeration or integral type. Given the expression E1[E2][E3], the result is an lvalue of the same type as the underlying element type of the matrix that refers to the value at E2 row and E3 column in the matrix. The expression E1 is sequenced before E2 and E3. The expressions E2 and E3 are unsequenced.
> 
> Note: We thought about providing an expression of the form  `postfix-expression [expression]` to access columns of a matrix. We think that such an expression would be problematic once both column and row major matrixes are supported: depending on the memory layout, either accessing columns or rows can be done efficiently, but not both. Instead, we propose to provide builtins to extract rows and columns from a matrix. This makes the operations more explicit.
> 
> Are you aware of the OpenMP array sections extension? (https://www.openmp.org/spec-html/5.0/openmpsu21.html <https://www.openmp.org/spec-html/5.0/openmpsu21.html>) Inspired by that, you could use something like E1[:][E2] and E1[E2][:] to form column and row vectors. Just a thought; I think using builtins for these is also fine.

I was not aware of that, thanks for pointing it out! 

It looks like it would provide a convenient syntax to use (and similar to what some other languages use) for extracting rows and columns. However I think given that the performance characteristics depend on the underlying layout I think it would be preferable to just provide builtins initially, assuming it would be OK to add better syntax later on.

> 
> Matrix Type Binary Operators
> 
> Each matrix type supports the following binary operators: +, -, *, /, and %. The * operator provides matrix multiplication, while +, -, /, and % are performed element-wise. There are also scalar versions of the operators, which take a matrix type and the underlying element type. The operation is applied to all elements of the matrix using the scalar value.
> 
> Supporting elementwise matrix1 / matrix2 seems likely to be confusing if * means matrix multiplication. Is this an important operation? (I'd imagine not, if you're willing to give up elementwise *.)
> I think the following would all be OK:
> 
> 1) +, -, and * all follow normal math conventions (* is matrix multiplication or matrix/vector or matrix/scalar multiplication, + and - are elementwise and require the same type on both sides); / and % are not provided
> 2) +, -, *, /, and % are elementwise; matrix multiplication is done a different way.
> 3) + and - are elementwise; *, /, and % are not provided and those operations are provided a different way
> 
> Of those, I think (1) is the cleanest approach, even though it's inconsistent with how we treat * for two operands of vector type. (2) would be consistent with our approach for vectors, and might be a nice approach if we can find a good alternative syntax for matrix multiplication (infix x is likely unambiguous, but would certainly be novel).
> 

Thanks for highlighting the potential for confusion. I think dropping support for / and % (option 1) would be best from a user perspective. The most important operations to cover by far are +, - and matrix multiplication. We mostly added elementwise / and % for completeness, but given the potential for confusion it seems better to exclude them.


> The operands of +, -, *, and / shall have either matrix type, arithmetic or unscoped enumeration type. The operands of % shall have either matrix type with an element type of integral type, integral type or unscoped enumeration type. At least one of the operands shall be of matrix type.
> 
> For BIN_OP in +, -, *, /, and %, given the expression M1 BIN_OP M2 where, for *, one of M1 or M2 is of arithmetic type:
> 
> * The usual arithmetic conversions are applied to M1 and M2. [ Note: if M1 or M2 are of arithmetic type, they are broadcast to matrices here. — end note ]
> 
> * The matrix types of M1 and M2 shall have the same number of rows and columns.
> 
> * The result is equivalent to Res in the following where col is the number of columns and row is the number of rows in the matrix type:
> 
> decltype(M1) Res;
> for (int C = 0; C < col; ++C)
>   for (int R = 0; R < row; ++R)
>     Res[R][C] = M1[R][C] BIN_OP M2[R][C];
> 
> 
> Given the expression M1 * M2 where M1 and M2 are of matrix type:
> 
>  * The usual arithmetic conversions are applied to M1 and M2
> 
>  * The type of M1 shall have the same number of columns as the type of M2 has rows.
> 
>  * The resulting type, MTy, is the result of applying the usual arithmetic conversions to M1 and M2, but with the same number of rows as M1’s matrix type and the same number of columns as M2’s matrix type.
> 
>  * The result is equivalent to Res in the following where col is the number of columns and row is the number of rows in MTy:
> 
> MTy Res;
> for (int C = 0; C < col; ++C) {
>   for (int R = 0; R < row; ++R) {
>     EltTy Elt = 0;
> 
> Is EltTy the matrix element type or the promoted matrix element type? (Based on what you wrote below, I assume the former, just checking...)

EltTy here refers to the element type of MTy (I’ll clarify the wording), hence it would be the result of the conversion/promotion based on the types of M1 and M2.

>  
>     for (int K = 0; K < inner; ++K) {
>       Elt += M1[R][K] * M2[K][C];
>   }
>   Res[R][C] = Elt;
> }
> 
> 
> All operations on matrix types match the behavior of the underlying element type with respect to signed overflows. 
> With respect to rounding errors, the the * operator preserves the behavior of the separate multiply and add operations by default. We propose to provide a Clang option to override this behavior and allow contraction of those operations (e.g. -ffp-contract=matrix).
> 
> OK, so in particular you guarantee to perform the additions in the order given by the above rewrite (assuming no -ffp-contract option)? (So, for example, you get the precision and rounding behavior of doing the adds in that order, and for a signed integer type, you get signed overflow if and only if the intermediate Elt value overflows even if the final Elt value for any (R,C) is back in range.) Seems OK, if that's consistent with your goals.

Yes the order of the dependent operations should be equivalent to the re-write, unless relaxed by the user, e.g. via options like -ffp-contract.

Cheers,
Florian


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20200319/3717d419/attachment-0001.html>