cucapra / cucapra/packet-scheduling

Tracker for summer project

Open
#4 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
TeX
Stars
9
Forks
0
Avg merge
9h 11m
Merged PRs (30d)
27

Description

## Ready for you to start on

### Warm-up
_Each of you should work on these; with these I am mostly concerned with your learning and don't mind the duplication of work._

- [x] Read [Formal Abstractions for Packet Scheduling](https://dl.acm.org/doi/10.1145/3622845). For a warm-up, you may enjoy [this talk](https://www.youtube.com/watch?v=beTci1VsPHY&list=PLyrlk8Xaylp7q2tEU-tcQdENpnDSHVl5r&index=81) about the work. In the paper, I suggest you work through §2, §4.1, §5.1, and §6.1 with care. You can skim the rest. You can skip all the proofs, but try to understand the statements of theorems informally.
- [x] Calyx crash course. Our usual advice is to start [here](https://docs.calyxir.org/#getting-started), work through the [tutorial](https://docs.calyxir.org/tutorial/language-tut.html), and then try your hand at a very simple matrix-multiplier design. Ask lots of questions on the `#calyx` channel in the group Slack! Eventually please create a pull request containing your work on the Calyx repository.
- [x] These days we don't really write Calyx by hand. We tend to generate it using the [Calyx eDSL](https://docs.calyxir.org/builder/calyx-py.html), which is embedded in Python. Carefully work through the little example on that page. Try to change it, break it, fix it! Then move on to the [extended walkthrough](https://docs.calyxir.org/builder/walkthrough.html). Once more, with feeling! For the extended walkthrough, I recommend you have three windows open: the Python code, the Calyx code generated by the Python code, and the documentation explaining various features.
- [x] Look over our implementations of FIFOs, PIFOs, and PIFO trees in Calyx. They are documented [here](https://docs.calyxir.org/frontends/queues.html), and the docs point to the code.

### Quests
_The three items below are a little more open-ended. You are of course free to collaborate with each other, but I don't want you to spend your time duplicating this work. So please claim a task (with a partner if you wish) and take a crack at it!_
- [x] https://github.com/calyxir/calyx/issues/1810 sketches further steps for our basic PIFO. You have studied this already – it can handle fairness among two children and nothing else – but we think it would be interesting to generalize this lightweight PIFO a little.
- [x] https://github.com/calyxir/calyx/issues/2067 tees up a binary heap implementation. I have made some progress towards it, but now's your chance to take it all the way!
- [ ] See #9. During discussions with other academics, folks have often pointed us to two additional data structures: PIEO queues and calendar queues. Look into these, teach the team about them, and explore a Calyx implementation.

## Staging area
_Pause and discuss before going ahead with the following._

- [ ] The queue structures above have been tested somewhat modestly so far, and it would be nice to expand the test suite before we make the data structures fancier.
- [ ] Figure out what kinds of user-defined policies can still compile to our expanded PIFO tree implementation. See #3, where this set of policies is shown as a red subset of possible policies.
- [ ] Write a DSL that lets users express their scheduling policies, while limiting them to the set of shapes and policies that we can support (the red subset).
- [ ] Hook the DSL up to a compiler, as described in [Formal Abstractions for Packet Scheduling](https://dl.acm.org/doi/10.1145/3622845).

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by reading the linked Formal Abstractions for Packet Scheduling paper, the Calyx queue documentation, and issue #9. Compare PIEO queues and calendar queues, discuss their designs with the team, and explore a Calyx implementation; completion is teaching the team about them and producing an implementation or a documented conclusion.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.