search

gussmith23 / glenside

A pure, low-level tensor program representation enabling tensor program optimization via program rewriting. See the web demo at https://gussmith23.github.io/glenside-web-demo/
71 stars 10 forks source link

Simplifying rewrites for flatten/reshape #98

Open gussmith23 opened 3 years ago

gussmith23 commented 3 years ago

The intention here was to add simplifying rewrites so that flatten/unflatten wouldn't run rampant. If we could add more equivalences (i.e. saying that stacking flattens is equivalent to just one flatten, or that flatten-then-reshape is equal to just reshape) then we can compress the egraph down. However, we haven't seemed to improve much:

Without rewrites:

Runner report
=============
  Stop reason: TimeLimit(60.958206912)
  Iterations: 41
  Egraph size: 278240 nodes, 262325 classes, 278269 memo
  Rebuilds: 10977, 267.73 per iter
  Total time: 60.27503701900001
    Search:  (0.09) 5.527444559
    Apply:   (0.15) 8.843468115999999
    Rebuild: (0.76) 45.904067723999994

With rewrites:

Runner report
=============
  Stop reason: TimeLimit(61.440639892)
  Iterations: 40
  Egraph size: 280628 nodes, 260861 classes, 280782 memo
  Rebuilds: 14521, 363.02 per iter
  Total time: 60.788746081999996
    Search:  (0.09) 5.595972895000001
    Apply:   (0.14) 8.638404146000001

It seems like the number of classes goes down somewhat, but overall performance degrades (we run fewer iterations, have more rebuilding). I'm not quite sure how to interpret this -- is it just that these rewrites aren't actually useful, and are just hurting us?

gussmith23 commented 3 years ago

I think I have the right intention (trying to shrink the number of classes by adding simplifying rewrites) but perhaps I'm not focusing on the right target. The thing that (probably) blows things up the most is the slice/concat rewrite, so we should target that.

gussmith23 commented 3 years ago

I'm not going to merge this for now, as it doesn't seem to be doing anything good. I should take a look at this again after I try simplifying concatenates.