# Supporting Dynamic Dimensions
I recently opened an RFC proposing a new dynamic runtime (see #2810).
A missing piece of the puzzle for supporting fully dynamic models is typing,
and code generation for tensors with statically unknown shapes.
There are three critical steps to supporting dynamic tensors which I believe
are distinct tasks:
- Extending the type system
- Computing allocation sizes
- Code generation for dynamic shape
First we should consider a simple example which exhibits the hardest version of
this problem, how do we type such a function:
```
operator arange(%start: int32, %stop: int32, %step: int32) -> Tensor((Any,),
int32)
fn (%i: int32) {
let seq = arange(0, %i, 1);
sum(seq);
}
```
This example is challenging to type check due to `arange`'s output shape
depending on the value of `%i`. Currently we are able to statically determine
the
output shape if it is a function of the input's shape, but not if the output
shape is a function of the input *itself*.
*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 `arange`) we must generate code which computes the precise
size of the output buffer for the return value at execution time.
For example even when if we know `f: (Tensor<n>, Tensor<m>) -> Tensor<n + 1,
m>` we must
generate a function which can allocate space based on the runtime values of
`n`, `m`.
These cases are rare because most programs are closed program we know all
shapes statically, but once we introduce a dynamic shape, it is possible we
must defer arbitrary shape
computation until runtime.
# Extending the type system
The first proposed change is finish support for symbolic shapes.
For example `f` can be specialized to concrete shapes, and users
can pass around functions and operations which work over symbolic
shapes.
The second change is support for an `Any` shape.
`Any` represents a tensor dimension which is not statically known.
One possible design is to use a sub-shaping rule. This rule would be
similar to the traditional subtyping rule used in popular programming
languages.
For example in C++:
```
class T { ... };
class U : public T { ... };
```
We know `U <: T` (that is U is a subtype of T).
In this version of Relay this would mean `(1, 2, 3) <: (1, Any, 3)`.
Unfortunately this typing rule is not what we want. For example if
we have a function which expects a tensor of shape `(1, 2, 3)` we
can no longer call it with a tensor of type `(1, Any, 3)` we must
introduce explicit casting to properly check the runtime type.
Instead we propose borrowing ideas from gradual typing,
and introducing the notion of "gradual shaping". Any occurence
of a dynamic dimension is potentially unknown at compile time,
and when we demand a concrete dimension we must dynamically
check. This introduces the ability for runtime shape mismatches
but ensures that dynamically shaped and statically shaped code
can interact gracefully.
This is important, for example in many cases `Any` would pollute
the types of functions that are static, but their argument has
an unknown shape.
For example, we can optimize the below code under the assumption
that it will always have shape `(10, 10)`, and then perform
one runtime check of shape when calling f.
```
fn @f(%x : Tensor[(10, 10)]) { ... }
let x: Tensor(Any, Any) = ...;
@f(x)
```
# Computing allocation sizes
The second component is computing the allocation size required.
We must due this because TVM requires its output buffers to be preallocated.
When the output is dependent on input, or a symbolic relationship which has not
been specialized we need to generate a function at runtime which computes
the output buffer size.
```
Array<IndexExpr> ShapeFunc(const Array<Input>& inputs) {
...
}
```
We can then invoke this function to allocate the appropriate output storage,
during execution.
# Code generation for dynamic shape
The final challenge is performing code generation, this RFC only proposes
solving the
representation problem and generating naive TVM code in these cases which use
fully
symbolic shapes which are not known until runtime.
I believe there are a variety of different code-generation strategies which
each may suit different situations, and we implement a mechanism for specifying
the code generation policy in the face of dynamic shapes seperately from
shape functions, and typing of dynamic shapes.
Some of the possible code generation strategies:
- Generate placeholder code when symbolic relationship holds.
- Generate placeholder code and make use of shape functions.
- Implement bucketing style approach to code generation.
- Your ideas here!
--
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/dmlc/tvm/issues/3042
