Low-power Finite-State Machine (FSM) design

Introduction

Power consumption in a synchronous FSM can be reduced by partitioning it into a number of coupled sub-FSMs where only the part that is involved in a state transition is clocked. By using dynamic power managment, the dynamic power consumption can be reduced. To have an efficient implementation architecture for finite-state machines, we have proposed the usage of asynchronous circuits for controlling the partitioned FSM.

Background on "dynamic power management"

Dynamic power managment is a concept that includes various design methods and techniques and is based on shutting down the parts of the circuit that are not currently active. In digital CMOS design, this is usually accomplished by stopping the clock signal to the part to be shut down. This technique is referred to as clock-gating. Planning for dynamic power management is a part of the structural decomposition of a system. This activity starts at the very beginning of the design process. Here, most of the design work is done manually because the abscence of tools. In general, manual design reduces the design space that can be explored. Here, clock-gating can only be introduced for a small number of places where the different units are well separated and therefore easy to identify. For large circuits, such as complex microprocessors, functional units can be shut-down when not used. Examples of such units are cache memories and floating point units. This type of coars-grained gated-clock technique is possible to apply manually by the designer thanks to the smal number of places where clock-gating is introduced and to the fact that the different units are easy to identify. In order to do fine-grained clock-gating, a single functional unit is partitioned into several sub-units where each of them are conditionally clocked by a gated-clock signal. An automated procedure is needed for synthesizing the original design description to a gated-clock implementation optimized for power. The number of places where the clock is gated increases and in becomes less obvious as to how to partition the unit.

Low-power FSM design

There are three commonly used low-power FSM design techniques. The first is state assignment for low-power that reduces the switching activity in the state register and in the transition function. The second and third techniques, gated-clocks and input-disabling, are two similar techniques that shut down the parts of the design that are not active (dynamic power management). In general, clock gating provides FSMs with lower power consumption than the state assignment technique. The FSM is decomposed into two or more sub-FSMs. Only one is clocked at a time, which leads to lower dynamic power consumption. The sub-FSMs interact with each other through a simple protocol. The interaction protocol handles the activation and de-activation of the sub-FSMs. The amount of power that can be saved by partitioning the FSM is mainly determined by two factors: 1) how well the partitioning algorithm can cluster strongly connected states together in sub-FSMs, 2) how large the cost is, in terms of power, to make a state transition from one sub-FSM to another (i.e. to detect idle states and shut-down idel parts).

Low-power FSMs with mixed synchronous/asynchronous implementation

Most work on low-power FSM uses some implementation architecture that is based on a number of separate modules, one for each sub-FSM, and a number of circuits takes care of the hand-over from one sub-FSM to another when there is a state transition that crosses the boundaries of the sub-FSMs. When analysing fully synchronous implementation architectures, it is clear that the power-overhead in circuits handling the hand-over is substantial. There are two main reasons for that: 1) In a synchronous FSM, it is only possible to complete one state change in one cycle. A hand-over from one sub-FSM to another requires two state changes (the source sub-FSM must go to a sleep-state and the destination sub-FSM must go from its sleep-state to an active state). Within the synchronous framework the only solution is to clock both sub-FSMs simultanously at a hand-over. This will of course increase the power consumption for these crossing transitions (almost double). Another drawback with synchronous hand-over is that extra capacitive load is added on the free-running clock and will add to the power consumption.

We propose to use asynchronous circuits for controlling enabling, disabling, and hand-over for the sub-FSMs. An asynchronous circuit is not bound to clock cycles for its operation which makes it possible to make a hand-over within one clock cycle only clocking one sub-FSM at the time. In addition, the asynchronous circuits does not add any capacitance on the free-running clock signal. The power consumption for the synchronous and asynchronous solutions are shown in the figure below.

To really make low-power FSMs based on this implementation architecture, an CAD-tool for optimizing the original FSM is needed. We have developed a tool, called LIFS, that takes a State Transition Graph (STG) together with staticstical information for the input signals and technology information as inputs for the optimization. The output from LIFS is a synthesizable RTL code (now only VHDL) that could be fed into any rtl synthesis tool (like Design Compiler) to obtain a gate-netlist. An overview of LIFS is shown in the figure below.

The average power reduction we have obtained from LIFS on the MCNC benchmarks is 45%. The best result we got on the benchmarks was 68% power reduction.

Some of the papers we published that are related to LIFS:

1. Bengt Oelmann, "Design Model for FSMs with Mixed Synchronous/Asynchronous State Memory," manuscript submitted for publication, 2001.
2. Bengt Oelmann, Kalle Tammemäe, Margus Kruus, and Mattias O'Nils, "Automatic FSM synthesis for low-power mixed synchronous/asynchronous implementation," in Journal of VLSI Design 2001, Special issue on low-power design, vol. 12, no. 2, pp. 167-186, 2001. (pdf)
3. Bengt Oelmann and Mattias O'Nils, "LIFS: A tool for low-power implementation of FSMs," in Proceedings of the 17th IEEE Norchip Conference, Oslo, Norway, pp. 205-210, 1999. (pdf)
4. Bengt Oelmann and Mattias O'Nils, "Asynchronous control of low-power gated-clock finite-state machines," in Proceedings of the 16th IEEE International Conference on Electronics, Circuits, and Systems, Pafos, Cyprus, September, 1999, pp. 915-918. (pdf)
5. Bengt Oelmann and Mattias O'Nils, "A low-power hand-over mechanism for gated-clock FSMs," in Proceedings of the European Conference on Circuit Theory and Design, Stresa, Italy, August, 1999, pp. 118-121. (pdf)