Bi-Decomposition of Large Boolean Functions Using Blocking Edge Graphs
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
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
