Transcript PTreeSVer Peano Count Tree based simulation and

Very Large Scale Integrated chips
(VLSI)
• The complexity of the digital computation chips is
increasing in line with Moore’s law.
• P6 (Pentium III family) architecture had 5-10 million
transistors
• Willamette (Pentium4) has 38 million transistors
• It is common today to have over a million transistors.
Cost of errors in ICs
• The requirements of most ICs do not allow for
errors in the design/manufacture
• The cost of discovering design bugs increases
exponentially after the product is shipped.
• The infamous Pentium bug cost intel $475
million in 1993.
How can errors be found BEFORE
building the chip? Simulation!
• Stimulate (apply input vectors) and then
propagate the values through the circuit and
observe the output values.
• Equivalence checking:
– Stimulate (apply input vectors) to 2 circuits, one
of them called the known_correct_circuit and the
other is the under_test_circuit
– check if the output matches when both of the
above circuits are applied the same input vector
Logic simulation
i
n
p
u
t
s
0
0
0
0
0 1
0 1
0
0
0
1
1 1
0 1
1
o
1 1 1 0 u
t
p
u
t
s
Different kinds of digital circuits
• Combinational circuit with n input bits and m
output bits with no don’t cares or properties
on the inputs (all 2n bit combinations are
valid inputs to the circuit)
• Combinational circuit with n input bits and m
output bits
• Sequential circuits: have definite set of input
bit vectors for each “test”.
Encoding of the function table
of a circuit into Ptrees
Bit1
Bit2
Sum
Carry
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Function table of a half adder circuit
Function table of a Full adder circuit
input1
input2
Carry
forward
Sum
Carry
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
0
0
1
0
1
1
1