Tracker for summer project

[anshumanmohan]

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.

• Read Formal Abstractions for Packet Scheduling. For a warm-up, you may enjoy this talk 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.
• Calyx crash course. Our usual advice is to start here, work through the tutorial, 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.
• These days we don't really write Calyx by hand. We tend to generate it using the Calyx eDSL, 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. 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.
• Look over our implementations of FIFOs, PIFOs, and PIFO trees in Calyx. They are documented here, 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!

• Queues: generalize PIFOs calyxir/calyx#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.
• Tracker: binary heaps calyxir/calyx#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 Tracker for PIEO/Calendar Queue Research #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 Summer Project: PIFO trees in hardware, and a DSL that targets them #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.

[sampsyo]

One quick note on step 2: PLEASE ask questions on Slack!!!!! We love to help out when people are learning Calyx, so part of the "homework" here is to post any and all questions you have about Calyx (while you go through the tutorial and write your matrix multiply implementation) in the #calyx channel. The simpler and more basic, the better! Seriously, we REALLY want you to ask for help with this; it is NOT something that you can feasibly do completely by yourself.

[sampsyo]

Here are a couple of threads we could imagine adding to this plan, somewhere:

• Getting the design running "for real" on hardware. Namely:
  1. Using our existing tools to run the PIFO trees we generate as-is (in their "bulk-synchronous" evaluation mode) on the FPGA we have in our lab. This would be a "fun" way to learn a lot about real hardware-generation tools!
  2. Figure out how to make this real hardware process real packets! We now have a license for Xilinx's VitisNetP4 package which may let us do this, but it will require some serious hardware-hacking effort to get this going.
• Decide on how to execute user-defined policies in hardware. This is related to the "figure out what kinds of user-defined policies…" bullet, but the point is that—after we nail down what kinds of policies we want to support—we can decide how those will be implemented in hardware. A handful of fixed-function units? Maybe something more expressive? This requires a lot of creativity.