Efficient variable partitioning method for functional decomposition

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

Abstrakty

EN

In recent years 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. However, its practical usefulness for very complex systems has been limited by the lack of an efficient method for selecting the appropriate input variable partitioning. This is an NP-hard problem and thus heuristic methods have to be used to efficiently and effectively search for optimal or near-optimal solutions. In this paper, a heuristic method for the input variable partitioning is discussed. The method is based on an application of evolutionary algorithms, what allows exploring the possible solution space of problem while keeping the high-quality solutions in this reduced space. The experimental results show that the proposed heuristic method is able to construct an optimal or near optimal solution very efficiently even for large systems. It is much faster than the systematic method while delivering results of comparable quality.

Słowa kluczowe

PL

synteza logiczna; dekompozycja funkcjonalna; algorytm ewolucyjny

EN

logic synthesis; functional decomposition; evolutionary algorithms

• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2007
• Tom: Vol. 53, No 1
• Strony: 63-81
• Opis fizyczny: Bibliogr. 27 poz., tab., wykr.

Twórcy

autor

Rawski, M.

• Warsaw University of Technology, Institute of Telecommunications, Poland,

Bibliografia

• 1. J.A. Brzozowski, T. Luba: Decomposition of Boolean Functions Specified by Cubes, Part 1: Theory of Serial Decompositions Using Blankets. Research Report CS-97-01, University of Waterloo,Waterloo, Canada, 1997; REVISED October 1998.
• 2. M. Burns, M. Perkowski, L. Jóźwiak: An Efficient Approach to Decomposition of Multi-Output Boolean Functions with Large Set of Bound Variables. EUROMICRO'98 Conference, Vasteras, Sweden, 1998.
• 3. S.C. Chang, M. Marek-Sadowska, T.T. Hwang: Technology Mapping for TLU FPGAs Based on Decomposition of Binary Decision Diagrams. IEEE Trans, on CAD, vol. 15, No 10, October, 1996, pp. 1226-1236.
• 4. C. Files, M. Perkowski: Multi-Valued Functional Decomposition as a Machine Learning Method, ISMVL'98, Fukuoka, Japan, 1998, pp. 173-178.
• 5. J.F. Frenzel: Application of Genetic Algorithms to Pattern Theory. Final Report for Summer Faculty Research Program, Wright Laboratory, Sponsored by Air Force Office of Scientific Research, Boiling Air Force Base, DC and Wright Laboratory, July 1993.
• 6. J.H. Holland: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. 1975 and 1992, MIT Press.
• 7. L. Jóźwiak: Information Relationships and Measures: An Analysis Apparatus for Efficient Information System Synthesis. 23rd EUROMICRO Conference, Budapest, Hungary, Sept. 1-4, 1997, pp. 13-23.
• 8. S. Khuri: An Evolutionary Approach to Combinatorial Optimization Problems. Proceedings of CSC, Phoenix, Arizona. March 1994.
• 9. Y.T. Lai, K.R.R. Pan, M. Pedram: OBDD-Based Functional Decomposition: Algorithm and Implementation. IEEE Trans, on CAD, vol. 15, No 8, August, 1996, pp. 977-990.
• 10. T. Luba, H. Selvaraj, M. Nowicka, A. Kraśniewski: Balanced multilevel decomposition and its applications in FPGA-based synthesis. G.Saucier, A.Mignotte (ed.), Logic and Architecture Synthesis, Chapman&Hall, 1995.
• 11. T. Luba, H. Selvaraj: 4 General Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis. VLSI Design, Special Issue on Decompositions in VLSI Design, vol. 3, No. 3-4, 1995, pp. 289-300.
• 12. T. Luba: Decomposition of Multiple-Valued Functions. 25th International Symposium on Multiple-Valued Logic, Bloomington, Indiana, 1995, pp. 256-261.
• 13. Z. Michalewicz: Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag,Berlin, third edition, 1996.
• 14. M.J. Noviskey, T.D. Ross, D.A. Gadd, M. Axtell: Application of Genetic Algorithms to Functional Decomposition in Pattern Theory. Report WL-TR-94-1015, Wright Laboratory, WL/AART-2. WPAFB, OH 4533-5543. Jan 1994.
• 15. M. Perkowski: A Survey of Literature on Function Decomposition. Final Report for SummerFaculty Research Program, Wright Laboratory, Sponsored by Air Force Office of Scientific Research, Boiling Air Force Base, DC and Wright Laboratory, September 1994.
• 16. M. Perkowski, M. Marek-Sadowska, L. Jóźwiak, T. Luba, S. Grygiel, M. Nowicka, R. Malvi, Z. Wang, S. Zhang: Decomposition of Multiple-Valued Relations. International Symposium on Multiple-Valued Logic, Antigonish, Nova Scotia, Canada 1997, pp. 13-18.
• 17. M. Rawski, L. Jóźwiak, M. Nowicka, T. Luba: Non-Disjoint Decomposition of Boolean Functions and Its Application in FPGA-oriented Technology Mapping. Proc. of the EUROMICRO'97 Conference, Budapest, Hungary, Sept. 1-4, 1997, pp. 24-30, IEEE Computer Society Press.
• 18. M. Rawski, L. Jóźwiak, T. Luba: Efficient Input Support Selection for Sub-functions in Functional Decomposition Based on Information Relationship Measures. EUROMICRO'99 Conference, Milan, Italy, 1999.
• 19. M. Rawski, L. Jóźwiak, T. Luba: The Influence of the Number of Values in Sub-functions on the Effectiveness and Efficiency of the Functional Decomposition. EUROMICRO'99 Conference, Milan, Italy, 1999.
• 20. M. Rawski, H. Selvaraj, P. Morawiecki: Efficient Method of Input Variable Partitioning in Functional Decomposition Based on Evolutionary Algorithms. DSD 2004, Proc. Euromicro Symposium on Digital System Design, Architectures, Methods and Tools, IEEE Computer Society, Selvaraj H. (Editor), Rennes, France, August 31 - September 3, 2004, pp. 136-143.
• 21. T. Ross, M. Noviskey, T. Taylor, D. Gadd: Pattern Theory: An Engineering Paradigmfor Algorithm Design. Final Technical Report, Wright Laboratories, WL/AART/WPAFB, 1991.
• 22. T. Sasao: FPGA design by generalised functional decomposition. Logic Synthesis and Optimisation, pp. 231-258, Kluwer Academic Publishers, 1993.
• 23. B. Steinbach, M. Stoker t: Design of Fully Testable Circuits by Functional Decomposition & Implicit Test Pattern Generation. IEEE VLSI Test Symposium Proceedings, 1994, pp. 22-27.
• 24. W. Wan, M. 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 IEEE European Design Automation Conference, September 7-10, Hamburg, 1992.
• 25. B. Zupan, M. Bohanec: Experimental Evaluation of Three Partition Selection Criteria for Decision Table Decomposition. Research Report, Department of Intelligent Systems, Josef Stefan Institute, Ljubljana, Slovenia, Oct. 1966.
• 26. B. Zupan, M. Bohanec: Learning Concept Hierarchies from Examples by Functional Decomposition. Research Report, Department of Intelligent Systems, Josef Stefan Institute, Ljubljana, Slovenia, Sept. 1966.
• 27. Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University, http://www.cbl.ncsu.edu/