3
\$\begingroup\$

From curiosity and to understand the cost of the operator I often using in FPGA design.

Let's assume I am doing the following equation in Verilog:

OUT = A[15:0] >= B[15:0];

How will the FPGA implement this operator? Will it just use a LUT? I don't understand how a LUT solves this logic.

More specifically if relevant I am using Quartus and Stratix10 FPGA.

This is what the RTL Viewer shows:

enter image description here

This is what the Technology Map Viewer shows:

enter image description here

I would like to understand how it is actually fitted into a Stratix10 logic cell:

enter image description here

What I understand:

I can see that in the technology viewer it is using 4 or 5 primitives with 4 inputs to calculate the inequality - meaning it's probably using 2 logic cells.

I can't imagine what the logic inside the LUT looks like.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ It's basically a subtraction operation, looking at the sign of the result. \$\endgroup\$
    – Dave Tweed
    Commented Feb 15 at 15:51
  • 2
    \$\begingroup\$ It subtracts two numbers and checks "equal 0" and sign. \$\endgroup\$
    – TQQQ
    Commented Feb 15 at 15:51
  • \$\begingroup\$ @DaveTweed So each primitive LessThan_0~X is just 4bits subtraction? that nested to each other to give result of 16bits subtraction? and how LUT implement subtraction? \$\endgroup\$ Commented Feb 15 at 15:59
  • 2
    \$\begingroup\$ The comments by Dave Tweed and TQQQ are wrong, Quartus is not implementing subtraction. \$\endgroup\$ Commented Feb 15 at 16:02
  • 1
    \$\begingroup\$ If you right click on each of the LUT primitivs in the tech viewer, and select properties, somewhere in one of the tabs it shows you the logic representation of what the LUT is doing \$\endgroup\$ Commented Feb 15 at 18:11

1 Answer 1

6
\$\begingroup\$

Let's just derive the circuit ourselves. The key is to break the operation on the input integers down into smaller pieces.

Given two numbers, for example 234 and 125, you can immediately tell that 234 is larger by just looking at their first digits. Any number of the form 2xx is always larger than one of the form 1xx.

Only when the first digits are identical do we need to look at the others. For example, let's take 148 and 125. The first digits are identical, so we move on to the second digits. Here, the digit "4" is greater than "2", so we can conclude that 148 > 125 without needing to check the last digit at all.

This is called a lexicographic comparison, and it's the key to implementing magnitude comparators in hardware.

Let's apply this to our A[15:0] >= B[15:0] operation, which is the same as A[15:0] < B[15:0] inverted. Using 5-input LUTs, we can process 2 bits at a time, using 4 of the available LUT inputs.

We'll start with the topmost two bits. There are essentially three cases:

  1. If A[15:14] < B[15:14] is true, A[15:0] < B[15:0] must also be true. The entire comparison should output 1.
  2. If, on the other hand, A[15:14] > B[15:14] is true, then A[15:0] > B[15:0] is also definitely true. The entire comparison should output 0.
  3. Lastly, if A[15:14] == B[15:14] is true, we need to look at the other bits (13 and downwards).

Case 1 and 2 are easy, only case 3 is a bit more difficult. We need to forward the result from the comparisons of the other bits... But luckily we've only used 4 LUT inputs so far, which means that we have one to spare that we can use for this purpose!

In the end, it boils down to the following pseudocode:

inputs: a[1:0], b[1:0], lessthan_in
outputs: lessthan_out

if (a < b)
  lessthan_out = 1;
else if (a > b)
  lessthan_out = 0;
else
  lessthan_out = lessthan_in

Since this block of logic only has 5 inputs and 1 output, you can map it onto a single LUT5 by evaluating it for all possible input values. (There are only 32 of them.) Now all you have to do is to repeat this for the other bit positions and chain the resulting (identical) LUTs together. In the end, you can compare two 16-bit values with eight LUT5 instances using this scheme.

I can see that in the technology viewer it is using 4 or 5 primitives with 4 inputs to calculate the inequality - meaning it's probably using 2 logic cells.

Note that this is wrong, given that it would mean there are only 20 inputs in total across all those primitives, which is insufficient to process two 16-bit integers (32 bits total). The eight LUT5s from the solution I presented have 40 inputs in total, meaning there's only an overhead of 8 inputs. This is the best you can do with 5-input primitives.

The only case where Quartus might be able to compare two 16-bit values with less than eight LUT5 instances is when some of the bits are constant. (I.e. you're not using the full range of a 16-bit integer, or skipping some values with a counter, etc)

For example, if you compare a 16-bit value to another one that only has 8 bits, you need four of the previously mentioned LUT5 instances to compare the lower 8 bits. For the upper 8 bits of the 16-bit operand, you only have to check that they're zero. You can use two LUT5s for that, with each of them checking four bits at a time, as in the following pseudocode:

inputs: a[3:0], lessthan_in
outputs: lessthan_out

if (a > 0)
  lessthan_out = 0;
else
  lessthan_out = lessthan_in;

In total, the circuit will look as follows, from LSB to MSB:

   0 -> COMP2 -> COMP2 -> COMP2 -> COMP2 -> ZERO4 -> ZERO4  -> output
bits#   [1:0]    [3:2]    [5:4]    [7:6]    [11:8]   [15:12]

Each of the "COMP2" blocks takes as input two bits from A and B respectively, and each of the "ZERO4" blocks takes four bits from the 16-bit-wide A. The arrows between the blocks represent the "lessthan" inputs and outputs of the blocks, which chain them together.

\$\endgroup\$
3
  • \$\begingroup\$ ok Thanks! but how you explain the Technology Map Viewer image? its looks like it's using 5 primitives? by the way in my real use case I am comparing 8 real bits with 16 bits (I expand the 8 bits bus to 16 to match) \$\endgroup\$ Commented Feb 15 at 16:55
  • \$\begingroup\$ @MichaelRahav A comparison between a 16-bit and an 8-bit value can be done in six LUT5 instances. (There's likely a 6th primitive to the right that's cut off on your screenshot.) You need 4 LUTs to compare the lower 8 bits, then another 2 LUTs to ensure that the upper 8 bits are zero. 5 LUTs might be possible if the range of values on the two buses is limited. \$\endgroup\$ Commented Feb 15 at 17:22
  • \$\begingroup\$ @MichaelRahav, your Technology Map Viewer image doesn't show bits 0 or 15 of the input bus being used. Possibly synthesis was able to prove that these bits never change and simplify the logic accordingly. \$\endgroup\$
    – The Photon
    Commented Feb 15 at 18:05

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.