Boolean factoring and decomposition of logic networks

ABSTRACT

This paper presents new methods for restructuring logic networks based on fast Boolean techniques. The basis for these are 1) a cut-based view of a logic network, 2) exploiting the uniqueness and speed of disjoint-support decompositions, 3) a new heuristic for speeding these up, 4) extending these to general decompositions, and 5) limiting local transformations to functions with 16 or less inputs so that fast truth table manipulations can be used in all operations. Boolean methods lessen the structural bias of algebraic methods, while still allowing for high speed and multiple iterations. Experimental results on K-LUT networks show an average additional reduction of 5.4% in LUT count, while preserving delay, compared to heavily optimized versions of the same networks.

REFERENCES

• 1: Afshin Abdollahi , Massoud Pedram, A new canonical form for fast boolean matching in logic synthesis and verification, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065681]
• 2: Actel Corp., "ProASIC3 flash family FPGAs datasheet," http://www.actel.com/documents/PA3_DS.pdf
• 3: Altera Corp., "Stratix II device family data sheet", 2005, http://www.altera.com/literature/hb/stx/stratix_section_1_vol_1.pdf
• 4: R. L. Ashenhurst, "The decomposition of switching functions", Proc. Intl Symposium on the Theory of Switching, Part I (Annals of the Computation Laboratory of Harvard University, Vol. XXIX), Harvard University Press, Cambridge, 1959, pp. 75--116.
• 5: Berkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification, Release 70911. http://www.eecs.berkeley.edu/~alanmi/abc/
• 6: Valeria Bertacco , Maurizio Damiani, The disjunctive decomposition of logic functions, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.78-82, November 09-13, 1997, San Jose, California, United States
• 7: R. Brayton and C. McMullen, "The decomposition and factorization of Boolean expressions," Proc. ISCAS '82, pp. 29--54.
• 8: Donald Chai , Andreas Kuehlmann, Building a better Boolean matcher and symmetry detector, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 9: Satrajit Chatterjee , Alan Mishchenko , Robert Brayton, Factor cuts, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233531]
• 10: S. Chatterjee , A. Mishchenko , R. Brayton , X. Wang , T. Kam, Reducing structural bias in technology mapping, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.519-526, November 06-10, 2005, San Jose, CA
• 11: D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382677]
• 12: Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296425]
• 13: A. Curtis. New approach to the design of switching circuits. Van Nostrand, Princeton, NJ, 1962.
• 14: Debatosh Debnath , Tsutomu Sasao, Efficient computation of canonical form for Boolean matching in large libraries, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 15: A. Farrahi and M. Sarrafzadeh, "Complexity of lookup-table minimization problem for FPGA technology mapping," IEEE TCAD, Vol. 13(11), Nov. 1994, pp. 1319--1332.
• 16: C. Files and M. Perkowski, "New multi-valued functional decomposition algorithms based on MDDs". IEEE TCAD, Vol. 19(9), Sept. 2000, pp. 1081--1086.
• 17: Yu Hu , Victor Shih , Rupak Majumdar , Lei He, Exploiting symmetry in SAT-based Boolean matching for heterogeneous FPGA technology mapping, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 18: Victor Nikolayevich Kravets , Karem A. Sakallah, Constructive multi-level synthesis by way of functional properties, 2001
• 19: Victor N. Kravets , Karem A. Sakallah, Constructive library-aware synthesis using symmetries, Proceedings of the conference on Design, automation and test in Europe, p.208-215, March 27-30, 2000, Paris, France [doi>10.1145/343647.343734]
• 20: E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping," IEEE TCAD, Vol. 16(8), 1997, pp. 813--833.
• 21: Andrew Ling , Deshanand P. Singh , Stephen D. Brown, FPGA technology mapping: a study of optimality, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065693]
• 22: V. Manohara-rajah, S. D. Brown, and Z. G. Vranesic, "Heuristics for area minimization in LUT-based FPGA technology mapping," Proc. IWLS '04, pp. 14--21.
• 23: Y. Matsunaga. "An exact and efficient algorithm for disjunctive decomposition". Proc. SASIMI '98, pp. 44--50.
• 24: Jason Cong , Kirill Minkovich, Improved SAT-based Boolean matching using implicants for LUT-based FPGAs, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA [doi>10.1145/1216919.1216944]
• 25: A. Mishchenko and T. Sasao, "Encoding of Boolean functions and its application to LUT cascade synthesis", Proc. IWLS '02, pp. 115--120. http://www.eecs.berkeley.edu/~alanmi/publications/2002/iwls02_enc.pdf
• 26: Alan Mishchenko , Xinning Wang , Timothy Kam, A new enhanced constructive decomposition and mapping algorithm, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775871]
• 27: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, DAG-aware AIG rewriting a fresh look at combinational logic synthesis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147048]
• 28: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton , Niklas Een, Improvements to combinational equivalence checking, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233679]
• 29: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, Improvements to technology mapping for LUT-based FPGAs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117208]
• 30: Alan Mishchenko , Robert Brayton , Jie-Hong Roland Jiang , Stephen Jang, Scalable don't-care-based logic optimization and resynthesis, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA [doi>10.1145/1508128.1508152]
• 31: Alan Mishchenko , Sungmin Cho , Satrajit Chatterjee , Robert Brayton, Combinational and sequential mapping with priority cuts, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 32: A. Mishchenko, S. Chatterjee, and R. Brayton, "Fast Boolean matching for LUT structures". ERL Technical Report, EECS Dept., UC Berkeley. http://www.eecs.berkeley.edu/~alanmi/publications/2007/tech07_lpk.pdf
• 33: Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275118]
• 34: M. Perkowski , M. Marek-Sadowska , L. Jozwiak , T. Luba , S. Grygiel , M. Nowicka , R. Malvi , Z. Wang , J. S. Zhang, Decomposition of multiple-valued relations, Proceedings of the 27th International Symposium on Multiple-Valued Logic, p.13, May 28-30, 1997
• 35: S. Plaza and V. Bertacco, "Boolean operations on decomposed functions", Proc. IWLS' 05, pp. 310--317.
• 36: J. P. Roth and R. Karp, "Minimization over Boolean graphs", IBM J. Res. and Develop., 6(2), pp. 227--238, April 1962.
• 37: Sean Safarpour , Andreas Veneris , Gregg Baeckler , Richard Yuan, Efficient SAT-based Boolean matching for FPGA technology mapping, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147034]
• 38: Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
• 39: T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for functional decomposition," Proc. IWLS'98, pp. 471--477.
• 40: Navin Vemuri , Priyank Kalla , Russell Tessier, BDD-based logic synthesis for LUT-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.501-525, October 2002 [doi>10.1145/605440.605442]
• 41: Bernd Wurth , Ulf Schlichtmann , Klaus Eckl , Kurt J. Antreich, Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.313-350, July 1999 [doi>10.1145/315773.315783]