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