SIS - sequential interactive synthesis - is a software package for logic design developed at the University of California, Berkeley.

SIS can synthesise combinational, synchronous and asynchronous circuits, generating either two-level or multi-level (factorised) equations. These equations can then be mapped onto a user-defined component library representing gates, flip-flops, standard cells, etc, and these circuits optimised for minimum size, maximum speed, etc.

SIS contains a range of algorithms chosen to generate good quality, rather than minimal results. Such results are sometimes approximations, but this means that SIS can process much larger problems than would be possible by exhaustive methods such as K-maps or Quine-McCluskey minimisation.

This document contains three sections -

SIS tutorial exercises - to introduce the operation and capabilities of SIS

SIS reference guide - detailing all SIS commands

Input/output file formats - defining the available formats for the source and output files

 

 

 

 

The command line typed at the system prompt looks like the following:

Since SIS is normally executed in an interactive mode, it is normally invoked with no options or files whatsoever. Sometimes a given set of commands are invoked so frequently and in the same sequence that it is worthwhile to place them in a script and to run SIS in batch mode - details are given in the Reference Guide.

In this exercise, you will gain experience in using SIS to map a collection of functions into optimised multi-level Boolean expressions. In particular, you will:

Become familiar with some of the operations provided by SIS for manipulating a Boolean network.

Use SIS to map an optimised multi-level expression onto a component library.

Perform simple timing simulations to identify critical delay paths.

 

You will find it helpful to sketch the logic diagrams corresponding to the equations generated by SIS during these tutorial examples.

First we will introduce the basic commands supported by SIS, and use them to obtain a multi-level solution for the full adder circuit - with which you should be familiar..

SIS can take as input a truth table or a set of equations (there are other formats it understands, but we won’t yet be concerned with those). Details of these formats are given in the final section of this guide.

To begin, an input file must be created using a text editor.

It is a good idea to create your own input file and follow this example step by step by typing the same commands at the keyboard.

Most commands can be entered in either long or short mode, for example, "read_pla" or "rp".

A list of these commands and their shortform aliases is given in the Reference Guide.

We invoke SIS and read in the network:

To see the equations in sum-of-products form, type the "p" command:

Note that co and sum are in curly brackets: these have been identified by SIS as output nodes.

To carry out a two-level minimisation on all the nodes of current network, we will use a version of the "simplify" command - simply type "sim1 *" to simplify all of the output functions:

A number of other minimisation commands exist, some of which will be seen in the next exercise.

The "ps" ("print_stats") command will show the number of literals required to represent the functions in both sum-of-products and factored forms :

The two level network should look familiar to you. The factored form is not surprising either:

The ‘decompose’ command can be used to identify common subexpressions and represent them as new nodes in the circuit. In this case, {co} and {sum} are decomposed into a collection of simpler functions:

Two new functions have been introduced and are represented by nodes [2] and [3].

Note how SIS has identified that a’ b’ + a b and a’ b + a b’ are complements of each other, and how this has been reflected in the new expression for {sum}.

We will now carry out technology mapping, that is, the mapping of the current network onto a predefined library of gates.

To use a library, we must first issue a "rlib" command followed by the "map" command.

To see the revised multi-level network, type "pf":

A number of new nodes have been introduced during the mapping onto the library components. The "pg" command will print out the gates used in deriving each of the non-leaf nodes of the network (the leaf nodes describe input literals) The figure following the gate name is the cost or area of the library component :

We see that SIS has implemented the circuit using 2-input AND and OR gates and inverters.

We now see that the full-adder has been implemented using the XOR gates, even though they are more expensive, since this has reduced the overall cost and delay of the circuit.

A summary of the gates used is given by the "pgc" command :

The circuit propagation delay is given by the "pat" command :

sis> pat sum co
... using library delay model
{sum} : arrival=( 6.10 6.10)
{co} : arrival=( 4.40 4.40)

These commands use the area and delay information specified in the library models, where the ‘area’ is a measure of the cost of the component (typically representing the silicon area required for VLSI layout) and the ‘delay’ represents the propagation delay of the component.

The next example is a multiple-output function that contains don’t care conditions. It will also illustrate the use of ‘scripts’ to run a series of commands stored in a text file and the commands used to output results to text files.

Note that the truth-table format allows ‘dont-care’ terms to be included.

We will now use the "full_simplify" command, which includes any dont-care terms in the minimisation process :

To display the equations in terms of the primary input variables only, we may use the "collapse" command :

The current network data may be written out to a file at any time, allowing intermediate or final results to be saved.

The data may be saved in a number of different formats. For this example, we will use the "write_blif" command :

... remaining output (including dont-care terms) not shown.

full_simplify 796 literals processing time : 34 sec.

source script 470 literals processing time : 86 sec.

In this section, we will further examine some of the commands used for processing circuit equations. Such commands are used to change the form of multi-level networks.

Normally, logic equations are manipulated in order to reduce the number of literals that they contain, since this is taken as an indicator of the number and size of logic gates that will be required to implement the circuit.

An equation may be ‘factorised’ in order to extract literals common to a number of terms.

If the factorised form of an equation does not already exist, SIS performs a "quick factorisation" by simply extracting a single literal which is present in a number of product terms, as seen above.

Better quality results are typically obtained using the "factor -good" or "gf" command :

The process of choosing the best factor(s) can be explicitly shown by the "gkx" command :

In this case, the new node [5] shows the largest factor (and makes the multi-level nature of the network more explicit).

The process of ‘decomposition’ (seen in the first example) is similar to factoring except that each factor is shown as a new node in the network and that the resulting equations are further factored until each equation contains at most one instance of any literal. In practice, decomposition may be used to break down complex functions into simpler components :

The ‘eliminate’ command carries out the reverse of decomposition by replacing a node with the equation it represents, according to the number of times that node is used in the network. For example, the command "eliminate -1" will remove any nodes which are only used once :

In this case, node [9] has been eliminated. The eliminate command will tend to reduce the number of levels in a network.

For a multiple-output circuit, the common factors, or ‘divisors’, must be chosen in order to minimise the overall number of literals in the combined equations.

Consider the following example :

This shows the result of factoring each equation seperately. The "gkx" command may be used to extract the largest factor common to both equations :

We see that in this instance the use of the common factor gives a result which is less than optimal in each individual case, but gives a better overall result.

Lastly, we may find that part of an expression is the same as, and can be replaced by, a variable which exists elsewhere in the network. The variable can then be substituted for the expression. This operation is known as ‘resubstitution’ :

Note that the "resub" command will attempt to use both the true and complement forms of the variable.

In this section, a range of different operations have been demonstrated. In practice, it will often be found that a series of commands are used in order to try and find the optimal representation of a given function. Such lists of commands can be found in the scripts supplied with SIS and introduced in the previous section. Refer to the documentation for the "source" command for more details.

The process of ‘technology mapping’ describes the conversion of a network described only by Boolean equations into a circuit made up of logic components chosen from a particular device library.

In general, we begin technology mapping with a network containing a minimum number of literals - on the basis that this will generate the simplest logic circuit. However, if the component library does not contain a component corresponding to a particular expression in the network, then the given expression will be automatically decomposed. For example, if a library contains only simple NAND gates, then the network will be decomposed until it consists only of NAND functions, even though this may increase the number of literals (and logic levels).

SIS carries out technology mapping using a pattern-matching technique. Beginning at a primary output of the network, SIS compares the logic equation for the output node with each of the library components. When a match is found, the pattern-matching procedure is repeated at each of the component inputs until the primary inputs of the network are reached. It is normally possible to implement a design using different combinations of components, and SIS can be directed to choose components on the basis of their speed or their cost, allowing the designer to make a trade-off between these factors.

The input file is read, and the equations printed in SOP form :

The "ps" command shows the literal count for these equations as 83 (sop) or 71(factored).

The "pgc" command will be used to display the gates used, and the "pat -p 1" command will show the maximum propagation delay present in the resulting circuit. Since these commands will be used each time the circuit is mapped, the "alias" command is used to define a name, ‘pr’, to represent the required command string :

The " -m 0" switch on the map command specifies a minimum-area mapping.

The example is now repeated using different delay-area trade-offs :

These results show that a range of results may be obtained, with a variation of around 1.7:1 in cost and 1.4:1 in worst-case delay.

It can be seen that the simplification of the original equations has been reflected in the circuits obtained.

Finally, the simplified equations are collapsed before mapping, in an attempt to reduce the propagation delay irrespective of the effect on area. The literal count increases to 684 (sop) or 134 (factored).

The results above may be compared graphically -

This shows the ‘best’ solutions (that is the fastest, the smallest and the optimum combinations of delay and area) marked as circles, with the suboptimal points (in that for each one there is another point which is as small but faster or as fast but smaller) shown as crosses.

Script V1.1 session started Wed May 29 09:05:12 1996

UC Berkeley, SIS 1.3 (compiled May 28 1995)

sis> !type ez.eqn

x1 = a * (b + c*d ) ;

x2 = d + e*f ;

sis> re ez.eqn

sis> p

{x1} = a b + a c d

{x2} = d + e f

sis> act_map -h 4 -s -r ezact

block count: 0

number of blocks using OR gate = 0

sis> !type ezact

MODEL "ez.eqn";

TECHNOLOGY scmos;

VIEWTYPE SYMBOLIC;

EDITSTYLE SYMBOLIC;

INPUT "a" : "a";

INPUT "b" : "b";

INPUT "c" : "c";

INPUT "d" : "d";

INPUT "e" : "e";

INPUT "f" : "f";

OUTPUT "x1" : "[0]";

OUTPUT "x2" : "[1]";

INSTANCE "BASIC_BLOCK":physical NAME = INST0;

"A0" : "GND";

"A1" : "GND";

"SA" : "Vdd";

"B0" : "GND";

"B1" : "Vdd";

"SB" : "a";

"S0" : "b";

"S1" : "GND";

"out" : "[2]";

INSTANCE "BASIC_BLOCK":physical NAME = INST1;

"A0" : "GND";

"A1" : "d";

"SA" : "a";

"B0" : "GND";

"B1" : "Vdd";

"SB" : "a";

"S0" : "b";

"S1" : "GND";

"out" : "[3]";

INSTANCE "BASIC_BLOCK":physical NAME = INST2;

"A0" : "GND";

"A1" : "[2]";

"SA" : "Vdd";

"B0" : "GND";

"B1" : "[3]";

"SB" : "Vdd";

"S0" : "c";

"S1" : "GND";

"out" : "[0]";

INSTANCE "BASIC_BLOCK":physical NAME = INST3;

"A0" : "GND";

"A1" : "e";

"SA" : "f";

"B0" : "GND";

"B1" : "Vdd";

"SB" : "Vdd";

"S0" : "d";

"S1" : "GND";

"out" : "[1]";

ENDMODEL;

sis> re ez.eqn

sis> p

{x1} = a b + a c d

{x2} = d + e f

sis> act_map -s -r ezact

block count: 3

number of blocks using OR gate = 0

sis> !type ezact

MODEL "ez.eqn";

TECHNOLOGY scmos;

VIEWTYPE SYMBOLIC;

EDITSTYLE SYMBOLIC;

INPUT "a" : "a";

INPUT "b" : "b";

INPUT "c" : "c";

INPUT "d" : "d";

INPUT "e" : "e";

INPUT "f" : "f";

OUTPUT "x1" : "[4]";

OUTPUT "x2" : "[5]";

INSTANCE "BASIC_BLOCK":physical NAME = INST0;

"A0" : "GND";

"A1" : "c";

"SA" : "d";

"B0" : "GND";

"B1" : "Vdd";

"SB" : "Vdd";

"S0" : "b";

"S1" : "GND";

"out" : "[6]";

INSTANCE "BASIC_BLOCK":physical NAME = INST1;

"A0" : "GND";

"A1" : "GND";

"SA" : "Vdd";

"B0" : "GND";

"B1" : "[6]";

"SB" : "Vdd";

"S0" : "a";

"S1" : "GND";

"out" : "[4]";

INSTANCE "BASIC_BLOCK":physical NAME = INST2;

"A0" : "GND";

"A1" : "e";

"SA" : "f";

"B0" : "GND";

"B1" : "Vdd";

"SB" : "Vdd";

"S0" : "d";

"S1" : "GND";

"out" : "[5]";

ENDMODEL;

sis> act_map -v

[6] = b + c d

Printing F matrix

122

211

The most binate col is -1

the phase is 1

the phase is 1

the phase is 1

Printing F matrix

222

Printing F matrix

212

current variable - b

current variable - d

END- 0

current variable - c

END- 0

END- 1

END- 1

total mux_structures used for the node [6] = 1, arrival_time = 0.000000

{x1} = [6] a

total mux_structures used for the node [4] = 1, arrival_time = 0.000000

{x2} = d + e f

Printing F matrix

122

211

The most binate col is -1

the phase is 1

the phase is 1

the phase is 1

Printing F matrix

222

Printing F matrix

212

current variable - d

current variable - f

END- 0

current variable - e

END- 0

END- 1

END- 1

total mux_structures used for the node [5] = 1, arrival_time = 0.000000

