Ethan Lab Notebook

[gabizon103]

6/1/23

Hi and welcome to those reading! Will be posting updates here about implementing a RISC-V Processor in Filament.

[rachitnigam]

Woo! Excited to see the start of the world's greatest RISC-V processor!! I'll recommend the name frisc but final naming rights are entirely yours @gabizon103!

Couple of other logistical thoughts:

1. Let's keep the code for the processor in a directory within this repository.
2. Instead of waiting for the perfect processor, I recommend breaking things into small pull requests and committing them often
3. Once things start taking shape, let's add some correctness tests for the various modules you're going to be building for the processor. Adding the tests to our runt.toml configuration would be best since that makes it a default test that must succeed with every commit

[gabizon103]

6/2/23

This week I added support to fud for passing binary and hex data into Filament designs. I figured this was a good place to start because it would make testing parts of my RISC-V implementation much easier. This sounded pretty simple, but I had to integrate it with the rest of the fud codebase that already existed, which was a little daunting and took some time to get the hang of. After some trial and error I came up with a good solution that fit pretty nicely with the rest of the code.

Then, I moved on to starting the RISC-V processor (I like the name frisc but I will spend the next few weeks brainstorming some other cool names). I figured the instruction decoder would be a good place to start. A few weeks ago I played around with implementing this in Filament, so I was a bit familiar and focused on making my code cleaner/easier to read, since my first implementation was neither of those things. I took a bit of a detour and spent some time looking through the Filament compiler code because I was interested in implementing some syntactic sugar like in[30:20], which is not currently supported. I hit some roadblocks here (mostly with trying to figure out how to print the AST), so I figured it was a better use of my time to just start implementing the decoder. I made good progress with this and it is mostly done, although untested. Finishing up won't take long, and it'll take a bit of time to write tests that ensure it can decode all of the RISC-V 32I instructions properly.

Rachit helped me out with printing the AST, so next week I plan on revisiting this. I think it would be nice and not that difficult to have syntax like in[30:20] get parsed into an AST node for a Slice instantiation. I think it would make Filament code less verbose and easier to read.

Fun first week two days!

[rachitnigam]

Awesome work @gabizon103! Yeah, the fud codebase is daunting and slightly insane but I like your approach of representing the transformation as a source-to-source problem (generating a new JSON from an existing one). It fits pretty neatly and makes debugging easier!

The decoder certainly seems a good place to start since it is (presumably) fully combinational. One thing you might consider doing in absence of the nice syntactic sugar is defining components that abstract extraction of relevant parts of the instruction. For example, in my floating point implementation, I defined several components to do something similar.

The change to AST sounds good but might be a little finicky; regardless, you should roll ahead with it and we can figure out problems as we go along!

[gabizon103]

6/9/23

This week, I finished up the decoder, started/completed the register file and ALU, and wrote tests for each component (#171). Once I was convinced each component was working properly, I connected them together in a top-level module called CPU and tested it. As far as I know, this little piece of the processor works correctly for R-type and I-type instructions. My next steps are to implement branching and the rest of the RV32I instruction set. This will require finding a way for the processor to read from memories. I'm not quite sure how to do this yet, so it will require some thinking and experimenting.

I wrote quite a bit of Filament code to get this part of the processor working, and it was fun. This part of the design is mostly combinational so I wasn't working much with Filament's type system, but it was interesting to get a feel for the syntax of the language. I think it will be really interesting to eventually use the type system to pipeline this design.

Apart from the processor, I also spent time this week learning about Filament's new IR. I implemented some small changes to the IR printer at first (#168). Then, I started working on the monomorphize pass. I haven't made much tangible progress yet, since most of the things I did so far ended up being incorrect, and it took me a bit of time to understand how the IR is structured. I think I have a better understanding of it now, and will continue this next week.

[rachitnigam]

Awesome stuff! Most of the specific comments are in #171

since most of the things I did so far ended up being incorrect

You can spin it as "updating your stochastic priors" like the machine learning people do ;-)

[gabizon103]

6/16/23

