Bi-Decomposition of Large Boolean Functions Using Blocking Edge Graphs
Mihir Choudhury, Kartik Mohanram
(ICCAD’10 best paper nominee)
Presentor: ABert Liu
Introduction
Terminology
Algorithm
Illustration
Experimental Result
Conclusion
Outline
Introduction
Bi-decomposition is a special kind of functional
decomposition
Functional decomposition
Break a large function into a network of
smaller functions
Reduce circuit and communication complexity
and thus simplify physical design
Bi-decomposition plays an important role in logic
synthesis for restructuring Boolean networks
Introduction
Problem
f
f
A
f
B
h
X
A
X
B
X
C
X
B
X
C
Bi-decompose
X
A
Terminology
Blocking Edge Graph (BEG):
It’s an undirected graph.
Every vertex represent a variable.
One graph represents only one non-decomposability
of
and, or,
or
xor
.
The edges connected variable pair {i , j} means novariable partition can decompose this variable pair.
BEG can extract variable partition.
Terminology
( a, b) and ( b, d) are not blocked in the
and
BEG.
( c, d) and ( c, b) are not blocked in the
or
BEG.
The
xor
BEG is complete graph.
BEG Example
OR
AND
a
b
d
c
a
b
d
c
XOR
a
b
d
c
Algorithm
1.Construct BEG
2.Do variable partition on the BEG.
3.Compute the decomposed functions.
4.Recursively bi-decompose the decomposed
functions from 3.
In 4. if the function is not decomposable it will do
some relaxation to make further decompose. (It’s not
bi-decomposition)
Algorithm
Illustration
Construct BEG
Blocking condition:
One square blocks the others.
Construct BEG
K-map
ij\k 0 1
00 1 1
01 1 0
11 0 1
10 1 0
Example
AND
i
k
j
OR
i
k
j
XOR
i
k
j
For { i, j } pair :assign k=0 assign k=1
i\j 0 1 i\j 0 1
0 1 1 or 0 1 0 xor
1 1 0 square 1 0 1 square
Blocking all { i, j} in all BEGs.Other pair do the same thing to finish
constructing the BEGs.
K-map
ij\k 0 1
00 1 0
01 1 0
11 0 0
10 0 0
Example
AND
i
k
j
OR
i
k
j
XOR
i
k
j
For { i, j } pair :assign k=0 assign k=1
i\j 0 1 i\j 0 1
0 1 1 Literal 0 0 0 Zero
1 0 0 square 1 0 0 square
We can compute whether the edge ( i, j) should be
added or not in
and
and
or
BEGs by compute x. If x
is not constant 0 the edge will be added.
Construct BEG
i
j
k
On-Set
Off-set
The same for
or
and
and
:
Construct BEG
i
j
k
On-Set
Off-set
Whether the function is bi-decomposable or not?
Guarantee the existence of variable partition.
Variable Partition
Who can be common variable?
Vertex cut is necessary but not sufficient condition.
Variable Partition
Vertex Cut: A set of vertices whose removal renders
a connected graph disconnected.
Examples:
Variable Partition
a
b
d
c
Legal cut
Not a vertex cut
a
b
d
c
e
Legal cut
Another legal cut
Decomposed function for
or
and
and
:
For an
or
bi-decomposition.
Decomposed Function
Off-set
On-set
An and bi-decomposition can be obtained in a similar
manner by interchanging the off-set and the on-set of
f
.
It’s subset of off-set of f.
It’s obtained from expanding on-set
of f and does not overlap with off-set
of decomposed function.
For
xor
:
Decomposed Function
Example
Experimental Result
Experimental Result
Experimental Result
Conclusion
The experimental result looks good.
This work implemented in ABC using CUDD
package, it might have memory problem when
function is large.
Solving problem with new graph structure might be
a good idea.
The BEG has global view of the decomposability of
every variable pairs to choose the best partition.
Maybe we can improve our bi-decomposition work.
Conclusion
Thanks for Attention
Bi-decomposition is a vital technique in logic synthesis for restructuring Boolean networks. This paper discusses the methodology of breaking down large Boolean functions using Blocking Edge Graphs (BEG) to simplify physical design and reduce complexity. The process involves constructing BEG, performing variable partition, computing decomposed functions, and recursively bi-decomposing. Key components include terminology, algorithms, illustrations, and experimental results highlighting the significance of bi-decomposition in functional decomposition.
Uploaded on Sep 07, 2024 | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Bi-decomposition of large Boolean functions using blocking edge graphs Mihir Choudhury, Kartik Mohanram (ICCAD 10 best paper nominee) Presentor: ABert Liu
Outline Introduction Terminology Algorithm Illustration Experimental Result Conclusion m
Introduction Bi-decomposition is a special kind of functional decomposition Functional decomposition Break a large function into a network of smaller functions Reduce circuit and communication complexity and thus simplify physical design Bi-decomposition plays an important role in logic synthesis for restructuring Boolean networks m
Problem h f Bi-decompose fA fB XAXBXC XA XC XB m
Terminology Blocking Edge Graph (BEG): It s an undirected graph. Every vertex represent a variable. One graph represents only one non-decomposability of and, or, or xor. The edges connected variable pair {i , j} means no variable partition can decompose this variable pair. BEG can extract variable partition. m
BEG Example b a b a a b c d c d c d OR XOR AND ( a, b) and ( b, d) are not blocked in the and BEG. ( c, d) and ( c, b) are not blocked in the or BEG. The xor BEG is complete graph. m
Algorithm 1.Construct BEG 2.Do variable partition on the BEG. 3.Compute the decomposed functions. 4.Recursively bi-decompose the decomposed functions from 3. In 4. if the function is not decomposable it will do some relaxation to make further decompose. (It s not bi-decomposition) m
Construct BEG Giving a function f with variable set V. To construct BEG for f: 1.Choose a variable pair { i, j }. 2.Give an assignment c to V/{ i, j}. (Restricting the K-map of function to 2x2 squares.) (There are 2? 22x2 K-maps for each pair { i, j}) 3.Test the blocking condition to add edges ( i, j) to BEGs. 4. Go back to 1. until all the pairs have been tested. m
Construct BEG Blocking condition: One square blocks the others. m
Example i i i K-map ij\k 0 1 00 1 1 01 1 0 11 0 1 10 1 0 j k j k j k AND OR XOR For { i, j } pair : assign k=0 assign k=1 i\j 0 1 i\j 0 1 0 1 1 or 0 1 0 xor 1 1 0 square 1 0 1 square Blocking all { i, j} in all BEGs. Other pair do the same thing to finish constructing the BEGs. m
Example i i i K-map ij\k 0 1 00 1 0 01 1 0 11 0 0 10 0 0 j k j k j k AND OR XOR For { i, j } pair : assign k=0 assign k=1 i\j 0 1 i\j 0 1 0 1 1 Literal 0 0 0 Zero 1 0 0 square 1 0 0 square m
Construct BEG We can compute whether the edge ( i, j) should be added or not in and and or BEGs by compute x. If x is not constant 0 the edge will be added. On-Set Off-set i k j m
Construct BEG The same for or and and: On-Set Off-set i k j m
Variable Partition Whether the function is bi-decomposable or not? Guarantee the existence of variable partition. m
Variable Partition Who can be common variable? Vertex cut is necessary but not sufficient condition. m
Variable Partition Vertex Cut: A set of vertices whose removal renders a connected graph disconnected. Examples: Another legal cut b a b a d c d c Legal cut e Not a vertex cut Legal cut m
Decomposed Function Decomposed function for or and and: For an or bi-decomposition. Off-set It s subset of off-set of f. It s obtained from expanding on-set of f and does not overlap with off-set of decomposed function. On-set An and bi-decomposition can be obtained in a similar manner by interchanging the off-set and the on-set of f. m
Decomposed Function For xor : m
Example m
Conclusion The experimental result looks good. This work implemented in ABC using CUDD package, it might have memory problem when function is large. Solving problem with new graph structure might be a good idea. The BEG has global view of the decomposability of every variable pairs to choose the best partition. Maybe we can improve our bi-decomposition work. m
