Thinking software at the RTL level

hdl-design myhdl

Introduction

In my essay The Case for a Better HDL I called the analogies between HDL design and software development "obvious and beautiful". From this observation, I suggested that a "software perspective" would be very useful for certain HDL design tasks. My goal with this essay is to put that idea into practice at the RTL level.

As an example, I chose a Gray counter that uses the Gray code word itself as the state. This example builds further on the reference model for Gray codes that I developed in my essay Why HDL designers should learn Python. That reference model can be used to verify the RTL design.

You can find prior art for this design on the web. In particular, Altera has published a Verilog and VHDL solution. However, I think we can do much better by using a "software perspective".

The algorithm

The first task is to develop an algorithm. Recall that successive words in a Gray count sequence differ in a single bit. The purpose of the algorithm is thus to find the bit to toggle for any given Gray code word. Let's consider the first steps in a 4-bit Gray count sequence:

For even steps, the bit to toggle is always the lsb at position 0. As a single bit changes at each step, the corresponding words share a common property: even parity. This part of the algorithm is easy enough: for even parity words, toggle the lsb.

For odd steps, the solution is a little more complex. It turns out that you have to find the first 1 in the word, starting from the lsb. The bit to toggle is located at the next higher position.

The remaining problem is to combine even and odd steps in one algorithm. The idea I had is to construct a new word by shifting the Gray code word one bit to the left. For odd steps, the first 1 in that word gives you the exact position to toggle. Moreover, the lsb position is now vacant. If you put the even parity bit in there, the first 1 in the word should give you the position to toggle for all cases.

This works fine, except for Gray code word "1000". If you shift this word to the left, all 1's are gone, so we don't know what position to toggle. Upon inspection, this word should be followed by "0000". Therefore, the solution is to set the msb of the shifted word unconditionally to 1, as a fallback solution. The final algorithm is as follows:

Given a Gray code word G = { g[n-1] g[n-2] g[n-3] ... g[0] }, with g[k] the individual bits of the word:

construct a new word W = { 1 g[n-3] ... g[0] p }, with p being the even parity bit of G
starting from the lsb at position 0, look for the first 1 in W
toggle the bit in G at the corresponding position

RTL coding

Coding at the RTL level means describing the hardware behavior in a single clock cycle. Therefore, if an algorithm requires a number of steps, you have to code it as an FSM so that the behavior depends on the state you are in. The resulting code is fairly low level. For example, a loop is emulated by explicit transitions between states.

However, there is an interesting special case. When the algorithm is simple enough to complete within a single clock cycle, you can use higher level features such as a for loop to describe the behavior in a straightforward way. Clearly, that is the case for the Gray counter example.

Here is the resulting MyHDL code:

def gray_counter(gray_count, enable, clock, reset):

    n = len(gray_count)
    gray = Signal(intbv(0)[n:])
    even = Signal(bool(1))

    @always_seq(clock.posedge, reset=reset)
    def seq():
        word = concat('1', gray[n-2:], even)
        if enable:
            found = False
            for i in range(n):
                if word[i] == 1 and not found:
                    gray.next[i] = not gray[i]
                    found = True
            even.next = not even

    @always_comb
    def alias():
        gray_count.next = gray

    return seq, alias

As you may not be familiar with MyHDL, let me first show the equivalent Verilog and VHDL. Synthesizable MyHDL can be converted to Verilog and VHDL automatically. The following is the relevant part of the output Verilog code, for a bit width of 8:

reg even;
reg [7:0] gray;