Much of my time this week was spent trying to find ways for the RISC-V core to interface with memories, which are not yet a part of the Filament language. I thought about this problem for a bit and figured a good approach to start with would be compiling my Filament program to Calyx, then instantiating it in a Calyx program along with whatever memories I wanted to use. I made a harness would read an instruction from memory into the CPU and write the output of the ALU to a separate memory, but ran into some strange bugs. I loaded a simple instruction sequence into the instruction memory:
sub x1, x1, x1
addi x1, x1, 1
addi x1, x1, 1
addi x1, x1, 1
addi x1, x1, 1
The expected output was of course 0, 1, 2, 3, 4, but I was getting something like 0, 2, 10, 18, 26 and it was also taking more cycles than it should have to execute, since the CPU triggers every cycle. I suspected that since the CPU was always active, it was running the same instruction for multiple cycles until it got a new one. I did not know how to fix this until my meeting with Rachit and he showed me I could use Calyx's static feature to ensure that each instruction would run for only one cycle. This fixed most of the issues, only now the output looked like 0, 0, 1, 2, 3. The result of each instruction was being written to the wrong index of the result memory. After inspecting the waveforms I found that this was due to a pipelining issue, since reading the instruction from memory takes an extra cycle that I was not aware of. I registered the pc signal that I was using to index into both of the memories for another cycle, and the issue was fixed.

The harness was working, but it wasn't exactly easy to use. The compiler did not emit any Calyx for Filament programs that did not have a main component, so I had to create fake mains for each of the components in my design and compile those (and then remove the main component that was generated in Calyx). This seemed like a good thing to fix for the language in general, so I made some modifications that allowed the user to pass in the name of the top-level component of their design when invoking the compiler, and if it exists, that is where the compiler will enter the program. This made it much easier to compile the RISC-V core.

With the harness in a pretty good place, I started implementing the rest of the instruction set, which I hope to finish up next week. I think we are pretty close to being able to actually run programs on the processor, which is exciting.

I spent most of my time on frisc stuff this week, but I did make some progress with the monomorphize pass, mostly in the form of pseudocode and examples I wrote out to convince myself of a good approach. I think I know how I want to structure it now, and next week I will spend time implementing it.

[rachitnigam]

Awesome work Ethan! Really impressive to see all the progress on this and excited to see what the full processor can do!

[gabizon103]

Little mid-week update/to-do list for myself:

So I wanted to use memories implemented in Filament (or at least with a Filament signature) because it was a bit troublesome to reason about the timing of the Calyx memories. And there was also no explicit reason I could come up with for why the data memory had to be instantiated outside of the Filament CPU module, so I wrote a Filament signature for the std_mem_d1 Calyx component and instantiated that inside CPU. This worked when I was testing it outside of the Calyx harness (manually passing in each instruction instead of using an instruction RAM), but gave me an error about a combinational loop when testing it inside the harness.

