Browse Prior Art Database

Timing Enhancement to a Finite State Machine Compiler

IP.com Disclosure Number: IPCOM000121980D
Original Publication Date: 1991-Oct-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 122K

Publishing Venue

IBM

Related People

Brodnax, T: AUTHOR [+2]

Abstract

This article describes a coaching feature for use with an FSM compiler. A Finite State Machine (FSM) compiler processes a table (or other specified input format) which maps the current state (CS) and inputs of a machine to its next state (NS) and its outputs. The compiler derives a sum-of-products equation for each output and for each bit of the state latch. Different minimization algorithms have been used with varying degrees of success. However, it is not possible for a simple FSM compiler alone to determine if a particular FSM contains subpaths of a timing critical path. This can only be determined after the FSM has been inserted into the chip and a timing analysis has been executed. At this time, the designer knows which FSM paths contribute to timing critical paths.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Timing Enhancement to a Finite State Machine Compiler

      This article describes a coaching feature for use with an
FSM compiler.  A Finite State Machine (FSM) compiler processes a
table (or other specified input format) which maps the current state
(CS) and inputs of a machine to its next state (NS) and its outputs.
The compiler derives a sum-of-products equation for each output and
for each bit of the state latch.  Different minimization algorithms
have been used with varying degrees of success.  However, it is not
possible for a simple FSM compiler alone to determine if a particular
FSM contains subpaths of a timing critical path.  This can only be
determined after the FSM has been inserted into the chip and a timing
analysis has been executed.  At this time, the designer knows which
FSM paths contribute to timing critical paths.  If this information
were somehow fed into the FSM compiler, the compiler could reorder
the sum-of-products equations to reduce the delay of the critical
subpath based on the designer's 'coaching'.

      Figure 1 is a typical FSM table.  Tables are usually larger,
but this demonstrates the timing problem and its solution without
being so large as to distract by its size. Figure 2 illustrates the
equations derived by the compiler for the table from Figure 1.  If a
timing analysis revealed that the path from I4 to O3 is part of an
overall timing problem, it would be desirable to reduce the path in
the equation.  (The user would expect a synthesis program to generate
logic with two AND gates and two OR...