printing network ez.eqn

{x1} = [6] a

cost = 1

{x2} = d + e f

cost = 1

[6] = b + c d

cost = 1

**** total cost of network after all iterations is 3

*** block count: 3

sis> q

Script completed Wed May 29 09:09:02 1996

xilinx

Script V1.1 session started Wed May 29 09:09:25 1996

UC Berkeley, SIS 1.3 (compiled May 28 1995)

sis> re ez.eqn

sis> xl_ao

sis> re ez.eqn

sis> xl_imp

sis> p

{x1} = a b + a c d

{x2} = d + e f

sis> xl_partition

sis> p

{x1} = a b + a c d

{x2} = d + e f

sis> xl_partition -v 2

---collapsed 0 nodes in trivial collapse one iter

---collapsed 0 nodes in trivial collapse

sis> xl_partition -v 4

---collapsed 0 nodes in trivial collapse one iter

---collapsed 0 nodes in trivial collapse

sis> pf

{x1} = a (c d + b)

{x2} = e f + d

sis> xl_merge

usage: xl_merge [-f MAX_FANIN] [-c MAX_COMMON_FANIN] [-u MAX_UNION_FANIN] [-n support] [-o filename] [-vlF]

-f MAX_FANIN is the limit on the fanin of a mergeable node(default = 4)

-c MAX_COMMON_FANIN is the limit on the common fanins of two mergeable nodes(default = 4)

-u MAX_UNION_FANIN is the limit on the union of the fanins of two mergeable nodes(default = 5)

-n support fanin limit of nodes. (default = 5)

-o filename is the file in which information about the nodes merged is printed. Must specify.

-l do not use lindo, use a heuristic to solve max. card. matching.

-F do not do further collapsing after matching pairs of nodes (default: do it).

-v verbosity option.

sis> xl_merge -o xltemp

YOU DO NOT HAVE LINDO INTEGER PROGRAMMING PACKAGE

IN YOUR PATH.

PLEASE OBTAIN LINDO FROM

The Scientific Press, 540 University Ave.

Palo Alto, CA 94301, USA

TEL : (415) 322-5221

USING A HEURISTIC INSTEAD.....

No space for mergeFile to be written

sis> !type xltemp

Merging two CLB's into one CLB

# of CLB's = 2

sis> xl_merge -l -v 2 -o xltemp

usage: xl_merge [-f MAX_FANIN] [-c MAX_COMMON_FANIN] [-u MAX_UNION_FANIN] [-n support] [-o filename] [-vlF]

-f MAX_FANIN is the limit on the fanin of a mergeable node(default = 4)

-c MAX_COMMON_FANIN is the limit on the common fanins of two mergeable nodes(default = 4)

-u MAX_UNION_FANIN is the limit on the union of the fanins of two mergeable nodes(default = 5)

-n support fanin limit of nodes. (default = 5)

-o filename is the file in which information about the nodes merged is printed. Must specify.

-l do not use lindo, use a heuristic to solve max. card. matching.

-F do not do further collapsing after matching pairs of nodes (default: do it).

-v verbosity option.

sis> xl_merge -l -v -o xltemp

No space for mergeFile to be written

Total number of matchings = 0

Merging two CLB's into one CLB

# of CLB's = 2

checking for collapses after merge...

deleted 0 nodes in the final collapse, final CLBs = 2

sis> p

{x1} = a b + a c d

{x2} = d + e f

sis> xl_cover

sis> re ez.eqn

sis> p

{x1} = a b + a c d

{x2} = d + e f

sis> xl_imp -n 2

sis> re ez.eqn

sis> xl_imp -v 2 -n 2

node [35][{x1}]

{x1} = a b + a c d

---collapsed 0 nodes in trivial collapse one iter

---collapsed 0 nodes in trivial collapse

Generate matching for [37] (PO: [35])

Suppressed nodes :

Found a separating set (0) : [39] [40]

Suppressed nodes : [39]

Squeezing operation ...

Suppressed nodes : [39]

Suppressed nodes : [40]

No more finite maxflows

Generate matching for [38]

Suppressed nodes :

Found a separating set (1) : a c

Suppressed nodes : a

Squeezing operation ...

Suppressed nodes : a

Suppressed nodes : c

No more finite maxflows

Generate matching for [39]

Suppressed nodes :

Found a separating set (2) : a b

Suppressed nodes : a

Squeezing operation ...

Suppressed nodes : a

Suppressed nodes : b

No more finite maxflows

Generate matching for [40]

{x2} = d + e f

the best possible??

---replacing node [36] by 2 feasible nodes

sis> xl_imp -v 1 -n 2

sis> p

{x1} = [62] a

{x2} = [65] + d

[61] = c d

[62] = [61] + b

[65] = e f

sis> xl_imp -v 2 -n 3

sis> p

{x1} = [62] a

{x2} = [65] + d

[61] = c d

[62] = [61] + b

[65] = e f

sis> re ez.eqn

sis> xl_imp -n 3

sis> p

{x1} = [70] + a b

{x2} = d + e f

[70] = a c d

sis> xl_cover -n 3

sis> p

{x1} = [70] + a b

{x2} = d + e f

[70] = a c d

sis> ps

ez.eqn pi= 6 po= 2 nodes= 3 latches= 0

lits(sop)= 9 lits(fac)= 9

sis> rp bcdinc.pla

sis> ps

bcdinc.pla pi= 4 po= 4 nodes= 4 latches= 0

lits(sop)= 60 lits(fac)= 34

sis> full_simplify

sis> ps

bcdinc.pla pi= 4 po= 4 nodes= 4 latches= 0

lits(sop)= 17 lits(fac)= 16

sis> xl_imp

sis> ps

bcdinc.pla pi= 4 po= 4 nodes= 4 latches= 0

lits(sop)= 17 lits(fac)= 16

sis> p

{qa} = {qb}' b + a d'

{qb} = {qd} b + {qd}' b' c + b c'

{qc} = {qd} c + {qd}' a' c'

{qd} = d'

sis> collapse

sis> p

{qa} = a d' + b c d

{qb} = b c' + b d' + b' c d

{qc} = a' c' d + c d'

{qd} = d'

sis> re cla3.eqn

sis> full_simplify

sis> collapse

sis> p

{s0} = a0 b0 ci0 + a0 b0' ci0' + a0' b0 ci0' + a0' b0' ci0

{s1} = a0 a1 b0 b1 + a0 a1 b0' b1 ci0 + a0 a1' b0 b1' + a0 a1' b0' b1' ci0 + a0' a1 b0 b1 ci0 + a0' a1 b0' b1' + a0' a1 b1' ci0' + a0' a1' b0 b1' ci0 + a0' a1' b0' b1 + a0' a1' b1 ci0' + a1 b0' b1' ci0' + a1' b0' b1 ci0'

{s2} = a0 a1 a2 b0 b1' b2 + a0 a1 a2 b0' b1' b2 ci0 + a0 a1 a2' b0 b1' b2' + a0 a1 a2' b0' b1' b2' ci0 + a0 a1' a2 b0 b1 b2 + a0 a1' a2 b0' b1 b2 ci0 + a0 a1' a2' b0 b1 b2' + a0 a1' a2' b0' b1 b2' ci0 + a0' a1 a2 b0 b1' b2 ci0 + a0' a1 a2' b0 b1' b2' ci0 + a0' a1' a2 b0 b1 b2 ci0 + a0' a1' a2 b0' b2' + a0' a1' a2 b2' ci0' + a0' a1' a2' b0 b1 b2' ci0 + a0' a1' a2' b0' b2 + a0' a1' a2' b2 ci0' + a0' a2 b0' b1' b2' + a0' a2 b1' b2' ci0' + a0' a2' b0' b1' b2 + a0' a2' b1' b2 ci0' + a1 a2 b1 b2 + a1 a2' b1 b2' + a1' a2 b0' b2' ci0' + a1' a2 b1' b2' + a1' a2' b0' b2 ci0' + a1' a2' b1' b2 + a2 b0' b1' b2' ci0' + a2' b0' b1' b2 ci0'

{co2} = a0 a1 a2 b0 b1' b2' + a0 a1 a2 b0' b1' b2' ci0 + a0 a1 a2' b0 b1' b2 + a0 a1 a2' b0' b1' b2 ci0 + a0 a1' a2 b0 b1 b2' + a0 a1' a2 b0' b1 b2' ci0 + a0 a1' a2' b0 b1 b2 + a0 a1' a2' b0' b1 b2 ci0 + a0' a1 a2 b0 b1' b2' ci0 + a0' a1 a2' b0 b1' b2 ci0 + a0' a1' a2 b0 b1 b2' ci0 + a0' a1' a2' b0 b1 b2 ci0 + a1 a2 b1 b2' + a1 a2' b1 b2 + a2 b2

sis> ps

cla3.eqn pi= 7 po= 4 nodes= 4 latches= 0

lits(sop)= 310 lits(fac)= 94

sis> xl_imp

sis> ps

cla3.eqn pi= 7 po= 4 nodes= 6 latches= 0

lits(sop)= 144 lits(fac)= 67

sis> p

{s0} = a0 b0 ci0 + a0 b0' ci0' + a0' b0 ci0' + a0' b0' ci0

{s1} = a0 a1 b0 b1 + a0 a1 b0' b1 ci0 + a0 a1' b0 b1' + a0 a1' b0' b1' ci0 + a0' a1 b0 b1 ci0 + a0' a1 b0' b1' + a0' a1 b1' ci0' + a0' a1' b0 b1' ci0 + a0' a1' b0' b1 + a0' a1' b1 ci0' + a1 b0' b1' ci0' + a1' b0' b1 ci0'

{s2} = [105] a1 a2 b2 + [105] a1 a2' b2' + [105] a2 b1 b2 + [105] a2' b1 b2' + [105]' a1' a2 b2' + [105]' a1' a2' b2 + [105]' a2 b1' b2' + [105]' a2' b1' b2 + a1 a2 b1 b2 + a1 a2' b1 b2' + a1' a2 b1' b2' + a1' a2' b1' b2

{co2} = [122] a1 a2 + [122] a1 b2 + [122] a2 b1 + [122] b1 b2 + a1 a2 b1 + a1 b1 b2 + a2 b2

[105] = a0 b0 + a0 ci0 + b0 ci0

[122] = a0 b0 + a0 ci0 + b0 ci0

sis> xl_partition

sis> ps

cla3.eqn pi= 7 po= 4 nodes= 6 latches= 0

lits(sop)= 144 lits(fac)= 67

sis> q

Script completed Wed May 29 09:36:31 1996

The file is read in using the "read_blif" ("rl") command, and the "ps" command shows that the design contains 10 states, but that no circuit equations yet exist :

The "sm" command is now used to carry out state minimisation :

The minimised state table may now be displayed :

To carry out state assignment, the "jedi" program is used :

The state assignment may be displayed using the "write_blif" command :

...remainder of file not shown.

The network equations may now be displayed :

In cases where unused states exist, the "extract_seq_dc" command will identify them so that they can be used as dont-care states which may help to further simplify the circuit equations :

In this case, no improvement has been achieved.

Technology mapping may now be carried out :

We can see that the resulting circuit contains two d-type flip-flops as expected.

Note that -

The assigned state table is now read in and the "stg_to_network" command used to generate the circuit equations :

The "print_latch" command shows the signal names and current states of the d-type latches that have been generated.

The "simulate" command is used to display the values of the primary output signals as a function of the primary inputs (and, for sequential designs, the current state).

...and so on.

Note that it is only the steady-state output values that are displayed. This simulation does not account for any timing information contained in the circuit, and will not show any transient output values, for example, glitches due to circuit hazards.

While simulation is the primary tool used for investigating the behaviour of a design, it is not well suited for checking ‘correctness’, that is, checking that a circuit functions identically to its specification, or that two different implementations of a design are equivalent, since this will require simulating the circuit(s) for all possible input combinations or sequences and checking for any incorrect responses. The alternative to exhaustive simulation is to prove mathematically (algebraically) that the two functions are equivalent, in which case they will always generate the same output values.

For combinational functions, the "verify" command checks the equivalence of two networks stored in BLIF format.

In this example, two different interpretations of a full-adder circuit are compared :

For sequential designs, the "verify_fsm" command generates a list of all possible states and outputs that can be reached from the initial state of each circuit as a basis for comparison.

In this example, a state table has been minimised by hand and SIS used to compare the original and minimised designs :

The first design is read, state assignment is carried out, and the network written to a BLIF format file.

The second design is now read and the verification performed :

Note that the "verify_fsm" command will not correctly detect the equivalence of designs with state tables having dont-care input values, that is, it will not verify that two ‘dont-care’ values are equivalent.

SIS is an algorithmic sequential circuit optimisation program. SIS starts from a description of a sequential logic macro-cell and produces an optimised set of logic equations plus latches which preserves the input-output behaviour of the macro-cell. The sequential circuit can be stored as a finite state machine or as an implementation consisting of logic gates and memory elements. The program includes algorithms for minimising the area required to implement the logic equations, algorithms for minimising delay, and a technology mapping step to map a network into a user-specified cell library. It includes all of the optimisation techniques available in MIS, and replaces MIS completely.

