程序代写代做代考 Microsoft PowerPoint - 052-optimizing-the-comparator

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

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.

8 (6 AND, 2 OR)

How Many Gate Delays to Z1?

A to Z1:

C1 to Z1:

C0 to Z1:

B to Z1:

2 gate delays

not relevant

2 gate delays
(ignoring NOT)

Delays to Z0
are symmetric.

Extending from One Bit Slice to N Bit Slices

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 -∞).

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

Calculate the Time at Which CM Becomes Available

0 0 0 0

– ∞

When
available?

A More Detailed Version of Our Calculations

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

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

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

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’)

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

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

6 (NAND)
6

Let’s analyze area for the new design.
How many literals?
How many operators?

Delay Analysis for the New Design

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

0 0 0 0

– ∞

When
available?

9/26/2016

A More Detailed Version of Our Calculations

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

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

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).

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.

Related Posts