Input Variable Partitioning Method for Decomposition-Based Logic Synthesis targeted Heterogeneous FPGAs

• Autorzy: Rawski M.
• Konferencja: International Conference on System Engineering - ICSEng (21 ; 16-18.08.2011) ; Las Vegas, USA
• Języki publikacji: EN

Abstrakty

EN

The functional decomposition has found an application in many fields of modern engineering and science, such as combinational and sequential logic synthesis for VLSI systems, pattern analysis, knowledge discovery, machine learning, decision systems, data bases, data mining etc. It is perceived as one of the best logic synthesis methods for FPGAs. However, its practical usefulness for very complex systems depends on efficiency of method used in decomposition calculation. One of the most important steps in functional decomposition construction is selection of the appropriate input variable partitioning. In case of modern heterogeneous programmable structures efficiency of methods used to solve this problem becomes especially important. Since the input variable partitioning problem is an NP-hard, heuristic methods have to be used to efficiently and effectively search for optimal or near-optimal solutions. The paper presents a method for bound set selection in functional decomposition targeted FPGAs with heterogeneous structure. This heuristic algorithm delivers optimal or near optimal results and is much faster than other methods.

Słowa kluczowe

EN

functional decomposition; heterogeneous FPGA; bound set selection

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2012
• Tom: Vol, 58, No. 1
• Strony: 15--20
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Rawski M.

• Institute of Telecommunications, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland,

Bibliografia

• [1] J. Cong and K. Yan, “Synthesis for fpgas with embedded memory blocks,” in Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, ser. FPGA ’00. New York, NY, USA: ACM, 2000, pp. 75–82. [Online]. Available: http://doi.acm.org/10.1145/329166.329183
• [2] S. Krishnamoorthy and R. Tessier, “Technology mapping algorithms for hybrid fpgas containing lookup tables and plas,” IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 22, no. 5, pp. 545–559, 2003.
• [3] M. Rawski, T. Łuba, Z. Jachna, and P. Tomaszewicz, The Influence of Functional Decomposition on Modern Digital Design Process. Springer, 2005, inbook 17. [Online]. Available: http://www.springerlink.com/content/p775582342t64847/
• [4] T. Sasao, Y. Iguchi, and T. Suzuki, “On lut cascade realizations of fir filters,” in DSD. Washington, DC, USA: IEEE Computer Society, 2005, pp. 467–475.
• [5] M. Rawski, P. Tomaszewicz, H. Selvaraj, and T. Łuba, “Efficient implementation of digital filters with use of advanced synthesis methods targeted fpga architectures,” in 8th Euromicro Conference on DIGITAL SYSTEM DESIGN, Architectures, Methods and Tools DSD’05, C. Wolinski, Ed., IEEE Computer Society. Portugal: IEEE Computer Society, 2005, inproceedings, pp. 460–466. [Online]. Available: http://portal.acm.org/citation.cfm?id=1100234
• [6] C. Scholl, Functional Decomposition with Application to FPGA Synthesis. Kluwer Academic Publisher, 2001.
• [7] M. Rawski, “Decomposition of boolean function sets,” Electronics and Telecommunications Quarterly, vol. 53, no. 3, pp. 231–249, 2007.
• [8] J. A. Brzozowski and T. Łuba, “Decomposition of boolean functions specified by cubes,” Journal of Multiple-Valued Logic and Soft Computing, vol. 9, pp. 377–417, 2003.
• [9] T. Łuba, H. Selvaraj, M. Nowicka, and A. Kraśniewski, “Balanced multilevel decomposition and its applications in fpga-based synthesis,” in Novel Approaches in Logic and Architecture Synthesis, A. M. Gabriele Saucier, Ed. Chapman and Hall, 1995, pp. 109–115.
• [10] R. Murgai, N. V. Shenoy, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, “Improved logic synthesis algorithms for table look up architectures,” in ICCAD, 1991, pp. 564–567.
• [11] Y.-T. Lai, M. Pedram, and S. B. K. Vrudhula, “Bdd based decomposition of logic functions with application to fpga synthesis,” in Proceedings of the 30th international Design Automation Conference, ser. DAC ’93.New York, NY, USA: ACM, 1993, pp. 642–647. [Online]. Available: http://doi.acm.org/10.1145/157485.165078
• [12] T. Sasao, Logic synthesis and optimization, ser. Kluwer international series in engineering and computer science. Kluwer Academic Publishers, 1993. [Online]. Available: http://books.google.pl/books?id=GuaV re0DF8C
• [13] H. Sawada, T. Suyama, and A. Nagoya, “Logic synthesis for look-up table based fpgas using functional decomposition and support minimization,” in Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, ser. ICCAD ’95. Washington, DC, USA: IEEE Computer Society, 1995, pp. 353–358. [Online]. Available: http://dl.acm.org/citation.cfm?id=224841.225063
• [14] M. Perkowski, “A survey of literature on function decomposition. final report for summer faculty research program,” Wright Laboratory, Sponsored by Air Force Office of Scientific Research, Bolling Air Force Base, DC and Wright Laboratory, Tech. Rep., September 1994.
• [15] W. Wan and M. 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,” in Proceedings of the conference on European design automation, ser. EURO-DAC ’92. Los Alamitos, CA, USA: IEEE Computer Society Press, 1992, pp. 230–235. [Online]. Available: http://dl.acm.org/citation.cfm?id=159754.161757
• [16] M. Rawski, L. Jóźwiak, and T. Łuba, “Efficient input support selection for sub-functions in functional decomposition based on information relationship measures,” Journal of Systems Architecture, vol. 47, no. 2, pp. 137–155, 2001.
• [17] M. Rawski, “Efficient variable partitioning method for functional decomposition,” Electronics and Telecommunications Quarterly, vol. 53, no. 1, pp. 63–81, 2007.
• [18] P. Morawiecki and M. Rawski, “Method of input variable partitioning in functional decomposition based on evolutionary algorithm and binary decision diagrams,” Proc. of IEEE 2008 Conference Human Systems Interaction, 2008.
• [19] M. Rawski, “Evolutionary algorithms in decomposition-based logic synthesis,” in Evolutionary algorithms, E. Kita, Ed. Intech, 2011.
• [20] M. Rawski, L. Jóźwiak, and T. Łuba, “The influence of the number of values in sub-functions on the effectiveness and efficiency of functional decomposition,” Proceedings of the 25th EUROMICRO Conference, IEEE Computer Society, pp. 86–93, 1999.
• [21] S. Yang, “Logic synthesis and optimization benchmarks user guide version 3.0,” 1991.