[RFC][Relay] Program Matching for Relay Pt 1: A pattern language

jwfromm · February 28, 2020, 9:15pm

I really like the regex style matching syntax! I think it’d be helpful to have an example showing how a matched subgraph could be used. For example, after matching a diamond in graph, how we would annotate that subgraph to run on a different device than the rest of the graph? Is it worth considering the post-match API in this RFC or would that be part of future work?

manupa-arm · February 28, 2020, 9:33pm

Sounds great! When you say “graph rewrites”, are you proposing a interface to define a “graph grammer” ?

tqchen · February 28, 2020, 9:38pm

I was think similar to to regex rewriting, e.g.

"def\(\s*\"(?P<fn_name>[a-z0-9|_]+)" -> "<fn_name>xyz"

Will allow us to represent the rewrite that extracts the function name after def and append xyz to it. We can brainstorm possible rewrites that we might do for graphs(the concrete DAG->DAG pattern is fine and we know how to do that, just wonder if there is a need for wildcard like patterns like the above)

lhutton1 · February 28, 2020, 9:36pm

I can see this being a very useful feature, it looks great! One question I had was will we also be able to specify certain properties for an op to match against? E.g. for a convolution op: data layout = NHWC, groups = 1

manupa-arm · February 28, 2020, 10:00pm

I guess there is a need for optional ops – as @mbaret pointed out (that could be handled by “?” pattern, I guess ) and a list of ops like [abc] in regex. Not sure about a full wildcard though.

manupa-arm · February 28, 2020, 10:19pm

In the multi output scenario, we need to make sure that any output is not an ancestor to any input of the same pattern through connections that are outside the pattern. Right? If the goal is targeting offloading to backends OR at least provide an interface to specify to avoid such matches ? (as discussed in [Relay] Improved graph partitioning algorithm)

tqchen · February 28, 2020, 10:43pm

What you are describing belongs to A3 – the algorithm e.g. graph partition need to ensure that the there is no overlapping patterns in the partitioned graph.

Of course, it would be interesting to ask whether the above line itself is a pattern(for a bigger graph) which could be overkill for now(then it comes back to A0)

masahi · March 1, 2020, 10:44am

Torch also has a mechanism for subgraph matching and rewrite. In their case, the pattern and replacement are both textual representation of their IR.

For example, their pass for automatically transforming fp32 graphs to quantized ones are based on pat matching. Here is an example of a pattern and its replacement.

github.com

pytorch/pytorch/blob/bbff06ee96f4ce7323f5bb1043b802833362e075/torch/csrc/jit/passes/quantization_patterns.h#L11-L23


  std::string conv2d = R"(
graph(%a_quant, %packed_params, %r_scale, %r_zero_point, %r_dtype, %stride, %padding, %dilation, %groups):
        %a_dequant = aten::dequantize(%a_quant)
        %w_quant : Tensor, %b : Tensor? = quantized::conv2d_unpack(%packed_params)
        %w_dequant = aten::dequantize(%w_quant)
        %r = aten::conv2d(%a_dequant, %w_dequant, %b, %stride, %padding, %dilation, %groups)
        %r_quant = aten::quantize_per_tensor(%r, %r_scale, %r_zero_point, %r_dtype)
        return (%r_quant) )";


  std::string quantized_conv2d = R"(
graph(%a_quant, %packed_params, %r_scale, %r_zero_point, %r_dtype, %stride, %padding, %dilation, %groups):
        %r_quant = quantized::conv2d(%a_quant, %packed_params, %stride, %padding, %dilation, %groups, %r_scale, %r_zero_point)
        return (%r_quant) )";

tqchen · March 1, 2020, 4:51pm

It is indeed interesting to see if we can have a textual repr for pattern that is related to IR. I wonder though how can we go beyond the concrete DAG->DAG pattern to wildcard related, as discussed in the current proposal

jonso · March 1, 2020, 7:53pm

+1, wildcards and generalizations are really important in making this a flexible system.

yzhliu · March 2, 2020, 12:21am

I wonder how practical can the infrastructure be shared with low-level tir?

tqchen · March 10, 2020, 8:36pm

Great discussions so far, it would be great if we can comment on API choices. So far I see the need to have ? pattern.

@jroesch can you incorporate the feedback and give a couple of API design choices, then we can try to conclude and move to implementation(by sending a formal RFC to github)

forrestm-quic · March 10, 2020, 10:20pm

Seconding @yzhliu’s question on sharing infrastructure and code with the low level TIR, especially w.r.t. python bindings. For the Hexagon backend, we want to do more work in the TIR but a lack of good pattern matching utilities in python is hindering our efforts there. A unified pattern matcher for relay and TIR would be a big +1 for us.

tqchen · March 11, 2020, 12:35am

To followup discussions on TIR pattern matching. it would be great to get a sense of potential use-cases

If the task is expression level pattern matching, we currently have a rewriting util that can be used now: https://github.com/apache/incubator-tvm/blob/master/src/arith/pattern_match.h which is used in the arithmetic simplifier
If the match involves match over a multi-level loop(e.g. tensorization) we will need specialized design mechanisms

jonso · April 1, 2020, 5:21pm

@jroesch, is there any update on this feature? I’m really excited to try it out

jroesch · April 3, 2020, 5:42am

Sorry for the lack of updates been super oversubscribed lately (in the process of finishing my thesis) plus lots of stuff at OctoML. @mbrookhart is a hero and has a production quality version he has been working on in C++. I think he is getting really close to shipping a first version of the matcher, and is working on a rewriter based on this. I will talk with him at (virtual)work tomorrow and try and craft an update.

mbrookhart · April 3, 2020, 3:15pm

Hi @jonso,

You can take a look at the matcher here: https://github.com/apache/incubator-tvm/pull/5231

Need to add a little more documentation, and I’m working on a second stage pattern-based rewriter now.

jonso · April 3, 2020, 8:21pm

Awesome! Thanks so much for the update. @jroesch sorry to bug you while you’re working on your thesis, I’ll bug @mbrookhart if I have any questions

mbrookhart · April 14, 2020, 8:19pm

I think the PR is ready for review as V1 of the pattern language, it contains some documentation, testing, and the language itself, the matcher, and pattern-based expression rewriting.

V2 will include graph partitioning and verification to better support bring your own code gen, starting in on those passes now.

Any and all comments are appreciated!

masahi · April 14, 2020, 10:11pm

I’m very interested in this. Using composite, I have to generate many slightly different patterns (with_bias, with_pad etc), leading to combinatorial explosion. Optional matching can clean this up a lot.

Maybe this has been discussed before, but if we integrate full blown pattern matching into BYOC, what is the future of composite? Do we still have a use case for it?