A method for finding good Ashenhurst decompositions and its application to FPGA synthesis

• Main Authors: Stanion, Ted, Sechen, Carl
• Format: Conference Proceeding
• Language: English
• Subjects: Binary decision diagrams; Boolean functions; Computing methodologies > Machine learning > Machine learning approaches > Markov decision processes; Data structures; Design automation; Distributed computing; Field programmable gate arrays; Hardware > Electronic design automation > High-level and register-transfer level synthesis; Hardware > Integrated circuits > Logic circuits; Logic functions; Mathematics of computing > Probability and statistics > Probabilistic representations > Decision diagrams; Permission; Size measurement; Table lookup; Theory of computation > Computational complexity and cryptography > Oracles and decision trees; Theory of computation > Theory and algorithms for application domains > Machine learning theory > Markov decision processes; Theory of computation > Theory and algorithms for application domains > Machine learning theory > Reinforcement learning > Sequential decision making
• ISSN: 0738-100X
• DOI: 10.1145/217474.217507

In this paper, we present an algorithm for finding a good Ashenhurst decomposition of a switching function. Most current methods for performing this type of decomposition are based on the Roth-Karp algorithm. The algorithm presented here is based on finding an optimal cut in a BDD. This algorithm differs from previous decomposition algorithms in that the cut determines the size and composition of the bound set and the free set. Other methods examine all possible bound sets of an arbitrary size. We have applied this method to decomposing functions into sets of k-variable functions. This is a required step when implementing a function using a lookup table (LUT) based FPGA. The results compare very favorably to existing implementations of Roth-Karp decomposition methods.