Combinational logic synthesis for LUT based field programmable gate arrays

ABSTRACT

The increasing popularity of the field programmable gate-array (FPGA) technology has generated a great deal of interest in the algorithmic study and tool development for FPGA-specific design automation problems. The most widely used FPGAs are LUT based FPGAs, in which the basic logic element is a K-input one-output lookup-table (LUT) that can implement any Boolean function of up to K variables. This unique feature of the LUT has brought new challenges to logic synthesis and optimization, resulting in many new techniques reported in recent years. This article summarizes the research results on combinational logic synthesis for LUT based FPGAs under a coherent framework. These results were dispersed in various conference proceedings and journals and under various formulations and terminologies. We first present general problem formulations, various optimization objectives and measurements, then focus on a set of commonly used basic concepts and techniques, and finally summarize existing synthesis algorithms and systems. We classify and summarize the basic techniques into two categories, namely, logic optimization and technology mapping, and describe the existing algorithms and systems in terms of how they use the classified basic techniques. A comprehensive list of references is compiled in the attached bibliography.

REFERENCES

• 1: AT&T MICROELECTRONICS 1995. AT&T Field-Programmable Gate Arrays Data Book. AT&T Corp., Berkeley Heights, NJ.
• 2: AKERS, S.B. 1978. Binary decision diagrams, IEEE Trans. Comput. 27, 6, 509-516.
• 3: Dave Allen, Automatic One-Hot Re-Encoding for FPLs, Selected papers from the Second International Workshop on Field-Programmable Logic and Applications, Field-Programmable Gate Arrays: Architectures and Tools for Rapid Prototyping, p.71-77, August 31-September 02, 1992
• 4: ALTERA 1994. Programmable Logic Devices Data Book, Altera Corp., San Jose, CA.
• 5: ASHENHURST, R.L. 1957. The decomposition of switching functions. In Proceedings of International Symposium on Theory of Switching. (Harvard University, MA, Apr.), 74-116.
• 6: B. Becker , R. Drechsler, How many decomposition types do we need? [decision diagrams], Proceedings of the 1995 European conference on Design and Test, p.438, March 06-09, 1995
• 7: BESSON, T., BOUZOUZOU, H., LE, V.V., TIXIER, S., AND SAUCIER, G. 1994. Use of binary decision diagram for FPGA mapping. Proceedings of ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.).
• 8: BHAT, N. 1993. Library-based mapping for LUT FPGAs revisited. In Proceedings of the International Workshop on Logic Synthesis (Tahoe City, CA, May), P9b.1-6.
• 9: Narasimha B. Bhat , Dwight D. Hill, Routable Technologie Mapping for LUT FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.95-98, October 11-14, 1992
• 10: 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]
• 11: 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
• 12: BRAYTON, R.K., HACHTEL, G., AND SANGIOVANNI-VINCENTELLI, A.L. 1990. Multilevel logic synthesis. Proc. IEEE 78, 2, 264-300.
• 13: BRAYTON, R. K., RUDELL, R., SANGIOVANNI-VINCENTELLI, A. L., AND WANG, A.R. 1987. MIS: A multiple-level logic optimization system. IEEE Trans. Comput. Aided Des. 6, 6, 1062-1081.
• 14: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 15: Randal E. Bryant, Binary decision diagrams and beyond: enabling technologies for formal verification, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.236-243, November 05-09, 1995, San Jose, California, United States
• 16: Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
• 17: 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]
• 18: Kenneth M. Butler , Don E. Ross , Rohit Kapur , M. Ray Mercer, Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams, Proceedings of the 28th conference on ACM/IEEE design automation, p.417-420, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127705]
• 19: Pak K. Chan , Samiha Mourad, Digital system design using field programmable gate arrays, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 20: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, On routability prediction for field-programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.326-330, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164915]
• 21: Shih-Chieh Chang , Malgorzata Marek-Sadowska, Technology Mapping via Transformations of Function Graphs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.159-162, October 11-14, 1992
• 22: Shih-Chieh Chang , Kwang-Ting Cheng , Nam-Sung Woo , Malgorzata Marek-Sadowska, Layout driven logic synthesis for FPGAs, Proceedings of the 31st annual conference on Design automation, p.308-313, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196388]
• 23: Chau-Shen Chen , Yu-Wen Tsay , TingTing Hwang , Allen C. H. Wu , Youn-Long Lin, Combining technology mapping and placement for delay-optimization in FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.123-127, November 07-11, 1993, Santa Clara, California, United States
• 24: CHEN, K.-C. 1992. Logic minimization of lookup-table based FPGAs. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.) 71-76.
• 25: Kuang-Chien Chen , Jason Cong, Maximal reduction of lookup-table based FPGAs, Proceedings of the conference on European design automation, p.224-229, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 26: Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
• 27: Kuang-Chien Chen , Yusuke Matsunaga , Saburo Muroga , Masahiro Fujita, A resynthesis approach for network optimization, Proceedings of the 28th conference on ACM/IEEE design automation, p.458-463, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127712]
• 28: Amit Chowdhary , John P. Hayes, Technology mapping for field-programmable gate arrays using integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.346-352, November 05-09, 1995, San Jose, California, United States
• 29: K. Chung , J. Rose, TEMPT: technology mapping for the exploration of FPGA architectures with hard-wired connections, Proceedings of the 29th ACM/IEEE conference on Design automation, p.361-367, June 08-12, 1992, Anaheim, California, United States
• 30: CHUNG, K., SINGH, S., ROSE, J., AND CHOW, P. 1991. Using hierarchical logic blocks to improve the speed of FPGAs. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Oxford, England, Sept.) 103-113.
• 31: Jason Cong , Yuzheng Ding, On nominal delay minimization in LUT-based FPGA technology mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.82-88, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201324]
• 32: Jason Cong , Yuzheng Ding, On nominal delay minimization in LUT-based FPGA technology mapping, Integration, the VLSI Journal, v.18 n.1, p.73-94, Dec. 1994 [doi>10.1016/0167-9260(94)90012-4]
• 33: CONG, J. AND DING, Y. 1994b. On area/depth trade-off in LUT-based FPGA technology mapping. IEEE Trans. VLSI Syst. 2, 2, 137-148.
• 34: CONG, g. AND DING, Y. 1994c. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Comput. Aided Des. 13, 1, 1-12.
• 35: Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164675]
• 36: Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
• 37: 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
• 38: CONG, J., DING, Y., GAO, T., AND CHEN, K.-C. 1994. LUT-based FPGA technology mapping under arbitrary net-delay models. Comput. Graph. 18, 4, 137-148.
• 39: CONG, J., DING, Y., GAO, T., AND CHEN, K.-C. 1993. An optimal performance-driven technology mapping algorithm for LUT based FPGAs under arbitrary net-delay models. In Proceedings of the International Conference on CAD and Computer Graphics (Beijing, China, Aug.), 599-603.
• 40: Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar , Kuang-Chien Chen, An Improved Graph-Based FPGA Techology Mapping Algorithm For Delay Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.154-158, October 11-14, 1992
• 41: Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA design, Proceedings of the 33rd annual conference on Design automation, p.726-729, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240656]
• 42: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 43: CONG, g. AND HWANG, Y.-Y. 1995b. A theory on partially dependent functional decomposition with application in LUT-based FPGA. UCLA Computer Science Department Tech. Rep. CSD-950050, Dec.
• 44: CONG, J., KAHNG, A. B., TRAJMAR, P., AND CHEN, K.-C. 1992b. Graph based FPGA technology mapping for delay optimization. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.) 77-82.
• 45: Jason Cong , John Peck , Yuzheng Ding, RASP: a general logic synthesis system for SRAM-based FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.137-143, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228390]
• 46: H. Allen Curtis, Generalized Tree Circuit—The Basic Building Block of an Extended Decomposition Theory, Journal of the ACM (JACM), v.10 n.4, p.562-581, Oct. 1963 [doi>10.1145/321186.321202]
• 47: H. Allen Curtis, A Generalized Tree Circuit, Journal of the ACM (JACM), v.8 n.4, p.484-496, Oct. 1961 [doi>10.1145/321088.321091]
• 48: DETJENS, E., GANNOT, G., RUDELL, R., SANGIOVANNI-VINCENTELLI, A., AND WANG, A.R. 1987. Technology mapping in MIS. In Proceedings of the IEEE International Conference on Computer-Aided Design (Nov.), 116-119.
• 49: Srinivas Devadas , Abhijit Ghosh , Kurt Keutzer, Logic synthesis, McGraw-Hill, Inc., New York, NY, 1994
• 50: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 51: DRESIG, F., RETTIG, O., AND BAITINGER, U.G. 1991. Logic synthesis for universal logic cells. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Oxford, England, Sept.), 181-190.
• 52: Amir H. Farrahi , Majid Sarrafzadeh, FPGA Technology Mapping for Power Minimization, Proceedings of the 4th International Workshop on Field-Programmable Logic and Applications: Field-Programmable Logic, Architectures, Synthesis and Applications, p.66-77, September 07-09, 1994
• 53: FARRAHI, A. AND SARRAFZADEH, M. 1994b. Complexity of the lookup-table minimization problem for FPGA technology mapping. IEEE Trans. Comput. Aided Des. 13, 11, 1319-1332.
• 54: David Filo , Jerry Chih-Yuan Yang , Frédéric Mailhot , Giovanni De Micheli, Technology mapping for a two-output RAM-based field programmable gate array, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 55: Robert J. Francis, A tutorial on logic synthesis for lookup-table based FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.40-47, November 1992, Santa Clara, California, United States
• 56: Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123418]
• 57: FRANCIS, R. J., ROSE, J., AND VRANESIC, Z.G. 1991a. Technology mapping of lookup tablebased FPGAs for performance. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 568-571.
• 58: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 59: S. J. Friedman , K. J. Supowit, Finding the Optimal Variable Ordering for Binary Decision Diagrams, IEEE Transactions on Computers, v.39 n.5, p.710-713, May 1990 [doi>10.1109/12.53586]
• 60: FUJITA, M. AND MATSUNAGA, Y. 1991. Multi-level logic minimization based on minimal support and its application to the minimization of look-up table type FPGAs. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 560 -563.
• 61: Masahiro Fujita , Yuji Kukimoto, Patching Method for Lookup-Table Type FPLs, Selected papers from the Second International Workshop on Field-Programmable Logic and Applications, Field-Programmable Gate Arrays: Architectures and Tools for Rapid Prototyping, p.61-70, August 31-September 02, 1992
• 62: Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
• 63: GAO, T., CHEN, K.-C., CONG, J., DING, Y., AND LIU, C.L. 1993. Placement and placementdriven technology mapping for FPGA synthesis. In Proceedings of the IEEE International ASIC Conference (Rochester, NY, Sept.), 91-94.
• 64: 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
• 65: GROH, M. 1991. Technology mapping for look-up table FPGAs. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Oxford, England, Sept.), 191-200.
• 66: HALATSIS, C. AND GAITANIS, N. 1978. Irredundant normal forms and minimal dependence sets of a Boolean function. IEEE Trans. Comput. 27, 11, 1064-1068.
• 67: HE, J. AND ROSE, J. 1994. Technology mapping for heterogeneous FPGAs. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.).
• 68: HE, S. AND TORKELSON, M. 1993. Decomposition of logic functions with partial vertex chart. In Proceedings of the IEEE International ASIC Conference (Rochester, NY, Sept.), 430-433.
• 69: Mark A. Heap , William A. Rogers , M. Ray Mercer, A Synthesis Algorithm for Two-Level XOR Based Circuits, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.459-463, October 11-14, 1992
• 70: Alan J. Hu , David L. Dill, Reducing BDD size by exploiting functional dependencies, Proceedings of the 30th international conference on Design automation, p.266-271, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164888]
• 71: Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.359-363, November 05-09, 1995, San Jose, California, United States
• 72: HUFFMAN, D.A. 1952. A method for the construction of minimum-redundancy codes. Proc. IRE 40, 9, 1098-1101.
• 73: HWANG, T.-T., OWENS, R. M., AND IRWIN, M.J. 1992. Efficiently computing communication complexity for multilevel logic synthesis. IEEE Trans. Comput. Aided Des. 11, 5, 545-554.
• 74: HWANG, T.-T., OWENS, R.M., IRWIN, M.g., AND WANG, K.-H. 1994. Logic synthesis for field-programmable gate arrays. IEEE Trans. Comput. Aided Des. 13, 10, 1280-1287.
• 75: JOHNSON, D. S., DEMERS, A., ULLMAN, J. D., GAREY, M. R., AND GRAHAM, R.L. 1974. Worstcase performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299-325.
• 76: KAPOOR, B. 1994. An efficient graph-based technology mapping algorithm for FPGAs using lookup tables. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.).
• 77: KARP, R.M. 1963. Functional decomposition and switching circuit design. J. SIAM 11, 2, 291-335.
• 78: Kevin Karplus, Xmap: A technology mapper for table-lookup field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.240-243, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127672]
• 79: Kevin Karplus, Using if-then-else DAGs for multi-level logic minimization, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.101-117, June 1989, Cambridge, Massachusetts, United States
• 80: KERNIGHAN, B.W. AND LIN, S. 1970. An efficient heuristic procedure for partitioning of electrical circuits. Bell Syst. Tech. J. 49, 2, 291-308.
• 81: 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]
• 82: KIRKPATRICK, S., GELAT, C.D., AND VECCHI, M.P., JR. 1983. Optimization by simulated annealing. Science 220, (May), 671-680.
• 83: KOMMU, V. AND POMERANZ, I. 1993. GAFPGA: Genetic algorithm for FPGA technology mapping. In Proceedings of the European Design Automation Conference (Hamburg, Germany, Sept.), 300-305.
• 84: Yuji Kukimoto , Masahiro Fujita, Rectification method for lookup-table type FPGA's, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.54-61, November 1992, Santa Clara, California, United States
• 85: Y.-T. Lai , S. Sastry, Edge-valued binary decision diagrams for multi-level hierarchical verification, Proceedings of the 29th ACM/IEEE conference on Design automation, p.608-613, June 08-12, 1992, Anaheim, California, United States
• 86: Yung-Te Lai , Kuo-Rueih Ricky Pan , Massoud Pedram, FPGA Synthesis Using Function Decomposition, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.30-35, October 10-12, 1994
• 87: LAI, Y.-T., PAN, K.-R. R., PEDRAM, M., AND VRUDHULA, S. 1993b. FGMap: A technology mapping algorithm for lookup table type FPGAs based on function graphs. In Proceedings of the International Workshop on Logic Synthesis (Tahoe City, CA, May) 9b.1-4.
• 88: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 89: William K. C. Lam , Robert K. Brayton, On Relationship Between ITE and BDD, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.448-451, October 11-14, 1992
• 90: LAWLER, E. L., LEVITT, K. N., AND TURNER, J. 1969. Module clustering to minimize delay in digital networks. IEEE Trans. Comput. 18, 1, 47-57.
• 91: Christian Legl , Bernd Wurth , Klaus Eckl, An Implicit Algorithm for Support Minimization during Functional Decomposition, Proceedings of the 1996 European conference on Design and Test, p.412, March 11-14, 1996
• 92: LEVIN, I. AND PINTER, R.Y. 1993. Realizing expression graphs using table-lookup FPGAs. In Proceedings of the European Design Automation Conference (Hamburg, Germany, Sept.), 306-311.
• 93: Aiguo Lu , Jonathan Saul , Erik L. Dagless, Architecture Oriented Logic Optimization for Lookup Table Based FPGAs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.26-29, October 10-12, 1994
• 94: Jean-Christophe Madre , Jean-Paul Billon, Proving circuit correctness using formal comparison between expected and extracted behaviour, Proceedings of the 25th ACM/IEEE conference on Design automation, p.205-210, June 12-15, 1988, Atlantic City, New Jersey, United States
• 95: MALIK, S., SENTOVICH, E. M., AND BRAYTON, R.K. 1991. Retiming and resynthesis: Optimizing sequential networks with combinational techniques. IEEE Trans. Comput. Aided Des. 10, 1, 74-84.
• 96: MATHUR, A. AND LIU, C.L. 1994. Performance driven technology mapping for lookup-table based FPGAs. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.).
• 97: MATSUNAGA, Y. AND FUJITA, M. 1989. Multi-level logic minimization using binary decision diagrams. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 556-559.
• 98: Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic Synthesis for Field-Programmable Gate Arrays, Kluwer Academic Publishers, Norwell, MA, 1995
• 99: Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Optimum functional decomposition using encoding, Proceedings of the 31st annual conference on Design automation, p.408-414, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196440]
• 100: MURGAI, R., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1993a. Some results on the complexity of Boolean functions for table look up architectures. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 505-512.
• 101: Rajeev Murgai , Robert K. Brayton , Albert Sangiovanni-Vincentelli, Sequential synthesis for table look up programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.224-229, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164681]
• 102: 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
• 103: Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
• 104: MURGAI, R., SHENOY, N., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1991a. Performance directed synthesis for table look up programmable gate arrays. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 572- 575.
• 105: MURGAI, R., SHENOY, N., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1991b. Improved logic synthesis algorithms for table look up architectures. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 564-567.
• 106: S. Muroga , Y. Kambayashi , H. C. Lai , J. N. Culliney, The Transduction Method-Design of Logic Networks Based on Permissible Functions, IEEE Transactions on Computers, v.38 n.10, p.1404-1424, October 1989 [doi>10.1109/12.35836]
• 107: Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, Proceedings of the 33rd annual conference on Design automation, p.720-725, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240655]
• 108: Shipra Panda , Fabio Somenzi , Bernard F. Plessier, Symmetry detection and dynamic variable ordering of decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.628-631, November 06-10, 1994, San Jose, California, United States
• 109: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 110: ROSE, J., EL GAMAL, A., AND SANGIOVANNI-VINCENTELLI, A. 1993. Architectures of fieldprogrammable gate arrays. Proc. IEEE 81, 7, 1013-1029.
• 111: ROTH, g. P. AND KARP, R.M. 1962. Minimization over Boolean graphs. IBM J. Res. Dev. (Apr.) 227-238.
• 112: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 113: SANGIOVANNI-VINCENTELLI, A., EL GAMAL, A., AND ROSE, J. 1993. Synthesis methods for field programmable gate arrays. Proc. IEEE 81, 7, 1057-1083.
• 114: SASAO, T. 1993. FPGA design by generalized functional decomposition. In Logic Synthesis and Optimization, Ed. Sasao, T., Norwell, MA (Jan.), 233-257.
• 115: G. Saucier , D. Brasen , J. P. Hiol, Partitioning with cone structures, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.236-239, November 07-11, 1993, Santa Clara, California, United States
• 116: SAUCIER, G., FRON, J., AND ABOUZEID, P. 1993b. Lexicographical expressions of Boolean functions with application to multilevel synthesis. IEEE Trans. Comput. Aided Des. 12, 11, 1642-1654.
• 117: Jonathan Saul, An Algorithm for the Multi-Level Minimazation of Reed-Muller Rpresentations, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.634-637, October 14-16, 1991
• 118: 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
• 119: Prashant Sawkar , Donald Thomas, Performance directed technology mapping for look-up table based FPGAs, Proceedings of the 30th international conference on Design automation, p.208-212, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164672]
• 120: P. Sawkar , D. Thomas, Area and delay mapping for table-look-up based field programmable gate arrays, Proceedings of the 29th ACM/IEEE conference on Design automation, p.368-373, June 08-12, 1992, Anaheim, California, United States
• 121: SCHAFER, I. AND PERKOWSKI, M.A. 1993. Synthesis of multiplexer circuits for incompletely specified multioutput Boolean functions with mapping to multiplexer based FPGAs. IEEE Trans. Comput. Aided Des. 12, 11, 1655-1664.
• 122: SCHLAG, M., CHAN, P.K., AND KONG, J. 1991. Empirical evaluation of multilevel logic minimization tools for a field programmable gate array technology. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Oxford, England, Sept.), 201-213.
• 123: SCHLAG, M., KONG, J., AND CHAN, P.K. 1994. Routability-driven technology mapping for lookup table-based FPGAs. IEEE Trans. Comput.-Aided Des. 13, 1, 13-26.
• 124: Martine D. F. Schlag , Jackson Kong , Pak K. Chan, Routability-Driven Techology Mapping for LookUp-Table-Based FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.86-90, October 11-14, 1992
• 125: SCHUBERT, E., KEBSCHULL, U., AND ROSENSTIEL, W. 1994. Functional decision diagrams for technology mapping to lookup-table FPGAs. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.).
• 126: Wen-Zen Shen , Juinn-Dar Huang , Shih-Min Chao, Lambda set selection in Roth-Karp decomposition for LUT-based FPGA technology mapping, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.65-69, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217508]
• 127: Hyunchul Shin , Chunghee Kim, Performance-oriented technology mapping for LUT-based FPGA's, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.2, p.323-327, June 1995 [doi>10.1109/92.386231]
• 128: SOE, S. AND KARPLUS, K. 1993. Variable ordering heuristics for ordered binary decision diagrams and canonical if-then-else DAGs. In Proceedings of the International Workshop on Logic Synthesis (Tahoe City, CA, May), P3d.l-15.
• 129: Ted Stanion , Carl Sechen, A method for finding good Ashenhurst decompositions and its application to FPGA synthesis, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.60-64, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217507]
• 130: Shashidhar Thakur , D. F. Wong, Simultaneous area and delay minimum K-LUT mapping for K-exact networks, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.402-408, October 02-04, 1995
• 131: THAKUR, S., WONG, D.F., KRISHNAMOORTHY, S., AND MOCEYUNAS, P. 1995. Delay minimal decomposition of multiplexers in technology mapping. In Proceedings of the International Workshop on Logic Synthesis (Tahoe City, CA, May), 1.59-1.68.
• 132: Nozomu Togawa , Masao Sato , Tatsuo Ohtsuki, A simultaneous technology mapping, placement, and global routing algorithm for field-programmable gate arrays, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.156-163, November 06-10, 1994, San Jose, California, United States
• 133: TOUATI, H., SHENOY, N., AND SANGIOVANNI-VINCENTELLI, A. 1992. Retiming for table-lookup field-programmable gate arrays. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.), 89-93.
• 134: TREVILLYAN, L. 1993. An experiment in technology mapping for FPGAs using a fixed library. In Proceedings of the International Workshop on Logic Synthesis (Tahoe City, CA, May), P9c.1-6.
• 135: Stephen M. Trimberger, Field-Programmable Gate Array Technology, Kluwer Academic Publishers, Norwell, MA, 1994
• 136: TRIMBERGER, S.M. 1993. A reprogrammable gate array and applications. Proc. IEEE 81, 7, 1030-1041.
• 137: Wei Wan , Marek A. Perkowski, A new approach to the decomposition of incompletely specified multi-output functions based on graph coloring and local transformations and its application to FPGA mapping, Proceedings of the conference on European design automation, p.230-235, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 138: Albert Ren Rui Wang, Algorithms for multilevel logic optimization, University of California at Berkeley, Berkeley, CA, 1991
• 139: WEINMANN, V. AND ROSENSTIEL, W. 1994. Logic module independent mapping for tablelookup FPGAs. In Proceedings of the ACM/SIGDA International Workshop on Field Programmable Gate Arrays (Berkeley, CA, Feb.).
• 140: WEINMANN, V. AND ROSENSTIEL, W. 1993. Technology mapping for sequential circuits based on retiming techniques. In Proceedings of the European Design Automation Conference (Hamburg, Germany, Sept.), 318-323.
• 141: Nam-Sung Woo, A heuristic method for FPGA technology mapping based on the edge visibility, Proceedings of the 28th conference on ACM/IEEE design automation, p.248-251, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127675]
• 142: Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217506]
• 143: XILINX. 1994. The Programmable Logic Data Book. Xilinx, Inc., San Jose, CA.
• 144: Honghua Yang , D. F. Wong, Edge-map: optimal performance driven technology mapping for iterative LUT based FPGA designs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.150-155, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis; Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
FPGA, area minimization, computer-aided design of VLSI, decomposition, delay minimization, delay modeling, logic optimization, power minimization, programmable logic, routing, simplification, synthesis, system design, technology mapping