On the design of state-machines



Over the last year I have been prototyping various embedded systems and I have used FPGAs for rapid development where many developers would use micro-controllers. With Python/MyHDL this has worked very well for me because I can simulate much of the system before I have hardware and from the early tests developed (TDD) I have a set of regression tests that allow me to quickly adapt the code and target numerous platforms (e.g. I have used the HDL base on almost every FPGA vendor).

From these efforts a few design patterns that have emerged. I want to focus on one in particular: state-machines.

In these systems I have numerous state-machines and a hierarchy of state-machines. Many of these state-machines become unyielding as source. They are minimal resources in hardware but typically require too many lines for their complexity. I have experimented with different representations but there are a couple that have significant impact: inlined methods; class based state-machines; and very-long encoding soft state-machines.

Inlined methods

I heavily use interfaces in my designs. From my perspective the use of interfaces is orders of magnitude improvement to the readability and maintainability of the code as well as enabling levels of testing (e.g. easy to use interface based transactors to build tests to the various blocks). These designs are not processor centric and thus not memory-mapped centric. Rather the various controllers and peripherals are built around ControlStatus attributes. For a set of peripherals a common ControlStatus interface emerges - one that allows the start of a command. The design patterns discussed are applicable to processor / memory-mapped designs as well.

For example, a state-machine might interface with a peripheral where it sets an external address, read or write command, and the number of bytes it wants to send or receive. A single command to the peripheral might look something like:

    # ...
    elif state == states.first_command_beg:
        if not per.busy:
            per.dev_addr.next = PER_DEVICE1_ADDR
            per.command.next = PER_CMD_WRITE
            per.num_bytes.next = 6
            per.commence.next = True
            state.next = states.first_command_end

    elif state == states.first_command_end:
        if per.busy:
            per.commence.next = False
        elif per.done:
            state.next = states.second_command_beg

This could be improved by having a method that is part of the per interface:

    elif state == states.first_command_beg:
        ok = per.write_command(PER_DEVICE1_ADDR, 6)
        if ok:
            state.next = states.first_command_end

    elif state == states.first_command_end:
        complete = per.command_complete()
        if complete:
            state.next = states.second_command_beg

If a state-machine has multiple interaction with the peripheral the use of the methods has quite an impact on the readability of the state-machine. The methods are very different from the functions that are currently convertible. It seems these functions would best converted as inline functions. The methods might look something like:

class Peripheral(object):
    def __init__():
        self.dev_addr = Signal(intbv(0)[7:0])
        self.commands = Constants(none=0, write=1. read=2)
        self.command = self.commands.signal_type()
        self.commence = Signal(bool(0))
        self.done = Signal(bool(0))
        self.busy = Signal(bool(0))

    def write_command(self, dev_addr, num_bytes):
        if not self.busy:
            ok = True
            self.dev_addr.next = dev_addr
            self.command.next = self.commands.write
            self.num_bytes.next = num_bytes
            self.commence.next = True
            ok = False
        return ok

    def command_complete(self):
        ok = False
        if self.busy:
            self.commence.next = True
        if self.done:
            ok = True
        return ok

I will cover more in subsequent replies to this thread.


This is an interesting idea. I have had occasions in my VHDL past where I used a procedure to take the same action in various states of a state machine.
Perhaps the first step would be to work on in-lining procedures, I think this could be implemented reasonably easy, as it would come down to replacing one line of code by a set of lines of code. The return value of a function is more work, but we might find the solution along the way.
I suppose that what you suggest already passes through MyHDL’s simulator? Or can you supply a complete example?


@josyb one of the gsoc students generated a proposal to work on the inline functions for the summer. That was my thought as well is that the inline functions are a reasonable task and, from my perspective, valuable.

Yes, this works in the simulator and I suppose I could generate a full example :slight_smile:


Yes, proper interface classes! This would be awesome.