made the codebase slightly more readable

Minor timing improvements; I realized that the multiplication path was poor for timing. However, I found out this only increased it to about 120mhz and that BRAM latency was the real killer.

I wrote up the entire architecture updated my overall testbench. I do not know why this took so long.

Cleaned up the codebase. The final thing I need to do before the technical write-up is make the overall test bench for a performance report & overall correctness.

Fixed the permutation testbench, which I didn’t even know was broken! Apparently it broke when I changed the memory access system to flatten the 2d array, it also exposed some other bugs that have been hiding.

Well, I think this is it! I have some code hygiene to do, and I have to make the presentation video, but it’s done! I’ll be making a video presentation soon and pushing a release. Attached are some benchmark results; it’s pretty fast!

Finished the Gaussian elimination testbench! Only bugs I caught were in the testbench itself (which was expected, since I tested it in hardware before simulating). One complicated thing was to undo the row swaps, I had to scan the identity matrix.

I’ve been running benchmarks. So far, the largest challenge I’ve been able to solve has an error length of 280 and a weight of 35, it took 13 hours and was externally verified.

It’s done. This script receives, from UART, the columns needed for the error. However, due to the nature of the algorithm, it also contains non-error columns. With one RREF run on the permutated matrix we can recover the error vector. I have to clean the code up globally and finish the Gaussian elimination testbench before I start thinking about writing this up, benchmarking it, and publishing it.

Implemented the UART logic, unfortunately there was a fire that led me to evacuate my house so I can not test it on my FPGA. Pictured is the top-level logic. (Each green block is a single unit, each unit contains one permutation unit and one Gaussian elimination unit).

Got it to synthesize and work, it’s faster than my CPU implementation!

Almost done rewriting the Gaussian elimination module. Today I worked on the elimination part and finished the selection part. It’s really hard because all memory accesses are pipelined, and what’s worse is that the depth is >4, making it complicated enough where I need to diagram. Below is the RTL view, you may notice some tall stuff, that’s free list access, but besides that it’s highly optimized. All that’s left for this module is bitcounting & stalling, which are both trivial, however the testbench is a different story.

This is the new RTL view for the permutation! After changing some logic and fixing the testbench today I don’t think it will look much different in the future. The long thing is a 32 bit seed being used in the xorshift32 algorithm (a PRNG). Today I worked on the Gaussian elimination unit, there is a lot to do to move it into BRAM. First, I have to adapt it to receive the permutated matrix, which is the easy part. Everywhere else the architecture heavily diverges. I will be scanning the columns to build a list (in BRAM) of every row I need to eliminate, at the same time I will use a free list to prevent using an already-used row (which would break the algorithm) and select a row to use for elimination (and rename and allocate it to prevent re-use and actual swaps). During the elimination step, I will fetch the current word used for elimination, then eliminate every row in the list for the current word. I will repeat until it is done. Additionally, I’ll save some time by skipping unneeded words at the beginning (which should be all zero in our selected row by construction). The bit count implementation is pretty easy, all I need to do is read the new syndrome bits in many cycles, adding them together, then comparing against a constant. Most of this is not yet implemented, but progress is being made!

After an excessive amount of work, the permutation stage is now fully BRAM and the testbench is updated to match. This required renaming, state machines, multi-cycle delays, look ahead memory accesses, etc. I am very happy it is done, however the bigger beast (Gaussian elimination) is up next.

Spent the entire day trying to refactor the permutation logic to use BRAM. So far, I was able to get the static matrix put into BRAM. I am currently working on getting the permutation matrix and snapshots put into BRAM. To prevent excessive logic or stale periods I am implementing a renaming system that allows for quick swaps of permutation matrixi. The testbench works for the static matrix in BRAM, but since the permutation logic is still being adapted to BRAM I am not near finished.

RTL view or Factorio map?

If you guessed RTL view, you would unfortunately be correct. My naive architecture was not a great idea! Pictured here is only 2% of the problem, the other 97% is the Gaussian elimination unit which doesn’t manage to load in RTL view even after an hour of waiting. Why? Muxes. I treated access into a 20k entry bitarray as cheap, which was not very smart, especially since I did multiple reads/writes in a single cycle (which duplicates logic). As a result, I am currently refactoring the codebase to store more things in BRAM. This will come at a heavy, heavy, heavy performance cost, but at least it’ll be synthesizable and the units may be duplicatable. This will require me to rewrite the permutation unit, the Gaussian unit, and both testbenches. Essentially 10 hours of work are down the drain.

I am in the testing stage of the Prange implementation, simulation is really slow, so it will take a while. So far it has been running for an hour without a solution. However, other testbenches and results show that there likely will be a solution in some time.

I wanted to one-up my time from yesterday so I continued working on my project. I implemented a fully randomized testbench of the new unit’s (responsible for gaussian elimination and hamming weight calculation) receiving protocol, hamming weight calculation, solution correctness, and more. Overall I found a few major bugs, but they’re all fixed now. My Prange implementation is nearly complete!

This has been an undertaking, I present to you, a very very tunable Gaussian elimination unit in GF(2). This is essentially a state machine that copies over a partial permutated matrix from the other permutation unit, then it finds a non-zero coordinate for the current column, swaps, eliminates, and repeats. Afterwards, it does a hamming weight calculation to see if it’s equal to our needed weight, if yes then it stalls, otherwise it requests another matrix and restarts. The hardest part of this was making every parameter tunable, because doing so allows us to later use something like an evolutionary algorithm to reach a theoretical optimal design for a given dimension.