Article

Software synthesis from synchronous specifications using logic simulation techniques

Authors:

Robert K. BraytonAuthors Info & Claims

DAC '02: Proceedings of the 39th annual Design Automation Conference

Pages 319 - 324

https://doi.org/10.1145/513918.514002

Published: 10 June 2002 Publication History

Abstract

This paper addresses the problem of automatic generation of implementation software from high-level functional specifications in the context of embedded system on chip designs. Software design complexity for embedded systems has increased so much that a high-level functional programming paradigm need to be adopted for formal verifiability, maintainability and short time-to-market. We propose a framework for efficiently generating implementation software from a synchronous state machine specification for embedded control systems. The framework is generic enough to allow hardware/software partition for a given architecture platform. It is demonstrated that the logic optimization and simulation techniques can be combined to produce fast execution code for such embedded systems. Specifically, we propose a framework for software synthesis from multi-valued logic, including fast evaluation of logic functions, and scheduling techniques for node execution. Experiments are performed to show the initial results of our algorithms in this framework.

References

[1]

P. Ashar and S. Malik. Fast functional simulation using branching program. In Proc. of the Intl. Conf. on Computer-Aided Design, pages 408--412, Nov. 1995.]]

Digital Library

[2]

F. Balarin, M. Chiodo, P. Giusto, H. Hsieh, A. Jurecska, L. Lavagno, C. Passerone, A. Sangiovanni-Vincentelli, E. Sentovich, K. Suzuki, and B.Tabbara. Hardware-Software Co-Design of Embedded Systems: The Polis Approach. Kluwer Academic Press, 1997.]]

Digital Library

[3]

F. Balarin, M. Chiodo, P. Giusto, H. Hsieh, A. Jurecska, L. Lavagno, A. L. Sangiovanni-Vincentelli, E. M. Sentovich, and K. Suzuki. Synthesis of software programs for embedded control applications. IEEE Trans. Comput.-Aided Design Integrated Circuits, 18(6):834--49, June 1999.]]

Digital Library

[4]

M. Baleani, F. Gennari, Y. Jiang, Y. Patel, R. K. Brayton, and A. Sangiovanni-Vincentelli. Hw/sw partitioning and code generation of embedded control applications on a reconfigurable architecture platform. In Proc. of the Intl. Symposium on Hardware/Software Co-Design, May. 2002.]]

Digital Library

[5]

G. Berry. Esterel on hardware. Philosophical Transactions of the Royal Society of London. Series A, 1992.]]

[6]

G. Berry. The constructive semantics of pure Esterel. Book in preparation, 1996.]]

[7]

G. Berry and G. Gonthier. The Esterel synchronous programming language: Design, semantics, implementation. Science of Computer Programming, 1992.]]

Digital Library

[8]

R. K. Brayton and et al. MVSIS. http://www-cad.eecs.berkeley.edu/mvsis.]]

[9]

K. T. Cheng and A. Krishnakumar. Automatic functional test generation using the extended finite state machine model. In Proc. of the Design Automation Conf., June 1993.]]

Digital Library

[10]

S. Edwards. Compiling esterel into sequential code. In Proc. of the Design Automation Conf., June 2000.]]

Digital Library

[11]

The ESTEREL language. {On-line} http://www.esterel.org.]]

[12]

M. Gao and R. K. Brayton. Semi-algebraic methods for multi-valued logic. In Proc. of the Intl. Workshop on Logic Synthesis, May. 2000.]]

[13]

M. Gao, J. Jiang, Y. Jiang, Y. Li, S. Singha, and R. K. Brayton. MVSIS. In Proc. of the Intl. Workshop on Logic Synthesis, May. 2001.]]

[14]

O. Hainque, L. Pautet, Y. L. Biannic, and E. Nassor. Cronos: a separate compilation toolset for modular esterel applications. Formal Methods, 1999.]]

Digital Library

[15]

Y. Jiang and R. K. Brayton. Don't cares and multi-valued logic network minimization. In Proc. of the Intl. Conf. on Computer-Aided Design, Nov. 2000.]]

Digital Library

[16]

Y. Jiang and R. K. Brayton. Logic optimization and code generation for embedded control applications. In Proc. of the Intl. Symposium on Hardware/Software Co-Design, Apr. 2001.]]

Digital Library

[17]

C. Kim, L. Lavagno, and A. Sangiovanni-Vincentelli. Free MDD-based software optimization techniques for embedded systems. In Proc. of the Conf. on Design Automation & Test in Europe, Mar. 2000.]]

Digital Library

[18]

P. M. Maurer. Event driven simulation without loops or conditionals. In Proc. of the Intl. Conf. on Computer-Aided Design, Nov. 2001.]]

Digital Library

[19]

P. McGeer, K. McMillan, A. Saldanha, A. Sangiovanni-Vincentelli, and P. Scaglia. Fast discrete function evaluation using decision diagrams. In Proc. Of the Intl. Conf. on Computer-Aided Design, pages 402--407, Nov. 1995.]]

Digital Library

[20]

E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. SIS: A System for Sequential Circuit Synthesis. Technical Report UCB/ERL M92/41, Electronics Research Laboratory, Univ. of California, Berkeley, CA 94720, May 1992.]]

[21]

E. M. Sentovich, H. Toma, and G. Berry. Latch optimization in circuits generated from high-level descriptions. In Proc. of the Intl. Conf. on Computer Aided Design, pages 428--35, Nov. 1996.]]

Digital Library

[22]

M. Sgrio, L. Lavagno, Y. Watanabe, and A. L. Sangiovanni-Vincentelli. Synthesis of embedded software using free-choice petri nets. In Proc. of the Design Automation Conf., June 1999.]]

Digital Library

[23]

