Transcript Document

Abstract
A classical problem in logic synthesis is to find a sum-of-product (SOP) Boolean expression with the
minimum number of product terms that implements a Boolean function. In this work, we focus on a related
yet different synthesis problem targeted toward probabilistic computation. In our scenario, we want to
synthesize a Boolean function that covers an exact number of minterms, say m minterms. This is the only
requirement; which m minterms are covered does not matter. The objective is to find a SOP Boolean
expression with the minimum number of product terms with this property. Solving this problem provides a
solution to the problem of generating arbitrary probability values from unbiased input probabilities values of
0.5 with combinational logic.
Two-Level Logic Synthesis for
Probabilistic Computation
We first show a method for constructing a set of product terms to cover exactly m minterms; this gives an
upper bound. Then, as our major contribution, we propose a method for deriving a lower bound. We show
that the problem of finding such a lower bound can be converted into an optimization problem which we call
the optimal subtraction problem. We solve it with dynamic programming. Experiments on benchmarks show
that for some numbers m, the lower bound meets the upper bound, indicating that the solution corresponding
to the upper bound is optimal. For some other numbers m, the gap between the lower bound and the upper
bound is small, indicating that the solution corresponding to the upper bound is nearly optimal.
Weikang Qian and Marc D. Riedel
ECE Department, University of Minnesota
Probabilistic Computation
What is it?
Why need it?
• Digital circuit operating on random bit streams
Other
Probabilities
Needed
Input
Probabilities
p1
0, 1, 1, 0, 1, 0
Probability
Generator
…
P(z = 1) = 0.2
z
0,0,0,1,0,0,1,0,0,0
Random
Sources
Deterministic
Hardware
p2
Digital
Circuit
p3
P(z = 1) = P(x = 1) P(y = 1)
Ultimate Question: Given number of inputs n and
integer m, find a SOP expression with the minimum
number of products to cover m minterms.
Optimization Flow
Focus of this
work
Exists λ cubes to
cover m interms?
q
Definitions and Preliminaries
?
Question 1: What could q be?
Answer: q = m/2n
• Each input combination has probability
• If the Boolean function has m minterms, then q = m/2n
• V( f ): number of minterms covered by f
• B(m): number of ones of binary number m
• B((1011)2) = 3
• Boolean product, also known as cube, denoted by c
• If cube c contains k literals, V(c) = 2n − k
•
• How to count number of minterms?
Upper Bound
Theorem 2: If there exists λ cubes to
cover m minterms, then we can find
a, b ≥ 0 such that: m = a − b;
B(a) ≤ 2λ − 1; B (b) ≤ 2λ − 1 − 1
Proof:
•
• Synthesize cubes so that cube ck has n − ik
literals and cubes ck and cl are disjoint, for any
0 ≤ k < l ≤ λ − 1.
Mutually
Disjoint
N
λ=λ+1
(a*, b* denotes optimal solution)
Case 1: 0 & carry 0
(… 000 mk …m0)2
+ (… ??? b*k…b*0)2
Case 2: 0 & carry 1
(… 000 mk …m0)2
+ (… ??? b*k…b*0)2
Carry 0
Then, ??? = 000
Carry 1
Then, ??? = 000 or 111
Case 3: 1 & carry 0
(… 111 mk …m0)2
+ (… ??? b*k…b*0)2
Case 4: 1 & carry 1
(… 111 mk …m0)2
+ (… ??? b*k…b*0)2
Carry 0
Then, ??? = 000 or 001
Carry 1
Then, ??? = 000
• Given m = (md…m0)2, 0 ≤ i ≤ d, l, ξ in {0, 1},
define problem Q(i, l, ξ) as:
Find a, b ≥ 0 to minimize B(a) such that
• B(b) ≤ l
• a = (md…mi)2 + b + ξ
• Optimal solution a*(i, l, ξ) and b*(i, l, ξ).
• Optimal cost: A(i, l, ξ) = B(a*(i, l, ξ))
Optimal Subtraction Problem: Q(0, t, 0)
Optimal Structure of Problem Q
Q(i, l, 0)
Q(j, l, 0)
Case (mj − 1…mi) = (1…1)
Q(i, l, 1)
Q(j, l, 0)
Q(i, l, 1)
Q(j, l, 1)
(A(i, l, 1) = min{A(j, l, 0) + 1,
A(j, l − j + i, 1)})
• Treat m as alternating zeros and ones: Exist 0 = i0 < i1 < ••• < i2q = d + 1
• m[i2r + 1 − 1, i2r] = (1…1), m[i2r + 2 − 1, i2r + 1] = (0…0)
Case: m[i2r + 2 − 1, i2r + 1] = (0…0)
m[i2r + 1 − 1, i2r] = (1…1)
Q(j, l − 1, 1)
(A(i, l, 0) = min{A(j, l, 0) + j − i,
A(j, l − 1, 1)})
Case: m[i2r + 1 − 1, i2r] = (1…1)
m[i2r − 1, i2r − 1] = (0…0)
Q(i2r − 1, l, 1)
Q(i2r, l, 0)
Q(i2r + 1, l, 0)
Q(i2r + 1, l − 1, 1)
Q(i2r + 1, l − i2r + i2r − 1, 1)
A(i2r, l, 0) = min{A(i2r + 1, l − 1, 1),
A(i2r + 2, l, 0) + i2r + 1 − i2r}
Q(0, t, 0)
Q(i0, t, 0)
Q(i2r, l − i2r + i2r − 1, 1)
Q(i2r, l, 0)
Q(i2r + 2, l, 0)
A(i2r − 1, l, 1) = min{A(i2r, l, 0) + 1,
A(i2r + 1, l − i2r + i2r − 1, 1)}
1
1
1
11
1
1
1
1
1
10
10
Optimal Subtraction Problem
a − b = (101101)2
Given m, t ≥ 0, find a, b ≥ 0 to
minimize B(a) such that
• B(b) ≤ t
•m =a − b
X
Find lower bound by solving
optimal subtraction problem:
• Set t = 2λ − 1 − 1
• If min B(a) > 2λ − 1, then lower
bound > λ
λ=3
• B(a) ≤ 2λ − 1 = 4
• B(b) ≤ 2λ − 1 − 1 = 3
• a = (110001)2, b = (100)2
Lower bound: λ = 3
Q(i2, t2, 0)
Q(i1, t1, 1)
•••
Q(i2q − 4, t2q − 4, 0)
Q(i3, t3, 1) ••• Q(i2q − 3, t2q − 3, 1)
Optimal Cost Table T
• T(2r, l) = A(i2r, l, 0)
• T(2r − 1, l) = A(i2r − 1, l, 1)
2q − 1
2q − 2
2q − 3
2q − 4
⁞
0
0
1
y
*
*
⁞
*
1
1
1
*
*
⁞
*
2
1
1
*
*
⁞
*
…
…
…
…
…
⁞
…
t
1
1
*
*
⁞
*
• Base Case:
• T(2q − 1, *) and T(2q − 2, *)
• General Cases:
Recursive Relation
Q(j, l, 0)
Q(i, l, 0)
Q(j, l − j + i, 1)
11
01
Solving Optimal Subtraction Problem by Dynamic Programming
Optimization Problem Q
Case (mj − 1…mi) = (0…0)
1
• B(a) ≤ 2λ − 1 = 2
• B(b) ≤ 2λ − 1 − 1 = 1
• No solution!
Lower bound is the minimum λ
satisfying the above property
Observation of Optimal
Solution of OSP
1
Example: m = (101101)2
λ=2
Proof:
• In equation of Inclusion-Exclusion
Principle, put “plus” terms together
to get a; put “minus” terms together
to get b
• We can show B(a) ≤ 2λ − 1,
B (b) ≤ 2λ − 1 − 1
•m =a − b
Example: m = (1011)2, n = 4
Generalization of Optimal Subtraction Problem
01
Lower Bound and Optimal Subtraction Problem (OSP)
Theorem 1: If B(m) = λ, then an upper bound is λ
end
x0x1
x2x3 00 01 11 10
00 1 1
x0x1
x2x3 00 01 11 10
00 1 1
0.5
?
Inclusion-Exclusion Principle
Y
Combinational
Logic
Question 2: How to implement q = m/2n?
Answer: choose m minterms, BUT …
A Hard Question: Which m minterms to choose?
Example: q = 7/16
1/2n
Probability 4/6
Two-Level Logic Synthesis
0.5
q1
q2
q3
q4
1, 1, 0, 1, 0, 1
λ = Lower bound on
the number of cubes
to cover m minterms
0.5
0.5
• In test: Weighted random pattern generation
Stochastic Bit Streams: Probability 3/6
AND
Independent
How to design it?
• Hardware implementation of probabilistic algorithm
• Transform probabilities into probabilities
P(x = 1) = 0.4
0,1,0,1,0,0,1,1,0,0
x
y
1,0,1,1,0,0,1,0,0,1
P(y = 1) = 0.5
Problem: A Special One
Q(i2q − 2, t2q − 2, 0)
Q(i2q − 1, t2q − 1, 1)
• T(2r, l) = min{T(2r + 1, l − 1),
T(2r + 2, l) + i2r + 1 − i2r}
• T(2r − 1, l) = min{T(2r, l) + 1,
T(2r + 1, l − i2r + i2r − 1)}
Example: m = (01100101111)2, t = 3
0
1
2
3
3
4
7
5
4
3
2
1
0
1
1
1
2
2
3
4
2
1
1
1
2
2
3
3
1
1
1
1
1
2
• 2q = 6
• i0 = 0, i1 = 4, i2 = 5,
i3 = 6, i4 = 8, i5 = 10
Optimal Cost: 2
Optimal Solution:
• b* = (100010001)2
• a* = (10001000000)2
Experimental Results
Results on modified Espresso benchmarks:
circuit
newapla1
exp
shift
newcond
in2
in1
bca
x1dn
ts10
#cubes #inputs
6
14
21
28
30
55
72
80
128
12
8
19
11
19
16
26
27
22
#minterms
(hex)
109
59
7FF01
288
66950
6900
94000
49E0D80
7FFF8
lower
bound
3
3
2
3
4
3
3
3
2
upper
bound
3
4
12
3
8
4
3
10
16
Upper
Bound
Optimal!