SIS can be run in interactive mode accepting commands from the user, or in batch mode reading commands from a file or from the command line. If no options are given on the command line, SIS will enter interactive mode. Otherwise, SIS will enter batch mode. When running in batch mode, SIS reads its input from the file given on the command line, or from standard input if no filename is given; output is directed to standard output, unless -o is used to specify an output filename.

All commands are summarised below according to their function : network manipulation (operations on the logic-level implementation), ASTG manipulation (operations on the asynchronous signal transition graph), STG manipulation (operations on the synchronous state transition graph), input/output, network status, command interpreter, and miscellaneous. The last two tables summarise the new commands that operate on ASTG's and sequential circuits, respectively.

The last two tables summarise the new commands that operate on ASTG's and sequential circuits, respectively.

Most commands which take a node also take a list of nodes as an argument. This is referred to as a node-list in the documentation below. This list of nodes includes * to specify all nodes in the network, i() to specify the primary inputs of the network, o() to specify the primary outputs of the network, i(node) to specify the direct fanin of node, and o(node) to specify the direct fanout of node.

When SIS starts, it executes commands from a system startup file (usually sis_lib/_misrc and sis_lib/.sisrc). This defines a standard set of aliases, and then sources the files ./misrc, and ./sisrc to allow users to define their own set of aliases. The default alias set includes the following aliases which have proven useful.

add_inverter

Add inverters into the network wherever needed to make each signal (including the primary inputs) used only in its negative form. After this command, every literal in a node is in the negative form. This is the appropriate starting point for the technology mapping step.

alias [name [string]]

unalias name ...

The alias command, if given no arguments, will print the definition of all current aliases. Given a single argument, it will print the definition of that alias (if any). Given two arguments, the keyword name becomes an alias for the command string, replacing any other alias with the same name. The unalias command removes the definition of an alias.

It is possible to create aliases that take arguments by using the history substitution mechanism. To protect the history substitution character `%' from immediate expansion, it must be preceded by a `\' when entering the alias. For example:

sis> alias read read_\%:1 \%:2.\%:1 sis> alias write write_\%:1 \%:2.\%:1 sis> read blif lion sis> write eqn tiger

will create the two aliases `read' and `write', execute "read_blif lion.blif", and then execute "write_eqn tiger.eqn". And...

sis> alias echo2 "echo Hi ; echo \%* !" sis> echo2 happy birthday

would print:

Hi happy birthday !

CAVEAT: Currently there is no check to see if there is a circular dependency in the alias definition. e.g.

sis> alias foo "print_stats -f; print_level -l; foo"

creates an alias which refers to itself. Executing the command "foo" will result an infinite loop during which the commands "print_stats -f" and "print_level -l" will be executed.

astg_contract [-f] <signal-name>

Generate the contracted net for the specified signal of the ASTG.

The -f option adds the restriction that the contracted net must also be free-choice. Chu has conjectured that this restriction may not be necessary, so it is optional at this time until we have answered this question.

astg_current

Display information about the current ASTG: its name, whether it is a free-choice net, state machine, or marked graph, and the number of state machine (SM) and marked graph (MG) components if astg_smc or astg_mgc have been run on the ASTG.

astg_lockgraph [-l]

Build the lock graph for the current ASTG.

With the -l option, edges are added to the ASTG to ensure that the lock graph is connected, and thus that the ASTG has the Complete State Coding property.

If an ASTG has the CSC property, the state of the circuit can be represented completely by the collection of input, output and internal signals specified in the ASTG. This simplifies many synthesis algorithms.

The algorithm works only for ASTG's that are marked graphs (no choice).

astg_marking [-s] [<marking>]

Display or set the initial marking of the ASTG. If no marking is given, the current initial marking is displayed. The default format for the marking is the same as for the

The -s option uses a state code format for the marking. This is a list of signal name and value pairs. For example, to set an initial state with signal A at value 0 and B at value 1, use the command: astg_marking -s A 0 B 1

astg_persist [-p]

Add constraints to make an ASTG persistent. With the -p option, nonpersistent transitions are printed but the ASTG is not modified.

For small ASTGs with very high concurrency, enforcing the ASTG persistency property will partially and sometimes completely enforce the Complete State Coding property (CSC). If an ASTG has the CSC property, the state of the circuit can be represented completely by the collection of input, output and internal signals specified in the ASTG. This simplifies many synthesis algorithms.

astg_print_sg

Print the state graph of the current ASTG. If no state graph is present, this will create one by token flow.

astg_print_stat

Print the statistics of the current ASTG: name of the ASTG file, initial marking, total number of states in the state graph and the total number of I/O signals.

astg_slow [-v debug_level] [-t tolerance] [-s] [-f external_delay_file] [-d default_external_delay] [-m min_delay_factor]

Remove hazards from the STG implementation, inserting delay buffers after some STG signals. Delays are inserted so that no gate within the circuit implementation can react as though the STG specified ordering of signals is reversed in time.

It must be invoked after technology mapping (see astg_to_f for a recommended script file).

The -m option specifies the amount by which all MINIMUM delays are MULTIPLIED (this until the delay computation will understand min/max delays). Of course 0.0 < min_delay_factor <= 1.0. Default value: 1.0.

The -t option specifies the tolerance to be used during the hazard check procedure (the larger the specified value, the more conservative is the algorithm). Default value: 0.0.

The -s option specifies not to use the shortest-path algorithm when computing the delays in the network. This might result in being overly pessimistic (this option is only experimental).

The -f option specifies a file name to search for the minimum delays between output signals and input signals of the STG (i.e. for those signals that are not being synthesised). This can be useful if some information about these signals is known either from the specification or from the synthesis of another sub-component of the total asynchronous system.

The file can also be updated with the minimum delays between each input signal and each output signal if the -F option is used in place of -f. This allows for separate synthesis of various sub-components of an asynchronous system. In this case iteration might be necessary to obtain optimal results, and a warning message is issued when the stored information is changed, and a new iteration is required.

The -d option specifies the default minimum delay between output signals and input signals of the STG (if no information can be obtained from the above described file). The default value is 0.0 (i.e. the environment responds instantaneously), but this can be overly pessimistic, and result in an unnecessary slow and large implementation.

astg_syn [-m] [-r] [-v debug_level] [-x]

Synthesise from the current signal transition graph a two-level implementation which is hazard-free under the unbounded gate delay model (i.e., gates have unbounded delays, wires have zero delays).

The synthesis is performed in two steps. The first step derives a state graph from the ASTG by performing a reachability analysis. If no initial marking is given, then astg_syn will try to find a live, safe initial marking. The second step uses the state graph generated in step one to perform hazard analysis and synthesis. All static hazards and critical races are removed. astg_syn tries to remove all dynamic hazards arising from multiple input or output changes. When it cannot remove such hazards, it will print the terms which can potentially produce hazards and the conditions under which hazards can be produced. From this user can remove the dynamic hazards by removing some concurrency. The resulting implementation may be neither prime nor irredundant.

The following options are not intended for general use.

The -m does not perform cube reduction and always returns a prime cover implementation free of static hazards. As a consequence, dynamic hazards due to multiple input/output changes may not be removed.

The -r option runs ESPRESSO in single-output mode. The implementation will be prime and irredundant, but may have static hazards and dynamic hazards.

The -v option specifies the debug level.

The -x assumes that a state graph has already been derived, and perform synthesis directly from the given state graph. State graph can be derived by using _astg_flow.

astg_to_f [-v debug_level] [-r] [-s signal_name] [-d]

Generate an initial two-level implementation of each output signal specified by the current Signal Transition Graph.

If the initial marking is not defined, then a valid marking is searched for. The list of potential hazards, used by astg_slow, is also produced.

One primary input is generated for each signal (both input and output) specified by the STG, with the same name as the signal (and "_" appended if the signal is an output).

One primary output is generated for each output signal specified by the STG, with the same name as the signal. The primary output is driven directly by the primary input.

One asynchronous latch is generated for each output signal specified by the STG, connecting the combinational logic function implementing the signal (a "fake" primary output with the same name as the signal and "_next" appended) and the corresponding primary input.

If some signal is not used inside the combinational logic, then the corresponding primary input and latch is not created (unless the option -r is specified).

The -s option adds a set of fake primary outputs that ensure that the named signal is implemented as a Set-Reset flip-flop. If, in addition, the -d option is specified, the functions for the Set and Reset input are made disjoint. This may increase the implementation cost, but reduces its sensitivity to dynamic hazards.

An error message results if either no valid marking is found (in which case it might be advisable to define it in the STG specification file) or the STG does not have the Compatible State Coding property (i.e. if two markings with different sets of enabled output signals have the same binary label).

A typical STG synthesis and optimisation script should look like:

astg_to_f

gkx -ab

resub -ad;

sweep

gcx -b

resub -ad;

sweep

eliminate 0

decomp -g *

eliminate -1

map astg_slow

 

astg_to_stg [-v debug_level]

Generate a State Transition Graph (STG) from the current Signal Transition Graph (ASTG). The State Transition Graph has one input signal for each signal in the Signal Transition Graph (both input and output), and one output signal for each output signal in the Signal Transition Graph.

If the initial marking is not defined, then a valid marking is searched for.

An error message results if no valid marking is found (in which case it might be advisable to define it in the ASTG specification file).

atpg [-acdflrtD] [file]

Perform combinational test generation using random test generation, deterministic test generation, and fault simulation. Random test generation is done by using parallel fault simulation. Deterministic test generation is accomplished by using Boolean satisfiability. Fault collapsing is first performed, but only across simple gates and both fault equivalence and fault dominance are used to reduce the fault list. The network is changed in the case when a node exists that is locally redundant, e.g. f = a + a' is replaced by f = 1.

The -a option removes active clauses. Active clauses are used to accelerate the deterministic test generator by minimising the search space of the boolean satisfier. Removing active clauses will dramatically degrade the performance of the dtg.

The -c option prevents fault collapsing.

The -d option is a low verbosity debug option.

The -f option causes the atpg not to do fault simulation after each deterministic test generation.

The -l option sets the give-up level of the rtg. A value of 1 means that the atpg will end the RTG phase if a parallel simulation of 32 patterns does not detect any new faults. A value of 2 causes RTG to end if 64 patterns does not detect any new faults, and so on. The default value is 10.

The -r option causes the atpg not to do random test pattern generation.

The -t option first converts the network to arbitrary fanin AND and OR gates. This is typically faster than using test generation on a complex gate network. The decomposed network is returned.

The -D option is a verbose debug option.

If file is specified, test patterns are written out to the given file.

