Finite State Machine Synthesis In Programmable Circuits

Well, summer has been and gone; and for most of us it was a time to relax and reflect on our working practices. What can we do to achieve better results? And what can we do to break out of the routine of working on so many revisions?

For me, one of my summer break ponderings was thinking back on a trick I learned while working with my colleagues at the Silesian University of Technology.

CMOS technology is the one that has dominated all applications of digital circuits. Power consumed by a CMOS digital circuit is the sum of two components: static power and dynamic power. The static power is a characteristic feature of the technology process used, and is associated with leakage currents in steady state. The dynamic power consumed by a CMOS gate is proportional to average switching activity at the output of the gate, which describes how often the state at the gate output is changing. The dynamic power component can thus be considered and minimized in the appropriate process of logic synthesis.

The essence of logic synthesis oriented toward energy-efficiency requires finding a circuit structure in which the number of state transitions is minimized.

Switching global clock networks are responsible for a significant part of the total power dissipated by a CMOS VLSI circuit. That’s why many engineers try to block the clock signal to achieve power reductions in synchronous circuits.

Programmable Logic Devices (PLDs), and especially Field Programmable Gate Arrays (FPGAs), constitute a relatively new and rapidly developing branch of digital electronics. Constantly growing logic capacities at moderate prices make PLDs an attractive platform for not only prototyping but also short- and medium-volume production.

It is not always obvious though how best to map logic structures (resources) within a given PLD architecture when designing with energy-efficiency in mind. In particular, implementing clock gating is difficult, as PLD circuits contain dedicated clock networks, which do not contain any gating elements. “Disabling” the clock signal in PLD structures can be accomplished in two ways: firstly, by utilizing the “Enable Clock” inputs of memory elements or, secondly, by distributing the clock signal using local clock lines or general-purpose routing resources (which enable the insertion of logic gates).

Logic Synthesis of energy efficient FSMs in nutshell

Fig. 1: D function for the example FSM

Let’s consider a simple 4-state machine (figure 1) that is coded ‘one-hot’ (figure 2) to visualize the idea. We will use the Keep It Simple, Steel (KISS) format to abstract it from the HDL level. Each FSM can be implemented into an HDL model.

The state-transition function needs to be decomposed into two components: one describing the expected changes in the flip-flop states, which will be further called the “D function”, and one detecting the times at which the changes occur (this will be called the “EC function”).

Fig. 2: One-hot state assignment for FSM from Fig. 1

Fig. 3: EC function for example presented in Fig. 1.

The EC function can be easily obtained by a simple analysis of the coded FSM. Every time a change in a flip-flop state is triggered, the relevant EC function needs to be activated. However, if there is no change in the flip flop state, the EC function is indefinite. After the EC function is known (figure 3), determining the D function as well is straightforward. How can we extract the EC function? Easy. If we are using Riviera-PRO we can simply toggle the FSM coverage technology (figure 4). Results stored in ASDB can be easily exported to a SAIF or VCD file to estimate power consumption using a silicon vendor tool. High FSM or toggle coverage results are extremely important for power estimations based on simulations. The most credible results can be obtain for 100% toggle coverage at post-fitting gate-level structure (figure 5).

Fig. 4: Finite State Machine in Riviera-PRO.

Fig. 5: FSM coverage in Riviera-PRO

Conclusions
Every project can be realized using modern EDA tools and they typically provide very good results. Of course, a real FPGA-ninja can achieve much more! When we close our eyes and think about such people we picture geeks in front of a whiteboard or computer with a command line. This is not true! EDA vendors provide tools that are useful to not only newbies. They automate tedious and boring processes such that your imagination becomes the only limit.

An outline of a simple synthesis method of energy-efficient FSMs was presented in a white paper, which can be found here. I encourage you to familiarize yourself with this paper. The idea consists of using local clock gating to selectively block the clock signal, if no transition of a state of a memory element is required. The research was dedicated to logic circuits using PLDs as the implementation platform, but the conclusions can be applied to any synchronous circuit. Results obtained from experiments were most spectacular for clock gating methodology. This is another example how modern EDA tools can help us providing better solution not only at automation level but also at design and methodology stage.