1

I am trying to port my k-nearest-neighbor code (in MATLAB) to Verilog so that I can use it in my design and ultimately put on a FPGA board. Now the code and its operations are fairly simple in MATLAB because things like making null and identity matrices, or multiplying 2D matrices are conveniently handled by prebuilt functions. I am trying to do the same in Verilog, but without the use of 'for' loops as they are only to be used in parallel structures and not terribly efficient (right?). I can handle one dimensional arrays, but I can't seem to think of anything for the 2D matrices that would be efficient (or at least as efficient as it can get on hardware). Any advice would be helpful.

Thanks in advance!!

2 Answers 2

2

Unfortunately I think this is going to end up being a much bigger project than you anticipated.

Remember that verilog is not a programming language, but rather a hardware description language. It knows not that you are trying to perform large mathematical computations, a single multiplication operation of two numbers is the highest level of abstraction you can get.

Therefore you have to think about all of the individual add/multiply operations that go into a matrix multiplication, and think about how to write a state machine that can perform each one of these operations while keeping track of all the intermediate products.

Even a 4x4 matrix multiply needs over a hundred addition/multiplication operations, and you're going to have to describe a processor that is aware of and can keep track of all of these.

Rather than being a one line statement, I would guess that to someone new with Verilog this could be a multi-week project to plan, write, and verify a matrix multiplication circuit. I know this is not a concrete answer, but just wanted you to be aware of the scope of this project.

If you want to attempt it, start by deciding how many parallel multipliers and adders you can afford to instantiate, and then start thinking about how to write a state machine that can keep track of all the individual add/multiply operations, and then how to farm out all those operations in parallel to all of the multipliers and adders you have available in as few clock cycles as possible.

4
  • Yes, I am aware of the limitations of a HDL. Infact, I just implemented a custom AES implementation on a board, so I know how painfully long it takes to plan and map each unit. However, since this code is relatively easier, I thought it would be less of a headache. Can you point me to some reference code for large multipliers?
    – Sam29
    Oct 3, 2013 at 18:56
  • I got a couple potential hits by searching opencores matrix multiplication, might want to check those out. @Sam29
    – Tim
    Oct 3, 2013 at 21:09
  • thanks for the help. Right now, since I just want to "convert" the code to Verilog, efficiency isn't too important to me (at the moment, ofcourse. The whole mapping thing will be thought of later). However, I just wanted to know and avoid bad coding practices in Verilog for such operations.
    – Sam29
    Oct 3, 2013 at 22:30
  • Maybe a systolic architecture would help?
    – Renato
    Dec 14, 2016 at 14:34
0

The for loop is your friend, but only when it's used in a generate, and not in sequential code (always/initial/function/task). Sequential for loops can potentially lead to convoluted hardware if you're not careful.

You can basically code this in the same way as you would in any other language, with the (major) problem that you can't pass arrays through module ports. Working tested example below. This would be a lot easier and clearer in VHDL (and probably SV, which I don't use). If you're going to do a lot of this sort of thing and you're just starting you should change language.

The hardware for the 3x3 square matrix multiply below is fast, at the expense of lots of hardware. It generates 9 MAC units, each of which requires three multipliers and two adders. you'll need to think about bit widths; the code as it stands assigns the MAC result to an 18-bit value, which won't work in general (the code simulates correctly because the values in A and B are small).

You need to think about resources and timing. If you haven't got 27 multipliers and 18 adders, but you don't need the answer in a hurry, then share them. In the limit, you can build very compact serial hardware, at the expense of lots of cycles and complex control.

module top;

   wire[17:0]A[1:3][1:3];    // the matrices
   wire[17:0]B[1:3][1:3];
   wire[17:0]C[1:3][1:3];

   wire[(9*18)-1:0] Abits;   // bit-decomposed versions of the above
   wire[(9*18)-1:0] Bbits;
   wire[(9*18)-1:0] Cbits;

   genvar i,j;

   // set A and B with initial values
   generate 
      for(i=0; i<3; i=i+1)
         for(j=0; j<3; j=j+1) begin
            assign A[i+1][j+1] = i*3 + j;
            assign B[i+1][j+1] = i*3 + j + 1;
         end
   endgenerate

   // decompose A and B, set C
   generate 
      for(i=1; i<=3; i=i+1)
         for(j=1; j<=3; j=j+1) begin
            assign Abits[(((i-1)*3 + (j-1)) * 18)+17 -:18] = A[i][j];
            assign Bbits[(((i-1)*3 + (j-1)) * 18)+17 -:18] = B[i][j];
            assign C[i][j] = Cbits[(((i-1)*3 + (j-1)) * 18)+17 -:18];
         end
   endgenerate

   initial
      #1 $display("%4d %4d %4d\n%4d %4d %4d\n%4d %4d %4d\n",
                  C[1][1], C[1][2],C[1][3],
                  C[2][1], C[2][2],C[2][3],
                  C[3][1], C[3][2],C[3][3]);

   mmult3x3 U1(Abits, Bbits, Cbits);
endmodule

module mmult3x3
   (input  wire[(9*18)-1:0] AI,
    input  wire[(9*18)-1:0] BI,
    output wire[(9*18)-1:0] CO);

   wire[17:0]A[1:3][1:3];
   wire[17:0]B[1:3][1:3];
   wire[17:0]C[1:3][1:3];

   genvar i,j;

   generate 
      for(i=1; i<=3; i=i+1)
         for(j=1; j<=3; j=j+1) begin
            assign A[i][j] = AI[(((i-1)*3 + (j-1)) * 18)+17 -:18];
            assign B[i][j] = BI[(((i-1)*3 + (j-1)) * 18)+17 -:18];
            assign CO[(((i-1)*3 + (j-1)) * 18)+17 -:18] = C[i][j];
         end
   endgenerate

   // this is the bit that matters - everything else just works around shortcomings 
   // in the language:
   generate 
      for(i=1; i<=3; i=i+1)
         for(j=1; j<=3; j=j+1)
            assign C[i][j] = A[i][1]*B[1][j] + A[i][2]*B[2][j] + A[i][3]*B[3][j];
   endgenerate
endmodule
3
  • That is some interesting code. I used almost the same thing to initialize the matrices. Anyways, I was wondering if it would be better to treat each row as a separate array and perform ops on it, then get the second row at the next clock etc. That way, I will only have to deal with a fixed width array (say 128 bits). I know this is a rather vague question (you can't say if that will work unless you know what kinda operations I am talking about). But for complex operations, is it an option?
    – Sam29
    Oct 5, 2013 at 13:00
  • Not sure that I really understand you. The inner loop operates on one complete row and one complete column at a time, producing one single result, and this inner loop is replicated 9 times over, to produce all 9 results (for a 3 by 3) 'simultaneously', ie. in the same clock cycle. This only makes sense if you have enough multipliers and adders to do the whole matrix multiply in one cycle. Start by deciding how many multipliers and adders you have, how many you need, and how many clock cycles you've got. Now draw a circuit diagram. After that, the coding is easy.
    – EML
    Oct 6, 2013 at 20:10
  • Nevermind, I found the answer to my own question. But what I was saying was: since Verilog won't accept 2D arrays as input from an input port, I would have to get the data 'one row at a time' and then store the data in a temp 2D array. This would take M clock cycles for M rows, right? And then once I am done getting the input and storing it in a 2D matrix, I can use your suggestion, right?
    – Sam29
    Oct 8, 2013 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.