Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement PIFO trees using binary-heap PIFOs #2187

Open
Tracked by #2067
anshumanmohan opened this issue Jul 1, 2024 · 3 comments
Open
Tracked by #2067

Implement PIFO trees using binary-heap PIFOs #2187

anshumanmohan opened this issue Jul 1, 2024 · 3 comments
Assignees
Labels
C: calyx-py Items that have to do with the builder library C: Queues One of the queue-style frontends

Comments

@anshumanmohan
Copy link
Contributor

anshumanmohan commented Jul 1, 2024

#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 anshumanmohan changed the title Explore what it would take to implement PIFO trees using these binary-heap PIFOs. Implement PIFO trees using binary-heap PIFOs Jul 1, 2024
@anshumanmohan anshumanmohan added C: calyx-py Items that have to do with the builder library C: Queues One of the queue-style frontends labels Jul 1, 2024
@anshumanmohan
Copy link
Contributor Author

@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
Copy link
Contributor Author

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
Copy link
Collaborator

Yes sounds good! To both :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C: calyx-py Items that have to do with the builder library C: Queues One of the queue-style frontends
Projects
None yet
Development

No branches or pull requests

2 participants