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

ILP Extraction #32

Closed gussmith23 closed 4 years ago

gussmith23 commented 4 years ago

See #31 for more detail.

gussmith23 commented 4 years ago

Remy says: beware of extracting cycles! You can either rely on luck (which he does in SPORES), or explicitly stop cycles (which Tamago does).

gussmith23 commented 4 years ago

At Zach's suggestion, I'm trying out CPLEX using the rust library RPLEX. I had been using lp-modeler which was proving to be not so friendly.

gussmith23 commented 4 years ago

Installing CPLEX was kind of a pain. Got academic account, downloaded, then needed to set PATH and CPLEX_LIB to the folders inside the installed application containing the executable and static libraries.

gussmith23 commented 4 years ago

Alright, I think I'm at the point where CPLEX is doing extractions -- but it's finding cycles, I think? I'm not sure yet.

gussmith23 commented 4 years ago

Yes, it is. So I need to understand how Remy avoided cycles or come up with a way to avoid cycles myself.

gussmith23 commented 4 years ago

Sorry, this was actually Yichen who figured out how to do cycle-less ILP extraction. See here: https://github.com/uwplse/tamago/blob/master/extractor/extract.py

gussmith23 commented 4 years ago

I'm reading through this to understand it.

gussmith23 commented 4 years ago

Here's the constraint:

                    solver.Add(t[g[i]] - t[m] + A * (1 - x[i]) >= 1)

t is an array of topological ordering variables. Each class gets assigned a unique integer t from the range [0, num_classes-1]. i goes over all nodes (which are assigned int ids). t[g[i]] is the topological ordering var for eclass g[i] (g converts nodes to their eclass id). m iterates over all eclass children of node i. t[m] is the ordering var for the child m. A is some arbitrarily large value. x[i] is the indicator variable indicating whether node i is selected.

So this constraint basically ensures that an eclass's topological variable is greater than the topological variable of its direct child. The A * (1 - x[i]) basically says that, if this node is not selected, then the constraint is guaranteed to be satisfied (because A is sufficiently large, e.g. num_nodes).

gussmith23 commented 4 years ago

Closed by #64!