R. Ubar, J. Raik, and A. Morawiec. Back-Tracing and Event-Driven Techniques in High-Level Simulation with Decision Diagrams. In Proc. of the Intl. Symposium on Circuits and Systems, pages 208--211, May 2000.]]

[24]

D. Weil, V. Bertin, E. Closse, M. Poize, P. Venier, and J. Pulou. Efficient compilation of Esterel for real-time embedded systems. In Proc. of the Intl. Conf. on Compilers, Architecture and Synthesis for Embedded Systems, Nov. 2000.]]

Digital Library

Cited By

Abd-El-Barr M(2010)Ant colony optimisation–direct cover: a hybrid ant colony direct cover technique for multi-level synthesis of multiple-valued logic functionsInternational Journal of Electronics10.1080/00207217.2010.48891097:12(1391-1404)Online publication date: Dec-2010
https://doi.org/10.1080/00207217.2010.488910
Gädtke STraulsen Cvon Hanxleden RHa SChoi KDutt NTeich J(2007)HW/SW co-design for Esterel processingProceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1289816.1289842(99-104)Online publication date: 30-Sep-2007
https://dl.acm.org/doi/10.1145/1289816.1289842
Jabir APradhan DRajaprabhu TSingh A(2007)A Technique for Representing Multiple Output Binary Functions with Applications to Verification and SimulationIEEE Transactions on Computers10.1109/TC.2007.105656:8(1133-1145)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1109/TC.2007.1056
Show More Cited By

Index Terms

Software synthesis from synchronous specifications using logic simulation techniques
1. Hardware
  1. Hardware validation
    1. Functional verification
      1. Simulation and emulation
2. Software and its engineering

Recommendations

Synthesis of synchronous pipelined circuits from high-level modular specifications
Synchronous logic synthesis: algorithms for cycle-time minimization

A novel approach to logic synthesis of digital synchronous circuits is presented. A model for synchronous circuits that supports logic transformations aimed at optimizing the circuit performance is presented. Previous synthesis approaches attacked this ...
Logic Synthesis with High Speed CMOS Circuit Techniques
Special issue: selected articles from the 1995 NORCHIP seminar

Systems for automated logic synthesis with the True Single Phase Clocking circuit technique (TSPC) and a modified form of the Clock and Data Precharged Dynamic (CDPD) circuit technique, are presented. The CDPD system synthesizes high speed one clock ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '02: Proceedings of the 39th annual Design Automation Conference

June 2002

956 pages

ISBN:1581134614

DOI:10.1145/513918

General Chair:
Bryan Ackland
Agere Systems, Inc., Holmdel, NJ

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC02

Sponsor:

SIGDA

DAC02: 39th Design Automation Conference

June 10 - 14, 2002

Louisiana, New Orleans, USA

Acceptance Rates

DAC '02 Paper Acceptance Rate 147 of 491 submissions, 30%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
14
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abd-El-Barr M(2010)Ant colony optimisation–direct cover: a hybrid ant colony direct cover technique for multi-level synthesis of multiple-valued logic functionsInternational Journal of Electronics10.1080/00207217.2010.48891097:12(1391-1404)Online publication date: Dec-2010
https://doi.org/10.1080/00207217.2010.488910
Gädtke STraulsen Cvon Hanxleden RHa SChoi KDutt NTeich J(2007)HW/SW co-design for Esterel processingProceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1289816.1289842(99-104)Online publication date: 30-Sep-2007
https://dl.acm.org/doi/10.1145/1289816.1289842
Jabir APradhan DRajaprabhu TSingh A(2007)A Technique for Representing Multiple Output Binary Functions with Applications to Verification and SimulationIEEE Transactions on Computers10.1109/TC.2007.105656:8(1133-1145)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1109/TC.2007.1056
Stanković RJanković DFalkowski B(2005)Minimization of Haar wavelet series and Haar spectral decision diagrams for discrete functionsComputers and Electrical Engineering10.1016/j.compeleceng.2005.01.00331:3(203-216)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.compeleceng.2005.01.003
Nagayama SSasao TImai M(2004)Minimization of memory size for heterogeneous MDDsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015322(871-874)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015322
Posadas HHerrera FFernández VSánchez PVillar EBlasco F(2004)Single Source Design Environment for Embedded Systems Based on SystemCDesign Automation for Embedded Systems10.1007/s10617-005-1199-z9:4(293-312)Online publication date: 1-Dec-2004
https://dl.acm.org/doi/10.1007/s10617-005-1199-z
Jiang YMatic SBrayton RGetreu IFix LLavagno L(2003)Generalized cofactoring for logic function evaluationProceedings of the 40th annual Design Automation Conference10.1145/775832.775873(155-158)Online publication date: 2-Jun-2003
https://dl.acm.org/doi/10.1145/775832.775873
Jiang YBrayton RYasuura H(2003)Don't cares in logic minimization of extended finite state machinesProceedings of the 2003 Asia and South Pacific Design Automation Conference10.1145/1119772.1119951(809-815)Online publication date: 21-Jan-2003
https://dl.acm.org/doi/10.1145/1119772.1119951
Iguchi YSasao TMatsuura MYasuura H(2003)Evaluation of multiple-output logic functions using decision diagramsProceedings of the 2003 Asia and South Pacific Design Automation Conference10.1145/1119772.1119832(312-315)Online publication date: 21-Jan-2003
https://dl.acm.org/doi/10.1145/1119772.1119832
Yunjian Jiang Matic SBrayton R(2003)Generalized cofactoring for logic function evaluationProceedings 2003. Design Automation Conference (IEEE Cat. No.03CH37451)10.1109/DAC.2003.1218924(155-158)Online publication date: 2003
https://doi.org/10.1109/DAC.2003.1218924

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten