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. ALLEN, D. 1992. Automatic one-hot re-encoding for FPGAs. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Vienna, Austria, Aug.), 71-77.
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. BECKER, B. AND DRECHSLER, R. 1995. How many decomposition types do we need. In Proceedings of the European Design and Test Conference, (Paris, March).
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. BHAT, N. AND HILL, D.D. 1992. Routable technology mapping for LUT FPGAs. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 95-98.
10. BRACE, K., RUDELL, R.L., AND BRYANT, R.E. 1990. Efficient implementation of a BDD package. In Proceedings of the ACM/IEEE Design Automation Conference (Orlando, FL, June), 40-45.
11. BRAYTON, R. K., HACHTEL, G. D., MCMULLEN, C. T., AND SANGIOVANNI-VINCENTELLI, A.L. 1984. Logic Minimization Algorithms for VLSI Synthesis, Kluwer, Hingham, MA.
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. BROWN, S. D., FRANCIS, R. J., ROSE, J., AND VRANESIC, Z.G. 1994. Field-Programmable Gate Arrays. Kluwer, Norwell, MA.
15. BRYANT, R.E. 1995. Binary decision diagrams and beyond: Enabling techniques for formal verification. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 236-243.
16. BRYANT, R.E. 1992. Symbolic Boolean manipulation with ordered binary-decision diG- grams. ACM Comput. Surv. 24, 3, 293-318.
17. BRYANT, R.E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35, 6, 677-691.
18. BUTLER, K.M., ROSS, D.E., KAPUR, R., AND MERCER, M.R. 1991. Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 417-420.
19. CHAN, P. K. AND MOURAD, S. 1994. Digital Design Using Field Programmable Gate Arrays. PTR Prentice-Hall, Englewood Cliffs, NJ.
20. CHAN, P.K., SCHLAG, M. D. F., AND ZIEN, J.Y. 1993. On routability prediction for fieldprogrammable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference (Dallas, TX, June), 326-330.
21. CHANG, S.-C. AND MAREK-SADOWSKA, M. 1992. Technology mapping via transformations of function graphs. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 159-162.
22. CHANG, S.-C., CHENG, K.-T., WOO, N.-S., AND MAREK-SADOWSKA, M. 1994. Layout driven logic synthesis for FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference (San Diego, CA, June), 308-313.
23. CHEN, C.-S., TSAY, Y.-W., HWANG, T.-T., WU, A. C. H., AND LIN, Y.-L. 1993. Combining technology mapping and placement for delay-optimization in FPGA designs. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 123-127.
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. CHEN, K.-C. AND CONG, J. 1992. Maximal reduction of lookup-table based FPGAs. In Proceedings of the European Design Automation Conference (Hamburg, Germany, Sept.), 224-229.
26. CHEN, K.-C., CONG, J., DING, Y., KAHNG, A. B., AND TRAJMAR, P. 1992. DAG-map: Graphbased FPGA technology mapping for delay optimization. IEEE Des. Test Comput. (Sept.), 7-20.
27. CHEN, K.-C., MATSUNAGA, Y., FUJITA, M., AND MUROGA, S. 1991. A resynthesis approach for network optimization. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 458-463.
28. CHOWDHARY, A. AND HAYES, J.P. 1995. Technology mapping for field-programmable gate arrays using integer programming. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 346-352.
29. CHUNG, K. AND ROSE, J. 1992. TEMPT: Technology mapping for exploration of FPGA architectures with hard-wired connections. In Proceedings of the ACM/IEEE Design Automation Conference (Anaheim, CA, June) 361-367.
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. CONG, J. AND DING, Y. 1995. On nominal delay minimization in LUT-based FPGA technology mapping. In Proceedings of the ACM International Symposium on Field Programmable Gate Arrays (Monterey, CA, Feb.), 82-88.
32. CONG, J. AND DING, Y. 1994a. On nominal delay minimization in LUT-based FPGA technology mapping. Integration--VLSI J. 18, 73-94.
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. CONG, J. AND DING, Y. 1993a. On area/depth trade-off in LUT-based FPGA technology mapping. In Proceedings of the ACM/IEEE Design Automation Conference (Dallas, TX, June), 213-218.
36. CONG, g. AND DING, Y. 1993b. Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 110-114.
37. CONG, g. AND DING, Y. 1992. An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 48-53.
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. CONG, J., DING, Y., KAHNG, A.B., TRAJMAR, P., AND CHEN, K.-C. 1992a. An improved graph-based FPGA technology mapping for delay optimization. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 154-158.
41. CONG, g. AND HWANG, Y.-Y. 1996. Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs. In Proceedings of the ACM/IEEE Design Automation Conference (Las Vegas, NV, June), 726-729.
42. CONG, J. AND HWANG, Y.-Y. 1995a. Simultaneous depth and area minimization in LUT- based FPGA mapping. In Proceedings of the ACM International Symposium on Field Programmable Gate Arrays (Monterey, CA, Feb.), 68-74.
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. CONG, J., PECK, J., AND DING, Y. 1996. RASP: A general logic synthesis system for SRAM- based FPGAs. In Proceedings of the ACM International Symposium on Field Programmable Gate Arrays (Monterey, CA, Feb.), 137-143.
46. CURTIS, H.A. 1963. Generalized tree circuit--the basic building block of an extended decomposition theory. J. ACM 10, 3, 562-581.
47. CURTIS, H.A. 1961. A generalized tree circuit. J. ACM 8, 4, 484-496.
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. DEVADAS, S., GHOSH, A., AND KEUTZER, K. 1994. Logic Synthesis. McGraw-Hill, New York.
50. DE MICHELI, G. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill, New York.
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. FARRAHI, A. AND SARRAFZADEH, M. 1994a. FPGA technology mapping for power minimization. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Prague, Czech Republic, Aug.), 66-77.
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. FILO, D., YANG, J., MAILHOT, F., AND DE MICHELI, G. 1991. Technology mapping for a two-output RAM-based field programmable gate arrays. In Proceedings of the European Conference on Design Automation (Amsterdam, the Netherlands, Feb.), 534-538.
55. FRANCIS, R.J. 1992. A tutorial on logic synthesis for lookup-table based FPGAs, In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 40-47.
56. FRANCIS, R. J., ROSE, J., AND CHUNG, K. 1990. Chortle: A technology mapping program for lookup table-based field programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference (Orlando, FL, June), 613-619.
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. FRANCIS, R. J., ROSE, J., AND VRANESIC, Z.G. 1991b. Chortle-crf: Fast technology mapping for lookup table-based FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 227-233.
59. FRIEDMAN, S. J. AND SUPOWIT, K.J. 1990. Finding the optimal variable ordering for binary decision diagrams. IEEE Trans. Comput. 39, 5, 710-713.
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. FUJITA, M. AND KUKIMOTO, Y. 1992. Patching method for lookup-table type FPGAs. In Proceedings of the International Workshop on Field Programmable Logic and Applications (Vienna, Aug.), 61-70.
62. GABOW, H. 1976. An efficient implementation of Edmonds' algorithm for maximum matching on graphs. J. ACM 23, (Apr.), 221-234.
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. GAREY, M. R. AND JOHNSON, D.S. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
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. HEAP, M. A., ROGERS, W. A., AND MERCER, M.R. 1992. A synthesis algorithm for two-level XOR based circuits. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 459-462.
70. Hu, A. J. AND DILL, D.L. 1993. Reducing BDD size by exploiting functional dependencies. In Proceedings of the ACM/IEEE Design Automation Conference (Dallas, TX, June), 266- 271.
71. HUANG, J.-D., Jou, J.-Y., AND SHEN, W.-Z. 1995. Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 359-363.
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. KARPLUS, K. 1991. Xmap: A technology mapper for table-lookup field-programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 240-243.
79. KARPLUS, K. 1989. Using if-then-else DAGs for multi-level logic minimization. In Proceedings of the Decennial Caltech Conference on VLSI (Pasadena, CA, March), 101-118.
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. KEUTZER, K. 1987. DAGON: Technology binding and local optimization by DAG matching. In Proceedings of the ACM/IEEE Design Automation Conference (Miami Beach, FL, June), 341-347.
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. KUKIMOTO, Y. AND FUJITA, M. 1992. Rectification method for lookup-table type FPGA's. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 54-61.
85. LAI, Y.-T. AND SASTRY, S. 1992. Edge-valued binary diagrams for multi-level hierarchical verification. In Proceedings of the ACM/IEEE Design Automation Conference (Anaheim, CA), 608-613.
86. LAI, Y.-T., PAN, K.-R. R., AND PEDRAM, M. 1994. FPGA synthesis using function decomposition. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 30-35.
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. LAI, Y.-T., PEDRAM, M., AND VRUDHULA, S. 1993a. BDD based decomposition of logic functions with application to FPGA synthesis. In Proceedings of the ACM/IEEE Design Automation Conference (Dallas, TX, June), 642-647.
89. LAM, W. K. C. AND BRAYTON, R.K. 1992. On relationship between ITE and BDD. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 448-451.
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. LEGL, C., WURTH, B., AND ECKL, K. 1996. An implicit algorithm for support minimization during functional decomposition. In Proceedings of the European Design and Test Conference (Paris, March).
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. Lu, A., SAUL, g., AND DAGLESS, E. 1994. Architecture oriented logic optimization for lookup table based FPGAs. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 26-29.
94. MADRE, J. C. AND BILLON, J.P. 1988. Proving circuit correctness using formal comparison between expected and extracted behaviour. In Proceedings of the ACM/IEEE Design Automation Conference (Anaheim, CA), 205-210.
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. MURGAI, R., BRAYTON, R.K., AND SANGIOVANNI-VINCENTELLI, A. 1995. Logic Synthesis for Field-Programming Gate Arrays. Kluwer, Norwell, MA.
99. MURGAI, R., BRAYTON, R. K., AND SANGIOvANNI-VINcENTELLI, A. 1994. Optimum functional decomposition using encoding. In Proceedings of the ACM/IEEE Design Automation Conference (San Diego, CA, June), 408-413.
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. MURGAI, R., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1993b. Sequential synthesis for table look up programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference (Dallas, TX, June), 224-229.
102. MURGAI, R., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A. 1992. An improved synthesis algorithm for multiplexor-based PGA's. In Proceedings of the ACM/IEEE Design Automation Conference (Anaheim, CA, June), 380-386.
103. MURGAI, R., NISHIZAKI, Y., SHENOY, N., BRAYTON, R.K., AND SANGIOVANNI-VINCENTELLI, A. 1990. Logic synthesis algorithms for programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference (Orlando, FL, June), 620-625.
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. MUROGA, S., KAMBAYASHI, Y., LAI, H. C., AND CULLINEY, J.N. 1989. The transduction method--design of logic networks based on permissible functions. IEEE Trans. Comput. 38, 10, 1404-1424.
107. PAN, P. AND LIU, C.L. 1996. Optimal clock period FPGA technology mapping for sequential circuits. In Proceedings of the ACM/IEEE Design Automation Conference (Las Vegas, NV, June), 720-725.
108. PANDA, S., SOMENZI, F., AND PLESSIER, B.F. 1994. Symmetry detection and dynamic variable ordering of decision diagrams. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 628-631.
109. PAPADIMITRIOU, C. H. AND STEIGLITZ, K. 1982. Combinatorial Optimization: Algorithm and Complexity. Prentice-Hall, Englewood Cliffs, NJ.
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. RUDELL, R. 1993. Dynamic variable ordering for ordered binary decision diagrams. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 42-47.
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. SAUCIER, G., BRASEN, D., AND HIOL, J.P. 1993a. Partitioning with cone structures. In Proceedings of the IEEE International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 236-239.
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. SAUL, J. 1991. An algorithm for the multi-level minimization of Reed-Muller representations. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 634-637.
118. SAWADA, H., SUYAMA, T., AND NAGOYA, A. 1995. Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 353-358.
119. SAWKAR, P. AND THOMAS, D. 1993. Performance directed technology mapping for look-up table based FPGAs. In Proceedings of the ACM/IEEE Design Automation Conference (Dallas, TX, June), 208-212.
120. SAWKAR, P. AND THOMAS, D. 1992. Area and delay mapping for table-look-up based field programmable gate arrays. In Proceedings of the ACM/IEEE Design Automation Conference (Anaheim, CA, June), 368-373.
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. SCHLAG, M., KONG, J., AND CHAN, P.K. 1992. Routability-driven technology mapping for lookup table-based FPGAs. In Proceedings of the IEEE International Conference on Computer Design (Cambridge, MA, Oct.), 86-90.
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. SHEN, W.-Z., HUANG, J.-D., AND CHAO, S.-M. 1995. Lambda set selection in Roth-Karp decomposition for LUT-based FPGA technology mapping. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 65-69.
127. SHIN, H. AND KIM, C. 1995. Performance-oriented technology mapping for LUT-based FP- GAs. IEEE Trans. VLSI Syst. 3, 2, 323-327.
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. STANION, T. AND SECHEN, C. 1995. A method for finding good Ashenhurst decomposition and its application to FPGA synthesis. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 60-64.
130. THAKUR, S. AND WONG, D.F. 1995. Simultaneous area and delay minimum K-LUT mapping for K-exact networks. In Proceedings of the IEEE International Conference on Computer Design (Austin, TX).
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. TOGAWA, N., SATO, M., AND OHTSUKI, T. 1994. Maple: A simultaneous technology mapping, placement and global routing algorithm for field-programmable gate arrays. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 156-163.
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. TRIMBERGER, S.M. 1994. Field-Programmable Gate Array Technology. Kluwer, Norwell, MA.
136. TRIMBERGER, S.M. 1993. A reprogrammable gate array and applications. Proc. IEEE 81, 7, 1030-1041.
137. WAN, W. AND PERKOWSKI, M.A. 1992. 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. In Proceedings of the European Design Automation Conference (Hamburg, Germany, Sept.), 230-235.
138. WANG, A.R. 1989. Algorithms for multi-level logic optimization. UC Berkeley Tech. Memor. UCB/ERL M89/50 (Apr.).
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. Woo, N.-S. 1991. A heuristic method for FPGA technology mapping based on the edge visibility. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 248-251.
142. WURTH, B., ECKL, K., AND ANTREICH, K. 1995. Functional multiple-output decomposition: Theory and an implicit algorithm. In Proceedings of the ACM/IEEE Design Automation Conference (San Francisco, CA, June), 54-59.
143. XILINX. 1994. The Programmable Logic Data Book. Xilinx, Inc., San Jose, CA.
144. YANG, H. AND WONG, D.F. 1994. Edge-map: Optimal performance driven technology mapping for iterative LUT based FPGA designs. In Proceedings of the IEEE International Conference on Computer-Aided Design (San Jose, CA, Nov.), 150-155.

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Hardware

  • Electronic design automation

    • High-level and register-transfer level synthesis

    • Logic synthesis

      • Circuit optimization

  • Integrated circuits

    • Logic circuits

      • Combinational circuits

  • Very large scale integration design

    • Application-specific VLSI designs