Description
1 Overview
This project illustrates the process of logic and data synthesis. Given an existing infrastructure in
C++, you will instantiate logic modules, including adders, multipliers, and a datapath module. All
files generated should be BLIF (Sec. 2), and verified using the software package abc from UC
Berkeley (Sec. 3).
2 Berkeley Library Interchange Format (BLIF)
Digital circuits can be represented in the Berkeley Library Interchange Format (BLIF). This format
defines a truth table for each logic element (e.g., gate) as well as the connections between these
elements.
The general format is as follows.
1 .model
2
3 .inputs
4
5 .outputs
6
7 .names
8 # truth table involving
9 # …
10 # many truth tables can be specified
11
12 .end
Line 1 defines the model or circuit name. Line 3 specifies the primary inputs of the circuit. Line
5 specifies the primary outputs of the circuit. Lines 7-10 specify a truth table for a logic element
with inputs in1 … ink and output out. A ’1’ means the variable is uncomplemented, a ’0’ means the
variable is complemented, and ’-’ means the variable is not set (don’t care). By default, any input
combinations not specified will mean the output result is 0. Therefore, it is sufficient to specify a
cover for the output function. Multiple truth tables may be specified to define the full logic of the
circuit. Line 12 defines the end of the model or circuit definition.
For example, given the following circuit definition (using Boolean logic), where the primary inputs are a, b, c, d, the primary output is f3
f1 = a+b
f2 = cd
f3 = f1 ⊕ f2
2
A corresponding BLIF file would be:
1 .model example
2
3 .inputs a b c d
4
5 .outputs f3
6
7 .names a b f1
8 0- 1
9 -1 1
10
11 .names c d f2
12 0- 1
13 -0 1
14
15 .names f1 f2 f3
16 01 1
17 10 1
18
19 .end
3 abc
abc (http://www.eecs.berkeley.edu/˜alanmi/abc/) is a free software package from
UC Berkeley that can validate the correctness of your circuit through equivalence checking.
Given a .blif file, you can check if the module you generated is equivalent to a trusted circuit.
Consider two simple circuits.
1 .model simple0 1 .model simple1
2 2
3 .inputs x y 3 .inputs x y
4 4
5 .outputs z 5 .outputs z
6 6
7 .names x y z 7 .names x y z
8 00 1 8 0- 1
9 01 1 9 -0 1
10 10 1 10
11 11 .end
12 .end
In this case, simple0 represents z = xy and simple1 represents z = x+y. The two circuits are
equivalent by de Morgan’s Law.
3
When verifying two circuits, the .inputs and .outputs must be exactly the same. Otherwise, abc will conclude that the two circuits are not equivalent, regardless of the logic. After
installing the package, you should see the following after starting up abc.
UC Berkeley. ABC 1.01
abc 01>
For this project, you will mainly be concerned with the command cec. To check the equivalency
of two .blif files, type the following after starting up abc.
cec file1.blif file2.blif
4 Provided Files
Log into CTools and download the tar ball eecs478p2.tar.gz. After you untar the tar ball, you
should see the following source files.
• truthTable.h and truthTable.cpp
• node.h
• circuit.h and circuit.cpp
• library.cpp, modules.cpp, and datapaths.cpp
• main.cpp
• Makefile
• adder16.blif
Feel free to modify any and all of these files to suit your needs. Please make sure that your final
binary is called project2.
4.1 truthTable.h and truthTable.cpp
These two files store the underlying infrastructure for representing a truth table. Each entry stored
represents a cover for the logic function.
4.2 node.h
This file defines a logical element (node) of a circuit. It includes a truth table, a list of fanin nodes,
and a type (PRIMARY INPUT, PRIMARY OUTPUT, INTERNAL, ZERO NODE, ONE NODE).
4
4.3 circuit.h and circuit.cpp
These two files define the circuit or model, which is defined as a collection of nodes.
4.4 library.cpp, modules.cpp, and datapaths.cpp
These three files contain the implementation of different functions defined in circuit.h.
• library.cpp contains functions operating on nodes (mainly used for internal purposes)
• modules.cpp contains the implementations of the logic modules
• datapaths.cpp contains the implementations of the datapath module
4.5 main.cpp
This file contains the general wrapper on how to use the executable. There is a ’-help’ function built
in. To see the usage, type ./project2 -help.
4.6 Makefile
This file compiles and creates the final binary for this project. You are allowed to modify this file and
add any optimization flags of your choice.
4.7 adder16.blif
This file is a reference .blif file that implements a 16-bit adder module.
5 Getting Started
Download and untar the package abc70930.tar.gz from CTools by typing
tar -xvf abc70930.tar.gz
Go into the abc70930 directory and type make. This should create the binary abc (it may take a
few minutes). If you’re having trouble installing abc, consult the readme file or go to
http://www.eecs.berkeley.edu/˜alanmi/abc/
Download the tar ball eecs478p2.tar.gz from CTools. To decompress the tar ball, type
tar -xvf eecs478p2.tar.gz
into a directory of your choosing. This will create a directory named eecs478p2, and will include
the necessary files for your program to compile. In that directory, compile the program by typing
make. To run the program, type ./project2. This will display the usage options of the binary.
You are allowed to do your development in any platform. However, we will be testing and
evaluating your code strictly on the CAEN Linux machines.
5
6 Tasks (100 points)
This section details the different tasks you must complete. Be sure and test your code thoroughly before submitting. The more testing you do, the more confident you can be that your code is correct. The
bulk of your modifications should be done in library.cpp, modules.cpp, datapaths.cpp,
and main.cpp, but feel free to modify other files as needed. If you plan on making substantial
changes to the code base, such as the underlying infrastructure, please consult with John or Shaobo
first.
6.1 Creating Simple Gates (10 points)
You must implement the following three functions found in library.cpp.
6.1.1 2-Input AND (3 points)
Complete the implementation for the function createAND2Node(…). This function should
create the logical AND function in the output node output from the two input nodes input1 and
input2.
6.1.2 3-Input XOR (3 points)
Complete the implementation for the function createXOR3Node(…). This function should
create the logical XOR function in the output node output from the three input nodes input1,
input2, and input3.
6.1.3 4-Input MUX With 2 Select Bits (4 points)
Complete the implementation for the function createMUX4Node(…). This function should
create a 4-input multiplexer with inputs input1 … input4 and two select bits select1 and
select2 in the output node output. Assume that the most significant bit (MSB) of the select bits
is select2, and the MSB of the input bits is input4. Likewise, the least significant bit (LSB) of
the select bits is select1, and the LSB of the input bits is input1.
6.2 Creating Logic Modules (55 points)
You must implement the following two logic modules found in modules.cpp. The adder module
is worth 25 points, and the multiplier module is worth 30 points. For all cases, let the MSB be the
bit with the highest index, and let the LSB be the bit with the lowest index. For instance, given
inputs a[3]a[2]a[1]a[0], a[3] is the MSB, and a[0] is the LSB. Please make sure the name/format of the
inputs/outputs are consistent with the name/format given in the instructions.
6
6.2.1 Adder (25 points)
Complete the implementation for the function createADDModule(…). This function should
create an numBits-bit adder that computes a+b+cin and stores the result in s and cout. Assume the
inputs are unsigned.
Primary Inputs: a[numBits−1]…a[0], b[numBits−1]…b[0], cin
Primary Outputs: s[numBits−1]…s[0], cout (cout is considered the MSB or equivalently s[numBits])
6.2.2 Multiplier (30 points)
Complete the implementation for the function createMULTModule(…). This function should
create an numBits-bit multiplier that computes a ∗ b and stores the result in s. Assume the inputs are
unsigned.
Primary Inputs: a[numBits−1]…a[0], b[numBits−1]…b[0]
Primary Outputs: s[2 ∗ numBits−1]…s[0]
6.2.3 Verification
It is your job to define a verification strategy and follow it throughout the project. You can start by
writing 1-bit and 2-bit modules in BLIF and then increase your bit-size to check the limits of your
program. We have provided a 16-bit adder adder16.blif to help verify the correctness of your
generated module.
You can use the BLIF simulator available in the sim.tar.gz file. This simulator runs in CAEN
machines only. You may also swap BLIF files with other students. If you do, state clearly who you
have collaborated with in your report. In any case, you should include your verification strategy in
your final report.
6.3 Creating a Datapath (20 points)
Complete the implementation function createSUMABMULTPLYSUMCDModule(…) in
datapaths.cpp. This function gets four 8-bit inputs a, b, c and d and returns an 18-bit output
z = (a + b) × (c + d). The inputs a, b, c and d are unsigned binary numbers. Note that unlike the
previous tasks, the inputs of this module are fixed to 8 bits and the output has 18 bits. As with the
logic modules, the MSB is the bit with the highest index, and the LSB is the with the lowest index.
Primary Inputs: a[7]…a[0],b[7]…b[0], c[7]…c[0],d[7]…d[0]
Outputs: z[17]…z[0]
You may use previously designed modules such as multiplexer, adder, multiplier, and shifter. You
may also want to design new modules to simplify your code.
7
6.4 Code Readability (5 points)
A small portion of points will be for coding style and readability. Your code does not need to be
perfectly clean, but should be well-structured and clear. The following are some helpful guidelines to
writing readable code.
• Use proper indentation when declaring while and for loops, and when declaring if statements.
• Avoid going over 80 characters per line.
• Write a 1-2 line comment for explaining non-standard coding syntax.
• Write a short comment for explaining what each function (or sub-function) does.
6.5 Report (10 points)
You will need to write a 1-2 page report using 12-point font in either .pdf or .doc format. On
the front page, print your name and uniquename. For each Task, write a brief description of your
implementation. Explain any specific issues you faced and any optimizations you performed (or
could have performed). In addition, include anything of interest that you think may be helpful when
evaluating your submission.
6.6 Additional Files To Submit
In addition to all your code, you must submit the following .blif files.
• add8 {uniquename}.blif (8-bit adder module).
• mult16 {uniquename}.blif (16-bit multiplier module).
• sumab multiply sumcd {uniquename}.blif ((a+b)×(c+d) datapath).
Be sure to replace {uniquename} with your own uniquename. For submission instructions, refer
to the front page.
8
