[LSQ] Proposal for LSQ Generator Refactoring, Improvements, and Documentation

[Jiahui17]

[LSQ] Proposal for LSQ Generator Refactoring, Improvements, and Documentation

Introduction

Thanks to Hailin (@bertwhl) and Jiantao (@qianxu1998), now we can generate LSQs with substantially better area and frequency (#211). Yet, a few main things are missing:

1. Verilog support: The current LSQ generator only emits VHDL. Most of the popular RTL simulators and synthesis tools exclusively support Verilog instead of VHDL.
2. Better documentation: LSQ is the most complex block in Dynamatic-produced circuits. Although there exist papers that document the high-level principles, we still need better documentation on the internal/interface signals.
3. Fuzzer: We need a comprehensive tester for LSQ.
4. Support for zero load ports: see [Backend] Chisel LSQ generator fails on LSQs with 0 load ports  #111

There are a few minor things to improve as well, besides the points above:

1. Code organization: The code is not structured ideally. For instance, the generation logic that prints out LSQ has 2000+ lines of Python code and is kept in a single file. It would be healthy to break it into more modular parts.
2. Configuration organization: LSQ configuration has many fields. Although we have concise descriptions for each field, one still needs to read the generator code to understand how to create a legal configuration. Also, maybe the configuration format in its current form is not the most intuitive one.

Code Organization Idea

One possible way to organize the directory would be (I am improvising here):

$ ls lsq-generator-python

hdl_types.py                # Data types for representing RTL logic
hdl_utils.py                # Common logic (OH encoder and decoder, shifter, rotation etc.)
lsq_dependency_checking.py  # dependency checking logic between queues and decide what to issue and retire
lsq_group_allocator.py      # group allocator module
lsq_port_to_queue.py        # port to queue dispatcher module
lsq_queue.py                # FIFO logic
lsq_queue_to_port.py        # queue to port dispatcher module
lsq_top.py                  # Top module: putting everything together
lsq_wrapper.py              # Adapter module for interfacing with different memory hierarchy

Now, everything is in one file; the FIFO logic, dependency checking logic, and the logic that instantiates the rest of the LSQ components (group allocator, etc) are in one function.

It would be great if we could:

1. Come up with a (better) organization and motivate why this makes sense (e.g., good for pipelining, etc.)
2. Come up with exact lists of signals connecting these modules (lsq_*.py).

Integration Idea

We can incrementally create the subcomponents in experimental/tools/lsq-generator-python and eventually graduate it to non-experimental.

Remarks

What do you think? Anything to add?

[pcineverdies]

I think it's a good idea to start from what @qianxu1998 provided and slowly move to a more modular system!

From a software perspective, I expect that having the code generation made out of string concatenation can be suboptimal for maintainability. Maybe jinja can be an alternative? (TLDR: Python templating engine that dynamically generates text files using placeholders and control structures).
This can be useful also when it comes to the verilog support: a set of scripts generates all the LSQ data which are HDL-agnostic, and then different templates are used for verilog and vhdl.

@qianxu1998 did you consider this possibility when starting the project?

[qianxu1998]

Thank you for the suggestions. I agree that using a template engine is the right approach. To clarify, this project was not initiated by me. As mentioned in the pull request description, the core logic (specifically in lsq_core.py) remains nearly identical to the original version. My contribution was focused on adding the necessary integration logic. During wrapper generation, I aimed to reuse the existing structure to avoid restructuring the entire codebase.

That said, I agree that a complete restructuring would be beneficial for improving code clarity and extensibility.

[murphe67]

Just a heads up for @pcineverdies, we should be starting a student project on this in the next term, though we are going to use our new approval process for it also.

My thoughts for moving forward-

1. Generate as many valid configurations as we can, and use the current code to generate LSQ implementations, and save them.
2. Attempt to figure out a natural structure for the current implementation- the code as written has very little structure, and so we should first try to massage it into shape and see what comes out. For any updated version of the code, we should run the full list of configurations and make sure that the output files remain unchanged.
3. Once some kind of natural structure has emerged, we can analyze it so see what we think of the structure and see what changes should be made. This is when I think we should consider moving to a templating engine or something similiar. From here we might want the output code to change slightly, if it enables us to move to a better structure, and so this step will require proper testing to be safe.
4. See what kind of simple variants we can implement to stress-test the modularity of the structure- if we cannot make even simple changes to features without changing interfaces etc., we won't be able to move to some of the more exotic variants we want to consider.

[pcineverdies]

Good morning everyone! I have a question related to the LSQ implementation. I wonder if @qianxu1998, @Jiahui17 or @murphe67 can give me some insights about my issues.

In Dynamatic as it has been since 2018, we allocate the group in the LSQ thanks to the cmerges, which follow the order of the BBs in the program's CFG. I tend to say that, as a consequence of this, at most 1 group allocation can be done for a LSQ in one clock cycle (I am referring here to allocations related to different groups connected to the same LSQ).

Do you have any idea whether the LSQ is robust enough to support allocations of different groups in the same clock cycle? Does it even make sense in the context of the LSQ?

My question arises as one of the features of Fast Token Delivery is the - so called - Straight To The Queue which allows to speed up group allocations. However, in some "safe" scenarios, the algorithm of the paper would allow multiple group allocations in the same clock cycle. Yesterday me and @rpirayadi had a fun debug session trying to understand the way the LSQ behaved in such a context, but it was difficult to navigate over its thousands of signals.

[murphe67]

Sorry for never seeing this! Honestly, I am currently trying to figure out how the hell the LSQ works- Youngjung has just finished writing his LSQ project proposal, so I'll send him the stuff for the github and then he can open an issue page, but the process of making the LSQ make sense is still very much a long-term thing.

[pcineverdies]

I see, thanks for your reply! For the records, I'll link some of the issues I think are reasonable to address asap related to the LSQ (but you probably already noted them down): #194 #111 (which was related to the Chisel implementation, but the bug was still there in the python version...)

[murphe67]

Thanks for the issues, we will take a look at them!

Do you guys have access to Hailin's thesis? Just sitting down to read it properly but-