buffer_opt [-l #] [-f #] [-c] [-d] [-T] [-L] [-v #] [-D] nodelist

Builds fanout trees for the nodes in the node-list. If no nodes are specified selects the nodes to be buffered in order to improve performance of the entire network. The network is assumed to be mapped.

The -l # option specifies the number of fanouts which a node can have so as to be eligible for buffering. The default is 2, hence any multi-fanout node is a candidate for buffering.

The -f # option specifies the transformations to use. Set the three least significant bits indicate the use (value == 1) of the transformations. xx1 to use the repower transformation, x1x to use an unbalanced transformation and 1xx to use the balanced distribution of signals. More than one transformation can be set active. Thus to allow the algorithm full flexibility use the value = 7 (111 in binary notation) which is also the default.

The -c option specifies that one pass be carried out. The default is to iterate till no improvement is achieved.

The -d option allows the complex gates to be decomposed into smaller ones so as to increase drive capability. By default the complex gates are retained.

The -L option traverses the network from outputs to inputs ensuring that for every node, the gate that implements it does not drive a load greater than the max_load limit specified for that gate. THIS OPTION IS NOT YET IMPLEMENTED.

The -T option displays the circuit performance as the iterations progress. If the required times at the outputs are not specified the circuit delay is shown, else the minimum slack value is displayed.

The -v #,-D option are for debugging. The -v # option is the most verbose and the amount of verbosity can be increased by letting the argument for -v range from 1 to 100.

chng_clock

Toggles the setting of the clock between the user-specified clock settings (specified in the blif file) and the working values (generated by algorithms inside SIS).

All algorithms use the current setting as input. If the algorithms modify the clocking scheme or the cycle-time they write the modified clocking scheme into the working fields. Thus, to write out the blif file containing the clock scheme generated by algorithms inside SIS, the setting must first be set to the working one and then write_blif must be invoked.

chng_name

Toggles the network between long-name mode (user supplied names) and short-name mode (automatically generated single character names).

collapse [n1] [n2]

Collapse nodes in the network. With no arguments, the entire network is collapsed into a single-level of functions (i.e., two-level form). Each output will be expressed in terms of the primary inputs.

Given a single node, that function is collapsed until it is represented entirely in terms of primary inputs.

Given two arguments, it is assumed that the second node is a fanin of the first node. In this case, this dependency is removed (the first node is expressed without the second node as a fanin).

Please note that this command negates any mapping that may have been done at an earlier time.

Caution should be taken when collapsing network to two levels because the two level representation may be too large.

The alternative is to use eliminate (selective collapse). Refer to eliminate for the details.

constraints [node_1....node_n]

Print the values of the various delay constraints for the nodes in the argument list, which must be either inputs or outputs. Also prints the default values of the default delay parameters for the network. Used to check the values set by set_delay.

decomp [-gqd] [node-list]

Decompose all the nodes in the node-list. If the node-list is not specified, all the nodes in the current network will be decomposed. Decompostion will factor nodes and make the divisor a new node within the network, re-expressing other nodes in terms of this newly introduced node. It is one of the transforms used to break down large functions into smaller pieces, usually at the cost of introducing a few more literals.

If the -q option (the default) is specified, the quick decomp algorithm is used which extracts out an arbitrary kernel successively. Because of the fast algorithm for generating an arbitrary kernel, decomp -q is very fast compared with the decomp -g. In most cases, the result is very close. This command is recommended at the early phase of the optimisation.

If the -g option is specified, the good decomp algorithm is used which successively extracts out the best kernel until the function is factor free, and applies the same algorithm to all the kernels just extracted. This operation will give the best algebraic decomposition for the nodes. But, since it generates all the kernels at each step, it takes more CPU time. In general, decomp -q should be used in the early stage of the optimisation. Only at the end of the optimisation, should decomp -g be used.

If the -d option is specified, the disjoint decomposition is performed. Currently, the disjoint decomposition is limited to the following simple algorithm: It partitions the cubes into sets of cubes having disjoint variable support, creates one node for each partition, and a node (the root of the decomposition) which is the OR of all the partitions.

echo args ...

Echoes the arguments to standard output.

eliminate [-l limit] thresh

Eliminate all the nodes in the network whose value is less than or equal to thresh. The value of a node represents the number of literals saved in the literal count for the network by leaving the node in the network. If the value is less than (or equal to) the threshold, the node will be eliminated by collapsing the node into each of its fanouts. A primary input or a primary output will not be eliminated.

The value of the node is approximated based on the number of times the node is used in the factored form for each of its fanouts. Note that if a node is used only once, its value is always -1.

limit is used to control the maximum number of cubes in any node. The default is 1000. Using a very large limit may result in collapsing the network to two levels. In general, if the circuit is collapsible, the command collapse is more efficient.

espresso

Collapse the network into a PLA, minimise it using espresso, and put the result back into the multiple-level nor-nor form.

extract_seq_dc [-o depth] [-v n] [-m method]

Extract sequential don't cares based on unreachable states. The unreachable states are computed by implicitly enumerating the set of reachable states in the product machine starting from an initial state and then computing the inverse of that set. full_simplify should be run afterwards to exploit these don't cares.

-o depth allows the specification of the depth of search for good variable ordering. A larger value for depth will require more CPU time but determine a better ordering. The default value is 2.

-v allows specification of the verbosity level of the output.

The -m option specifies method for determining the reachable states. consistency builds the entire transition relation and uses it to determine the reached states. bull does output cofactoring to find the reachable states. The product method is similar to the consistency method but input variables are smoothed as soon as possible as the characteristic function is being built. This makes the size of the resulting BDD representing the characteristic function of the transition relation smaller. The default method is product.

factor [-gq] node-list

Throw away the old factored forms and factor each node in the node-list, and store the factored forms with the nodes. If the -q option is specified, the quick factor algorithm is used to factor the node. If the -g option is specified, the good factor algorithm is used to factor the node.

fanout_alg [-v] alg_list

Activates selectively one or more fanout algorithms. For a list of fanout algorithms known to the system, use the -v option. The algorithms activated are the ones specified in the list. One algorithm, noalg, is always active. two_level is a fast, area efficient algorithm. The best results are obtained with two_level, bottom_up, lt_trees, and mixed_lt_trees.

Fanout optimization itself is performed using the map command.

fanout_param [-v] fanout_alg [property value]

Changes the default parameter values associated with specific fanout algorithms. For a list of these parameters and their values, use the -v option with a fanout algorithm.

full_simplify [-d][-o ordering] [-m method] [-l] [-v verbose]

Simplify each node in the network using the local don't cares generated in terms of fanins of each node. First compatible observability plus external don't cares are generated for each node in terms of primary inputs. Then the image computation techniques are used to map these don't cares to the local space of each node. This technique removes most redundancies in the network. The satisfiability don't cares for a subset of the nodes in the network which have the same support as the node being simplified is also generated. An ordering is given to the nodes of the network and local don't cares for the nodes are computed according to that ordering. Each node is simplified using its local don't cares and an appropriate satisfiability don't care subset.

-d If this option is used no observability don't cares are computed. In this case the local don't cares are only the unreachable points in the local space of each node (a subset of the satisfiability don't care set).

-o Used for BDD ordering. If 0 (default) is used, variables are ordered based on their depth. If 1 is used, the level of a node is used for its ordering.

method specifies the algorithm used to minimise the nodes. snocomp (default) invokes a single pass minimisation procedure that does not compute the complete offset. nocomp invokes the full minimisation procedure (ala ESPRESSO) but does not compute the complete offset. dcsimp invokes single pass tautology-based minimiser.

-l generates fanin don't cares only for nodes with the same or subset support as the node being minimised which have level less than the node being minimised. The level is the largest number of nodes on the longest path from the node to a primary input.

-v prints out extra info for debugging the code.

fx [-o] [-b limit] [-l]

Greedy concurrent algorithm for finding the best double cube divisors and single cube divisors. Finds all the double cube and single cube divisors of the nodes in the network. It associates a cost function to each node, and extracts the node with the best cost function greedily.

The -o option only looks for 0-level two-cube divisors.

The -b option reads an upper bound for the number of divisors generated. The default value is 50000. This is because the number of divisors in some cases can grow very large.

The -l option changes the level of each node in the network as allowed by the slack between the required time and arrival time at that node.

gcx [-bcdf] [-t threshold]

Extract common cubes from a network, re-express the network in terms of these cubes, and in the process cut down on the number of literals needed in the network.

The -b option chooses the best cube at each step when examining possible cubes to be extracted; otherwise, the more efficient ping-pong algorithm is used to find a good (but not necessarily the best) cube at each step.

The -c option uses the complement of each cube as well as the cube when dividing the new cube into the network.

The -f option uses the number of literals in the factored form for the network as a cost function for determining the best cube to be extracted.

The -t option sets a threshold such that only a cube with a value greater than the threshold will be extracted. By default, the threshold is 0, so that all possible cube divisors are extracted.

The -d option enables a debugging mode which traces the execution of gcx.

gkx [-1abcdfo] [-t threshold]

Extract multiple-cube common divisors from the network.

The -a option generates all kernels of all function in the network when building the kernel-intersection table. By default, only level-0 kernels are used.

The -b option chooses the best kernel intersection as the new factor at each step of the algorithm; this is done by enumerating and considering each possible kernel intersection, and choosing the best. By default, the more efficient ping-pong algorithm is used to find a good (but not necessarily the best) kernel intersection.

The -c option uses the new factor and its complement when attempting to introduce the new factor into the network.

The -d option enables debugging information which traces the execution of the kernel extract algorithm.

The -f option uses the number of literals in the factored form for the network as the cost function when determining the value of a kernel intersection; by default, the number of literals in the sum-of-products form for the network is used.

The -o option allows for overlapping factors.

The -t option sets a threshold such that divisors are extracted only while their value exceeds the threshold. By default, the threshold is 0 so that all possible multiple cube divisors are extracted from the network.

The -1 option performs only a single pass over the network. By default, the kernel extract algorithm is iterated while there are still divisors whose value exceeds the given threshold.

help [-a] [command]

Given no arguments, help prints a list of all commands known to the command interpreter. The -a option provides a list of all debugging commands, which by convention begin with an underscore. If a command name is given, detailed information for that command will be provided.

history [-h] [num]

Lists previous commands and their event numbers. The -h option suppresses printing the event number. If num is specified, lists the last num events. Lists the last 30 events if num is not specified.

History Substitution:

The history substitution mechanism is a simpler version of the csh history substitution mechanism. It enables you to reuse words from previously typed commands.

The default history substitution character is the `%' (`!' is default for shell escapes, and `#' marks the beginning of a comment). This can be changed using the "set" command. In this description '%' is used as the history_char. The `%' can appear anywhere in a line. A line containing a history substitution is echoed to the screen after the substitution takes place. `%' can be preceded by a `\' in order to escape the substitution, for example, to enter a `%' into an alias or to set the prompt.

Each valid line typed at the prompt is saved. If the history variable is set (see help page for set), each line is also echoed to the history file. You can use the "history" command to list the previously typed commands.

Substitutions: at any point in a line these history substitutions are available

%:0 Initial word of last command.

%:n n'th argument of last command.

%$ Last argument of last command.

%* All but initial word of last command.

%% Last command.

%stuf Last command beginning with "stuf".

%n Repeat the n'th command.

%-n Repeat the n'th previous command. ^old^new Replace "old" w/ "new" in previous command.

Trailing spaces are significant during substitution. Initial spaces are not significant.

invert node-list

Invert each node in the node-list. It is used when the complement of a node is to be implemented. Note that it does not change the logic function of the current Boolean network, but will have an effect on the structure of the network.

map [-b #][-f #][-i][-m #][-n #][-r][-s][-p][-v #] [-A][-B #][F][-G][-W]

Perform a technology mapping on the current network. A library must be read using the read_library command before mapping can be performed. The result of the mapping may become invalidated if a command such as plot or print_stats -f is executed which computes a factored form representation of every node.

To produce a minimum area circuit with no consideration for load limits, the recommended option is map -m 0.

To produce a minimum area circuit that respects load limits, the recommended option is map -m 0 -AF. Use _check_load_limit command to check for load limit violations.

To produce a minimum delay circuit that respects load limits, the recommended option is map -n 1 -AFG. To specify required times in order to allow the mapper to trade off delay and area, use the set_delay command.

Details about the meanings of the various options follow.

The -b n sets the number by which the load value should be multiplied in case of a load limit violation during fanout optimization.

The -f n option controls the internal fanout handling. A value of '0' disables it completely (i.e. the mapping is strictly tree-based). A value of '1' enables an heuristics approximating the cost of the previous tree at fanout branches. A value of '2' enables the usage of cells with internal fanout (such as EXOR and MULTIPLEXER). A value of '3' (default) enables both. None of these values is guaranteed to give the best solution in all cases, but '3' usually does. A warning is issued if the current value can give bad results with the current network (use undo before mapping again).

The -i option disables the inverter-at-branch-point heuristic. It is intended for experimentation with different mapping heuristics.

The -m option controls the cost function used for a simple version of the tree covering algorithm. A mode of '0' (the default) minimises the area of the resulting circuit. A mode of '1' minimises the delay of the resulting circuit (without regard to the total area). An intermediate value uses as cost function a linear combination of the two, and can be used to explore the area-delay trade-off. A value of '2' minimises the delay on an estimate of the critical path obtained from a trivial 2-input NAND mapping, and the area elsewhere.

The -n option allows the access to a better tree covering algorithm. It can only be used in delay mode, i.e. with an argument of 1: -n 1. This algorithm gives better performance than -m 1 but is noticeably slower. It uses a finer dynamic programming algorithm that takes output load values into account, while -m 1 option supposes all loads to be the same. As a consequence, the -n 1 option performs better than -m 1 especially with rich libraries of gates. Both algorithms use heuristics to guess the load value at multiple fanout points. Both options should always be used with fanout optimization turned on.

If -r is given (raw mode), the network must already be either 1- and 2-input NAND gates, or 1- and 2-input NOR gates form, depending on whether a NAND-library, or a NOR-library was specified when the library was originally read (see read_library). If -r is not given, appropriate commands are inserted to transform the network into the correct format.

The -s option prints brief statistics on the mapping results.

The -p option forces the mapper to ignore the delay information provided by the user at primary inputs and primary outputs (arrival times, required times, loads, drive capability). It is intended for experimental use. This option forces the arrival times and required times to be all 0, the loads and drive capabilities to be all equal to the load and drive capability of the second smallest inverter in the library. If there is only one inverter, the data are taken from that inverter.

The -v n options is for development use, and provides debugging information of varying degrees of verbosity as the mapping proceeds.

The -A option recovers area after fanout optimization at little or no delay cost by resizing buffers and inverters.

The -B n option controls the enforcement of load limits during fanout optimization. A value of 0 ignores the load limits. A value of 1 takes load limits into account. The default is set to 1. This option is effective only in conjunction with fanout optimization. It is implemented by artificially increasing the load at a gate output by a multiplicative factor whenever the load exceeds the limit specified in the library. The default multiplicative factor is 1000. This value can be changed with the -b n option. There is a priori no reason to change this value.

The -F option performs fanout optimization. This disables the internal fanout handling (i.e. forces -f 0). In order to recover area after fanout optimization use the -A option. There are several fanout optimization algorithms implemented in SIS. For details, type help fanout_alg and help fanout_params.

The -G option recovers area after fanout optimization at no cost in delay by resizing all gates in the network.

The -W option suppresses the warning messages.

node_atpg [-acdflrtD] node-list

Same as atpg command but only does test generation for all faults on the nodes provided in the node-list.

one_hot

Does a quick one-hot encoding of the current STG. It assigns one-hot codes, minimises the resulting PLA using espresso, and returns the network to SIS.

phase [-qgst] [-r n]

Decide for each node whether to implement the node or its complement in order to reduce the total cost of the network. If the network is mapped, the cost is the total area and the network will be kept mapped, otherwise, the cost is the total number of inverters in the network assuming all the inverters are already in the network. At the end, all the necessary inverters are inserted into the network and all the extra inverters are removed from the network.

The default algorithm, which can also be specified by -q option, is a greedy algorithm called quick phase. The -g option uses the Kernighan-Lin type algorithm called good phase. The -s option chooses the Simulated Annealing algorithm. The -r n option chooses a random-greedy algorithm which does a random assignment first, uses a greedy approach to get to a local minimum, and iterates n times. If the -t option is specified, some tracing information is printed as the assignment proceeds.

plot_blif [-k] [-r] [-i]

The plot_blif command creates a window with a abstract representation of the network, at its current level of optimization, labelling all nodes, including primary inputs and outputs. Vectors are used to show relationships between the various nodes. Latches are not printed explicitly. The network is drawn as an acyclic combinational circuit. Labelled arrows indicate the locations of the latches.

The -k option "kills" (closes) the most recent plot window with the current network name.

The -r option replaces the contents of an existing plot window with the current network structure. This is useful if the network has been modified since it was last plotted. If no plot window is open with the current network name, the command has no effect.

The -i option forces a plot of the internal network structure used by SIS. The default is to plot the structure corresponding to the write_blif command. The primary difference in the internal structure is in how primary outputs are handled.

print [-n] [-d] node-list

Print all the nodes in the node-list in sum-of-product form.

If -n option is specified, the nodes are printed in the negative form. (i.e. a' + b' will be printed as (a + b)').

If -d option is specified, the nodes in the external don't care network are printed.

print_altname node-list

Print the alternate name of all the nodes in the node-list. If the current name mode is short (SIS internal name), the alternate name will be the long name (user-specified name) and vice-versa.

print_clock

Prints the clocking scheme associated with the current network. The clocking scheme printed depends on the current setting of the clock data structure (see chng_clock).

print_delay [-alrs] [-m model] [-p n] node-list

Do a delay trace (static timing analysis) on the network depending on the specified model and print the delay data. Without any arguments the routine will use the library model which assumes that the network is mapped and will print the arrival times, required times and the slack for all the nodes in the network.

Specifying an optional node-list will print the delay data only for the specified nodes.

The user can selectively have portions of the delay data printed. The option -a will cause the arrival times to be printed. The option -r will cause the required times to be printed. The option -s will cause the slacks at nodes to be reported. The option -l will cause the load driven by the node to be printed.

The option -p n when specified with one of the options -[alrs] will print out the delay data so that the first n nodes with the most critical values are printed. The critical portion of the delay data is determined by the first of the options -[alrs] specified. Thus specifying -p n -[al] prints the n nodes with the greatest arrival-time/load. For the -[rs] option the nodes with the smallest required time/slack are printed.

The delay model can be specified by the -m option followed by one of the following keywords --- unit, unit-fanout, library or mapped. Specifying unit results in delay being computed as 1 unit per node in the network. unit-fanout adds an additional delay of 0.2 per fanout. If a library has been read in using the read_library command one can use more accurate models, mapped and library, by using data stored in the library. Using the model library assumes that the network has been mapped. The mapped model does not make this assumption and will do a mapping of the nodes on an individual basis to compute a delay model for use during the delay trace.

print_factor node-list

Print all the nodes in the node-list in the factored form. If a node has not been factored, factor -q will be used to factor the node.

print_gate [-ps] node-list

Prints the information provided in the library for the list of mapped gates.

The -p option prints the pin information of the gates.

The -s option prints summary of the gates and their area.

print_io [-d] [node-list]

Print both fanin and fanout list for each node in the node-list. Absence of node-list implies all the nodes in the current network.

If the -d option is specified, the nodes in the external don't care network are considered.

print_kernel [-as] node-list

Print kernels and corresponding co-kernels of all the nodes in the node-list. If -a option (default) is specified, all kernels, including the function itself if it is a kernel, are printed. If -s option is specified, only the sub- kernels are printed.

print_latch [-s] [node-list]

With no arguments, print_latch prints out information for all the latches in the network. The information printed for each latch is the latch input, latch output, initial value, current value, synchronization type, and controlling node. The latch values can be 0, 1, 2 (don't care), and 3 (undefined).

If the -s option is specified, only the latch input, output, initial and current values are given. If a node-list is given, only the latches associated with those nodes are printed (each node should be a latch input or output).

print_level [-l] [-c] [-m model] [-t value] [node-list]

Prints the nodes of the network according to their level. When called with a node-list, only the nodes in the transitve fanin of the specified nodes are printed. The primary inputs are assigned level 0, and the level of a node is the length of the longest path from it to a primary input. The -l options prints only the number of levels in the network.

If the -c option is specified, only critical nodes are printed according to their level. The delay trace is done according to the -m model option (default is the unit-fanout model) and all the nodes with a slack within a -t value of the smallest slack are considered to be critical.

print_library [-a][-f][-h][-l][-r] [function-string]

Print the contents of the current library. If the optional string is given, only the combinational gates with the same logic function as the string will be printed. function-string is in the format of read_eqn. For example print_library "f=!(a*b);" will print all combinational gates with a NAND2 logic function.

The -a option prints asynchronous type latches matching the 'function-string'.

The -f option prints falling edge triggered flip-flops matching the 'function-string'.

The -h option prints active high transparent latches matching the 'function-string'.

The -l option prints active low transparent latches matching the 'function-string'.

The -r option prints rising edge triggered flip-flops matching the 'function-string'.

print_map_stats

Prints delay and area information of the network. The network should be mapped.

print_state

Prints out the current state of the machine for both the STG and the logic implementation. For the logic implementation, the current state is printed as a string of integers representing the values on the latches: 0, 1, 2 (don't care), and 3 (undefined). For the STG, the current state is printed with its symbolic and encoded names.

print_stats [-f] [-d]

Print the current network status, which includes the network name, number of primary inputs (pi), number of primary outputs (po), number of nodes (nodes), the number of latches (latches), the number of literals in the sum-of-product form (lits(sop)), and the number of states in the STG (#states(STG)).

If -f option is specified, the number of literals in the factored form (lits(fac)) is computed. This could be slow when the factored form for some network takes too long to generate.

If -d option is specified, the statistics of the external don't care network is printed.

print_value [-a] [-d] [-p n] node-list

Print the value of all the nodes in the node-list. The value is currently defined as the number of literals increased if the node were eliminated from the network. Since the value of a node depends on the particular factored form of the node and its fanouts, all the nodes which don't have factored forms will be factored using factor -q.

The -a option prints the values in ascending order.

The -d option prints the values in descending order.

The -p takes an argument n, and directs print_value to only print the top n values.

quit

Stop the program. Does not save the current network before exiting.

read_astg [<file-name>]

Read a text description of an Asynchronous Signal Transition Graph (ASTG). The overall format follows the style of BLIF, and uses an adjacency list to describe the net interconnection structure. If no filename is specified, the description is read from stdin.

All names in the ASTG description must start with a letter, consist of letters, digits and underscores, and are case sensitive. A signal transition is represented with a suffix: "+" means a low to high transition, "-" means high to low, "~" means toggles (changes to the opposite value).

.model <model-name> This gives an arbitrary name to the ASTG, and it must be the first line of the model description.

.inputs <signal-list> Specifies a list of names of ASTG input signals. Signals from multiple .inputs are concatenated.

.outputs <signal-list> Specifies a list of names of ASTG output signals. Signals from multiple .inputs are concatenated.

.internal <signal-list> Specifies a list of names of ASTG internal signals, i.e. signals which are only used to maintain state information.

.dummy <name-list> Specifies a list of names which are accepted as dummy or null transitions. Null transitions are necessary to specify some behaviors using the ASTG syntax. By convention, the name "e" is used as a dummy signal (to represent epsilon transitions).

.graph Indicates the lines which follow describe the ASTG net structure using an adjacency list format. This must follow all signal declarations (.inputs, etc.). Net places are optional for simple constraints between two transitions; in this case an intervening place is generated automatically. Multiple instances of a transition are distinguished by following them with a slash and a copy number. For example, a second instance of transition "t+" can be specified by "t+/2". Copy numbers do not have to be consecutive.

.marking {<place-list>} An initial marking can optionally be specified after the net structure has been given. Implied places (see .graph) between two transitions x* and y* can be specified using the syntax <x*,y*>.

.end This required line indicates the end of the ASTG description.

Error messages are printed for any unrecognised input sequences.

read_blif [-a] filename

Read in a network from the file filename which is assumed to be in blif format. The network name is given by the .model statement in the file. If a .model is not given, the network name is the filename with any trailing extension removed. See the blif.tex document for a complete description of the blif format.

The user can also specify an external don't care network. This network must be placed after the care network in the same file. The statement .exdc must precede the description of the external don't care network. The names of primary outputs and primary inputs of the external don't care network must be exactly the same as the names of primary outputs and primary inputs of the care network.

Usual filename conventions apply: - (or no filename) stands for standard input, and tilde-expansion is performed on the filename.

Normal operation is to replace the current network with a new network. If no external don't care network is specified, the external don't care network is set to NIL (non-existent). Otherwise the external don't care network is replaced by the new external don't care network. The -a option specifies that the new network should be appended to the current network. Functions are associated between the two networks using the long names of each network. Name conflicts (where two functions attempt to define the same name) generate warning messages and are resolved by renaming the signal from the new network.

The -s option, though accepted, has no effect on read_blif, and is instead reserved for the read_pla command.

read_eqn [-a] [filename]

Read a set of logic equations. Each equation becomes a node in the logic network.

read_eqn will not make an intermediate node a primary output unless it also appears in the OUTORDER list. Also, the resulting network is a multiple-level network with all of the intermediate signals preserved.

The -a option specifies that the new network should be appended to the current network. Functions are associated between the two networks using the long names of each network. Name conflicts (where two functions attempt to define the same name) generate warning messages and are resolved by renaming the signal from the new network.

The -s option, though accepted, has no effect on read_eqn and is instead reserved for the read_pla command. Note that since the characters '(' and ')' are used for grouping, they cannot be part of a signal name.

read_kiss [filename]

Reads a kiss2 format file into a state transition graph. The state names may be symbolic or strings of "0" and "1". Inputs and outputs should be strings of "0", "1", and "-"; inputs should not be symbolic. The kiss2 format is described in doc/blif.tex. Note that there is no mechanism for specifying the names of the I/O pins in kiss2. Naming can be done in SIS by specifying a blif file containing the .inputs and .outputs lines (which give I/O names) followed by the embedded kiss2 file. See also stg_to_network, read_kiss_net.

Note that read_kiss followed by write_kiss alters the ordering of the product terms. This could make a difference in the nova output.

read_library [-ainr] filename

Read a SIS-format library for future technology mapping. The -a option appends the library to the current library; otherwise, any previous library is discarded. The -i flag suppresses adding extra inverters to all of the primitives. This is intended for debugging only. The -n flag requests that a library, if it is generated, be made using NAND gates rather than NOR gates. The -r flag reads a raw library format (given in BLIF) rather than the normal genlib format.

read_oct cell[:view]

Read in a network from the Oct facet `cell:view:contents'. If `view' is not specified, it defaults to `logic'. The network name is set to `cell:view'. Oct nets without names are given machine-generated unique names. All primary inputs and outputs are named the same as the equivalent Oct formal terminals of the facet.

This operation replaces the current network with the new network.

read_pla [-a] [-s] [-c] filename

Read in an espresso-format PLA from the file filename (see espresso(5) for more information). The network name is derived from the filename with any trailing extension removed.

Usual filename conventions apply: - (or no filename) stands for standard input, and tilde-expansion is performed on the filename.

Normal operation is to replace the current network with a single-level network of complex gates with the same logic functions as the PLA outputs. This makes each PLA output a separate single-output function and is a good starting point for the standard scripts. If don't care conditions exist, the external don't care network is also replaced with a single-level network which implements the don't care conditions of the PLA. Otherwise, the external don't care network is set to NIL (nonexistent).

The -c option replaces the current network with a two-level network of NOR-gates (and inverters) which implements the PLA. This preserves the multiple-output nature of the PLA. The external don't care network is manipulated exactly the same as above. This used to be the default, while the -s option replaced the network with a single-level network as described above. The -s option has been retained for compatibility.

The -a option specifies that the new network should be appended to the current network. Functions are associated between the two networks using the long names of each network. Name conflicts (two functions attempt to define the same name) generate warning messages and are resolved by renaming the signal from the new network.

read_slif filename

Read in a network from the file filename which is in slif format. SLIF is a hierarchical circuit description language and the root network, the one returned to the caller, is defined to be the first network encountered in the file filename.

red_removal [-adtD]

Perform combinational redundancy removal using random test generation, deterministic test generation, and fault simulation. Random test generation is done by using parallel fault simulation. Deterministic test generation is accomplished by using Boolean satisfiability. Each time a redundancy is encountered, after its removal, the previous test patterns are first applied to reduce the fault list as much as possible.

At the end the network is 100% testable for single stuck faults unless the test generator aborts on some faults.

The -a option removes active clauses. Active clauses are used to accelerate the deterministic test generator by minimising the search space of the Boolean satisfier. Removing active clauses will dramatically degrade the performance of the dtg.

The -d option is a low verbosity debug option.

The -t option first converts the network to arbitrary fanin AND and OR gates. This is typically faster than using test generation on a complex gate network. The decomposed network is returned.

The -D option is a verbose debug option.

reduce_depth [-b] [-d #] [-g] [-r] [-s #] [-v #] [-R #.#] [-S #]

This command is to be used to improve the speed of a network before technology mapping. It performs a partial collapse of the network by first clustering nodes according to some criteria and collapsing each cluster into a single node. The clusters are formed as follows: a maximum cluster size is first computed, and the algorithm finds a clustering that respects this size limit and minimises the number of levels in the network after the collapsing of the clusters. The size limit is a limit on the number of nodes covered by the cluster, and does not take into account the complexity of the nodes. Therefore this command should only be used on networks decomposed into simple gates. The cluster size limit can be provided in a variety of ways, depending on which option is used.

The -b option performs the clustering under the duplication ratio constraint specified by -R option.

The -d # option specifies the desired depth of the network after clustering. The depth counts the number of nodes. Since each node is expressed as a sum-of-products, specifying depth of 1 corresponds to collapsing the network to two levels of logic. The algorithm computes the minimum cluster size limit that yields a depth of n.

The -g option prints out statistics based on cluster sizes. No clustering is done.

The -r option specifies a modification of the clustering algorithm that produces the same number of logic levels but with less duplication of logic.

The -s # option specifies the desired cluster size limit.

The -v # option specifies a verbosity level. It is used mainly for debugging.

The -R #.# option specifies the maximum duplication ratio. The default is 2.0.

The -S # option specifies the smallest cluster size limit that produces the same depth as a cluster size limit of n.

replace [-t n] [-v n]

This is a simple routine that performs the same function as resub -a -d on a network decomposed in 2-input NAND gates using tech_decomp -o 2. It is just much faster.

The -v n specifies the verbosity level. It is only used for debugging.

reset_name [-ls]

Resets either the short names (starting again from the single letter a) with the -l option, or the SIS-generated long-names (starting again from [0]) with the -s option.

resub [-a] [-b] [-d] [node-list]

Resubstitute each node in the node-list into all the nodes in the network. The resubstitution will try to use both the positive and negative phase of the node. If node-list is not specified, the resubstitution will be done for every node in the network and this operation will keep looping until no more changes of the network can be made. Note the difference between resub * and resub. The former will apply the resubstitution to each node only once.

The -a (default) option uses algebraic division when substituting one node into another. The division is performed on both the divisor and its complement.

The -b option uses Boolean division when substituting one node into another. NOTE: Boolean resubstitution has not yet been implemented.

The -d option directs resub not to use the complement of a given node in algebraic resubstitutions.

retime [-nfim] [-c #.#] [-t #.#] [-d #.#] [-a #.#] [-v #]

Applies the retiming transformation on the circuit in an effort to reduce the cycle time. The retiming operation is supported only for single phase, edge-triggered designs. Both mapped and unmapped networks can be retimed. The algorithm attempts to maintain the initial state information.

The algorithm expects to work on mapped networks so that accurate delays on the gates can be used. However, an unmapped network can be retimed by using the -n option. In that case the delay through each node is computed according to the unit-fanout delay model. The user should be aware of the fact that when retiming circuits containing complex registers (JK, D-flip flops with enables/presets), the complex registers may have to be decomposed into simpler gates.

By default the algorithm uses a relaxation based approach which is very fast. An alternate formulation uses a mathematical programming formulation and can be selected using the -f option. After profiling on a number of circuits only one will be retained.

The -m option can be used to minimise the number of registers under cycle time constraints. If the cycle time is not specified using the -c option then this command will try to minimise the cycle time. Thus to obtain the absolute minimum number of registers for a circuit the user should specify a very loose cycle time constraint (very large value for the -c option).

The retiming algorithm will try to compute the new initial states of the latches. In case no feasible initial state exists the retiming is aborted and the network is not modified. To suppress the initialisation routine use the -i option. In that case the initial values for all the latches after retiming is set to value of 2 (DONT_CARE).

The desired clock period can be specified with the -c value option. When this option is not used the algorithm first checks to see if there is a cycle_time specification with the current network (the value depends on the current setting of the clock_flag in the network) and tries to meet this. If no cycle_time is specified with the design the retiming operation tries to minimise the cycle time. For this it uses a binary search for testing feasible clock values. The tolerance of the binary search can be specified with the -t value option (the default is 0.1).

Latches in the network can be assigned a propagation delay and an area. These are helpful in the realistic modelling of the circuit delay and area. Use the -d value option to specify the delay through a latch (to approximate the setup and propagation delay of the latch) and the -a value option to specify the area of a latch. In case of mapped networks, these values are automatically determined from the library of gates.

The -v value selects the verbosity level. The range is 1-100 (100 will literally swamp you with a lot of unneeded data). Use the value 1 to see the progress of the algorithm.

save filename

Save a copy of the current executable to a file which can be restarted. This can be used to freeze the current network or the current library for later optimization. When the executable filename is executed, execution returns to the top-level of the command interpreter.

NOTE: The save command is very operating-system dependent and may not be implemented on your system. If this is the case then the save command is unusable on your system.

set [name] [value]

unset name ...

A variable environment is maintained by the command interpreter. The set command sets a variable to a particular value, and the unset command removes the definition of a variable. If set is given no arguments, it prints the definition of all variables.

Different commands use environment information for different purposes. The command interpreter makes use of the following:

autoexec Defines a command string to be automatically executed after every command processed by the command interpreter. This is useful for things like timing commands, or tracing the progress of optimization.

sisout Standard output (normally stdout) can be re-directed to a file by setting the variable sisout.

siserr Standard error (normally stderr) can be re-directed to a file by setting the variable siserr.

history Each valid command entered at the prompt can be echoed to a file by setting the variable history.

history_char By default the character `%' is used to do the history substitution inside SIS. This can be changed by setting the variable history_char.

shell_char By default the character `!' is used to do invoke shell commands from inside SIS. This can be changed by setting the variable shell_char. In order to switch the interpretation of shell_char and history_char it is necessary to first set history_char and then the shell_char. Alternately, you may escape the current history char by preceding it with a `' while setting the shell_char. In addition none of them can be set to a `#' which is reserved for comments.

filec Setting this variable enables the user to use "file-completion" like in the C-shell. An ESC causes the current line to be extended to its unique completion. A CTRL-d generates a list of the possible extensions.

open_path open_path (in analogy to the shell-variable PATH) is a list of colon-separated strings giving directories to be searched whenever a file is opened for read. Typically the current directory (.) is first in this list. The standard system library (typically $SIS/SIS_lib) is always implicitly appended to the current path. This provides a convenient short-hand mechanism for reaching standard library files.

prompt defines the prompt string. If the prompt string contains a `%'(or whatever the history_char has been set to using the set command), the `%' will be replaced whenever the prompt is printed by the current event number.

set_delay [-a|d|i|l|r f] [-A f] [-D f] [-I f] [-L f] [-R f] [-S f] [-W f][o1 o2 ... | i1 i2 ...]

Set various delay parameters for the inputs and outputs of a network. These timing constraints are used by the print_delay command in addition to commands like speed_up, buffer_opt, and map that perform delay optimisations. The values for these constraints are numbers and it is the user's responsibility to ensure that these values are meaningful when a particular delay model is used during the optimisations. Capitalised options set defaults, lower-case options set the parameters for the nodes in nodelist, which is either a list of output nodes or a list of input nodes.

The option -A sets the default arrival time for primary inputs to the real value f. The option -R sets the default required time for primary outputs to f. The -D option sets the default drive on a primary input to f, and the -L option sets the default load on primary outputs to f. The -I option specifies the default value for the maximum load that can be present at a primary input. The -S option sets the wire load per fanout to f. The wire loads for a given number of fanouts can be specified with the -W option. With the ith use of the -W option, the load for a gate driving i outputs is set to the value f.

The settings can be undone by using a negative number for the value. This will result in the parameter to be "unspecified" and the individual commands will use appropriate defaults if necessary.

The -a, -r, -d, -i, and -l options can be used to specify the delay constraints on specific nodes (as opposed to the uppercase options which specify a default value for ALL terminals). These terminal-specific values will supersede the defaults specified with the uppercase options. The -a (-r) option sets the arrival (required) time to f for the specified nodes if the node list given is a list of primary inputs (outputs). The -d (-i) option sets the drive (maximum load limit) for each node in the list to f; if there is a non-primary input in the list this is an error. The -l option sets the load on each node in the list to f; if there is a non-primary output in the list this is an error.

set_state [-s] [-i] [name]

Sets the current state in the machine to the given state. If no state is given, it sets the current state to the initial state (resets the machine). If the -s option is given, only the state of the STG is changed; if the -i option is specified, only the state of the logic implementation is changed. If no logic implementation exists, or if only the state of the STG is to be changed, then the state name should be symbolic; otherwise it should be the encoded name of the state.

sim_verify [-n # pats] filename.blif

Verify that two networks are equivalent using random-pattern simulation. That is, generate a random input vector, simulate the logic network, and check that the outputs between the two networks agree. The first network is the current network, and a second network is read from the file filename.blif: it must be a blif format file. (This restriction will be fixed when the command interpreter is expanded to handle multiple networks.)

-n gives the number of random patterns to simulate.

NOTE: this command only works for combinational networks.

simplify [-d][-i <num>[:<num>]] [-m method] [-f filter] [nodelist]

Simplify each node in the node-list using method with the don't-care set generated according to dctype.

method specifies the algorithm used to minimise the nodes. snocomp (default) invokes a single pass minimisation procedure that does not compute the complete offset. nocomp invokes the full minimisation procedure (ala ESPRESSO) but does not compute the complete offset. dcsimp invokes single pass tautology-based minimiser.

dctype specifies how the don't-care set is generated. The default don't care set generated is a subset of the fanin don't care set. -d option specifies that no don't care set is used. -i m:n specifies that the fanin don't cares of nodes within m levels of transitive fanin and n levels of transitive fanout of these transitive fanin are to be generated.

filter specifies how the don't-care set is filtered. exact (default) uses the exact filter. disj_sup uses the disjoint support filter.

simulate in1 in2 in3 ...

For the current implementation of the network, given a value ('0' or '1') for each of the primary inputs of the network, simulate prints the value produced at each of the primary outputs. The correspondence of the input values and the primary inputs can be determined by the order in which the primary inputs and outputs are printed using the write_eqn command.

For example, for a three-input AND gate, the command

simulate 1 1 0

will produce a

0

NOTE: For sequential circuits, this command essentially assumes that all latches are clocked simultaneously by a single clock. Simulation will take the current values on the latches (which can be displayed by using print_latch) and the user-supplied primary input values and simulate the network, placing the new latch values in the current state of the latches. The values of the outputs and the new state are printed. If a more sophisticated simulation method is needed, timing simulation should be used; this is not currently implemented in SIS.

source [-psx] filename

Read commands from a file. The -p option prints a prompt before reading each command, and the -x option echoes each command before it is executed. The -s option silently ignores an attempt to execute commands from a nonexistent file.

Arguments on the command line after the filename are remembered but not evaluated. Commands in the script file can then refer to these arguments using the history substitution mechanism.

Example:

Contents of test.scr:

read_blif %:2 collapse write_eqn %:2.eqn

Typing "source test.scr lion.blif" on the command line will execute the sequence

read_blif lion.blif collapse write_eqn lion.blif.eqn

If you type "alias st source test.scr" and then type "st lion.blif bozo", you will execute

read_blif bozo collapse write_eqn bozo.eqn

because "bozo" was the second argument on the last command line typed. In other words, command substitution in a script file depends on how the script file was invoked.

Some standard script files are provided.

script (executed by typing ‘source script’ is a script that works well on most examples.

script.boolean uses a larger part of the don't care set during two-level minimisation, requiring more time and producing better results.

script.algebraic uses a smaller part of the don't care set.

script.rugged uses the newest BDD-based techniques, and

script.delay synthesises a circuit for a final implementation that is optimal with respect to speed.

speed_up [-m model] [-d #] [-w #] [-t #.#] [-i] [-c] [-T] [-a #] [-vD] node-list

Speed-up the nodes in the node-list. If no nodes are specified, it selects the nodes to be speeded-up in order to speed-up the entire network. The best decomposition seen so far is accepted (except with the -c flag). The network after running speed_up is composed of 2-input AND gates and inverters.

The -m model option selects the delay model according to which the delay data is computed. The values allowed for model are unit, unit-fanout and mapped. The unit delay model counts the level of the circuit as its delay. The unit-fanout model is intended to capture a technology independent model and it assigns a delay of 1 unit to each gate and 0.2 units to each fanout stem. The mapped delay model uses the delay data in the library to compute delay.

The -d # option selects the distance up to which the critical fanins are collapsed in order to do the speed-up. A fast value is 3, a good one is 6.

The -t #.# option determines which nodes are considered critical. The critical nodes are those with a slack within #.# of the most negative slack.

The -w # option selects between the area mode and the pure timing mode. A value of 0 selects pure-timing mode while a value of 1 will conserve as much area as possible.

The -i option specifies that only the initial 2-input NAND decomposition be carried out.

The -c option specifies that one pass be carried out. The new decomposition is always accepted, even if it results in a slower circuit.

The -T option displays the delay as the iterations progress.

The -a # option tries to do the specified number of attempts when restructuring a node. By default the algorithm tries only one attempt at the restructuring. This option is for experimental use at this stage.

The -v and -D options display debugging information.

state_assign progname options

Perform state assignment on the current STG. The program used for state assignment is progname and it is given the options options. The program progname must exist somewhere in the user's path.

The state assignment program is given the current STG, and returns a logic implementation. After execution of the state_assign command, both the STG and the logic implementation are available for optimization.

The state assignment program called must conform to the specification (see doc/SPEC). Currently, the programs that are compatible with this specification and are shipped with SIS are nova and jedi. To get help information for a specific program, use the -h option (i.e. state_assign nova -h would produce help information for the nova state assignment program).

A one-hot encoding can be obtained by using state_assign progname -e h. Note that nova and jedi produce different results for one-hot encoding. jedi produces typical one-hot codes (1000) while nova produces one-hot codes with don't care conditions (1---).

state_minimize progname options

Perform state minimisation on the current STG. The program used for state minimisation is progname and it is given the options options. The program progname must exist somewhere in the user's path.

The state minimisation program is given the current STG, and returns a new STG. After execution of the state_minimize command, only the STG is available for optimization (any existing logic implementation is removed, since there is no guarantee that it implements the new STG).

The state minimisation program called must conform to the specification (see doc/SPEC). Currently, the program that is compatible with this specification and is shipped with SIS is stamina (from the University of Colorado, Boulder, rho@boulder.colorado.edu). To get help information for a specific program, use the -h option (i.e. state_minimize stamina -h would produce help information for the stamina state minimization program).

stg_cover

Check to see that the behavior of the STG covers that of the logic implementation. This operation is provided for the user to check that two descriptions of the same machine are consistent. Each edge in the STG is symbolically simulated in the logic implementation to ensure that the logic implementation behaves as specified by the STG.

stg_extract [-a] [-e] [-c]

Takes the current network and extracts the state transition graph from it.

If the -a option is not specified, the values on the latches are taken to be the start state, and every state reachable from the start state is explored. This is the normal method of execution.

If the -a option is specified, the state transition graph is extracted for all possible start states, provided the number of latches does not exceed 16. This limitation cannot be overridden (there are too many states to store).

Extraction of the STG could take an enormous amount of time. If there are more than 16 latches in the network, stg_extract won't attempt to extract the STG. This can be overridden with the -e option.

At the end of stg_extract, a check is done to ensure that the behavior of the STG is consistent with that of the logic implementation. This is done with symbolic simulation using BDDs, and could be expensive. stg_extract will not do this check for networks with more than 16 latches or more than 500 transitions unless the -c option is given.

Note: a sweep is done on the network before the STG is extracted. This removes latches that do not fanout, so the sweep makes the extraction more efficient.

stg_to_network [-e option]

Takes the current state-encoded state transition graph and generates an optimised two-level logic network. The initial mapping is optimised using a two-level Boolean minimiser (i.e. espresso) along with the invalid state codes as don't cares. -e allows the user to specify how the two-level logic-encoded network should be processed using espresso. The option can be either 0, 1, or 2. The -e 0 option simply runs espresso and executes read_pla. The -e 1 option runs espresso, but does a read_pla -s instead. This reads in the PLA in single-level form (fully collapsed) rather than two-level form. This often produces better results. The -e 2 option runs espresso -Dso, which does a single-output minimization. Again, read_pla -s is used. This option also produces better results for some cases, but typically takes more time. The default is the -e 1 option.

sweep

Successively eliminate all the single-input nodes and constant nodes (0 or 1) from the current network.

NOTE: Successfully invoking a sweep command on a mapped network can possibly "unmap" the network.

tech_decomp [-a and-limit] [-o or-limit]

Decompose all the nodes in the current network into AND gates or OR gates or both depending on whether -a, -o, or both flags are specified. The fanins of AND gates will be no more than and-limit and that of the OR gates will be no more than or-limit. and-limit and or-limit, if specified, must be at least 2. The default option is -a 2.

time

Prints the processor time used since the last time command, and the total processor time used since SIS was started.

timeout [-t n] [-k]

Sends an interrupt to the SIS process. With no argument, this routine inactivates any previous calls.

The -t n specifies the timeout limit, in seconds.

The -k option specifies that a kill signal is to be sent to SIS rather than a interrupt signal.

alias [name [string]]

unalias name ...

The alias command, if given no arguments, will print the definition of all current aliases. Given a single argument, it will print the definition of that alias (if any). Given two arguments, the keyword name becomes an alias for the command string string, replacing any other alias with the same name. The unalias command removes the definition of an alias.

undo

A simple 1-level undo is supported. It reverts the network to its state before the last command which changed the network. Note that interrupting a command (with ^C) which changes the network uses up the one level of undo.

set [name] [value]

unset name ...

A variable environment is maintained by the command interpreter. The set command sets a variable to a particular value, and the unset command removes the definition of a variable.

See the ‘set’ command entry for details of environment variables.

usage

Prints a formatted dump of processor-specific usage statistics. For Berkeley Unix, this includes all of the information in the getrusage() structure.

verify [-m method] [-v] file1 [file2]

Verify the Boolean equivalence of two networks. file1 is compared with the current network when file2 is not specified, otherwise, file1 is compared with file2. The input and output variables from two networks are associated by their names.

The -m option specifies the verification method. If method is clp (default), two networks are collapsed and compared as PLA's. If method is bdd, the BDD's are constructed for both networks and compared.

The -v option engages the "verbose" mode of verify.

verify_fsm [-o depth] [-v n] [-m method] filename.blif

Verify the equivalence of two synchronous networks. The current network is compared with filename.blif. The input and output variables from the two networks are associated by their names. It is assumed that all the latches in both designs are clocked by a single, global clock. The verification is done by implicitly enumerating all the states in the product machine, and checking that the outputs are equivalent for all reachable state pairs starting from the initial state of the product machine.

-o depth allows the specification of the depth of search for a good variable ordering. A larger value for depth will require more CPU time but determine a better ordering. The default value is 2.

-v allows specification of the verbosity level of the output.

The -m option specifies method for determining the reachable states. consistency builds the entire transition relation and uses it to determine the reached states. bull does output cofactoring to find the reachable states. The product method is similar to the consistency method but input variables are smoothed as soon as possible as the characteristic function is being built. This makes the size of the resulting BDD representing the characteristic function of the transition relation smaller. The default method is product.

wd [-c] node1 node2

The wd command (which stands for "weak division") is very similar to resubstitution (resub command), except that instead of operating on the entire network, wd simply reexpresses node1 in terms of node2.

The -c option allows re-substitution of the complement of node2.

write_astg [-p] [<file-name>]

Write a text description of an ASTG to a file, or stdout if no filename is given. See read_astg for a description of the format.

The -p option forces implied places to be written explicitly in the description. Normally a place with exactly one fanin and one fanout transition is suppressed by specifying the fanout transition as adjacent to the fanin transition.

write_bdnet [filename]

Write the current network to file filename in the format for a net-list defined by bdnet(1). This is allowed only after the network has been mapped into a final implementation technology.

The environment variable OCT-CELL-PATH defines where the cell library is located. If a cell does not have a leading '~' or '/' in its name, then OCT-CELL-PATH is prepended to the filename.

The variable OCT-CELL-VIEW defines the viewname to be used if the cell does not have a ':' in its name to separate the cell name from the view name.

The variables OCT-TECHNOLOGY, OCT-VIEWTYPE, and OCTEDITSTYLE define the technology, view-type, and edit-style properties for the Oct cell.

write_blif [-s] [-n] [filename]

Write the current network to file filename in the Berkeley Logic Interchange Format (blif).

The -s option uses the network short names rather than the network long names for the blif file. This can be used to encrypt the names of a net-list.

The -n option uses the net-list format of blif when a node has a gate implementation in the library.

write_eqn [-s] [filename]

The write_eqn command prints out the equations from the current network according to format specifications laid out in the documentation for read_eqn. Both primary inputs and outputs are indicated.

The -s option uses the network short names rather than the network long names for the output.

If filename is not specified the equations will be written to standard out, otherwise they will be written into the given file and may be read by read_blif at a later time.

Note that since the eqn format uses the '(' and ')' characters for grouping, they cannot appear in any of the signal names.

write_kiss [filename]

The current state transition graph is saved in kiss2 format to the file filename or printed to the screen if no filename is given.

write_oct [-m] cell[:view]

Write the current network to the Oct facet cell:view:contents. If view is not specified, it will default to `logic'.

If the -m flag is specified, the network is merged into an existing network. All of the logic elements and internal nets are ripped up and replaced with the new network. Oct net names are used to determine how to merge in the network, so if the net names at the interface of the logic are not defined the merge will fail.

The environment variable OCT-CELL-PATH defines where the cell library is located. If a cell does not have a leading '~' or '/' in its name, then OCT-CELL-PATH is prepended to the filename.

The variable OCT-CELL-VIEW defines the viewname to be used if the cell does not have a ':' in its name to separate the cell name from the view name.

The variables OCT-TECHNOLOGY, OCT-VIEWTYPE, and OCTEDITSTYLE define the technology, view-type, and edit-style properties for the Oct facet.

write_pla [filename]

Write the current network to file filename in the Berkeley PLA Format. No optimization is done on the PLA.

write_slif [-s] [-n] [-d] [filename]

Write the current network to the file filename in the Stanford Logic Interchange Format (SLIF).

The -s option uses the network short names rather than the network long names for the SLIF file. This can be used to encrypt the names of a net-list.

The -n option uses the net-list format of SLIF when a node has a gate implementation in the library.

The -d option makes the SLIF writer print out any delay information known about the current network. This is not the default because a standard for printing delay information has not been established for the SLIF format.

The following commands are specific to the design of Actel FPGA devices.

act_map [-h heuristic_num] [-n num_iteration] [-f collapse_fanin] [-g gain_factor] [-d decomp_fanin] [-r filename] [-M MAXOPTIMAL] [-qolDsv]

Routine to find an optimal mapping to the Actel architecture. The input is the Boolean network and the output is a netlist and the block count (reference: An Architecture for Electrically Configurable Gate Arrays, Gamal et. al., IEEE J. of Solid State Circuits, April 1989, pp. 394-398).

act_map synthesizes the given circuit onto Actel architecture. It uses a tree-mapping approach to cover the subject graph with the pattern graphs. The pattern graphs are hard-wired into the code and so no library is to be read in. Subject graph and pattern-graphs are in terms of 2-1 muxes. Subject graph is constructed for each intermediate node of the network. Either an OBDD (Ordered BDD) and/or a BDD is constructed for each such node. After the entire network is mapped, an iterative_improvement phase may be entered.

Following options are supported:

-h heuristic_number specifies which one of the two subject_graphs would be constructed.

heuristic num = 1 => OBDD

heuristic num = 2 => BDD (default)

heuristic num = 3 => program decides which one to construct.

heuristic num = 4 => both are constructed and the one with lower mapped cost is selected. Gives the best result, but typically takes more time.

-M MAXOPTIMAL constructs an optimal OBDD for a node if number of fanins is at most MAXOPTIMAL.

-n num_iteration specifies the maximum number of iterations to be performed in the iterative_improvement phase. Each such iteration involves a good_decomposition followed by a partial_collapse routine. Partial_collapse tries to collapse each node into its fanouts. Default is -n 0.

-f collapse_fanin considers only those nodes for partial_collapse which have fanin no more than collapse_fanin. (Default: -f 3).

-g gain_factor makes the program enter the next iteration only if gain in the present iteration is at least (present_cost * gain_factor). (Default: -g 0.01)

-d decomp_fanin considers only those nodes for good_decomposition which have fanin greater than or equal to decomp_fanin. (Default -d 4).

-r filename is the final mapping option. After mapping, a mapped network would be created, in which each intermediate node corresponds to one basic block of Actel architecture. A file filename having the netlist description in a BDNETlike format is also formed. The pin names of the basic block are the same as those given in a Figure in the paper on Actel architecture (reference: An Architecture for Electrically Configurable Gate Arrays, Gamal et al., IEEE J. Solid State Circuits, April 1989, pp. 394-398).

-q makes the program enter a quick_phase routine (after iterative_improvement phase), which greedily finds out if it is beneficial to implement the node in negative phase.

-D causes a disjoint decomposition routine to be invoked on the network before mapping starts.

-o causes the OR gate in the basic block to be ignored. So mapping is done onto a three-mux structure.

-v turns on the verbosity flag. When used, information about the algorithm is printed as it executes.

-s gives the statistics, regarding the block count of the circuit.

This is a package to optimise the Boolean network and map it onto the Xilinx Programmable Gate Array architecture (reference: Xilinx, the Programmable Gate Array Data Book, Xilinx Corporation). All the routines except xl_merge can be used to map the design onto an architecture with a CLB (Configurable Logic Block) realising an arbitrary function of up to n inputs, where n >= 2. The package contains the following commands available to the user for experimentation.

Suggested script -

time

sweep

simplify

sweep

simplify

xl_split -n 5

sweep

simplify

xl_split -n 5

sweep

xl_partition -n 5

sweep

simplify

xl_partition -n 5

sweep

xl_k_decomp -n 5

sweep

xl_cover -n 5 -h 3

xl_merge

time

Commands :

xl_absorb [-n support] [-f MAX_FANINS] [-v]

Given a possibly infeasible network, moves fanins of the nodes so as to decrease their number of fanins. Some infeasible nodes may become feasible and decomposition may not be applied on them.

-n: support is the size of the TLU block (default = 5)

-f: Does not move fanins of a node if it has more than MAX_FANINS (default 15).

-v: turns on the verbosity flag. When used, information about the algorithm is printed as it executes.

xl_ao [-n support]

Uses a cube-packing heuristic to do an AND-OR decomposition of an infeasible network. This is fast and the result is a feasible network.

-n: support is the size of the TLU block (default = 5)

xl_coll_ck [-n support] [-c collapse_input_limit] [-kv]

Assumes a feasible network. If the number of inputs to the network is at most collapse_input_limit (default 9), collapse the network, apply Roth-Karp decomposition and cofactoring schemes. Pick the best result and compare with the original network (before collapsing). If the number of nodes is smaller, accept the better decomposition. Does nothing if n = 2.

-k: does not apply Roth-Karp decomposition, just use cofactoring.

-n: support is the size of the TLU block (default = 5)

-v: turns on the verbosity flag. When used, information about the algorithm is printed as it executes.

xl_cover [-n number] [-h heuristic number]

For mapping onto Xilinx architecture. The initial network should have all intermediate nodes with fanin less than or equal to number (default is 5). Mathony's binate covering algorithm is used to minimise the number of nodes in the network. Different heuristics are used to solve the covering problem. The heuristic number can be specified by -h option. Heuristic number can be 0, 1, 2 or 3:

- 0 (exact),

- 1 (Mathony's method - stop when first leaf is reached),

- 2 (For large examples),

- 3 (default: automatically decides between 0 and 2)

xl_decomp_two [-n support] [-l lower_common_bound] [-L cube_support_lower_bound] [-f MAX_FANIN] [-c MAX_COMMON_FANIN] [-u MAX_UNION_FANIN] [-v]

Given an infeasible network, does decomposition knowing that each Xilinx3090 CLB can have two functions if they have no more than MAX_FANIN (default = 4) fanins each, their union has at most MAX_UNION_FANINS (default = 5) fanins and they have at most MAX_COMMON_FANINS (default = 4) common fanins. It does so by considering certain cubes of all the infeasible nodes of the network, and associating an affinity value with each cube-pair. Extracts cube-pairs with high affinity. Need to do a decomposition later to make the network feasible.

-n: support is the size of the TLU block (default = 5)

-l: do not consider a cube-pair for extraction if their number of common inputs is less than lower_common_bound (default = 2).

-L: do not consider a cube if it has less than cube_support_lower_bound inputs.

-v: turns on the verbosity flag. When used, information about the algorithm is printed as it executes.

xl_imp [-n support] [-c cover_node_limit] [-l lit_bound] [-Aabm] [-g good_decomp] [-M MAX_FANINS] [-v verbosity level]

Given an infeasible network, replaces each internal infeasible node by a set of feasible nodes. These nodes are derived by trying different decomposition strategies (like xl_ao, xl_split, cofactoring, decomp -d and tech_decomp -a 2 -o 2), each followed by a partition/cover phase. In the end, picks the best result (the one with minimum number of feasible nodes). The result is a feasible network.

-n: support is the size of the TLU block (default = 5)

-A do not move fanins around after decomp -g.

-a: do not apply all decomposition methods. Only cubepacking on sum-of-product (SOP), cube-packing on factored form (if g flag != 0) and cofactoring. If this option is not specified, also apply Roth-Karp, tech_decomp, decomp -d, and xl_split.

-b: for best results, use this option. Effective on a node only if its number of literals is greater than lit_bound. In that case, after the good decomposition, recursively call the command for each of the nodes in decomposition. Time consuming.

-c: sets the limit for the cover algorithm used after each decomposition. If the number of feasible nodes for an infeasible node is no more than cover_node_limit, then exact cover is used, else heuristic (-h 3) option is used. (default = 25).

-g: if 0 (default), do not use decomp -g for cube-packing, just SOP. If 1, use only decomp -g, not SOP. If 2, use both decomp -g and SOP for cube-packing, and pick the best result.

-l: if the infeasible node has greater than lit_bound literals, does a good decomposition of the node (i.e. decomp -g) (default: 50)

-m: While doing partition, move fanins around for a node with at most MAX_FANINS (default 15).

-v: this sets the verbosity level (amount of information printed as the algorithm proceeds) to verbosity_level.

xl_k_decomp [-n support] [-p node_name] [-v verbosity_level] [-f MAX_FANINS_K_DECOMP] [-de]

Uses Karp-Roth disjoint decomposition to recursively decompose nodes of the network having fanin greater than support to obtain nodes each having fanin of at most support. If -p node_name is specified, only the node with the name node_name is decomposed. Otherwise, all the nodes that have fanin greater than support are decomposed. If -d option is specified, then if k_decomp fails to find a disjoint decomposition on a node, the node is not decomposed by cubepacking. Option -e allows an exhaustive search over all possible partitions to pick the best decomposition of a node. Then the option -f MAX_FANINS_K_DECOMP sets the limit on maximum number of fanins of a node for exhaustive decomposition. If the number of fanins is higher, only the first input partition is considered.

xl_merge [-f MAX_FANIN] [-c MAX_COMMON_FANIN] [-u MAX_UNION_FANIN] [-n support] [-o filename] [-vlF]

Used for mapping onto Xilinx architecture. It selects pairs of nodes of the network that can be merged so as to minimise the number of nodes and solves an integer program using the package Lindo. In the end it lists the pairs of nodes that were merged. The command does not change the network.

-f: MAX_FANIN is the limit on the fanin of a mergeable node (default = 4).

-c: MAX_COMMON_FANIN is the limit on the common fanins of two mergeable nodes (default = 4).

-u: MAX_UNION_FANIN is the limit on the union of the fanins of two mergeable nodes (default = 5).

-n: support is the limit on the number of fanins of a single function that can be put on a CLB (default = 5).

-o: filename is the file in which information about the nodes merged is printed. Must specify.

-l: Do not use lindo, an integer-linear programming package used to solve the matching problem. Instead use a heuristic. If not specified, the program first searches for lindo in the path. If found, lindo is invoked, else the program automatically calls the heuristic.

-F: If the input network is say a 4-feasible network and the support = 5, it may be possible to reduce the number of nodes after matching. If this option is not used,xl_partition is called after matching step on the subnetwork composed of unmatched nodes. Otherwise, only matching is done and the network remains unchanged.

-v: turns on the verbosity flag. When used, information about the algorithm is printed as it executes.

xl_part_coll [-n support] [-C cost_limit] [-c cover_node_limit] [-l lit_bound] [-Aabm] [-g decomp_good] [-M MAX_FANINS] [-v verbosity_level]

This is a partial collapse routine. On an infeasible network, first runs trivial partition routine. Then for each node, finds the cost of the node using a routine similar to xl_imp. Collapses each node into fanouts and computes the cost of the fanouts likewise. If the new cost of the fanouts is less, accepts the collapse. Deletes the collapsed node from the network. It does this until no more collapses can be beneficially carried out. The nodes are visited topologically. The result is a feasible network.

-C: tries only those nodes for collapsing whose cost is less than or equal to cost_limit. Our experience has been that it is beneficial to collapse only feasible nodes. So the default is 1.

Other options are the same as in xl_imp except -c has default of 10 and -A means move fanins around.

xl_partition [-n support] [-M MAX_FANINS] [-v verbosity_level] [-tm]

Tries to reduce the number of nodes by collapsing nodes into their fanouts. Also takes into account extra nets created. Collapses a node into its fanout only if the resulting fanout is feasible. Associates a cost with each (node, fanout) pair which reflects the extra nets created if node is collapsed into the fanout. It then selects pairs with lowest costs and collapses them. The starting network need not be feasible, in which case the resulting network also may not be. But if the starting network is, so is the resulting network.

-n: support is the size of the TLU block (default = 5)

-t: Our experience was that if one is just interested in minimization of number of nodes, then those nodes which can be collapsed into all their fanouts are the main reduction contributors. This option removes a node from the network if it can be collapsed into all its fanouts. Very fast.

-m: move fanins around to increase collapsing possibilities. Do so for a node only if after collapsing, it has at most MAX_FANINS (default = 15)(as specified by -M option).

-v: this sets the verbosity level (amount of information printed as the algorithm proceeds) to verbosity_level.

xl_rl [-n support] [-m] [-M MAX_FANINS] [-t (trav_method-levels)] [-c collapse_input_limit] [-v verbosity_level]

Used for timing optimization for table look up architectures (phase 1). Given a feasible network (obtained say by using speed_up), reduces number of levels for table look up with "support" inputs. If -m is not given, it tries to move fanins for each node also, provided the number of fanins of the node does not exceed MAX_FANINS (default 15). As a final step, tries collapsing the network if number of inputs to the network is at most collapse_input_limit (default = 10). Then applies Roth-Karp decomposition and cofactoring (support > 2). If number of levels decreases, accepts the better decomposition.

-n: support is the size of the TLU block (default = 5)

xl_split [-n value] [-d]

Ensures that every node in the network has number of fanins less than or equal to value. This is accomplished by using kernel extraction and AND-OR decomposition. -d turns on debugging facilities.

SIS can read and write files in a number of different formats, most of which are provided as interfaces to other cad packages. However, all file formats contain only ASCII text and can be viewed and printed as required.

Component libraries, used for technology mapping, are also stored as text files.

The following operators may be used to construct the expression -

For example -

This format originated with the espresso two-level minimisation program intended for use in PLA design.

The following keywords are recognised, where [d] denotes a decimal number and [s] denotes a text

string.

The product terms (one per line) are now specified -

Example -

In order to represent sequential designs, the previous truth-table format is extended to include ‘present state’ and ‘next state’ entries, so allowing state tables to be described.

The following additional commands are used -

The entries in the state table are now given -

Example -

Specifications for asynchronous circuits are given in a text representation of an Asynchronous Signal Transition Graph. An ATSG is a form of Petri net.

The ‘Berkeley Logic Interchange Format’ describes a logic circuit comprised of a set of simple components or cells. These components may be logic gates, library components, flip-flops or state machines (sequential components).

A full description of the BLIF format is given in Appendix A of the paper "SIS: A System for Sequential Circuit Synthesis".

The following example shows a BLIF file containing a KISS state machine -

Stanford (university) Logic Interchange Format. Similar but different to BLIF.

Component libraries, made up of combinational ‘gates’ and flip-flops or latches, are described in this format.

A library component is specified in the following format -

Logic gates and other combinational devices are specified as follows -

GATE "cell_name" area equation

PIN pin_name phase input_load max_load

rise_delay rise_fanout_delay

fall_delay fall_fanout_delay

Where -

Notes -

3-input NOR gate, max fanout 999, same delays on all pins.

2-input XOR gate - note that the two forms of the output function are equivalent, but have different NAND decompositions. This means that the library cell matching algorithm requires both forms be available.

2-input MUX with different loading and delay characteristics per pin. Note that either D1 or D2 may determine the overall propagation delay, depending upon the loading.

Flip-flops and latches are specified as follows -

LATCH "cell_name" area equation

PIN pin_name phase input_load max_load

rise_delay rise_fanout_delay

fall_delay fall_fanout_delay

SEQ latch_input latch_output Latch_type

CONTROL clock_pin_name input_load max_load

rise_delay rise_fanout_delay

fall_delay fall_fanout_delay

CONSTRAINT pin_name setup_time hold_time

Where the parameters are as for combinational cells, with the addition of -

The CONTROL statement is only required for clocked devices, and specifies the propagation delay between the clock pin and the output. It has the same format as the PIN statement.

The CONSTRAINT statement optionally specifies the setup and hold time constraints of a pin with respect to the clock signal. If it is not specified, values of 0.0 are assumed.

Examples -