source: vis_dev/vis-2.1/share/help/restruct_fsmCmd.txt @ 14

Last change on this file since 14 was 11, checked in by cecile, 13 years ago

Add vis
File size: 6.3 KB
Line 
1
2  restruct_fsm - Restructre the STG of a finite state machine to reduce power
3  dissipation.
4     _________________________________________________________________
5
6   restruct_fsm  [-D  <fileHead>] [-d <divMethod>] [-E] [-F <factMethod>]
7   [-f   <probFile>]   [-h]  [-N]  [-o  <orderFile>]  [-p  <string>]  [-s
8   <restrMethod>] [-t <seconds>] [-v]
9
10   This  command  implements an STG restructuring algorithm that exploits
11   the  existence of equivalent states to decrease power dissipation, not
12   necessarily  by  collapsing the equivalence states, but by redirecting
13   transitions  in  the  state  transition graph (STG). This algorithm is
14   based   on  monolitic  transition  relation.  The  complexity  of  the
15   algorithm  in  general  increases  with an increase in the size of the
16   STG.  The number of states and edges in the STG are exponential in the
17   number  of  state variables and primary inputs. The memory utilization
18   is  not  necessarily exponential due to symbolic representation of the
19   STG.  For  more  details  see,  "A  Symbolic  Algorithm  for Low-Power
20   Sequential  Synthesis",  ISLPED  97. This command works only if VIS is
21   compiled   with  CUDD  package.  The  algorithm  can  handle  circuits
22   described  in  both  BLIF  and  BLIF-MV  format. However, multi-valued
23   variables  are  not  supported.  Also,  the  final synthesized circuit
24   (network  implementation of the restructured STG) is available only in
25   BLIF  format.  The  sequential  circuit  should  have a single initial
26   state.  A  network  should  have  been created for the circuit and its
27   primary  inputs  and  state  variables  assigned  BDD ids prior to the
28   invocation  of  this  command. A network can be created by the command
29   flatten_hierarchy  and  command  static_order  assigns  BDD ids to the
30   input  and  state variables. The command proceeds by creating BDDs for
31   the  outputs  and  next state functions. An FSM data structure is then
32   created on which subsequent operations are performed. After the STG is
33   restructured  a  new  circuit is synthesized by symbolic factorization
34   based   on   Zero-Suppressed   Decision  Diagrams  (ZDDs).  The  final
35   synthesized  circuit  is  a file in BLIF format with ".ml.blif" as the
36   extension.
37
38   The typical command flow in vis is the following:
39   vis> read_blif foo.blif
40   vis> flatten_hierarchy
41   vis> static_order
42   vis> dynamic_var_ordering -e sift
43   vis> restruct_fsm
44
45   In   the   above  case  example,  the  final  synthesized  circuit  is
46   MODEL.ml.blif if the name of the design in foo.blif is MODEL.
47   Command options:
48
49   -A
50          Allow realignment (during symbolic factorization) of ZDDs after
51          BDD  reordering  and  vice versa. This option is effective when
52          only one of the BDD or ZDD variable reordering is enabled.
53
54   -D <fileHead>
55          Specify  the  output  file  name  for synthesized circuit. File
56          extension  is  not necessary. By default, the model name of the
57          circuit  is  used.  For  example,  -D  foobar,  will  result in
58          foobar.ml.blif
59
60   -d <divMethod>
61          Choose a divisor. See synthesize_network for more details.
62
63   -E
64          Print the number of equivalence classes in the FSM.
65
66   -F <probFile>
67          File with primary input probabilities, one per line. input_name
68          <probability>
69
70   -f <factMethod>
71          Choose  a  method for factorization. See synthesize_network for
72          more details.
73
74   -h
75          Print command usage.
76
77   -i <string>
78          Specify  the  prefix  to be used to generate names for internal
79          nodes during synthesis. By default, the prefix is "_n".
80
81   -N
82          Expand  the  reachable  set R to include those states which are
83          equivalent  to  R  but  not  reachable.  The  default is not to
84          include such states.
85
86   -o <orderFile>
87          File  to  output  BDD  variable ordering after the restructured
88          circuit is synthesized.
89
90   -R <value>
91          Allow  reordering  in  BDD and/or ZDD variables during symbolic
92          factorization stage.
93
94          0 : (default) No reordering neither in BDD nor in ZDD.
95
96          1 : Allows reordering only in BDD, not in ZDD.
97
98          2 : Allows reordering only in ZDD, not in BDD.
99
100          3 : Allows reordering both in BDD and in ZDD.
101
102   -s <heuristic>
103          Heuristic  to  perform restructuring. Consider a fragment of an
104          STG  containing states A,B and C and an edge from A to B. Let B
105          and  C  be  equivalent.  Since  B  and  C are equivalent, it is
106          possible  to  change the transition between A and B to A and C.
107          In the more general case, the choice can be driven by different
108          cost constraints. The following are the heuristics:
109          ham  : Hamming distance based heuristic. An edge is chosen that
110          reduces the Hamming distance (or state bit transitions) between
111          the states.
112          fanin  :  Fanin  oriented  heuristic. A representative from the
113          equivalence  class  is  chosen  that  reduces the total average
114          state bit switching on the incoming edges.
115          faninout  :  Fanin-Fanout  oriented heuristic. A representative
116          from  the  equivalence  class  is chosen that reduces the total
117          average state bit switching on the incoming as well as outgoing
118          edges.
119          cproj  :  A  simple  C-Projection.  A  representative  from the
120          equivalence  class  is  chosen  which is closest to the initial
121          state. The distance d(x,y) is defined as:
122          sum_{i=0}^{N-1}(|x_i - y_i| cdot 2^{N-i-1}).
123
124   -T
125          Try to share more nodes during symbolic factorization. Existing
126          divisors  are  checked  for  potential  reuse before extracting
127          divisors from the current boolean function.
128
129   -t <seconds>
130          Time  in  seconds  allowed  to  complete  the  command.  If the
131          computation time goes above that limit, the process is aborted.
132          The default is no limit.
133
134   -v
135          Turn on verbosity.
136
137   See also command : synthesize_network
138     _________________________________________________________________
139
140   Last updated on 20050519 10h16
Note: See TracBrowser for help on using the repository browser.