Generalize Sharing Lab Notebook

[calebmkim]

I just discussed with @sampsyo and here is the plan we currently have for the Generalize Sharing. Tagging @rachitnigam so that you are up to date/ can make suggestions.

The overall idea is that, right now, we have two types of sharing:

1. "state sharing", in which components have a state, and therefore require live range analysis. minimize-regs does this type of sharing.
2. sharing in which components do not have a state and therefore do not require live range analysis: their "live range" is completely contained by their group. resource-sharing does this type of sharing.
   Ultimately, we want to combine both of these types of sharing into 1 pass. We also want to be able to incorporate user-defined components into this sharing pass too, not just combinational primitives and registers.

Here are the steps we were thinking of:

1. Change minimize-regs pass so that, instead of looking for "std_regs" components, it looks for any component with a new "state sharing" attribute that we will come up with, and does live range analysis on those components. This be helpful if we see state-shareable user defined components, as we would now be able to attach the "state-sharing" attribute to it. This won't actually change the functionality of the minimize-regs pass.

2. Somehow combine the minimize-regs and resource-sharing pass.
   A good first step will be to just use a lot of the code of resource-sharing and intelligently copy+paste parts of it into the minimize-regs pass in order to get both passes combined into one.
   However, this is still a bit like two passes running in parallel rather than the passes being truly combined.
   An idea (possibly a bad one) would be to edit LiveRangeAnalysis to include non-state shareable components too. The live range analysis would work like it usually does, except at the end, I could just also insert all of the non-state-shareable components as "live" in the group they are contained in.

3. Finally, another important idea in the writeup was to be able to detect when user-defined components are shareable. We can think of ways of being able to detect this.

[rachitnigam]

Awesome, this looks like a great place to start! Take a look at the infer-static-timing pass to see how we compute if a cell is being "strucutrally invoked" by a group. minimize-regs uses a hard-coded version of this to detect when a register write is performed.

[calebmkim]

Friday 6/17:

I combined the minimize-regs and resource-sharing passes, and made a PR. There was some interesting stuff I had to think about continuous assignments (I wrote an issue on Github about it).

Right now, the tests are just the previous minimize-regs and resource-sharing tests, with both passes run on them. We can possibly think of other tests to run too.

I think future plans will probably have to do with a) making the code that I have already written better and b) (a bigger question) think about a compiler pass to conservatively determine when determine when components are (state and non-state) shareable, as mentioned in the original writeup.

[sampsyo]

Wow; that was fast!! Awesome work, @calebmkim!

[calebmkim]

