Logic optimization and code generation for embedded control applications

ABSTRACT

We address software optimization for embedded control systems. The Esterel language is used as the front-end specification; Esterel compiler v6 is used to partition the control circuit and data path; the resulting intermediate representation of the design is a control-data network. This paper emphasizes the optimization of the control circuit portion and the code generation of the logic network. The new control-data network representation has four types of nodes: control, multiplexer, predicate and data expression; the control portion is a multi-valued logic network (MV-network). We use an effective multi-valued logic network optimization package called MVSIS for the control optimization. It includes algebraic methods to perform multi-valued algebraic division, factorization and decomposition and logic simplification methods based on observability don't cares. We have developed methods to evaluate a control-data network based on both an MDD and sum-of-products representation of the multi-valued logic functions. The MDD-based approach uses multi-valued intermediate variables and generates code according to the internal BDD structure. The SOP-based code is proportional to the number of cubes in the logic network. Preliminary results compare the two approaches and the optimization effectiveness.

REFERENCES

• 1: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 2: Stephen A. Edwards, Compiling Esterel into sequential code, Proceedings of the 37th conference on Design automation, p.322-327, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337429]
• 3: G. Berry, "Esterel on hardware," Philosophical Transactions of the Royal Society of London. Series A, 1992.
• 4: G. Berry, The coastruetiee semantics of pure Esterel. Book in preparation, 1996.
• 5: F. Baiarin and M. Chiodo, "Software synthesis for complex reactive embedded systems," in Prec. of the Intl. Conf. on Computer Design, Oct. 1999.
• 6: Massimiliano Chiodo , Paolo Guisto , Attila Jurecska , Luciano Lavagno , Ellen Sentovich , Harry Hsieh , Kei Suzuki , Alberto Sangiovanni-Vincentelli, Synthesis of software programs for embedded control application, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.587-592, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217594]
• 7: F. Balarin, M. Chiodo, P. Ginsto, H. Hsieh, A. Jurecska, L. Lavagno, A. L. Sangiovauni-Vincentelli, E. M. Sentovich, and K. Suzuki, "Synthesis of software programs for embedded control applications," IEEE Trans. Computer-Aided Design, vol. 18, pp. 834-49, June 1999.
• 8: M. Gag and R. K. Brayton, "Semi-algebraic methods for multi-valued logic," in Prec. of the Intl. Workshop on Logic Synthesis, May. 2000.
• 9: Yunjian Jiang , Robert K. Brayton, Don't cares and multi-valued logic network minimization, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: It. K. Brayton, M. Chiodo, R. Hojati, T. Kam, K. Kodandapani, R. P. Kurshan, S. Maiik, A. L. Sangiovanni-Vincentelli, E. M. Sentovich, T. Shiple, K. J. Singh, and H.-Y. Wang, "BLIF-MV: An Interchange Format for Design Verification and Synthesis," Tech. Pep. UCB/ERL M91/97, Electronics Research Lab, Univ. of California, Berkeley, CA 94720, Nov. 1991.
• 11: Robert K. Brayton , Gary D. Hachtel , Alberto L. Sangiovanni-Vincentelli , Fabio Somenzi , Adnan Aziz , Szu-Tsung Cheng , Stephen A. Edwards , Sunil P. Khatri , Yuji Kukimoto , Abelardo Pardo , Shaz Qadeer , Rajeev K. Ranjan , Shaker Sarwary , Thomas R. Shiple , Gitanjali Swamy , Tiziano Villa, VIS: A System for Verification and Synthesis, Proceedings of the 8th International Conference on Computer Aided Verification, p.428-432, August 03, 1996
• 12: It. K. Brayton and et ai., "MVSIS." http://mm-cad. eecs. berkeley, edu/Respep/Re ee arch/mve'l s/.
• 13: T. Kam and R. K. Brayton, "Mtdti-vaJued deisoin diagrams," Tech. Rep. UCB/ERL M90/125, Electronics Research Lab, Univ. of California, Berkeley, CA 94720, Dec. 1990.
• 14: R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Experimentation, Management

Keywords:
Esterel, MDD, code generation, logic optimization, multiple-valued