always @(posedge clock, posedge reset) begin: GRAY_COUNTER_8_SEQ
    integer i;
    reg [8-1:0] word;
    reg found;
    if (reset == 1) begin
        even <= 1;
        gray <= 0;
    end
    else begin
        word = {1'b1, gray[(8 - 2)-1:0], even};
        if (enable) begin
            found = 1'b0;
            for (i=0; i<8; i=i+1) begin
                if (((word[i] == 1) && (!found))) begin
                    gray[i] <= (!gray[i]);
                    found = 1'b1;
                end
            end
            even <= (!even);
        end
    end
end

And this is the equivalent VHDL code:

signal even: std_logic;
signal gray: unsigned(7 downto 0);
...
GRAY_COUNTER_8_SEQ: process (clock, reset) is
    variable word: unsigned(7 downto 0);
    variable found: std_logic;
begin
    if (reset = '1') then
        even <= '1';
        gray <= (others => '0');
    elsif rising_edge(clock) then
        word := unsigned'("1" & gray((8 - 2)-1 downto 0) & even);
        if bool(enable) then
            found := '0';
            for i in 0 to 8-1 loop
                if ((word(i) = '1') and (not bool(found))) then
                    gray(i) <= stdl((not bool(gray(i))));
                    found := '1';
                end if;
            end loop;
            even <= stdl((not bool(even)));
         end if;
    end if;
end process GRAY_COUNTER_8_SEQ;

Analysis of the RTL code

You can now go over the code in your favorite HDL. As this is a hardware description, I have added a clock, reset, and enable signal. Also, I made even part of the state by toggling it at each step.

Apart from this, the code is a straightforward implementation of the algorithm. As expected from a Gray counter, it is clear that a single bit is toggling. Moreover, anyone with some programming experience can easily reconstruct the algorithm from the code. The clarity of the code is a great advantage, because code is read much more often than it is written.

Variables word and found play a key role. word combines information like suggested in the algorithm, so it can be used in a for loop later on. found keeps track whether the bit to toggle has been found already. The power of variables is that they provide this type of "combinatorial" and "dynamic" semantics within a clocked process.

Those unfamiliar with this coding style may worry about synthesizability. However, synthesis tools have no problem with this kind of description. They will unroll the for loop and map the decision tree to a multi-level logic network.

The message

At this point, I would like to elaborate on what I mean with "thinking software at the RTL level." I have solved a hardware design problem by using a "software perspective". First, I developed an algorithm. Then I have used HDL language features to write code that resembles it as closely as possible. I haven't talked about hardware concerns much, because I know that synthesis tools create efficient implementations from this kind of description.

The alternative, much advocated strategy is "thinking hardware". Initially, this may sound like obviously good advice. However, upon reflection, "thinking hardware" is meaningless without a specification of the kind of abstractions one should use.

In practice, RTL hardware thinkers have their abstractions wrong: they try to think like a synthesis tool themselves, instead of like synthesis users. They typically advocate to "visualize" the design schematic first and then code the HDL accordingly. Also, they want to understand the direct hardware implications of every single line of HDL code, which is often a futile exercise. The problem with this approach is clear: one will never come up with a clear, algorithm-driven solution like the one I have presented for the Gray counter.

Let me be very clear though. The message of this essay is not that hardware concerns don't matter. On the contrary, the message is that one must understand synthesis capabilities in order to have more time for concerns that actually do matter. RTL synthesis tools will not help with tasks like architectural choices, design partitioning or power management. That is where valuable engineering time should go to, not to tasks that synthesis tools can do much better. And to complete the analogy: in concept this is exactly how good software engineers relate to their compilers.

If you would like to check the design yourself, you can find the code here. I have used the MyHDL converter to generate Gray counters in Verilog and VHDL for a number of bit widths between 4 and 32.

A warning to conclude

As a final point, I have to warn you that the conventional wisdom in HDL design is a major obstacle to put the presented ideas into practice. In particular, many guidelines and experts strongly discourage the use of variables in synthesizable code, and consequently the coding paradigm that I have used here. This matters, because the choice of a coding paradigm is not neutral. A solution that is straightforward with one paradigm may be quite cumbersome with another. The design problem in this essay is a good example.

The conventional wisdom has it all wrong. There is ample evidence that local variables in clocked processes are very useful, safe and fully supported. May this essay be an invitation for HDL designers to form their own opinions based on real evidence and experiments.

Thinking software at the RTL level 08-Jun-2014