Summer Progress Tracker – Kabir Samsi

[KabirSamsi]

Stores my weekly progress on this project, logged every Friday as an additional comment.

[KabirSamsi]

Overview

This was my first week on the project. My primary efforts have been concerned with learning how to write with basic Calyx, fully reviewing "Formal Abstractions in Packet Scheduling", and getting comfortable with the eDSL.

Specifically, I have been following along the tracker for this project. have completed the first two steps, and am currently working on the third.

Completed Work

I've fully read "Formal Abstractions in Packet Scheduling", focused on the sections highlighted, and made a summarized set of notes (in line with how Anshuman has described reading papers at depth). This is a continuation of what I've been doing over the last three weeks. This was just to ensure that I'm well-versed enough in the project.

I completed the Calyx matrix multiplier, as well as a couple of other memory-related programs to test myself (matrix adder, alternative dot product calculator, etc.). This took longer than expected or desired. Over the first two days, I was struggling a bit with the syntax, but things began to click on Wednesday. Since then I've been able to work at a better pace.

Next Tasks

I'm planning to spend the new day or two getting very familiar with the calyx-py eDSL. I intend to re-implement the matrix multiplier there and review the PIFO-related data structures (also in accordance with the checklist). I'd also like to take some time this weekend to review my own notes on the packet scheduling paper. I'd like to have this done by the end of the weekend. As such, I'd hope to move to the 'quests' section and begin to experiment with the generalized PIFO implementation next week.

[anshumanmohan]

Congrats on a great first week!

This took longer than expected or desired.

I get what you mean, but please don't place any hard demands on yourself at all! Research is funky and you folks are learning five wild new things at the same time. Plus you are using research tools, which are janky and not always documented helpfully. Be patient with yourself!

I super like that you created a little ramp-up for yourself enroute to the matrix multiplier! And, it's not on your list above, but you also figured out expect-testing using Runt and Calyx's CI. 🎉

I think you'll have fun reimplementing the matrix multiplier. Your first target may well be to recreate the code you wrote by hand, and then you may want to explore additional fun things that Python lets you do. A straightforward example is parameterizing your Python code so you can multiply matrices of various sizes. Chat with me if you'd like to explore this little extension. Good luck!

[KabirSamsi]

I had some fun with this, and also explored integrating a few of the features in the builder.py file. Reduced the code to almost half. Super cool functionality!

[KabirSamsi]

Overview

Posting this slightly late (following Monday rather than Friday).

This past week, with a stronger foundation in Calyx and in the project, I made progress in a few areas and began my first packet-scheduling specific task.

Completed Work

I spent a good deal of time working on the calyx-py eDSL. In re-implementing the matrix multiplier, I also had the opportunity to add new functionality to the eDSL – this is included in PR #2141 and extends the op_use and op_store_in_reg functionality to non-combinational operations like mul and div (and the corresponding cells). Included in this was creating my first official calyx PR and merge request (as opposed to the matrix multiplier, which was not to be merged). I also just spent a good deal of time studying the builder.py file in calyx-py.

I also conducted my first code review for Anshuman's seq_mem conversion PR. It wasn't a very involved review, but was a good experience and I'm looking forward to reviewing more!

For packet-scheduling specific tasks, I studied the PIFO and FIFO implementations in calyx-py, and then studied a handful of papers discussing a new data structure, PIEO queues. I did a lit review and put together a mini OCaml implementation for what functionality such a data structure should support – see #12. I have begun also studying Calendar Queues, which I will continue into next week.

Next Tasks

I will be working now on studying Calendar Queues, and seeing if they merit a Calyx implementation as well. I'll also be spending some time working with Akash on the binary heap structure, thinking about the implementation of PIEO queues (which I expect will involve the binary heap), and getting to work on that.

[anshumanmohan]

Sounds super! The merged Calyx PR is real neat; congrats on wrapping your head around some pretty baroque Python written by a bunch of other people. I am also very happy with your lit review and I'd love to see a Calyx implementation of PIEO queues. Just remember to start unambitious! Much easier to flesh things out and make them prettier/faster/slicker once we have a basic thing working.

[KabirSamsi]

Apologies for having missed out on a couple of weeks here!

Updates

My most updates as per the last few weeks involve a having proposed full implementations for PIEOs and Calendar Queues, and designed test oracles for them both as per Calyx PR #2192.

In particular, I explored both verbose and simple test oracles for the two structures. These involve implementing PIEOs as binary heaps, and Calendar Queues as hashtable-like structures which store PIEOs as buckets.

As of Friday 7/12 I am nearly finished with a calyx-py implementation for PIEOs in the branch pieo-impl.

Next Steps

My immediate task involves finishing the implementations for both of these in calyx-py. Concurrently (albeit on te back-burner), I am starting work implementing PIFO Trees using binary heaps. I'm hoping to have calyx-py implementations for both completed by the end of this week with PRs opened for each, and proposals for binary-heap PIFOs following soon after!

[KabirSamsi]

Update for last week:
There are two PIEO implementations which I am implementing concurrently. The first involves using @polybeandip's Stable Binary Heap and a caching system to create an abstraction of the queue system. The second involves a system which keeps elements stored in memory and sorted by rank. I spent some time modifying queue_call.py to be compatible with the PIEO interface.

Each draws a parallel to one of the two Python test oracles I implemented previously.

I worry that I've spent too much time reinventing the wheel – after effectively creating a more complex variant of the Stable Binary Heap, I figured out today a way to combine the two to improve the performance of the structure. I'll continue with this. Separately, I'm continuing to explore working with Binary-Heap PIFO Trees.

[anshumanmohan]

Super, and please don't worry about time spent experimenting and then later discovering a cleaner solution. That is very much a part of daily life when it comes to research. Is the improvement to stable binary heaps a general improvement to the structure itself, or is it better for your purposes only? Just curious!

[KabirSamsi]

Moreso for my purposes! It just involved figuring out how to use stable binary heaps to get the PIEO functionality I wanted without breaking anything else.

[KabirSamsi]

This week, I worked a lot on optimizing our parser, and on extending our DSL to be compatible with a handful of non-work-conserving policies. This involved researching new policies, and explored ways to target PIFO and PIEO Tree representations with our new policies.
I also began work on studying and proving Well-Formedness with PIEO Trees, and continued my work on developing representable PIEOs on hardware.

Specifically, I worked on error handling in the parser, such that faulty programs are rejected with more descriptive errors rather than outputting direct syntax errors. The setup for this now actually allows us to play with 'smarter' compiler options in the future, such as creating a way to catch erroneous programs and re-parse them to be well-formatted.

In addition to this, I researched four new, non-work-conserving policies, and documented them and their functionality in our Glossary. For two of these, I discussed clean translations from policy to queue representations, which I plan to do for the remaining ones as well. Along with four work-conserving policies we already have, I added these into the DSL, with lexing, parsing, formedness-checking and pretty-printing support.

Finally, I spent a good deal of time studying well-formedness and its meaning, both for PIFO and PIEO Trees. Formal Abstractions offers a strong definition, and outlines two lemmas whichsuggestiong that pushing and popping from a PIFO Tree preserve its well-formedness. My main goal is to justify such lemmas for PIEO Trees as well. To do so, I explored proofs for these lemmas with PIFO Trees, and on this path further formalized the $push$, $pop$ and $|\cdot|$ functions for PIFOs and PIFO Trees.

My next major goals are to complete this proof for PIEO Trees, finish up the PIEO representation in Calyx, and possibly get on the track of extending our language to deal with custom policies! On the backburner still is the issue of PIFO Tree representations with Binary Heap nodes.