A survey of Boolean matching techniques for library binding

ABSTRACT

When binding a logic network to a set of cells, a fundamental problem is recognizing whether a cell can implement a portion of the network. Boolean matching means solving this task using a formalism based on Boolean algebra. In its simplest form, Boolean matching can be posed as a tautology check. We review several approaches to Boolean matching as well as to its generalization to cases involving don't care conditions and its restriction to specific libraries such as those typical of anti-fuse based FPGAs. We then present a general formulation of Boolean matching supporting multiple-output logic cells.

REFERENCES

• 1: BENINI, L., FAVALLI, M., AND DE MICHELI, G. 1995. Generalized matching, a new approach to concurrent logic optimization and library binding. In Logic synthesis.
• 2: Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
• 3: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 4: BROWN, F. 1990. Boolean reasoning. Kluwer Academic Publishers, Hingham, MA.
• 5: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 6: Jerry R. Burch , David E. Long, Efficient Boolean function matching, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.408-411, November 1992, Santa Clara, California, United States
• 7: CHEN, K.-C. 1993. Boolean matching based on Boolean unification. In Computer-aided design, 346-351.
• 8: CHENG, D. I. AND MAREK-SADOWSKA, M. 1993. Verifying equivalence of functions with unknown input correspondence. In Design Automation, 81-85.
• 9: E. M. Clarke , K. L. McMillan , X Zhao , M. Fujita , J. Yang, Spectral transforms for large boolean functions with applications to technology mapping, Proceedings of the 30th international conference on Design automation, p.54-60, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164569]
• 10: Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
• 11: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 12: DARRINGER, J., JOYNER, W., BERMAN, L., AND TREVILLYAN, L. 1981. LSS: Logic synthesis through local transformations". IBM J. Res. Dev. 25, 4 (July), 272-280.
• 13: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 14: DETJENS, E. AND GANNOT, G., ET AL. 1987. Technology mapping in MIS. In Computer-Aided Design, 116-119.
• 15: EDWARDS, C. 1975. Applications of Rademacher-Walsh transform to Boolean function classification and threshold logic synthesis. IEEE Trans. Comput. (Jan.), 48-62.
• 16: Silvia Ercolani , Giovanni De Micheli, Technology mapping for electrically programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.234-239, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127671]
• 17: FORTAS, A., BOUZOUZOU, H., CRASTES, M., ROANE, R., AND SAUCIER, G. 1995. Mapping techniques for Quicklogic FPGA. In SASIMI.
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: GREEN, J., HAMDY, E., AND BEAL, S. 1993. Antifuse field programmable gate arrays. Proc. IEEE 81, 7 (July), 1041-1056.
• 20: David Gregory , Karen Bartlett , Aart de Geus , Gary Hachtel, SOCRATES: a system for automatically synthesizing and optimizing combinational logic, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.79-85, July 1986, Las Vegas, Nevada, United States
• 21: Stanley L. Hurst , Jon C. Muzio , D. Michael Miller, Spectral Techniques in Digital Logic, Academic Press, Inc., Orlando, FL, 1985
• 22: Kevin Karplus, Amap: A technology mapper for selector-based field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.244-247, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127673]
• 23: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 24: Janett Mohnke , Sharad Malik, Permutation and phase independent Boolean comparison, Integration, the VLSI Journal, v.16 n.2, p.109-129, Dec. 1993 [doi>10.1016/0167-9260(93)90041-A]
• 25: MORRISON, C. R., JACOBY, R. M., AND HACHTEL, G.D. 1989. Techmap: technology mapping with delay and area optimization. In Logic and Architecture Synthesis for Silicon Compilers. North-Holland Publishing Co., Amsterdam, The Netherlands, 53-64.
• 26: R. Murgai , R. K. Brayton , A. L. Sangiovanni-Vincentelli, An improved synthesis algorithm for multiplexor-based PGA's, Proceedings of the 29th ACM/IEEE conference on Design automation, p.380-386, June 08-12, 1992, Anaheim, California, United States
• 27: Hamid Savoj , Mário J. Silva , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Boolean matching in logic synthesis, Proceedings of the conference on European design automation, p.168-174, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 28: U. Schlichtmann , F. Brglez , M. Hermann, Characterization of Boolean functions for rapid matching in FPGA technology mapping, Proceedings of the 29th ACM/IEEE conference on Design automation, p.374-379, June 08-12, 1992, Anaheim, California, United States
• 29: SCHLICHTMANN, U., BRGLEZ, F., AND SCHNEIDER, P. 1993. Efficient Boolean matching based on unique variable ordering. In Logic Synthesis.
• 30: SOMENZI, F. AND BRAYTON, R.K. 1989. Minimization of Boolean relations. In Circuits and systems, 738-743.
• 31: TRIMBERGER, S. 1993. A reprogrammable gate array and application. Proc. IEEE 81, 7 (July), 1030-1041.
• 32: Chien-Chung Tsai , Malgorzata Marek-Sadowska, Boolean matching using generalized Reed-Muller forms, Proceedings of the 31st annual conference on Design automation, p.339-344, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196404]
• 33: Kuo-Hua Wang , Ting-Ting Hwang, Boolean matching for incompletely specified functions, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.48-53, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217505]
• 34: WANG, K. H., HWANG, T.-T., AND CHEN, C. 1996. Exploiting communication complexity in Boolean matching. IEEE Transactions on CAD/ICAS 15, 10 (Oct.), 1249-1256.
• 35: WATANABE, Y., GUERRA, L. M., AND BRAYTON, R.K. 1996. Permissible functions for multioutput components in combinational logic optimization. IEEE Transactions on CAD/ICAS 15, 7 (July), 734-744.
• 36: WONG, S., So, H., Ov, J., AND COSTELLO, J. 1989. A 5000-gate CMOS EPLD with multiple logic and interconnect array. In Custom Integrated Circuit, 581-584.
• 37: Jerry C Yang , Giovanni DeMicheli, Spectral Techniques for Technology Mapping, Stanford University, Stanford, CA, 1994
• 38: Cheng-Hsing Yang , Chia-Chun Tsai , Jan-Ming Ho , Sao-Jie Chen, Hmap: a fast mapper for EPGAs using extended GBDD hash tables, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.2, p.135-150, April 1997 [doi>10.1145/253052.253098]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

General Terms:
Design, Measurement, Performance