[11] | 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 |
---|