Application of Indexed Partition Calculus in Logic Synthesis of Boolean Functions for FPGAs

• Autorzy: Rawski M.
• Języki publikacji: EN

Abstrakty

EN

Functional decomposition of Boolean functions specified by cubes proved to be very efficient. Most popular decomposition methods are based on blanket calculus. However computation complexity of blanket manipulations strongly depends on number of function's variables, which prevents them from being used for large functions of many input and output variables. In this paper a new concept of indexed partition is proposed and basic operations on indexed partitions are defined. Application of this concept to logic synthesis based on functional decomposition is also discussed. The experimental results show that algorithms based on new concept are able to deliver good quality solutions even for large functions and does it many times faster than the algorithms based on blanket calculus.

Słowa kluczowe

EN

indexed partition; logic synthesis; FPGA

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2011
• Tom: Vol. 57, No. 2
• Strony: 209--216
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Rawski M.

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

Bibliografia

• [1] 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.
• [2] T. Łuba and H. Selvaraj, “A General Approach to Boolean Function Decomposition and its Applications in FPGA-Based Synthesis,” VLSI Design, vol. 3, no. 3-4, pp. 289–300, 1995.
• [3] M. Rawski, “Decomposition of Boolean Function Sets,” Electronics and Telecommunications Quarterly, vol. 53, no. 3, pp. 231–249, 2007.
• [4] T. Sasao, M. Matsuura, Y. Iguchi, and S. Nagayama, “Compact BDD Representations for Multiple-Output Functions and Their Application,” in Proceedings of ISMVL, 2001, pp. 207–212.
• [5] C. Scholl, Functional Decomposition with Application to FPGA Synthesis. Kluwer Academic Publisher, 2001.
• [6] R. Ashenhurst, “The Decomposition of Switching Functions,” in Proceedings International Symposium Theory of Switching, vol. 29, 1959, pp. 74–116.
• [7] H. A. Curtis, A New Approach to the Design of Switching Circuits. New Jersey: D. van Nostrand company, Princeton, 1962.
• [8] R. M. Karp, “Functional Decomposition and Switching Circuit Design,” SIAM Journal on Applied Mathematics, vol. 11, no. 2, pp. 291–335, June 1963.
• [9] J. Hartmanis and R. E. Stearns, Algebraic Structure Theory of Sequential Machines. Prentice-Hall, 1966.
• [10] H. Selvaraj, M. Nowicka, and T. Łuba, “Performance Oriented Decomposition Strategies for FPGA Based Technology Mapping,” in International Conference VLSI for Signal Processing, Chennai, India, 1998.
• [11] M. Rawski, L. Jóźwiak, and T. Łuba, “Functional Decomposition with an Efficient Input Support Selection for Sub-Functions Based on Information Relationship Measures,” Journal of Systems Architecture, vol. 47, no. 2, pp. 137–155, February 2001.
• [12] L. Jóźwiak, “Information Relationships and Measures: An Analysis Apparatus for Efficient Information System Synthesis,” 23rd EUROMICRO Conference, pp. 13–23, 1-4 September 1997.
• [13] A. Chojnacki and L. Jóźwiak, “High-Quality FPGA Designs Through Functional Decomposition with Sub-Function Input Support Selection Based on Information Relationship Measures,” in IEEE International Symposium on Quality of Electronic Design. San Jose, USA: IEEE Computer Society Press, Los Alamitos, CA, USA, 26-28 March 2011, pp. 409–414.
• [14] A. Chojnacki and L. Jóźwiak, “An Effective and Efficient Method for Functional Decomposition of Boolean Functions Based on Information Relationships Measures,” in Design and Diagnostics of Electronic Circuits and Systems DDECS'2000, Smolenice, Slovakia, April 2000.
• [15] C. Y. Lee, “Representation of Switching Circuits by Binary-Decision Diagrams,” The Bell System Technical Journal, pp. 985–999, 1959.
• [16] S. B. Akers, “Binary Decision Diagrams,” IEEE Transactions on Computers, vol. 27, no. 6, pp. 509–516, 1978.
• [17] R. E. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, vol. 35, no. 6, pp. 677–691, 1986.
• [18] T. Sasao and M. Fujita, Representations of Discrete Functions. Kluwer Academic Publishers, 1996.
• [19] G. D. Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.
• [20] M. Nowicka, T. Łuba, and M. Rawski, “FPGA-Based Decomposition of Boolean Functions, Algorithms and Implementation,” Advanced Computer Systems, pp. 502–509, 1999.
• [21] M. Rawski, “Efficient Variable Partitioning Method for Functional Decomposition,” Electronics and Telecommunications Quarterly, vol. 53, no. 1, pp. 63–81, 2007.
• [22] M. Rawski, Evolutionary Algorithms. Intech, 2011, ch. Evolutionary Algorithms in Decomposition-Based Logic Synthesis.
• [23] M. Rawski, H. Selvara, T. Łuba, and P. Szotkowski, “Multilevel Synthesis of Finite State Machines Based on Symbolic Functional Decomposition,” International Journal of Computational Intelligence and Applications, vol. 6, no. 2, pp. 257–271, June 2006, imperial College Press.
• [24] T. Łuba, “Decomposition of Multiple-Valued Functions,” in 25th International Symposium on Multiple-Valued Logic, Bloomington, Indiana, 1995, pp. 256–261.
• [25] J. Lewandowski, M. Rawski, and H. Rybiński, “Application of Parallel Decomposition for Creation of Reduced Feed-Forward Neural Networks,” in Proceedings of the International Conference, Rough Sets and Intelligent Systems Paradigms. Warsaw, Poland: Springer, 28-30 June 2007, pp. 564–573, lecture Notes in Artificial Intelligence, Subseries of Lecture Notes in Computer Science.
• [26] H. Selvaraj, P. Sapiecha, and T. Łuba, “Functional Decomposition and Its Applications in Machine Learning and Neural Networks,” International Journal of Computational Intelligence and Applications, vol. 1, no. 3, pp. 259–271, 2001.
• [27] A. Chojnacki and L. Jóźwiak, “Multi-Valued Sub-Function Encoding in Functional Decomposition Based on Information Relationship Measures,” in 30th IEEE International Symposium on Multiple-valued Logic, Portland, OR, May 2000.
• [28] T. Łuba, “Multi-Level Logic Synthesis Based on Decomposition,” Microprocessors and Microsystems, vol. 18, no. 8, pp. 429–437, 1994.
• [29] G. Borowik, T. Łuba, and P. Tomaszewicz, “A Notion of R-Admissibility and its Application in Logic Synthesis,” in DESDes’09, Preprints of the 4th IFAC Workshop Discrete-Event System Design 2009, Spain, 6–8 October 2009, pp. 207–212.