Luca Benini
Skip Abstract Section
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.
- BENINI, L., FAVALLI, M., AND DE MICHELI, G. 1995. Generalized matching, a new approach to concurrent logic optimization and library binding. In Logic synthesis.Google Scholar
- BRACE, K. S., RUDELL, R. L., AND BRYANT, R.E. 1990. Efficient implementation of a BDD package. In 27th ACM/IEEE design automation conference (Orlando, FL, June 24-28, 1990). ACM Press, New York, NY, 40-45. Google Scholar
- BRAYTON, R., HACHTEL, G., MCMULLEN, C., AND SANGIOVANNI-VINCENTELLI, A. 1984. Logic minimization algorithms for VLSI synthesis. Kluwer Academic Publishers, Hingham, MA. Google Scholar
- BROWN, F. 1990. Boolean reasoning. Kluwer Academic Publishers, Hingham, MA.Google Scholar
- BRYANT, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35, 8 (Aug.), 677-691. Google Scholar
- BURCH, J. R. AND LONG, D.E. 1992. Efficient Boolean function matching. In Computeraided design (Santa Clara, CA, Nov. 8-12, 1992). IEEE Computer Society Press, Los Alamitos, CA, 408-411. Google Scholar
- CHEN, K.-C. 1993. Boolean matching based on Boolean unification. In Computer-aided design, 346-351.Google Scholar
- CHENG, D. I. AND MAREK-SADOWSKA, M. 1993. Verifying equivalence of functions with unknown input correspondence. In Design Automation, 81-85.Google Scholar
- CLARKE, E. M., MCMILLAN, K. L., ZHAO, X, FUJITA, M., AND YANG, J. 1993. Spectral transforms for large boolean functions with applications to technology mapping. In Design automation conference (Dallas, TX, June 14-18, 1993). ACM Press, New York, NY, 54-60. Google Scholar
- CONG, J. AND DING, Y. 1992. An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. In Computer Aided Design, 48-53. Google Scholar
- CONG, J. AND DING, Y. 1996. Combinational logic synthesis for LUT based field programmable gate arrays. ACM Trans. Des. Autom. Electron. Syst. 1, 2 (Apr.), 145-204. Google Scholar
- 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.Google Scholar
- DE MICHELI, a. 1994. Synthesis and optimization of digital circuits. McGraw-Hill, Inc., New York, NY. Google Scholar
- DETJENS, E. AND GANNOT, G., ET AL. 1987. Technology mapping in MIS. In Computer-Aided Design, 116-119.Google Scholar
- EDWARDS, C. 1975. Applications of Rademacher-Walsh transform to Boolean function classification and threshold logic synthesis. IEEE Trans. Comput. (Jan.), 48-62.Google Scholar
- ERCOLANI, S. AND DE MICHELI, G. 1991. Technology mapping for electrically programmable gate arrays. In ACM/IEEE design automation conference (San Francisco, CA, June 17-21, 1991). ACM Press, New York, NY, 234-239. Google Scholar
- FORTAS, A., BOUZOUZOU, H., CRASTES, M., ROANE, R., AND SAUCIER, G. 1995. Mapping techniques for Quicklogic FPGA. In SASIMI.Google Scholar
- GAREY, M. AND JOHNSON, D. 1979. Computers and intractability. W. H. Freeman & Co., New York, NY. Google Scholar
- GREEN, J., HAMDY, E., AND BEAL, S. 1993. Antifuse field programmable gate arrays. Proc. IEEE 81, 7 (July), 1041-1056.Google Scholar
- GREGORY, D., BARTLETT, K., DE GEUS, A., AND HACHTEL, G. 1986. Socrates: A System for Automatically synthesizing and optimizing combinational logic. In Design automation, 79-85. Google Scholar
- HURST, S., MILLER, D., AND MUZIO, J. 1985. Spectral techniques in digital logic. Academic Press Ltd., London, UK. Google Scholar
- KARPLUS, K. 1991. Amap: a technology mapper for selector-based field-programmable gate arrays. In Design Automation, 244-247. Google Scholar
- KEUTZER, K. 1987. DAGON: technology binding and local optimization by DAG matching. In Design automation conference (Miami Beach, FL, June 28-July 1, 1987) A. O'Neill and D. Thomas, Eds. ACM Press, New York, NY, 341-347. Google Scholar
- MOHNKE, J. AND MALIK, S. 1993. Permutation and phase independent Boolean comparison. Integr. VLSI J. 16, 2 (Dec.), 109-129. Google Scholar
- 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.Google Scholar
- MURGAI, R., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. L. 1992. An improved synthesis algorithm for multiplexor-based PGA's. In Design automation conference (Anaheim, CA, June 8-12, 1992). IEEE Computer Society Press, Los Alamitos, CA, 380-386. Google Scholar
- SAVOJ, g., SILVA, M. J., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1992. Boolean matching in logic synthesis. In European Design Automation (Congress Centrum Hamburg, Hamburg, Germany, Sept. 7-10, 1992). IEEE Computer Society Press, Los Alamitos, CA, 168-174. Google Scholar
- SCHLICHTMANN, U., BRGLEZ, F., AND HERMANN, M. 1992. Characterization of Boolean functions for rapid matching in FPGA technology mapping. In Design automation conference (Anaheim, CA, June 8-12, 1992). IEEE Computer Society Press, Los Alamitos, CA, 374- 379. Google Scholar
- SCHLICHTMANN, U., BRGLEZ, F., AND SCHNEIDER, P. 1993. Efficient Boolean matching based on unique variable ordering. In Logic Synthesis.Google Scholar
- SOMENZI, F. AND BRAYTON, R.K. 1989. Minimization of Boolean relations. In Circuits and systems, 738-743.Google Scholar
- TRIMBERGER, S. 1993. A reprogrammable gate array and application. Proc. IEEE 81, 7 (July), 1030-1041.Google Scholar
- TSAI, C.-C. AND MAREK-SADOWSKA, M. 1994. Boolean matching using generalized Reed- Muller forms. In Design automation (San Diego, CA, June 6-10, 1994). ACM Press, New York, NY, 339-344. Google Scholar
- WANG, K.-H. AND HWANG, T.-T. 1995. Boolean matching for incompletely specified functions. In Design automation conference (San Francisco, CA, June 12-16, 1995). ACM Press, New York, NY, 48-53. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- YANG, J. AND DE MICHELI, G. 1991. Spectral techniques for technology mapping: A CSL report. Google Scholar
- YANG, C.-H., CHEN, S.-J., HO, J.-M., AND TSAI, C.-C. 1997. Hmap: a fast mapper for EPGAs using extended GBDD hash tables. ACM Trans. Des. Autom. Electron. Syst. 2, 2 (Apr.). Google Scholar
Index Terms
- A survey of Boolean matching techniques for library binding
Recommendations
Simulation and SAT-based Boolean matching for large Boolean networks
DAC '09: Proceedings of the 46th Annual Design Automation ConferenceBoolean matching is to check the equivalence of two target functions under input permutation and input/output phase assignment. This paper addresses the permutation independent (P-equivalent) Boolean matching problem. We will propose a matching ...
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiabilityWe present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSATCNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Comments