-4
\$\begingroup\$

Here are two equivalent ways of writing an 8-bit parity generator in VHDL 2008:

    parry      <=  (((d(0) xnor d(1)) xor (d(2) xnor d(3))) xnor
                    ((d(4) xnor d(5)) xor (d(6) xnor d(7))));
    not_parry  <=  not parry;

    sum_even   <=  (parry nand odd ) and (not_parry nand even);
    sum_odd    <=  (parry nand even) and (not_parry nand odd );

and

sum_even  <=  (xor d) xor even;
sum_odd   <=  not sum_even;

The first is a literal translation of the 74180, and the second the most obvious formulation. Assume the first variant is optimized for area and speed (it's in the datasheet) but we don't want to write that because it is more verbose than the second variant.

Can we trust that a good synthesis tool will generate a netlist that is just as optimal as the first variant?

Is the answer that, for most combinational circuits, it doesn't matter if synthesis produces results that are a few percent off the optimal?

\$\endgroup\$
17
  • 6
    \$\begingroup\$ There will be no definitive answer. It depends on the complexity of the design to implement, the target system (FPGA don't have single gates, just macro cells), the experience of the human designer, the quality of the synthesis software, and so on. This question leads only to opinions. -- I once cramped a design into a CPLD that filled about 90% or so. This worked only by shuffling around pins and some manual "hints". \$\endgroup\$ Jul 30 at 12:23
  • 7
    \$\begingroup\$ If a synthesis tool wouldn't get trivial stuff like this optimized, it wouldn't be able to cope with any adder, multiplexer or even state machines at all. \$\endgroup\$
    – asdfex
    Jul 30 at 12:25
  • 5
    \$\begingroup\$ You first have to start by defining what you mean by "optimal". You can only assume that your first implementation is optimized for some particular tradeoff between area and speed, because it is nearly impossible optimize both at the same time. Furthermore, as others have pointed out, the definition of optimal depends heavily on the target technology. LUTs vs. gates, the delays of interconnects, etc. \$\endgroup\$
    – Dave Tweed
    Jul 30 at 18:16
  • 2
    \$\begingroup\$ Asking if "Can designer beat synthesis tool" has no definite answer. Because these tools are also built by intelligent engineers who might have validated the tool over thousands of iterations and scenarios like this. So, in effect you are asking to compare their intelligence with the designer. Which is opinionated. \$\endgroup\$
    – Mitu Raj
    Jul 30 at 22:18
  • 2
    \$\begingroup\$ @MituRaj That a designer might be able to beat a synthesis tool does not mean that that designer is more intelligent than that tool's author. \$\endgroup\$ Jul 30 at 23:58

3 Answers 3

6
\$\begingroup\$

Can a digital designer beat synthesis tools?

The synthesizer will likely always find an optimal solution for any reasonably simple Boolean function.

To be useful, HDL needs to run on some sort of target hardware (either ASIC or FPGA). A good designer will structure the overall logic in their design to make efficient use of the hardware. That's where you will find the most gains. Not by trying to beat the synthesizer but by figuring out how to use it efficiently.

Regarding FPGAs, Xilinx (recently bought by AMD) controls like 90% of the FPGA market, so I will use them as an example.

I don't know of any FPGAs that synthesize AND, OR, NOT, XOR gates directly. Typically, all of your functions are made from LUTs (look up tables). If you take for example, a Xilinx 7 series FPGA it will have 6 input lookup tables.

No matter what the Boolean expression of that function is, any function of up to 6 inputs will most likely be synthesized from a single LUT6 hardware element in one of the slices.

On Xilinx 7-series FPGAs, the logic is divided into units called slices that each contain four LUT6 elements. Each slice also contains hardware multiplexors called the F7 and F8 mux. These mux elements allow you to combine all four LUT6 elements in that slice to make any function of up to eight bits.

So, an 8-bit parity function could be implemented as an 8-bit function made from four LUTs in the same slice + the F7 and F8 mux in that slice. This will give you the highest performance.

An 8-bit parity function could also be implemented as two LUT6 elements chained together. The result of the first 6 bits is calculated in the first LUT6. That output plus the other two bits feed into the next LUT6. This uses only two LUTs but likely runs at about half the frequency (since there is propagation delay from two LUT elements).

A possible implementation of an 8-bit parity function implemented as 4 x LUT6 elements in a slice is shown below.

enter image description here

\$\endgroup\$
1
  • \$\begingroup\$ LUTs operate significantly faster than any clocked elements in the design, so in this simple example chaining 2x LUT6s together will likely not impact max frequency IF there are registers (i.e. clocked elements) on the input & output. \$\endgroup\$
    – ks0ze
    Aug 3 at 0:03
5
\$\begingroup\$

For logic crunching of combinatorial HDL into combinatorial gates i.e. LUTs, then the synthesis tool will produce exactly the same firmware.

I've actually done the exercise you're describing and much more, radically changing HDL and producing the same logic.

This was several times in the past, when I've had to rewrite some existing cryptic VHDL into a new readable source file while ensuring that the compiled result is unchanged. That means compilation produces a programming file with the same CRC. Sometimes I recompiled about 30..50 times, at a guess.

To do this, I'd take combinatorial logic expressed in concurrent statements (sometimes a single line, sometimes a series of lines), processes, functions etc. and rewrite them into other concurrent statements, processes and functions. The new form and structure would often be very different to the previous one but it compiled to exactly the same logic circuit.

When you involve registers, such as DFFs, in the circuit, you have to be careful what you're changing. But combinatorial paths are fine.

Personally, I think it's somewhat a conceit in the very small strain of engineers who think they'll out-think the synthesis tool and produce better circuitry that it would. If your HDL implies what you want clearly enough, synthesis will nearly always infer the best implementation of the circuit from it.

So it's more about designing circuits in HDL that can produce a practical circuit. Once that can meet the speed and gate count targets, plus allow for any future expansion of it. It's best to put all one's efforts into doing that well.

And that comes down to always designing a logic circuit then implementing it in HDL. Don't write wish-list HDL, instead imagine how the circuit will have to be built, how simply and efficiently it can be made from LUTs and registers. You don't have to actually sketch it out in full gates. But have a rough picture of the blocks involved and how big or slow they might be. Always pick the design that's as simple as possible.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Sounds similar to high-level programming languages compiling to assembly: being aware of how asm works can sometimes let you hand-hold the compiler toward an efficient asm implementation. With VHDL being I think closer to the metal than for example C++ is to x86 assembly, and with the choice of what hardware functionality to use being much more restricted (always just LUTs), I'd guess it's a lot rarer for there to be an efficient implementation you can't get the compiler to make with the right source code. \$\endgroup\$ Jul 30 at 21:30
  • \$\begingroup\$ (Even the best software compilers like GCC/clang, minor missed-optimizations are common, and sometimes subtle but not-so-minor in effect. Not to mention SIMD auto-vectorization strategies... Like I said, software targeting assembly language has a much bigger "search space" for how to implement a program than VHDL -> FPGA, I think, so your answer makes sense) \$\endgroup\$ Jul 30 at 21:33
  • \$\begingroup\$ Anyway, key point: if you want to consider the hardware capabilities, think about it in terms of giving the compiler something it can implement efficiently, not in terms of doing it yourself by hand. That's usually true for software as well. \$\endgroup\$ Jul 30 at 21:35
  • 1
    \$\begingroup\$ @PeterCordes That's a good analogy. In software you can't beat the assembler (because it just translates to machine code), but with some effort and good knowledge of the target architecture you can in many cases beat a C compiler. But most of the time, it isn't worth the effort to write assembler code for N architectures. It seems to me that for combinational logic a synthesizer is more like an assembler than a compiler. \$\endgroup\$ Jul 31 at 0:16
  • \$\begingroup\$ @BjörnLindqvist: Oh yeah, that's a good way to make an analogy. (But fun counterexamples of "beating the assembler" for variable-length instruction sets like x86: Why is the "start small" algorithm for branch displacement not optimal?. Or microarchitectural quirks: the short 2-byte encoding of adc al,0 runs as 2 uops even on Skylake; And hand-holding NASM to a faster but larger addressing mode for LEA, or knowing to save a byte with vpxor xmm15, xmm0,xmm0) \$\endgroup\$ Jul 31 at 1:20
1
\$\begingroup\$

It only matters to humans doing a bit of intellectual sparring to come up with a design better optimised for this, or that, while using a defined set of components. The hardware equivalent of code golf if you will.

In practice, what a synthesis tool does is to meet constraints, with whatever hardware it has available to use. This hardware is rarely simple gates as you show in your question, but larger blocks which often contain multi-input LUTs, able to implement any binary function of a handful of variables.

The typical constraint is timing, is it fast enough? This is not just a local constraint, as the signals have to get through the FPGA routing from here, and get over to there within a constraint. While a designer who fancies himself as a brilliant logic optimiser might make a good fist of designing a single logic block, handling all the fabric delay issues would rapidly make him delegate that drudgery to the tools.

Change vendors, or even families within the same vendor, and the available logic may change totally. No problem to the synthesiser, but it's just trashed all your optimised blocks.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ So the answer is that most of the time it doesn't matter that the synthesized design is a little worse than the optimal as long as it meets constraints? \$\endgroup\$ Jul 30 at 13:26
  • 5
    \$\begingroup\$ @BjörnLindqvist Costs and development time are often included in "optimal". \$\endgroup\$
    – DKNguyen
    Jul 30 at 18:31
  • 2
    \$\begingroup\$ Any function that fits within one LUT (no matter what it is), will likely just synthesize as one LUT, so the hardware will be exactly the same no matter what the original equation was. \$\endgroup\$
    – user4574
    Jul 30 at 21:11
  • \$\begingroup\$ But this function has 10 input bits and 2 output bits. That takes more than a few LUTs doesn't it? \$\endgroup\$ Jul 31 at 0:00
  • 1
    \$\begingroup\$ @BjörnLindqvist Once you pass 6 inputs there are some implementation choices. This particular function can be implemented as either two LUT6 elements if you are optimizing for area, or four if you are optimizing for speed. Note that inversion of the output you basically get for free either at the IO pin or at the input of the next LUT. Therefore, the device likely won't need to generate separate sum_even and sum_odd signals. \$\endgroup\$
    – user4574
    Jul 31 at 16:24

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