Practical training with sis
1.Organization
For the course Computation you need to finish the practical training with sis. The training consists of a homework assignment and will be completed after a 10 minute oral exam at which the homework needs to be handed in. During the oral exam you need to you come in couples, and both need to be able to demonstrate the homework, so make sure you have your laptop running.
On Monday 31st October and Tuesday 1st November (08.45-10.30) the lab takes place. After the lab on 14 November (check the website for the latest updates) from 13.30 to 17.00, an instructor will be available in room EH9.05 to answer questions in case of problems. You should try to finish the assignment by then, since this arethe only possibility for you to consult an instructor. You can walk in and out, so do not all come at the same time. Together with a few students, the instructor will pick the dates at which the oral exam will take place. This will be 1 or two weeks later, depending on the exams and preference of the students. You need to subscribe yourself for this oral exam. There will be a list at the secretaries’ room at the ninth floor. Unless announced differently, the oral exams will take place in room EH9.17. Again, make sure you have the answers on paper and have your laptop running.
Updates and errata will be published on the computation web-page.
2.Contact
If you have difficulties with sis or have other question, send them to Calin Ciordas:.
3.Very short introduction to Linux
The program sis only runs under Linux. Make sure you have Linux running as fast as possible. If you have problems installing Linux, consult with the notebook service center. Make sure you remember the root password.
You can start a terminal or console as follows. Right-click on the background, and choose Open Terminal. You will use an editor to create files. You can start the gedit editor by clicking on the red hat on the lower-left, Accessories, Text editor. Alternatively, you can type gedit & at the command prompt. You can start a web browser by clicking on the globe on the taskbar.
On the web there are many tutorials on Linux. Here, only the very basics are given. First, note that the file-separator character is a slash (‘/’) rather than a backslash (‘\’) as under DOS/Windows. The Linux equivalents of cd, dir, del and md are cd, ls, rm and mkdir, respectively. For help on such commands you can usually add the option --help, or use man <command> for extensive documentation
Linux was developed as a multi-user system, and every user has his own home-directory. If you simply type cd, or cd ~, you go to this directory. In principle, this is the only directory (with its sub-directories) in which you have permission to write files.
4.Introduction to sis
Sis is a program for logic synthesis and optimization. Among others, truth tables, Boolean expressions and state diagrams can be used to input a specific function. This function can be manipulated by typing commands at the prompt or by using scripts. Eventually, the function can be mapped onto a library. With the function help, you can find the available commands.
Extensive documentation on sis is available in the document SIS_paper.ps, which is located in the directory sis-1.2_RH9/. You can read it for instance with the PostScript viewer that comes with linux (Red Hat -> Graphics -> PostScript viewer).
Running sis
Sis runs on a linux machine called o2.ics.ele.tue.nl. You need to do some things to make it accessible on your pc.
You need to tell your system to look on o2. Sis will be locally available in the directory /mnt/sis:
su (You become root. Give the root password you have chosen).
mkdir /mnt/sis
mount o2.ics.ele.tue.nl:/opt/sis /mnt/sis
exit
If you now type
ls /mnt/sis
You should see
sis-1.2_RH9
We want to make sis available anywhere on your system. Therefore, you need to tell the system where to look. This information is stored in the system variable PATH. Add the current directory and the directory where sis is stored to the path.
Open the file .bash_profile in your home directory with an editor.: add :.:/mnt/sis/sis-1.2_RH9/bin to the line starting with PATH. The line is now probably
PATH=$PATH:$HOME/bin:.:/mnt/sis/sis-1.2_RH9/bin
You can now make your changes work by exiting the editor and using the source command:
source .bash_profile
Make a directory where you store your work, and start sis from there. If you do not start sis from this directory, sis will not know how to find your files.
cd ~
mkdir sis_files
cd sis_files
gedit
sis
Every time you run sis, you have to mount sis on o2 and source the file.bash_profile. A session will from now on start with the following commands:
su
mount o2.ics.ele.tue.nl:/opt/sis /mnt/sis
exit
source .bash_profile
cd sis_files
sis
Examples
With a text editor you can create functional descriptions from which sis can read.
Example 1.
A file called eq.eqn containing the single line
O = a*b + !c*((d+e+f)*!(g+h));
can be read through the following sis command.
sis> read_eqn eq.eqn
We can see the result with the command print.
sis> print
{O} = a b + c' d g' h' + c' e g' h' + c' f g' h'
Example 2.
It is possible to specify so called logical networks in the blif format (Berkeleylogic interface format). This format supports truth tables. Below is an example that creates a network with NOR3 functionality by using two nodes with OR functionality, and one with inverter functionality.
# Start blif file
# Start with the name of the model
.model NOR3
# Define inputs and outputs of the WHOLE circuit
.inputs a b c
.outputs out
#define an OR2; truth table only contains positive entries
# use an internal signal and don’t cares
.names a b int1
1- 1
-1 1
# another OR2
.names int1 c int2
10 1
01 1
11 1
# The inverter is left
.names int2 out
0 1
# Close the description
.end
We can read the file as follows.
sis> read_blif nor3.blif
sis> print
{out} = int2'
int1 = a + b
int2 = c int1 + c int1' + c' int1
Example 3.
We can also specify a state machine in the blif format. The example below is a parity checker. The input is serial. It has one input: the next bit, and one output: 0 if there is an even number of 1s until now, and a 1 if this number is odd. There are two states: one for “even until now”, and one for “odd until now”. Sis can perform a number of operations to synthesize and optimize the state machine. One of these operations is called state_assign.
# Tell sis we specify a state machine
.start_kiss
# one input, one output
.i 1
.o 1
# <input> <current_state> <next_state> <output>
0 EVEN EVEN 0
1 EVEN ODD 1
0 ODD ODD 1
1 ODD EVEN 0
.end_kiss
Again, this file can be read with the read_blif command.
sis> read_blif parity.blif
sis> state_assign
command is : nova < /cygdrive/c/sis2/TEMP/SISDAAa00544 > /cygdrive/c/
sis2/TEMP/SISEAAa00544
Running nova, written by Tiziano Villa, UC Berkeley
sis> print
{OUT_0} = IN_0 LatchOut_v1' + IN_0' LatchOut_v1
v2.0 = IN_0 LatchOut_v1' + IN_0' LatchOut_v1
Assignment 1
In this assignment, we will have a look at some optimization techniques in sis. We will use a simple example. With each command that you issue, try to find out what happened, and if and how this could be useful.
1.1Find the least-number of literals expression for the following boolean function by hand:
f = b (a + c) + !a c + c (!a + b)
1.2Create a file 1_2.eqn containing the equation given in the previous question. Start sis, and read the file. Invoke print. What has sis done?
1.3Invoke simplify. Is the resulting expression equivalent to the original one? Prove this.
1.4Create a blif file for the network below, and save it as 1_4.blif. Invoke print. Is this the network as you entered it?
1.5Invoke collapse w r. Draw the resulting network. Is the functionality still the same?
1.6Run sweep. What happened? Can this be beneficial? Why?
1.7Invoke decomp y on the original network. Draw the resulting network. What has happened?
1.8Run print_kernel z q on the original network. How can the displayed information be used to optimize the network?
1.9Run gkx –1. Which part of the network has changed?
1.10Repeat 1.9.
1.11Run simplify x on the original network. What has changed?
Assignment 2. A vending machine
We will develop the electronics of a simplified vending machine. Our vending machine sells one product for 25 eurocents. It accepts only coins of 5 and 10 eurocents. The product is released by a ‘1” on the output of the circuit if exactly 25 cents is inserted. A sensor detects what was inserted. If it is not a valid coin, it is directly returned, so the circuit you design only gets signals for 5 and 10 cents.
2.1 What are the input-signals for our circuit? How many bits do we need to code this? Give such a coding.
We need to keep track of what was inserted in the machine, in order to know when to release the product. In this case, the machine keeps track of how many nickels and how many dimes were inserted. If e.g. first a nickel, then a dime and then a nickel again was inserted, the machine knows that in total one dime, and two nickels were inserted.
2.2 List all combinations of dimes and nickels that make up 25 cents.
2.3 Between the combinations you listed in 2.2 and the empty starting state, the machine may contain different combinations of coins. List those combinations (include the empty state). The order in which the coins were inserted is not of interest since the machine only stores the amount of each coins that is stored.
It turns out that the reservoir for the coins is a bit small. As a non-elegant last-minute way to solve this, it is decided to accept no more than four coins.
2.4 Repeat 2.3 for the new situation. You need to remove the combinations that necessarily will lead to more than four coins.
2.5 Each combination you listed in 2.4 represents a state the machine may be in. How many bits do you need to code all possibilities of 2.4? Give such a coding.
It is decided to use the following block diagram for the implementation of our piece of electronics.
The combinations of 2.4 represent the states. We are going to design “Our circuit”. The signal c is a one bit signal that is 0 if there is a nickel inserted, and 1 if a dime is inserted. If no coin is inserted, it is unknown what the signal is. The “Coins available” signal is 1 if some coin (either a dime or a nickel) is inserted, and 0 if no coin is inserted. The “coins available” signal prevents the product to be given if no money is inserted. If in total too much money is inserted, we assume for now that the product is given (20 cents already inserted, and subsequently a dime).
2.6 The circuit “Our circuit” is pure logic. How many input bits does the sub circuit have? How many outputs? Create a truth table that describes the function of the circuit. Use your own coding. Next, create a Karnaugh map and find a minimal sum of products expression. You do not have to make a state transition diagram.
It was decided to use the above block diagram because it is hard to make Karnaugh maps for more than four variables. Sis however, can handle truth tables with far more variables with ease. Therefore we decide to implement the whole diagram at once, using sis. The inputs are the coins and states signals, and the output is the Give_product signal.
2.7 Create a blif description of the circuit, and save it as 2_7.blif.
2.8 Minimize the literal count with sis. Use the commands that you have seen so far. Save the result as 2_8.blif. Write down the number of literals, and compare your results with your neighbor.
Don’t cares are used when a situation can not appear, or when we do not care about the output in this particular case. In our vending machine we have a similar situation. The circuit we are designing is part of a larger system. Some other sub-system checks if the input coins are valid. If for instance a whole euro was inserted, our circuit will get the same signals as if no coin at all was inserted. There is also a sub circuit that returns a nickel if already twenty cent was inserted. For our circuit, this means that in both cases the product should be given.
In the blif format, (External) Don’t Cares can be expressed as follows.
.exdc
.names a b out
# It never occurs that both a and b are 0
00 1
.end
2.9 Add the don’t cares to 2_7.blif, and save it as 2_9a.blif. Invoke simplify and look at the results. Invoke full_simplify, and look at the results. Save the result as 2_9b.blif. Explain what happened?
Until now, we have only dealt with boolean expressions. In real life, we need actual gates to implement these functions. The process from boolean expression to gate implementation is called technology mapping or library binding. There are multiple ways to implement a given boolean expression. The sis
command map tries to find an optimal mapping. Optimal may mean “as fast as possible”, or “as small as possible”, or somewhere in between. The algorithm needs information such as the size and speed of the different gates to be able to optimize. We will use the library lib2.genlib. It is located in the directory /mnt/sis/sis-1.2_RH9/sis/sis_lib. You can copy it to the sis_files directory, or load it from there immediately. Map statistics can be found through print_map_stats. A library is loaded through read_library.
2.10 Perform technology mapping for 2_7.blif and 2_9b.blif with the options –m 0 and –m 1. Write down the area and worst negative slack for both mappings for both circuits. This yields a table with 8 entries.
At the last minute, a design flaw is found. The vending machine may be empty. If a customer then inserts 25 cents, he simply loses his money. As a fix, a sensor that detects whether or not the machine is empty is added. It gives a '1’ if the machine is empty. This signal also becomes an input to our subcircuit. Besides for releasing a product, the output signal of our subcircuit is also used to “grab the money”. As long as the give product signal is not given, the customer can get his or her money back.
2.11 If you start all over, how large will the truth table be?
2.12 There is a faster way to add the extra signal. Use 2_9b.blif as the basis, and implement it the fast way. You only need a few extra lines. Save the file as 2_12.blif.
We have seen different boolean manipulations. In lots of (larger) cases, many of these manipulations need to be employed for a good result. Each of these manipulations may take some time. Therefore, one can create scripts that are basically a list of sis commands. Scripts can be run through the source command.
sis> source script.rugged.
The script script.rugged can be found in sis/sis/sis_lib. You can open it with an editor and have a look at it.
2.13 Try to minimize area for 2_12.blif by applying different commands. Let the scripts inspire you. Write down the area and worst slack numbers, and compare your results with your neighbors.
State machines
We have seen how we can implement logic. If we now add latches or flip-flops, we can implement a state machine. We have seen in example 3 that sis supports state machines as well. Of course, this is a faster way to design the electronics. On a separate piece of paper you find an incomplete Mealy state machine. Only the states are given.
2.14 What do the states represent?
2.15 Complete the state transition diagram. You do not need to add states. Just add the arrows between the states, and annotate them with the input and output signals. From now on, you do not need to take the situation when too much money is inserted into account. Simply leave it out.
2.16 Create a blif description of the diagram. Save it as 2_16.blif.
2.17 How many states are there? How many latches or flip-flops do you need at least to built this machine?
2.18 Load 2_16.blif, and run the command one_hot. How many latches are used? If we have a design with twice as many states, how many latches will one_hot use?
2.19 Reload 2_16.blif, and run state_assign. How many latches are used? If we have a design with twice as many states, how many latches will one_hot use?
2.20 Reload 2_16.blif, and run state_minimize stamina. Save the current situation with the command write_blif as 2_20.blif. How many states are are used?
2.21 Draw the state machine in 2_20.blif.
2.22 Give an interpretation of the states of the machine of the previous question.
2.23 Suppose we change the product in the vending machine, and it costs 50 cents. The machine will still only accept 5 and 10 cent coins. What is the minimum number of latches that is needed in this case?
2.24 If we also allow 20 cent coins, what is the minimum number of latches that is needed in this case? And what if we also allow 1 and 2 cent coins?