Motivation: DaphneDSL offers a couple of source operations, which take only scalars as arguments, but produce a matrix as their result. Examples include: fill(), rand(), and seq(). Subsequent arithmetic operations on this result could be pushed before the source operation, in many cases. That way, the program execution could be improved by avoiding unnecessary large intermediate results, thereby reducing the number processor instructions and the memory footprint.
For instance, fill(a, 10^6, 1) + b creates a (1Mx1) column matrix where all values are the scalar a and performs an addition with the scalar b, thereby creating another matrix of the same size. The memory footprint is 2 x 1M x 8 bytes (=16 MB)(assuming 64-bit floating-point numbers, and no update-in-place optimizations are done). Alternatively, one could calculate fill(a + b, 10^6, 1), where the addition happens on scalars and only one matrix is created, i.e., the footprint is halved (8 MB).
Some further examples:
(Lower case letters indicate scalars, upper case letters indicate matrices.)
fill(a, h, w) + b -> fill(a + b, h, w)
fill(a, h, w) * b -> fill(a * b, h, w)
rand(h, w, a, b, 1, -1) + c -> rand(h, w, a + c, b + c, 1, -1)
seq(s, e, i) + x -> seq(s + x, e + x, i)
seq(s, e, i) * x -> seq(s * x, e * x, i * x)
...
Task:
Get familiar with DaphneDSL operations (operators and built-in functions) in the user documentation.
The above cases are really just examples. Think of which arithmetic operations (elementwise unary/binary, some are operator symbols in DaphneDSL, some are built-in functions) can be pushed before which source operations with which adaptations to the source operation's arguments). This can be done with pen and paper first.
Implement these simplification rewrites as canonicalizations on DaphneIR (implementation in C++ using the MLIR framework). At the time of this writing, all existing canonicalizations reside in src/ir/daphneir/DaphneDialect.cpp.
Add script-level test cases and potentially test cases checking the IR (up to discussion).
Possible task extensions for teams:
Look broadly beyond just arithmetic operations, what other operations could be pushed down? Remember, the goal is to avoid matrix intermediates, and do operations on individual scalars instead. A few ideas:
reverse(seq(s, e, i)) -> seq(e, s, -i)
t(fill(a, h, w)) -> fill(a, w, h)
X + fill(a, h, w) -> X + a (assuming compatible shapes)
Motivation: DaphneDSL offers a couple of source operations, which take only scalars as arguments, but produce a matrix as their result. Examples include:
fill(),rand(), andseq(). Subsequent arithmetic operations on this result could be pushed before the source operation, in many cases. That way, the program execution could be improved by avoiding unnecessary large intermediate results, thereby reducing the number processor instructions and the memory footprint.For instance,
fill(a, 10^6, 1) + bcreates a (1Mx1) column matrix where all values are the scalaraand performs an addition with the scalarb, thereby creating another matrix of the same size. The memory footprint is 2 x 1M x 8 bytes (=16 MB)(assuming 64-bit floating-point numbers, and no update-in-place optimizations are done). Alternatively, one could calculatefill(a + b, 10^6, 1), where the addition happens on scalars and only one matrix is created, i.e., the footprint is halved (8 MB).Some further examples: (Lower case letters indicate scalars, upper case letters indicate matrices.)
fill(a, h, w) + b->fill(a + b, h, w)fill(a, h, w) * b->fill(a * b, h, w)rand(h, w, a, b, 1, -1) + c->rand(h, w, a + c, b + c, 1, -1)seq(s, e, i) + x->seq(s + x, e + x, i)seq(s, e, i) * x->seq(s * x, e * x, i * x)Task:
src/ir/daphneir/DaphneDialect.cpp.Possible task extensions for teams:
reverse(seq(s, e, i))->seq(e, s, -i)t(fill(a, h, w))->fill(a, w, h)X + fill(a, h, w)->X + a(assuming compatible shapes)seq(s1, e1, i1) + seq(s2, e2, i2)->seq(s1 + s2, e1 + e2, i1 + i2)(assuming compatible shapes)