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

Queues: massage away 2-way round-robin PIFOs #2226

Closed
4 tasks done
Tracked by #2191
anshumanmohan opened this issue Jul 26, 2024 · 1 comment · Fixed by #2234
Closed
4 tasks done
Tracked by #2191

Queues: massage away 2-way round-robin PIFOs #2226

anshumanmohan opened this issue Jul 26, 2024 · 1 comment · Fixed by #2234
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 26, 2024

As part of flag day (#2191), let's do a further piece of cleanup. We really have many different kinds of PIFOs hanging around now, but I'll point out two that should be merged thoughtfully.

  1. This style, developed by me a little while ago, does round-robin scheduling among exactly two sub-queues. Its variable names make it clear that the two sub-queues can themselves be queues, not just FIFOs. In particular, they can be FIFOs or, recursively, PIFOs exactly like itself. This style of PIFO can therefore be elegantly used to make PIFO trees, where of course the PIFO trees are limited to binary-branching PIFO trees where each node wants the round-robin policy. This tree-making superpower has been tested via Python oracle.
  2. Meanwhile, this style, developed by @csziklai this summer, does round-robin and strict scheduling among n sub-queues, not just two. This much has been tested via Python oracle. However, its variable names and testing thus far currently assume that the sub-queues are always FIFOs. That is, the file believes it can orchestrate n FIFOs to make an n-way PIFO, but it does not realize that it can orchestrate lists of PIFOs to make PIFO trees!

I would like to have the second style replace the first style. To do this, we need something like the following to happen:

  • Change the variable names and comments and such of the second style to accept queues in general, not just FIFOs. I do believe the change needed is modest. The structure is ready for tree-building, it's just been used to make trees of height two where the leaves are all FIFOs.
  • Make more ambitious trees, like this file does with the first style. First let's literally just make what's in that file, since that matches the Formal Abstractions paper's motivating example and is byte-to-byte testable versus the existing implementation. Like, it'll pass the runt tests with the same .data and .expect files! Then as an extra file let's make rr(strict(A, B, C), rr(D, E, F), strict(G, H)) or something to show the extended capabilities. Check this via Python oracle.
  • If this all works, remove the first style from the codebase and use the second style wherever the first was used!
  • Document the second style, removing the documentation of the first style. Documentation for RR and Strict Queues #2223 has begun the documentation task, but it adds on text below the text for the first style. I think we should just stamp out the old and sing the praises of the new! For this reason I'm going to skip on reviewing the PR. @csziklai could you please mark it as a draft for now? I'd like for it to be changed as described here and then review it!
@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 26, 2024
@csziklai csziklai self-assigned this Jul 26, 2024
@anshumanmohan
Copy link
Contributor Author

@csziklai just a reminder to heed this advice here too! Do make sure that you branch off from the latest main commit!

csziklai added a commit that referenced this issue Aug 9, 2024
This PR makes progress towards #2226 by updating variable names and
comments to account for the fact that round robin PIFOs can make n-way
trees. Additionally, it implements a PIFO tree and a more complicated
tree (`complicated_tree.py`) using round robin and strict queues. This
accounts for the first three checkboxes of #2226. The docs have been
updated to reflect the new PIFO style in #2223. To run the relevant
tests,
```
runt -i "queues"
```

(For sdn.py, I removed the stats component stuff because I thought it
was mentioned that this wasn't important and so the new style PIFOs are
not equipped to do stats. If it needs to be there, let me know.)

---------

Co-authored-by: Anshuman Mohan <[email protected]>
csziklai added a commit that referenced this issue Aug 9, 2024
This PR makes progress towards
#2191 by adding documentation
about round robin and strict queues. Additionally, it completes the last
checkbox of #2226 by updating the
documentation to use the new style of PIFOs. Recently, it also updates
the documentation to reflect the removal of peek (#2241). Because of a
git mistake carried forward, this PR supersedes #2223.

---------

Co-authored-by: Anshuman Mohan <[email protected]>
@anshumanmohan anshumanmohan linked a pull request Aug 9, 2024 that will close this issue
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

Successfully merging a pull request may close this issue.

2 participants