Sort-of-related tangent: I got this error (which I think is thrown by Verilator? unsure though) before when trying to build the circuitry for the program counter logic. I was connecting a nextPC signal to the input of the PC reg and updating it every cycle (which I don't really understand why it is a combinational loop), but then the error went away when I made nextPC an output of CPU and PC an input, and then connected the two signals in the Calyx harness. No idea why this fixed it (because it is functionally doing the same exact thing as before), but shrug.

Back to what I was saying before: I did this same thing to avoid the combinational loop error and instantiated a Filament memory in the Calyx harness, and then connected it to the CPU inputs/outputs. It worked! Yay! LW and SW instructions work now.

To-do list for myself:

• Implement LB, LH, SB, SH instructions (not hard)
• Work on fud so we can easily transform programs and load them into the instruction memory, instead of doing it manually
• Add some RISC-V extensions maybe, or connect with FFT

[rachitnigam]

Haven’t read everything yet but I’d recommend using seq_mem defined in memories.Futil instead. Those have both sequential reads and writes

[rachitnigam]

Also I don’t think there is an FFT yet (CC @UnsignedByte) so maybe we can start with pipelined floating point implementations?

[rachitnigam]

Can you share the two implementations: with and without the combinational loop? It is worth figuring out why one worked and the other didn’t

[gabizon103]

Can you share the two implementations: with and without the combinational loop? It is worth figuring out why one worked and the other didn’t

Yeah, I'll try to write a simpler program that captures what was happening later today

[gabizon103]

6/23/23

Rest of this week's update (refer to previous post to see the rest).

I implemented the load and store instructions for the processor, which ended up taking more time than I thought it would. Getting the logic right for loading/storing bytes and halfwords took a bit of time, and also made me realize I had to rethink how the memories were designed. I was previously using memories that had X blocks of 32-bit data. This meant that a memory address corresponded to whatever word was at that address, but the memory should be byte-addressable. Instead I wrote something up that could be instantiated with X bytes, and each of those can be addressed. This works fine, but it has no concept of alignment (should it? I am not too familiar) and the RISC-V spec says this about alignment:

For best performance, the effective address for all loads and stores should be naturally aligned
for each data type (i.e., on a four-byte boundary for 32-bit accesses, and a two-byte boundary for
16-bit accesses). The base ISA supports misaligned accesses, but these might run extremely slowly
depending on the implementation. Furthermore, naturally aligned loads and stores are guaranteed
to execute atomically, whereas misaligned loads and stores might not, and hence require additional
synchronization to ensure atomicity.

Similar thing needs to be done for the instruction RAM, but this would make loading programs into it a bit more annoying. Still need to think about this some more. In the meantime, I added a new data format risc-v to fud so that we can pass data in like this:
{
"iram": {
"data": [
"sub x1 x1 x1",
"addi x2 x1 99",
"addi x2 x2 1",
"addi x2 x2 1",
"addi x2 x2 1",
"addi x2 x2 1"
],
"format": {
"numeric_type": "risc-v",
"isa": "32i"
}
}
I'm not sure if it makes the most sense to have this be a numeric type, but doing so made it easy to implement with all the existing fud infrastructure for the bitnum and floating point types.

I think this is a start to building up a toolchain-like thing where you can compile a program, load it into the instruction memory, and then run it on the processor, all from the command line.

[rachitnigam]

Awesome stuff @gabizon103! I'm not too familiar with addressing modes in RISC-V so yet again have to summon @sampsyo's knowledge on this. I think asking the #overflow channel would also be a good idea to get a sense of the trade-off with aligned accesses.

The new format looks great! I agree that overloading "numeric_type" is a bit weird so maybe we need to rethink the name of that tag. Maybe just "type"? The annoying bit is that it would break a bunch of code to make that change.

[sampsyo]

Neato. Thanks for the detailed explanation, @gabizon103.

To expand a little, the reason the RISC-V manual says that stuff about alignment is because of the typical memory hierarchy of a CPU, i.e., the caches and such. The biggest and most obvious problem that can come up with unaligned loads/stores is that they might cross a cache line boundary. So a 32-bit word might have one byte at the end of one cache line and the other 3 bytes at the beginning of the next line. Loading or storing this word is much more expensive than a 32-bit word that fits within a single line. (Of course, alignment is sufficient but not necessary to prevent multi-line loads & stores. If you like, you can imagine other aspects of the interface to caches enjoying alignment properties as well.)

In general, unaligned accesses need to be translated into multiple serial accesses to different locations. That's the reason some RISC ISAs rule them out altogether. It's also the reason RISC-V discourages them and does not guarantee atomicity.

For our purposes (i.e., not having a cache or a real off-chip memory interface or whatever), I think you've done exactly the right thing by just having a byte-addressable memory. It is annoying that you have to access the memory $n$ types for an $n$-byte load/store, but that's life, obviously. A different local optimum would be to stick with a 32-bit access port to the memory, and to have two different ways to access it: one for aligned accesses (simple, easy) and one for unaligned accesses (annoying, requires doing two accesses and then carefully stitching together the results). But the byte-addressable approach is nice for now (while we are not caring about having a high-performance memory system) because it's at least uniform, even if it's uniformly slow.

[gabizon103]

I see, this clears a lot of things up. Thank you for the explanation!

[gabizon103]

6/30/23

This week I reached a good point to stop on frisc things, since most of the processor's functionality is implemented and now I need to think/research a bit more how to best implement the surrounding harness to make testing/running real programs easy and convenient. I turned my attention towards the IR and worked on implementing the monomorphize pass. This pass removes the parameters from components and hard-codes the values that they were instantiated with. The base functionality is mostly there, where new components are generated that have no parameters and the correct values hard-coded, but I haven't tested it super thoroughly so I figure I will find some bugs.

I understood generally how the IR is structured thanks to previous meetings, but it took a bit of time to get familiar with the technical details of the code, and I mostly figured things out as I went. Also, I am still getting familiar with Rust so it took a bit to figure out exactly how to implement the things I wanted to, but I think I have a good enough handle on it now.

[rachitnigam]

Sounds great! Looking forward to the PR for monomorphization. Almost there with the end-to-end IR flow!!

[gabizon103]

7/7/23

I spent all of this week working on monomorphization. I built up some infrastructure to replace all the params in a given IR data structure with concrete values, which was an ongoing task because they kept popping up in places I didn't know they were. Also, loop unrolling took kind of a while to get correct, because I had to add a lot of new times, invokes, instances, etc as I unrolled them and had to be careful about causing name collisions. There was a lot of information to track and it was not immediately obvious how to do it, like the bindings between invokes and instances that are inside loops and had to be added to the component. But I was able to figure most things out as I went.

Right now, I'm working on adding ports and if statements, which (I think?) are the last two things to do, besides bugs that still might pop up here and there. Ports also require a lot of information to be copied over from the original component, so I'll have to be careful about making sure everything is correct.

[rachitnigam]

Awesome work on this stuff! Looking forward to the PR. Couple of comments that will probably be answered when I start reading the code:

had to be careful about causing name collisions

I was hoping that this would be easy since we no longer have any names in the component, just indices into various IndexStores. I'm surprised that name collisions occur at all.

bindings between invokes and instances

Again, something I was hoping that the IR would make trivial by making each Invoke point to its corresponding Instance. Curious to see where the burden of tracking the bindings is coming from and how we can change the IR to make it easier.

[gabizon103]

Maybe collisions isn't the right word - it was just a little tricky to get the invoke in a loop iteration to point to the right instance, since the original component just has something like inv0 = invoke inst0, but then when I unroll it I had to make new invokes and new instances, and then have the new invoke point to the correct new instance, if that makes sense. It wasn't too bad, though. In any other scenario where I had to work with invokes and instances, it was pretty painless.

[rachitnigam]

Ah, that makes sense!

[gabizon103]

7/14/23

Again, this week was spent on monomorphization. I met with Rachit to do some pair programming, and we worked on parts of it together. We decided to make a new version of the pass, since the one I had been working on was getting pretty messy. I think working through it gave me a good sense of the things that need to be done, and also some possible shortcomings of the IR (like the EventBind business that we've been talking about). I think a lot of the machinery can be reused (or at the very least, the ideas behind it), and now we have a more structured approach to the pass that is more similar to the one in the original compiler flow.

Overall, this is taking longer than I thought it would take me, but I guess that makes sense because I had to learn how to work with the IR, as well as learn a lot of Rust, and also implement the pass. I apologize if this has been blocking other people's work, but I feel like I've been learning a lot while working through this, so at least there's that.

[gabizon103]

7/28/23

I spent most of the week working on more monomorphization things. At the start of the week I figured out there were a lot of bugs with ports and parameters, mainly arising from when we would unroll loops. New parameters would not be generated correctly, so the new ports that were being generated were using parameters that either didn't exist in the new component or were used by other ports. This wasn't too difficult to sort out, it mostly just required keeping track of some more information and being careful about where/when new parameters were generated.

Then the more difficult thing to figure out was why loop parameters were not being correctly substituted for concrete values in constructs like invoke events and port livenesses. With help from Rachit, we fixed it by restructuring the code to do the substitution before we check if we've already visited the expression. With monomorphization appearing to mostly work, I inserted it into the rest of the compiler flow and found some more bugs that were exposed by lowering and bundle elimination. I fixed these and then wrote up a PR for it, #216

[gabizon103]

(Repurposing this to just be a general lab notebook)

3/26/24

This week I worked on #437, which I ran into when implementing more of BLAS kernels. I was a little rusty on working with the IR so it took a little while longer than I thought, but it's done now. So now I'll go back to implementing some kernels, with a focus on getting some synthesis results for the kernels that are implemented.

[rachitnigam]

Awesome! Not sure if I will have the brain capacity to provide feedback on the PR so feel free to merge it if it's taking too much time.

[gabizon103]

No worries, thanks!