COMP290-084 Clockless Logic

Acknowledgment
Michael Theobald and Steven Nowick, for providing slides for this lecture.

An Implicit Method for Hazard-Free
Two-Level Logic Minimization
Michael Theobald and Steven M. Nowick
Columbia University, New York, NY
Paper appeared in Async-98
(Best Paper Finalist)

☹
Hazard-Free Logic Minimization
Given: Boolean function and multi-input change

☺
Hazard-Free Logic Minimization

☺
Hazard-Free Logic Minimization
☹
f(A) ? f(B)
0 ? 0
0 ? 1
1 ? 1
1 ? 0

☺
Hazard-Free 2-Level Logic Minimization

Classic 2-Level Logic Minimization
Step 1. Generate Prime Implicants
Step 2. Select Minimum # of Primes …to cover all Minterms
Quine-McCluskey Algorithm

2-level Logic Minimization:
Classic vs. Hazard-Free
Classic (Quine-McCluskey):
Hazard-Free: cubes, DHF-Prime implicants>
Given: Boolean function & set of “multi-input” changes
Find: min-cost 2-level implementation guaranteed to be glitch-free
Required cubes = sets of minterms
DHF-Prime implicants =
maximal implicants that do not intersect privileged cubes illegally

Hazard-Free Logic Minimization
Non-monotonic
function hazard
no implementation
hazard-free
Monotonic
function-hazard-free
☺
☹
Restriction to monotonic changes
Multi-Input Changes:

Hazard-Freedom Conditions: 1 -> 1 transition
☺
☹
Required Cube
must be covered

Hazard-Freedom Conditions: 1 -> 0 transition

Hazard-Freedom Conditions: 1 -> 0 transition

Hazard-Freedom Conditions: 1 -> 0 transition

Hazard-Freedom Conditions: 1 -> 0 transition

Hazard-Freedom Conditions: 1 -> 0 transition

Hazard-Freedom Conditions: 1 -> 0 transition
☹

Hazard-Freedom Conditions: 1 -> 0 transition
☹
illegal intersection

Hazard-Freedom Conditions: 1 -> 0 transition
☺ No illegal intersection
of privileged cube
☹
illegal intersection

Dynamic-Hazard-Free Prime Implicants
Prime
NO DHF-Prime
illegal
intersection

2-level Logic Minimization:
Classic vs. Hazard-Free
Classic (Quine-McCluskey):
Hazard-Free: cubes, DHF-Prime implicants>
Given: Boolean function & set of “multi-input” changes
Find: min-cost 2-level implementation guaranteed to be glitch-free
Required cubes = sets of minterms
DHF-Prime implicants =
maximal implicants that do not intersect privileged cubes illegally
Main challenge: Computing DHF-prime implicants

Hazard-Free 2-level Logic Minimization:
Previous Work
Early work (1950s-1970s):
Eichelberger, Unger, Beister, McCluskey
Initial solution: Nowick/Dill [ICCAD 1992]
Improved approaches:
HFMIN: Fuhrer/Nowick [ICCAD 1995]
Rutten et al. [Async 1999]
Myers/Jacobson [Async 2001]
No approach can solve large examples

IMPYMIN: an exact 2-level minimizer
Two main ideas:
novel reformulation of hazard-freedom constraints
used for dhf-prime generation
recasts an asynchronous problem as a synchronous one
uses an “implicit” method
represents & manipulates large # of objects simultaneously
avoids explicit enumeration
makes use of BDDs, ZBDDs
Outperforms existing tools by orders of magnitude

Review: Primes vs. DHF-Primes
Classic (Quine-McCluskey):
Hazard-Free: implicants>
DHF-Prime Implicants = maximal implicants that do not intersect “privileged cubes” illegally
Primes
DHF-Primes

Topic 1: New Idea
Challenge: Two types of constraints
maximality constraints: “we want maximally large implicants”
avoidance constraints: “we must avoid illegal intersections”
DHF-Prime Generation
New Approach: Unify constraints by “lifting” the problem into a higher-dimensional space:
g(x1, …, xn, z1, …, zl) maximality
f(x1,…,xn), T maximality & avoidance constraints

Auxiliary Synchronous Function g
0 0
0 1
1 1
1 0 0 0
1 0
0 0
0 0
z=0
z=1
Add one new dimension per privileged cube
0-half-space: g is defined as f
1-half-space: g is defined as f
BUT priv-cube is
filled with 0’s
f
g

Prime Implicants of g
Expansion in z-dimension
guarantees avoidance
of priv-cube in original domain
f
g

Prime Implicants of g
Expansion in x-dimension
corresponds to enlarging cube
in original domain.
f
g

Summary: Auxiliary Synchronous Function g
The definition of auxiliary function g exactly ensures :
Expansion in a z-dimension corresponds to avoiding the privileged cube in the original domain.
Expansion in a x-dimension corresponds to enlarging the cube in the original domain.

New approach: DHF-Prime Generation
Goal: Efficient new method for DHF-Prime generation
Approach:
translate original function f into synchronous function g
generate Primes(g)
after filtering step, retrieve dhf-primes(f)

Prime Generation of g
f
g
Prime implicants of g

Filtering Primes of g
Lifting
Prime implicants of g
3 classes of primes of synchronous fct g:
1. do not intersect priv-cube (in original domain)
2. intersect legally
3. intersect illegally
Transforming Prime(g) into DHF-Prime(f,T):
f
g

Projection
Lifting
Prime implicants of g
f
g
DHF-Prime(f,T)

Formal Characterization of DHF-Prime(f,T)

IMPYMIN
CAD tool for Hazard-Free 2-Level Logic
Two main ideas:
Computes DHF-Primes in higher-dimension space
Implicit Method: makes use of BDDs, ZBDDs

What is a BDD ?
Compact representation for Boolean function
a
b
c
0
1
0
1

What is implicit logic minimization?
Classic Quine-McCluskey:
Scherzo [Coudert] (implicit logic minimization):
?

IMPYMIN Overview:
Implicit Hazard-free 2-Level Minimizer
f, T
Scherzo’s
Implicit
Solver
objects-to-be-covered
covering
objects

Impymin vs. HFMIN: Results
39
23
0
9
0
#z
added variables