Chisel Synchronization

Question

Here is a description of one of the states in my state machine. What I would like to do is to go to the next state after the for loops.

is(s_multiplier){
      when(ready){state := s_ready}
      // Initialization of C memory to 0
      for(i <- 0 to matrixSize - 1){
        for(j <- 0 to matrixSize - 1){
          memC.write(i + j, 0.asSInt((2 * cellSize).W))
        }
      }
      // Objective 1 : Multiplication for the 128X128
      // Objective 2 : Multiplication for the n.m and m.p size parameters given
      for(i <- 0 to matrixSize - 1){
        for(j <- 0 to matrixSize - 1){
          sum := 0.asSInt(cellSize.W)
          for(k <- 0 to matrixSize - 1){
            sum = sum + memA.read(i * matrixSize + k, true.B) * memB.read(k * matrixSize + j, true.B) 
          }
          memC.write(i * matrixSize + j, sum)
        }
      }
      ready := true.B
    }

I just created a boolean variable ready that I put to true after the loops. But as everything is supposed to be executed in parallel, I Don't think that my code is correct :/

Chick Markley Chick Markley · Accepted Answer · 2019-11-25T06:21:51

There is a fundamental difference between writing software algorithms and using chisel to construct the hardware necessary to perform equivalent calculations.

Before discussing the matrix multiplication, consider (as a simpler example) your memory initialization operation loop. The way you have done it makes sense, but for hardware every time the inner body of the loop is executed the hardware necessary to init that memory cell is added to the hardware graph. That means you have created the necessary wires to initialize 16384 memory locations all at the same time. That a lot of wires. Not only that, it would require a memory that has 16384 write ports (you probably can't find that). Your hardware would initialize all this memory in one clock cycle, which is good, but by devoting an enormous number of gates to do so.

Typically one would initialize memory over a number of clock cycles and in this way reducing the amount of hardware required.

Similarly in the matrix multiplication section you are generating all the hardware necessary to compute a matrix multiplication in 1 clock cycle. This is great for performance but the number of multiplications required for this approach is 2,097,152 hardware multipliers plus a further large number of adders. Every * and + operation in the inner loop generates hardware. The number of gates required to multiply two 32 bit numbers is roughly 1024 gates.

The way to go about this is to figure out a way of breaking down the problem into stages. Maybe this would be module that can multiply one row by one column and sum the total. You would then need to use registers to work your way through the matrix, keeping track of the row and columns in order to compute the value at every point in the result matrix. In order to reduce the number of hardware elements you instead perform the calculation over multiple clock cycles keeping state information (indices to the rows and columns) on the progress of the calculation in registers or in memory.

There's a lot of ways to try and optimize a function this and Chisel is a great language for experimenting and testing out tactics.

Maybe you want to make the memory very wide to accommodate getting multiple cell values at once.
Maybe you will unroll your loop a bit more to compute multiple cell values at once by having more than one cell calculator.
Clever iteration strategies can optimize your memory accesses for both reading and writing.

The point is that writing hardware is not necessary harder than writing software (and Chisel helps there) but it is pretty different in the approach.

I would recommend you spend a little more time with Chisel bootcamp. The 2.3_control_flow page's section on sorting is pretty similar with respect to the discussion above. You can write a one cycle sorter but the size of the hardware to do it grows rapidly, in practice it is necessary to break the problem into pieces and spread the calculation over multiple cycles.

Good luck.

Chisel Synchronization

1 Answers