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.

Major changes, the permutation generator now can transfer data to the Gaussian elimination units in blocks. I made sure this, and some other logic I’ve added, works via a large test bench (larger than the actual implementation!).

Small changes. I implemented the permutation generator in systemverilog and made a testbench for it (looks for frozen random values, zero random values (breaks xorshift), and for invalid permutation states (multiple entries point to the same thing)). I used the xorshift32 algorithm because of how cheap it is on hardware. I would have used xorshift16, but the larger state prevents exhaustion of search space. Pictured is incremental changes in simulation.

I decided to take another look at my Prange implementation before committing it to hardware. It turns out that there was a lot of room for optimization. Originally, with full optimizations, the code solved an instance at 200 dimensions in 300 seconds. At that dimension, it is estimated to have a complexity of 2^21, which means that my code was not doing too well. First things first, I started storing bits in bit arrays rather than byte arrays. Since everything was in GF(2) it was much easier to simply use an array given that C had no high performance built-in bitarray. However, C++ did. So after migrating my code base and changing everything to bitarrays (and using the same random seed, meaning same solution and work) I got it solved in 150 seconds, which is a 2x improvement! After removing some repeated allocations, making my code take better advantage of boost’s high performance block operations (64 bits xored in a cycle rather than 1 (there’s some heavy nuance to this due to how modern processors work but there is an improvement)), and making the hamming weight calculator operate along with the Gaussian elimination rather than after it, I got a further 5x boost to 30 seconds (same randomness). I got another improvement to 10 seconds when I changed the randomness (so technically there is a different amount of work but the overall trend held for other tests) and permutation logic to prevent repeated allocations and to decrease the amount of swaps that were needed by partitioning two sections at the cost of some random uniformity. Overall, I achieved a 30x speedup and now I’m able to run higher dimensions in a reasonable time.

Small updates, I fixed memory leakages and got the algorithm working at 170 dimensions instead of just 100. The next algorithm I will be prototyping will be the final one used in-hardware. In the screenshot, part of the matrix with partial RREF is shown along with a found solution after list generation and matching.

I got the Stern algorithm prototype running! While the memory complexity makes it unusable for higher dimensions (multiple petabytes at just d=200), it is able to solve small dimensions relatively quickly. This is my last prototype until I start implementing BJMM in both software and HDL.

This is my first devlog post! For now, my code is relatively basic. The problem it is attempting to solve is the syndrome decoding problem, which is used in error correction and post-quantum cryptography. I made a prototype of Prange’s algorithm, but now I am working on Stern’s, which has a higher memory complexity but better time complexity. Screenshotted is the partial RREF achieved in order to split the syndrome into two parts (one for lookup and the other for exact matching).