Table of Contents
nova - State Assignment Program for PLA-based Finite-State Machines
nova
[options] [file]
nova is a program that performs an optimal
assignment of binary codes to the states of a Finite State Machine (FSM).
The primary goal is to optimize the silicon area occupied by the finite
state machine after two-level optimization using
espresso(1OCTTOOLS). The
program minimizes the number of product terms needed to implement the
encoded finite state machine, for a given code length. Different encoding
algorithms are available in nova. They are based on a FSM symbolic minimization
step that produces encoding constraints and an encoding step that produces
codes satisfying some or all of the encoding constraints, for a fixed
or free code-length. The user specifies which algorithm should be invoked
with the option -e and related arguments, according to the format explained
below. By default the algorithm -e ig is invoked. The user may specify a
code length with the options -i for symbolic inputs and -s for states, otherwise
by default the minimum code-length is assumed. nova reads the file provided
(or standard input if no files are specified), performs the state assignment,
and returns by default a big blif format to standard output. When invoked
as a stand-alone program, nova outputs also the best coded minimized two-level
implementation of the FSM, if the option -t is specified.
The following
keywords embedded in the input are understood by nova. The keyword lines
start with ".". Keywords not understood by the program are ignored.
- .symbolic
input
- Inputs are considered as symbolic strings and an optimal assignment
of binary vectors to each symbolic input is also performed.
A complete
list of the command line options is given below. Be warned that some of
the command line options are not intended for general use. [d] denotes
a decimal number and [s] denotes a text string.
- -e ig [-pr]
- The encoding
is driven only by input constraints. Input constraints are computed by
heuristic multiple-valued minimization and satisfied by an heuristic greedy
algorithm. Very fast, suboptimal. If -p is specified, some input constraints
unlikely to be satisfied by a short code are pruned. If -r is specified,
all the rotations of the codes are tried.
- -e ih [-r]
- The encoding is driven
only by input constraints. Input constraints are computed by heuristic
multiple-valued minimization and satisfied by an heuristic algorithm based
on limited backtracking. It produces on average very good results. It has
the best trade-off between quality of results versus computing time. If
-r is specified, all the rotations of the codes are tried.
- -e ioh [-jry]
- The encoding is driven by input and output (dominance) constraints. Input
and output constraints are computed by a version of symbolic minimization
and satisfied by an heuristic algorithm based on limited backtracking.
More computationally expensive than the previous one. It gives often better
results. If -j is specified, all output constraints are kept, while by default
the algorithm prunes those which don't guarantee a gain. If -y is specified,
only output constraints are satisfied. If -r is specified, all the rotations
of the codes are tried.
- -e iov [-jry]
- Variation of the previous encoding
strategy. In practice it works less effectively.
- -e ie [-br]
- The encoding
is driven only by input constraints. Input constraints are computed by
heuristic multiple-valued minimization and satisfied by an exact algorithm
based on backtracking. The minimum code length that allows the satisfaction
of all input constraints is found (the user cannot specify a code length).
It may be computationally unfeasible. -b is a debug option. If -r is specified,
all the rotations of the codes are tried.
- -e ia [-c=[d]] [-m=[d]] [-br]
- The
encoding is driven only by input constraints. Input constraints are computed
by heuristic multiple-valued minimization and satisfied by an algorithm
based on simulated annealing. -c specifies the cost function. It may assume
values 0 or 1. If the cost function is 0, the number of product terms is
minimized. If the cost function is 1, the number of literals after espresso
is minimized. By default the cost function has value 0. -m specifies the
number of moves of simulated annealing at a given temperature. It must
be a positive integer. By default it has value 10. -b is a debug option. If
-r is specified, all the rotations of the codes are tried.
- -e h
- Specifies
1-hot state assignment. In this case, the default two-level minimization
on the encoded finite state machine is not performed, and the external
don't care set is not computed. As an example, the 1-hot codes when there
are four states are 1---, -1--, --1- and ---1.
- -e r [-n=[d]]
- Random encodings are tried.
The user can specify how many trials by the option -n, otherwise the following
default values hold: #states if the proper inputs are not symbolic, #states
+ #inputs if the proper inputs are symbolic. The best result is kept.
- -e
u
- The user supplies in the input file file.codes the codes for the states
(and inputs, if symbolic), as suggested in the example #2 of the input
file format section. nova substitutes the codes in the fsm and minimizes
it.
- -e lb
- Computes a lower bound on the number of product terms needed
to implement the finite state machine. The lower bound is tight, i.e. there
are examples where it can be matched by the encoding found by nova, but
on the average there is a large gap between the lower and upper bounds.
It can be computationally very expensive. Use only when nova is invoked
as a stand-alone program.
- -h[elp]
- Outputs a summary of the command-line options.
- -i =[d]
- Specifies the code length of the symbolic inputs. The default value
of nova is the shortest code that allows an injective coding.
- -s =[d]
- Specifies
the code length of the states. The default value of nova is the shortest
code that allows an injective coding.
- -z =[s]
- Specifies the state whose
code has to be set to zero. By default the program chooses which state
to assign the zero code.
- -b
- Will produce a debug trace. Active only with
-e ie and -e ia. Use only when nova is invoked as a stand-alone program.
- -t
- Outputs the coded minimized two-level implementation of the FSM. Use only
when nova is invoked as a stand-alone program.
- -v
- Will produce a trace showing
the execution of the program. Use only when nova is invoked as a stand-alone
program.
- -a
- Analyzes the two-level realization after encoding. Not yet available.
- -d
- Obtains generalized input constraints, i.e. input constraints with don't-care
entries. Not yet available.
The FSM is described by a symbolic
cover. A symbolic cover is a set of symbolic implicants consisting of four
fields corresponding to the FSM inputs, present-states, next-states and
outputs respectively. The fields are separated by either blanks or tabs,
and all four fields must fit on a single line. To allow comments within
the input file, any characters after a pound sign ('#') are ignored.
The
FSM states are represented by strings of characters (at most 30 characters).
Either the present-state or the next-state may be given as ANY to indicate
that the state is a don't care. (This is useful, for example, in describing
the reset logic for the FSM.)
The inputs to the FSM are represented by
a string of characters of 0, 1, and - (where - indicates the symbolic implicant
does not depend on the corresponding input). The inputs may also be treated
as symbolic inputs (analogous to the way that the present-state is a symbolic
input), and nova will determine an optimal assignment for the inputs as
well (see below).
The outputs from the FSM are also given as a string of
characters from the set 0, 1, and -. A 0 or a 1 indicates that the output
must be either low or high (respectively) for this transition. A - indicates
that, for this transition, the output may be either low or high.
The meaning
of the first symbolic implicant in the first example below above is "when
input input_1 is asserted , proceed from state state_1 to state state_3
with the first, second, third and fifth outputs low, and the fourth output
high". Note that the symbolic implicants are in one-to-one correspondence
with the edges in a state-diagram representation of the FSM.
This
example shows the description of a finite state machine. .symbolic input
input_1 state_1 state_3 00010
input_1 state_2 state_1 01001
input_1
state_3 state_3 10010
input_1 state_4 state_3 00010
input_1 state_5
state_1 01001
input_1 state_6 state_1 01001
input_2
state_2 state_2 01001
input_2 state_5 state_2 01001
input_2 state_6
state_2 01001
input_2 state_1 state_4 00010
input_2 state_3 state_4
10010
input_2 state_4 state_4 00010
...
input_6 state_2 state_1 00101
input_6 state_5 state_1 00101
input_6 state_1 state_5 00010
input_6
state_3 state_5 10010
input_6 state_4 state_5 00010
input_6 state_6
state_5 10100
.end
This example shows how the user specifies
its own codes in the additional file file.codes, when the option -e u is
active. When the code-lengths are not the default ones (shortest ones),
the options -i and -s should be specified in the command line, as it happens
when nova finds an encoding. The token words icode and scode introduce,
respectively, a code and the symbolic input to which it is assigned or
a code and the state to which it is assigned. icode 0000 input_5
icode
0001 input_6
icode 0100 input_1
icode 0101 input_2
icode 0110 input_3
icode 0111 input_4
scode 1000 state_6
scode 1001 state_7
scode 1111 state_1
scode 0010 state_2
scode 1101 state_3
scode 1011 state_4
scode 0000 state_5
By default a big blif format is written to standard
output. When the option -t is specified, also the coded minimized two-level
implementation of the FSM is written to standard output (to use only when
nova is invoked as a stand-alone program). The option -v will produce a trace
showing the execution of the program.
A message like follows
(rarely issued and only when the option -e ig is active) warns only that
the detection of the lattice intersections has been stopped after a quite
large number of them has been computed . No action needs to be taken .
Message fac-simile : WARNING "After that lattice
added the 1001-th new constraint , Nova stopped executing lattice and went
ahead with the constraints that lattice already got" .
When running in
the -e ie mode, nova might issue a message warning that in the worst-case
too many configurations should be examined before finding an exact solution
and then it exits. Although it would have been possible to let the program
run for as long as needed, it exits because an exact solution appears
computationally unfeasible.
espresso(1OCTTOOLS),
kiss(1OCTTOOLS),
misII(1OCTTOOLS)
T.Villa, A.Sangiovanni-Vincentelli, "NOVA: state assignment
of finite-state machines for optimal two-level logic implementations",
IEEE Trans. on Computer-Aided Design , September 1990
Tiziano Villa
In a given state, if symbolic implicants are not specified for
all possible input conditions, then the state machine response for the
unspecified conditions is undefined. In particular, nova will use this
to its advantage when assigning the state codes. It is possible to see
all of the don't cares created in this way by using the -out fd option when
the PLA is minimized with espresso.
Temporary files with unique names are
created in the current working directory during the run of the program.
They are removed at the end. At the end of a run, nova creates two files:
file.esp stores the best coded minimized pla implementation, file.summ stores
the face and output constraints (if any) and the final codes. file.esp is
in pla(5OCTTOOLS) format,
suitable for input to espresso or misII(1OCTTOOLS).
Terminal names, when provided by the user, are retained.
Only a single
symbolic input (besides the present state) is allowed. The ability to specify
any number of symbolic inputs along with binary inputs would be much more
practical.
nova invokes the multiple-valued minimization program espresso.
nova is written in C. There are no limitations on the number of binary
or symbolic inputs, binary outputs, states, or symbolic implicants.
(implementation)
nova comes from Latin and means a new (implementation). No connection
to astronomical objects is implied.
It is possible to specify logically
inconsistent finite state machines (i.e., to specify two transitions for
the same set of inputs in a single state) and this should be, but is not,
detected as an error.
Keywords not understood by the program are ignored.
Table of Contents