Join GitHub today
GitHub is home to over 40 million developers working together to host and review code, manage projects, and build software together.Sign up
[RFC][Relay] Dynamic Dimensions #3042
Supporting Dynamic Dimensions
I recently opened an RFC proposing a new dynamic runtime (see #2810).
There are three critical steps to supporting dynamic tensors which I believe are distinct tasks:
First we should consider a simple example which exhibits the hardest version of this problem, how do we type such a function:
This example is challenging to type check due to
*Note: we could use full dependent typing here, but this introduces new challenges. *
In the cases where the output shape is symbolic function of the input, or fully dynamic (such as
For example even when if we know
Extending the type system
The first proposed change is finish support for symbolic shapes.
The second change is support for an
One possible design is to use a sub-shaping rule. This rule would be
For example in C++:
In this version of Relay this would mean
Unfortunately this typing rule is not what we want. For example if
Instead we propose borrowing ideas from gradual typing,
This is important, for example in many cases
For example, we can optimize the below code under the assumption
Computing allocation sizes
The second component is computing the allocation size required.
We can then invoke this function to allocate the appropriate output storage,
Code generation for dynamic shape
The final challenge is performing code generation, this RFC only proposes solving the
I believe there are a variety of different code-generation strategies which
Some of the possible code generation strategies:
This is a great progress towards deploying real-world NLP models. Thanks Jared for proposing this!
As far as I could tell, however, in the long term, we probably need more support for more general dependent typing for more data types. I am afraid that we will have to consider composite types in the very end.
referenced this issue
May 21, 2019
@ajtulloch @icemelon9 and I have been quietly hacking on a prototype the last few months but have been busy with other things (such as VM
One thing would be to help validate and criticize the design from the standpoint of a user who is deploying models day to day. We are also generally interested in thoughts about code generation strategies.
One change that we have decided on is adding the ability to type hint when generating IR.
When generating IR from frameworks we don't necessarily have all type information up front.
For example imagine a loop variable which starts as a (1, 1) matrix, but will grow by one in the first dimension on every loop. Eventually the matrix will have the shape (n, 1) where
Our current solution is to generate IR with unknown types, plus a type hint, allowing inference to eventually solve the most general type.
For example if we were to generate IR for a loop we can do:
These could later be used to inform code generation, but ensure that we get the correct typing.
I will also be at the Diff. Prog. Conf hosted by FB if you are around to talk more in person.