Wed 6/22:
One big question that is still stumping me while coding the Domination stuff:
If we compare:
1) seq{ (if cond {A} else {B}) C}
2) seq{ par {A; B} C}
In 1), we want to take dominators(A) \intersect dominators(B), to get the dominators of C, whereas in 2) we want to take dominators(A) \union dominators(B) to get the dominators of C. However, A and B are both predecessors of C in both scenarios. The problem comes from the fact that in 1) we know that either A or B will be executed directly before C (but don't know which one), whereas in 2) we know that both A and B will be executed directly before C.

Here's an example I've been thinking about:

seq{ 
    ...
    par { if Cond: par {A; seq{M;N;O}}  else: par{C;D} 
          X; 
          Y; 
    }
    Z
}

Here, I was thinking something like this is correct:
dom(Z) = [(dom(A) U dom(O)) intersect (dom(C) U dom(D))] U dom(X) U dom(Y) U {Z}

edit: it seems like there will be a lot of overlap between the dominators of A,O, C, and D. Moreover, there will be a lot of overlap between the dominators of groups in the same par block. I am tempted to use this idea but can't seem to figure out how.

I could be way off w/ my thinking though. @rachitnigam or @sampsyo would one of you be able to talk about this in more detail in person, maybe tomorrow? (I'll be at 407 in person).

In the meantime, I will work on some other stuff having to do with the PR I made combining minimize_regs and resource_sharing.

[sampsyo]

We talked about this a bit synchronously, and here are a couple of outcomes.

@calebmkim is absolutely right about how to calculate dominators in a parallel control flow graph (PCFG). In this program:

seq {
    if ... { ... x } else { ... y };
    z;
}

where x indicates the control-flow point at the "end" of the "if" branch and y similarly indicates the end of the "else" branch, $\mathrm{dom}(x) = \mathrm{dom}(y) \cap \mathrm{dom}(z)$. That's the normal dominator equation.

In this program:

seq {
    par { { ... x }; { ... y } };
    z;
}

where again x and y indicate the "ends" of the par branches, now $\mathrm{dom}(x) = \mathrm{dom}(y) \cup \mathrm{dom}(z)$. Union instead of intersection.

All this is complicated, implementation-wise, by the fact that our structured control flow representation doesn't make getting the set of PCFG predecessors easy—and we don't even really have a well-defined notion of "predecessor" that generalizes a CFG to a PCFG! So @calebmkim and I discussed three routes to implementing a dominator calculation:

1. Don't invent any new data structures for the PCFG. Just write queries to ask about predecessors and successors on the current control representation, which are inevitably going to be sort of complicated, but once implemented don't have be touched again to build up arbitrary PCFG analyses. (This is the current plan.)
2. Invent a new explicit PCFG data structure that looks more like a proper graph. Write a function that builds this representation from a Calyx control program, then do the dominator analysis on that. (This is the fallback if option 1 gets too messy.)
3. Radically rethink Calyx's native control representation to make this more convenient to do directly. In-scope ideas for a radical rethinking include abandoning structured control flow in favor of unstructured PCFGs with branches and jumps and stuff. They also include a representation that allows directly referring to control statements (PCFG nodes) without index annotations or pointers—perhaps using integer offsets into packed arrays of PCFG nodes, for example. (This is not in scope for the current work—just food for thought in a future phase.)

[sampsyo]

Forked out a separate thread about a different IR refactoring idea that may make this kind of thing easier: #1051

[calebmkim]

Fri 6/24:
I've been working on the domination stuff.

I'm pretty sure it for most cases, but I still haven't convinced myself fully that my thing is correct. Mainly it has to do with how I handle while loops; specifically how I calculate the dominators of a while loop guard.

Basically, I'm going to argue that I can ignore the last node in the body of a while loop when taking the predecessors of the while guard, since the dominators of the last node in the while body are either a) in the while loop, in which case we know it won't be a dominator of the while guard, or b) are outside the while loop, in which case we know they dominate at least one of the other predecessors of the while guard.

I'll continue working on this domination pass, and hopefully get it working.
I'll also need to add some test cases for the cell_share (which combines minimize_regs and resource_sharing), mainly testing the multipliers/other things that I gave the state_share label.

[sampsyo]

Incredibly cool. I think calculating dominators for Calyx control programs could be very useful in other contexts, so having a robust self-contained way to do this could be quite rad.

[calebmkim]

Wed 6/29:
(Sorry I forgot last Monday)

Tuesday pushed the changes for cell_share (which combined minimize_regs and resource_sharing).
Now all I'm working on writing the actual "infer-share" pass. This pass will actually attach the "state-share" attribute to user-defined components (conservatively). I have a good "rough draft" of it, but still need to think about some of the details.

One really specific thing that I was going to ask the other day about dominator_map is this (may be better to ask in person): the following code is from when I am trying to update the map and come across a Seq:

ir::Control::Seq(ir::Seq { stmts, .. }) => {
                //Should find a better way of doing this. This is ugly.
                let mut cur_pred = HashSet::new();
                let mut first = true;
                for stmt in stmts {
                    let id = Self::get_id(stmt, true);
                    if first {
                        Self::update_map(main_c, id, pred, d_map);
                        first = false;
                    } else {
                        Self::update_map(main_c, id, &cur_pred, d_map);
                    }
                    let end_id = Self::get_id(stmt, false);
                    cur_pred = match d_map.pred_map.get(&end_id) {
                        Some(hs) => hs.clone(),
                        None => unreachable!(
                            "pred map does not have value for control stmt {}",
                            end_id
                        ),
                    };
                }
            }

I still haven't come up with a good way to make it cleaner. I think trying to get Self::update_map() to take in a HashSet instead of &HashSet would work, it's just I think there will be more clones...

Nonetheless in the coming days my focus will be on getting the infer-share pass to work, which is coming along pretty well.

[sampsyo]

This is pretty tricky!! This idea probably doesn't work, but could you give up on the cur_pred thing and instead just keep around the last end_id? Something like this:

if first {
    Self::update_map(main_c, id, pred, d_map);
    first = false;
} else {
    Self::update_map(main_c, id, d_map.pred_map.get_mut(last_end_id).unwrap(), d_map);
}
last_end_id = Self::get_id(stmt, false);

…with last_end_id declared mut outside the loop. This could cause some lifetime wildness, however??

[calebmkim]

Friday 6/1

While working on the infer-share pass, I discovered that since LiveRangeAnalysis did not use invoke statements as nodes, this can lead to problems when we use invoke on state shareable components. The solution we came up with is to just add invokes as nodes in the LiveRangeAnalysis. I also have gotten the infer-share stuff to work (I think), but it still won't pass the compiler tests until I get the invoke stuff (mentioned above) working.

Another concerning problem with the infer share stuff is this: the Dahlia likes to compile groups like this, where bin_read0_0 is a register.

group let0<"static"=4> {
      bin_read0_0.in = mult_pipe0.out;
      bin_read0_0.write_en = mult_pipe0.done;
      let0[done] = bin_read0_0.done;
      mult_pipe0.left = a;
      mult_pipe0.right = b;
      mult_pipe0.go = !mult_pipe0.done ? 1'd1;
    }
group let1<"static"=1> {
      ...
      add0.left = bin_read0_0.out;
      ...
    }
...
control {
    seq {
      let0;
      let1;
    }
}

Unfortunately, the way my pass is currently written, since mult_pipe0 is being both read and written to in let0, it will mark this component as "not shareable", since it can't tell whether or not the read or write of mult_pipe0 is occuring first. 2 ideas.

• This is a clear place where something like Implement Copy Propagation  #1048 would be helpful, since the write to bin_read0_0 is pointless-- we could have just written the output of mult_pipe0` directly into add0.

• I could also write a very specific modification to the current pass that will specifically look for situations like this and be able to tell, within a group, when a stateful component is being written to before being read.

[calebmkim]

Wed 7/6
I've been working on a pass to split one big group into a seq of smaller groups. I'm trying to start with a pass that is quite conservative with when it applies the transformation.
Some things to think about for the future are this (discussed with @rachitnigam): make the group2invoke pass more aggressive so that it mirrors variable_detection. (My current pass will also help to create more opportunities to apply group2invoke).

[sampsyo]

Sounds really great. A more general group2invoke could clarify things for us.

[calebmkim]

I've been working on the group_to_seq pass, turning a large group into a seq of smaller groups.

One thing that came up w/ @rachitnigam was when we have a group like

group let0<"static"=4> {
      bin_read0_0.in = mult_pipe0.out;
      bin_read0_0.write_en = mult_pipe0.done;
      let0[done] = bin_read0_0.done;
      mult_pipe0.left = A_read0_0.out;
      mult_pipe0.right = B_read0_0.out;
      mult_pipe0.go = !mult_pipe0.done ? 1'd1;
}

one of the groups is

group begin_split{
      mult_pipe0.left = A_read0_0.out;
      mult_pipe0.right = B_read0_0.out;
      mult_pipe0.go = !mult_pipe0.done ? 1'd1;
      begin_split[done] = mult_pipe0.done; 
}

Group2Invoke isn't able to pick turn this into an invoke bc of the mult_pipe0.go = !mult_pipe0.done ? 1'd1 statement. I'm thinking of altering the pass so that I can detect this very specific situation to just turn it into mult_pipe0.go = 1'd1; we can discuss if you think this is a good idea.

I've also been starting to work on generalizing the group2invoke pass-- it's not ready to. make a PR but I've made some progress.

I also had a question that I outlined in #1086. It's a very code/rust specific question.

[rachitnigam]

Yeah, I think the very specific heuristic for this kind of group is probably fine. In general, the heuristic can say something like if a group's assignment is guarded by !group[done], we can just replace it to 1'd1. I think this is true but we should convince ourselves of that first

[calebmkim]

Monday 7/18

(Sorry I haven't been keeping up w/ this)

Got the infer sharing pass merged and working on getting group2seq and group2invoke merged as well. Not too many questions on it.

Future plans:

1. Alter canonicalize to account for this case: group[done] = a.done ? 1'd1 -> group[done] = a.done. We think you can do this since there's only one write to group's done port. (Will write up issue on it)
2. Start testing sharing on frontends. Make sure that my current changes allow us to share Dahlia multipliers. Also (bigger picture) test how sharing does on TVM generated Calyx files. Sharing will likely take too long so I also need to work on ways to speed it up.

[calebmkim]

Wed 7/20

Worked on making group2seq a little bit "neater" so that it can be merged sooner.

Now, working on trying to make sharing_components faster. I've started to have some success in making the conflict calculation faster (i.e. knowing register1 and register2 have overlapping live ranges for example), and I have some more ideas that I'll try to implement sooner.

I mentioned conflict calculation, since that's one of the two main things that makes the CellShare slow. The other is calculating the LiveRangeAnalysis. I can do some more investigating about what exactly in LiveRangeAnalysis makes it take so long.

Finally, I'm not sure if this is true, but the performance of CellShare may be hurt by the fact that for every time we get the live range of a group/invoke, we have to filter out all the cont_ref_cells. I can try to find a way to avoid this and see if performacne improves.

[calebmkim]

Fri 7/22

Worked on significantly speeding up the CellShare pass. I have just come up with an even faster version of CellShare that (I think?) is correct, but I'll clean the code a bit before I push.

A couple more thoughts:

I also think we can make cell_share.rs and sharing_components.rs one file.

'm beginning to think that I might need to speed up LiveRangeAnalysis, which I haven't done yet. One thought I had (and this could actually be a bad idea that would actually make the pass way slower) was maybe organize live ranges by cell type: so instead of having just a single HashSet with all the names of the live cells, have a HashMap that maps cell types to live cell names. We are going to need to organize by CellType at some point when we determine sharing, so I was thinking why not just do it as early as possible? Again, this could be a terrible idea, just writing down my thoughts.

I can also work on finishing up group2invoke.

[rachitnigam]

I think the idea of sorting by cell type is pretty sane!

[sampsyo]

Agreed!!

[calebmkim]

Monday 7/25
I made LiveRangeAnalysis be in terms of HashMaps (from cell types to sets of cell names) rather than a HashSet, but it didn't really seem to improve the timing all that much (it didn't really hurt timing either though). It's difficult to tell exactly, but I think the BitOr and BitSub functions might be the reason why this change is not yielding faster results. I also created a new PR that does speed up Sharing, although not by that much.
I'm not exactly sure what to work on next. I could try to improve sharing even more perhaps-- I still think the LiveRangeAnalysis idea has some potential if I improve the way it's implemented, even if it's not yielding results right now. I can also work on finishing group2invoke up.

[calebmkim]

7/27
I've made CellSharing faster by changing the way we query about live ranges.
Instead of asking "which cells are live at group g?" we now ask "for cell c, in which groups is c live?"
This has helped make the pass a lot faster?

One problem that I've been running into is this: say we have:

seq{
  par{
      seq{A;B;C}
      seq{D;E;F}
      seq{G;H;I}
      seq{J;K;L}
      register r1 live at J,K, and L
  } 
  par{
      seq{M;N;O}
      register r2 live at M,N, and O
  }
}

Right now when we determine whether or not r1 and r2 are conflicting, here is the process we go through:

1. See if their live ranges overlap. In this case, no.
2. Take all of the groups live at r1-- in this case, J,K, and L. First we look at J-- then we take all the groups that run in parallel to J-- in this case A-L. We see if A-L conflicts at all with the registers live at r2-- in this case M,N, and O. If not, we look at K. Then we take all the groups that run in parallel to J-- in this case A-L. We see if A-L conflicts with all the registers live at r2-- in this case M,N, and O. But we've already done this exact same comparison, so we are unfortunately wasting time.
   I talked synchronously w/ @sampsyo and we have an idea to try to combat this problem.

[rachitnigam]

Super exciting work!! It's crazy how fast it is already but we can definitely keep pushing!

[sampsyo]

Indeed; pretty rad! It would be interesting to see how far we've come in terms of optimization time after all this is over, from the first version to the last…

[calebmkim]

Update 8/2
I now have a PR for the "make Sharing faster" stuff. One unfortunate thing is that group2invoke creates some combinational groups, which are then turned into just regular groups after remove-comb-groups is run (which is needed for certain passes), which increases the number of groups in a given program. This means that cell-share now takes longer bc the program simply has more groups. I can try to make a separate PR in which cell-share handles comb groups and in which I try to rearrange the order of passes so that remove-comb-groups is run after cell-share.

I've also been thinking about bounded sharing (i.e. only sharing a given resource k times at most). I've been trying to think of non-greedy ways to implement a coloring algorithm that handles this.

[calebmkim]

8/4 Update
I got the making sharing faster stuff merged.

Now I'm focused on bounded sharing. We decided to go w/ the greedy algorithm for now (although that could change). I've wrote a (poorly written) python script that can collect the bounded-sharing information. It works on smaller files but I've been getting an error message on lenet.

[calebmkim]

8/8 Update

I'm a bit stuck on the lenet stuff. I've gotten it partially working but for some reason it only gives the resource estimates for the synthesis files and not the implementation files. My best shot at this point is probably to change the hardware we are targeting, so I'll see what leads I can get on that end tomorrow. However, I'm a bit worried (although this is just a feeling, not sure about it) that even if we just use the original lenet file targeting hardware that can handle bigger memory, that it still won't work for the implementation files.

In the meantime, I've edited LiveRangeAnalysis to include comb groups, which allows us to reorder the default passes.

I've also decided to push greedy bounded sharing. Right now, the bounds are an extra argument you can pass to cell-share. If you don't pass them, then you currently get the default values, which are 4 (for comb components), 6 (for registers), and 18 (for everything else). If/when I get lenet working and get results on what is the optimal sharing bounds are, we can set the default values to be less arbitrary.