Microsoft PowerPoint – 052-optimizing-the-comparator
9/26/2016
University of Illinois at Urbana-Champaign
Dept. of Electrical and Computer Engineering
ECE 120: Introduction to Computing
Analyzing and Optimizing the
Bit-Sliced Comparator
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 1
Area Heuristic for One Comparator Bit Slice is 20
Let’s analyze
area and delay.
How many
literals?
How many
operators?
So area is 20.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 2
12
8 (6 AND, 2 OR)
How Many Gate Delays to Z1?
A to Z1:
C1 to Z1:
C0 to Z1:
B to Z1:
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 3
2 gate delays
2 gate delays
not relevant
2 gate delays
(ignoring NOT)
Delays to Z0
are symmetric.
Extending from One Bit Slice to N Bit Slices
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 4
What happens in an N-bit design?
Say that A and B are available at time 0.
0 0 0 0
9/26/2016
Constant Inputs are Available Arbitrarily Early
What about the 0s on the right?
Available “forever” … (time -∞).
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 5
0 0 0 0
– ∞
– ∞
Use Bit Slice Timing to Calculate Times Between Slices
Now we must
◦ use the delays that we found for one bit slice
◦ to calculate times for inter-slice C values.
Recall that
◦ all A and B bits are available at time 0,
◦ so the C to Z delays are the most important.
We found
◦ C1 to Z1: 2 gate delays
◦ C0 to Z0: 2 gate delays
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 6
Calculate the Time at Which CM Becomes Available
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 7
0 0 0 0
– ∞
– ∞
When
available?
2
2
When
available?
4
4
A More Detailed Version of Our Calculations
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 8
Grey is “not relevant,” and green is maximum
(time at which Zi is available).
(bit slice 0) A B C1 C0
input available at 0 0 -∞ -∞
delay from input to Z1 +2 +2 +2
Z1 not available until 2 2 -∞
delay from input to Z0 +2 +2 +2
Z0 not available until 2 2 -∞
9/26/2016
A More Detailed Version of Our Calculations
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 9
Grey is “not relevant,” and green is maximum
(time at which Zi is available).
(bit slice 1) A B C1 C0
input available at 0 0 2 2
delay from input to Z1 +2 +2 +2
Z1 not available until 2 2 4
delay from input to Z0 +2 +2 +2
Z0 not available until 2 2 4
Generalize the Result to an N-Bit Comparator
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 10
and are available at time 2
(2 gate delays).*
and are available at time 4.
When are and available (these
are the answer for an N-bit comparator)?
*In the notes, the inverters are counted, so paths from A and B
are slightly longer, and all timings are increased by 1.
N-bit answer is available at time 2N.
We May be Able to Improve Our Comparator Design
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 11
Can we do better?
(You should ask: better in what sense?)
Can we reduce delay?
◦Unlikely with a bit-sliced design.
◦Not easy to implement most functions
with one gate.
Can we reduce area?
◦Maybe …
◦Let’s do some algebra.
Use Algebra to Find Common Subexpressions (A’B, AB’)
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 12
Start with Z1 = AB’ + AC1 + B’C1
then use distributivity to pull out C1:
Z1 = AB’ + (A + B’)C1
and rewrite the (A + B’) factor as a NAND:
Z1 = AB’ + (A’B)’C1
Similarly, Z0 = A’B + (AB’)’C0
Notice that we now reuse AB’ and A’B.
9/26/2016
The New Implementation Uses Fewer Gates
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 13
The diagram below shows the new equations
using NAND gates.
The single-bit core is here.
(AB’)’
(A’B)’
((A’B)’C1)’
Z1 = [ (AB’)’ ((A’B)’C1)’ ]’
= AB’ + (A’B)’C1
Area Heuristic for the New Design is 12
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 14
6 (NAND)
6
Let’s analyze area for the new design.
How many literals?
How many operators?
Delay Analysis for the New Design
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 15
A to Z1:
C1 to Z1:
B to Z1:
3 gate delays (ignoring NOT)
2 gate delays
3 gate delays
50% slower?!
Calculate the Time at Which CM Becomes Available
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 16
0 0 0 0
– ∞
– ∞
When
available?
3
3
When
available?
5
5
9/26/2016
A More Detailed Version of Our Calculations
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 17
Grey is “not relevant,” and green is maximum
(time at which Zi is available).
(bit slice 0) A B C1 C0
input available at 0 0 -∞ -∞
delay from input to Z1 +3 +3 +2
Z1 not available until 3 3 -∞
delay from input to Z0 +3 +3 +2
Z0 not available until 3 3 -∞
A More Detailed Version of Our Calculations
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 18
Grey is “not relevant,” and green is maximum
(time at which Zi is available).
(bit slice 1) A B C1 C0
input available at 0 0 3 3
delay from input to Z1 +3 +3 +2
Z1 not available until 3 3 5
delay from input to Z0 +3 +3 +2
Z0 not available until 3 3 5
The Slice-to-Slice Paths are the Important Ones
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 19
and are available at time 3
(2 gate delays).*
and are available at time 5.
When are and available (these
are the answer for an N-bit comparator)?
*In the notes, the inverters are counted, so paths from A and B
are slightly longer, and all timings are increased by 1.
N-bit answer is available at time 2N+1.
Overall: Much Better Area for Slightly More Delay
So the new design
◦ reduces area by about 40%
(area 12N compared to area 20N).
◦ increases delay by 1
(2N+1 gate delays compared to
2N gate delays).
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 20
9/26/2016
Can We Do Even Better?
Yes, but it’s not as easy.
For example, we can design a slice
◦ that compares multiple bits of A and B.
◦See Notes 2.4.6 for an example.
We can also solve the full N-bit problem.
In other words, trade more human work
and complexity for better area and delay.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 21