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.
3 Likes
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.
1 Like
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 
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!
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?
As far as I can tell, we’d still need MergeComposite. The main difference would be that we could replace the custom pattern-matching solution with this generic and more powerful pattern-matching. However, the creation of the composite functions will need to remain.
1 Like
Hi All,
Thanks for all of the comments. The PR is complete, I’ve added the Partitioner we were planning on doing. Since some of the API’s (especially around the dominator pattern) are somewhat novel, I’d appreciate anyone who can take a few minutes to look over the PR.
Matthew
In particular:
- The Dominator pattern adds some fuzziness to the pattern matching that is non-standard for graph pattern matchers. It provides a way to find something like a convolution op, who’s output is then used by several elementwise ops, that are then combined together. This kind of feature is often found in the current operator fusor and device code like VTA, we’re thinking of using the pattern to clean up and simplify those passes. A review of the API and the example unit tests would be appreciated.
- The pattern partitioning function finds matches for the patttern and replaces those subgraphs with function calls to identical subgraphs. This gives us a way of isolating patterns that can later be offloaded to a fusion or a bring your own codegen pass.
Another point bring out is that this pattern matcher, as it currently stands, is only capable of matching patterns with a single output. Matching something like an LSTM cell is currently out of scope. Is anyone aware of a case where mutli-output pattern matching is needed in the near term?
Thanks, Matthew