search

calyxir / calyx

Intermediate Language (IL) for Hardware Accelerator Generators
https://calyxir.org
MIT License
496 stars 50 forks source link

Implement PIFO trees using binary-heap PIFOs #2187

Open anshumanmohan opened 4 months ago

anshumanmohan commented 4 months ago

2067 got us binary heaps, which is super cool. It also got us a small number of scheduling transactions, such that the binary heap plus a scheduling transaction over it obeys the same interface as our simple round-robin PIFOs. With our simple round-robin PIFOs, it was easy to build a PIFO tree. This will be a little trickier to do with binary heaps at nodes. This issue tracks the need to do that.

We will need to lay out a number of binary heaps that match some given tree shape. In binary heaps at leaves, we will need to store user-given values. In binary heaps at internal nodes, we will need to store integers. We will need to define the push operation with care, to ensure that an appropriate path of integers (plus one, final, user-given value) is pushed into the tree. Similarly we will need to have a pop operation. The peek operation will be easy after that. Anyway, the point is that we no longer get trees for free, as we did from our RR PIFOs. Let's actually build them, much like the Formal Abstractions artifact does.

Assigning to @KabirSamsi since he requested it, but I sincerely encourage folks to talk this out in a meeting or in a 1:1 with me before jumping in!

anshumanmohan commented 3 months ago

@KabirSamsi just a quick request to please do a little documentation in this thread to capture our discussion from today! Don't spend too much time on it, but do get down the basic concrete plan so that we can look at it together. I think it'll really help you when you get back to this in a few days :)

anshumanmohan commented 3 months ago

Actually @KabirSamsi let's try and meet tomorrow morning if that's possible. Like, before you put in any energy towards a write-up. On further thinking I may have given you a bit of #fakenews during our chat today. The thing I'd like to revisit is your starting point. I told you you'd want to start with Calyx and create a Calyx-level tree, but I now think you may be able to start with OCaml and create a Calyx-level tree. @polybeandip feel free to join this chat, since it will involve a handshake with your work

KabirSamsi commented 3 months ago

Yes sounds good! To both :)