Tutorial: Compiling concurrent languages for sequential processors

ABSTRACT

Embedded systems often include a traditional processor capable of executing sequential code, but both control and data-dominated tasks are often more naturally expressed using one of the many domain-specific concurrent specification languages. This article surveys a variety of techniques for translating these concurrent specifications into sequential code. The techniques address compiling a wide variety of languages, ranging from dataflow to Petri nets. Each uses a different method, to some degree chosen to match the semantics of concurrent language. Each technique is considered to consist of a partial evaluator operating on an interpreter. This combination provides a clearer picture of how parts of each technique could be used in a different setting.

REFERENCES

• 1: Claude Ackad, Software synthesis from statechart models for real time systems, Proceedings of the IFIP WG10.3/WG10.5 international workshop on Distributed and parallel embedded systems, p.73-81, October 1998, Scholoß Eringerfeld, Germany
• 2: Balarin, F., Chiodo, M., Giusto, P., Hsieh, H., Jurecska, A., Lavagno, L., Sangiovanni-Vincentelli, A., Sentovich, E. M., and Suzuki, K. 1999. Synthesis of software programs for embedded control applications. IEEE Trans. Comput. Aided Des. Integ. Circ. Syst. 18, 6 (June), 834--849.
• 3: Benveniste, A., Caspi, P., Edwards, S. A., Halbwachs, N., Guernic, P. L., and de Simone, R. 2003. The synchronous languages 12 years later. Proc. IEEE 91, 1 (Jan.), 64--83.
• 4: Gérard Berry, Esterel on hardware, Mechanized reasoning and hardware design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 5: Berry, G. 1999. The constructive semantics of pure Esterel. Draft book.
• 6: Berry, G. 2000. The Esterel v5 Language Primer. Centre de Mathématiques Appliquées. Part of the Esterel compiler distribution.
• 7: Gérard Berry , Laurent Cosserat, The ESTEREL Synchronous Programming Language and its Mathematical Semantics, Seminar on Concurrency, Carnegie-Mellon University, p.389-448, July 09-11, 1984
• 8: 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]
• 9: Bertin, V., Poize, M., and Pulou, J. 1999. Une nouvelle méthode de compilation pour le language ESTEREL {A new method for compiling the Esterel language}. In Proceedings of GRAISyHM-AAA (Lille, France).
• 10: Bhattacharyya, S. S., Buck, J. T., Ha, S., Murthy, P. K., and Lee, E. A. 1993. A scheduling framework for minimizing memory requirements of multirate DSP systems represented as dataflow graphs. In Proceedings of the IEEE Workshop on VLSI Signal Processing VI. The Institute of Electrical and Electronics Engineers (IEEE), Veldhoven, The Netherlands, 188--196.
• 11: Bhattacharyya, S. S., Leupers, R., and Marwedel, P. 2000. Software synthesis and code generation for signal processing systems. IEEE Trans. Circ. Syst.---II: Analog Digital Signal Process. 47, 9 (Sept.), 849--875.
• 12: Shuvra S. Battacharyya , Edward A. Lee , Praveen K. Murthy, Software Synthesis from Dataflow Graphs, Kluwer Academic Publishers, Norwell, MA, 1996
• 13: Shuvra S. Bhattacharyya , Praveen K. Murthy , Edward A. Lee, Synthesis of Embedded Software from Synchronous Dataflow Specifications, Journal of VLSI Signal Processing Systems, v.21 n.2, p.151-166, June 1999 [doi>10.1023/A:1008052406396]
• 14: Bilsen, G., Engels, M., Lauwereins, R., and Peperstraete, J. A. 1995. Cyclo-static data flow. In Proceedings of the IEEE International Conference on Acoustics, Speech, & Signal Processing (ICASSP) (Detroit), 3255--3258.
• 15: Boussinot, F. and Doumenc, G. 1992. RC reference manual.
• 16: Loic C. Briand , Daniel M. Roy, Meeting Deadlines in Hard Real-Time Systems, IEEE Computer Society Press, Los Alamitos, CA, 1997
• 17: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 18: Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
• 19: Joseph Tobin Buck , Edward A. Lee, Scheduling dynamic dataflow graphs with bounded memory using the token flow model, 1993
• 20: Buck, J. T. 1994. Static scheduling and code generation from dynamic dataflow graphs with integer-valued control streams. In Conference Record of the Twenty-Eighth Asilomar Conference on Signals, Systems & Computers. The Institute of Electrical and Electronics Engineers (IEEE), Pacific Grove, CA, 508--513.
• 21: Luca Cardelli , Rob Pike, Squeak: a language for communicating with mice, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.199-204, July 1985
• 22: P. Caspi , D. Pilaud , N. Halbwachs , J. A. Plaice, LUSTRE: a declarative language for real-time programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.178-188, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41641]
• 23: 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]
• 24: Cortadella, J., Kondratyev, A., Lavagno, L., Massot, M., Moral, S., Passerone, C., Watanabe, Y., and Sangiovanni-Vincentelli, A. 1999. Task generation and compile-time scheduling for mixed data-control embedded software. Tech. Rep. LSI-99-47-R, Department of Software, Universitat Politècnica de Catalunya. November.
• 25: Jordi Cortadella , Alex Kondratyev , Luciano Lavagno , Marc Massot , Sandra Moral , Claudio Passerone , Yosinori Watanabe , Alberto Sangiovanni-Vincentelli, Task generation and compile-time scheduling for mixed data-control embedded software, Proceedings of the 37th conference on Design automation, p.489-494, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337553]
• 26: 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]
• 27: Edwards, S. A. 2002. An Esterel compiler for large control-dominated systems. IEEE Trans. Comput. Aided Des. Integ. Circ. Syst. 21, 2 (Feb.), 169--183.
• 28: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 29: Robert S. French , Monica S. Lam , Jeremy R. Levitt , Kunle Olukotun, A general method for compiling event-driven simulations, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.151-156, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217522]
• 30: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 31: Gonthier, G. 1988. Sémantiques et modèles d'exécution des langages réactifs synchrones; application à Esterel. {Semantics and models of execution of the synchronous reactive languages: application to Esterel}. Thèse d'informatique, Université d'Orsay.
• 32: Gary D. Hachtel , Fabio Somenzi, Logic Synthesis and Verification Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 33: Nicolas Halbwachs, Synchronous Programming of Reactive Systems, Kluwer Academic Publishers, Norwell, MA, 1992
• 34: Halbwachs, N., Caspi, P., Raymond, P., and Pilaud, D. 1991a. The synchronous data flow programming language LUSTRE. Proc. IEEE 79, 9 (Sept.), 1305--1320.
• 35: Halbwachs, N., Raymond, P., and Ratel, C. 1991b. Generating efficient code from data-flow programs. In Proceedings of the Third International Symposium on Programming Language Implementation and Logic Programming (PLILP), Lecture Notes in Computer Science, vol. 528, Springer-Verlag, Passau, Germany.
• 36: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9]
• 37: David Harel , Amnon Naamad, The STATEMATE semantics of statecharts, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.4, p.293-333, Oct. 1996 [doi>10.1145/235321.235322]
• 38: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 39: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 40: P. Hudak, Modular Domain Specific Languages and Tools, Proceedings of the 5th International Conference on Software Reuse, p.134, June 02-05, 1998
• 41: IEEE Computer Society. 1996. IEEE Standard Hardware Description Language Based on the Verilog Hardware Description Language. IEEE Computer Society, New York, 1364--1995.
• 42: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 43: Kahn, G. 1974. The semantics of a simple language for parallel programming. In Information Processing 74: Proceedings of IFIP Congress 74, North-Holland, Stockholm, 471--475.
• 44: Kahn, G. and MacQueen, D. B. 1977. Coroutines and networks of parallel processes. In Information Processing 77: Proceedings of IFIP Congress 77. North-Holland, Toronto, 993--998.
• 45: Jean J. Labrosse, Microc/OS-II, R & D Books, 1998
• 46: Le Guernic, P., Gautier, T., Le Borgne, M., and Le Maire, C. 1991. Programming real-time applications with SIGNAL. Proc. IEEE 79, 9 (Sept.), 1321--1336.
• 47: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987
• 48: Lee, E. A. and Messerschmitt, D. G. 1987b. Synchronous data flow. Proc. IEEE 75, 9 (Sept.), 1235--1245.
• 49: Lee, E. A. and Parks, T. M. 1995. Dataflow process networks. Proc. IEEE 83, 5 (May), 773--801.
• 50: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 51: B. Lin, Efficient compilation of process-based concurrent programs without run-time scheduling, Proceedings of the conference on Design, automation and test in Europe, p.211-217, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 52: Vijay K. Madisetti , Jean C. Walrand , David G. Messerschmitt, Asynchronous algorithms for the parallel simulation of event-driven dynamical systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.3, p.244-274, July 1991 [doi>10.1145/140765.140783]
• 53: Kenneth L. McMillan, Using Unfoldings to Avoid the State Explosion Problem in the Verification of Asynchronous Circuits, Proceedings of the Fourth International Workshop on Computer Aided Verification, p.164-177, June 29-July 01, 1992
• 54: K. L. McMillan, A technique of state space search based on unfolding, Formal Methods in System Design, v.6 n.1, p.45-65, Jan. 1995 [doi>10.1007/BF01384314]
• 55: Murata, T. 1989. Petri nets: Properties, analysis, and applications. Proc. IEEE 77, 4 (April), 541--580.
• 56: Thomas Martyn Parks, Bounded scheduling of process networks, University of California at Berkeley, Berkeley, CA, 1996
• 57: Petri, C. A. 1962. Kommunikation mit automaten. PhD Thesis, Institutes für Instrumentelle Mathematik, Bonn, Germany. In German.
• 58: Plotkin, G. D. 1981. A structural approach to operational semantics. Tech. Rep. DAIMI FN-19, Aarhus University, Åarhus, Denmark.
• 59: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 60: Sgroi, M., Lavagno, L., and Sangiovanni-Vincentelli, A. 1998. Quasi-static scheduling of free-choice Petri nets. Tech. Rep. UCB/ERL M98/9, University of California, Berkeley.
• 61: Marco Sgroi , Luciano Lavagno , Yosinori Watanabe , Alberto Sangiovanni-Vincentelli, Synthesis of embedded software using free-choice Petri nets, Proceedings of the 36th ACM/IEEE conference on Design automation, p.805-810, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310073]
• 62: Thomas R. Shiple , Gerard Berry , Herve Touati, Constructive Analysis of Cyclic Circuits, Proceedings of the 1996 European conference on Design and Test, p.328, March 11-14, 1996
• 63: Abraham Siberschatz , Peter B. Galvin, Operating System Concepts, 4th Ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 64: Simons, B. and Ferrante, J. 1993. An efficient algorithm for constructing a control flow graph for parallel code. Tech. Rep. TR--03.465, IBM, Santa Teresa Laboratory, San Jose, CA, February.
• 65: Steensgaard, B. 1993. Sequentializing program dependence graphs for irreducible programs. Tech. Rep. MSR-TR-93-14, Microsoft. October.
• 66: Karsten Strehl , Lothar Thiele , Dirk Ziegenbein , Rolf Ernst , Jürgen Teich, Scheduling hardware/software systems using symbolic techniques, Proceedings of the seventh international workshop on Hardware/software codesign, p.173-177, March 1999, Rome, Italy [doi>10.1145/301177.301523]
• 67: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 68: Scott A. Thibault , Renaud Marlet , Charles Consel, Domain-Specific Languages: From Design to Implementation Application to Video Device Drivers Generation, IEEE Transactions on Software Engineering, v.25 n.3, p.363-377, May 1999 [doi>10.1109/32.798325]
• 69: Donald E. Thomas , Philip R. Moorby, The Verilog hardware description language (4th ed.), Kluwer Academic Publishers, Norwell, MA, 1998
• 70: E. G. Ulrich, Programming languages for non-numeric processing—2: Time sequenced logical simulation based on circuit delay and selective tracing of active network paths, Proceedings of the 1965 20th national conference, p.437-448, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806065]
• 71: Ernst G. Ulrich, Exclusive simulation of activity in digital networks, Communications of the ACM, v.12 n.2, p.102-110, Feb. 1969 [doi>10.1145/362848.362870]
• 72: Daniel Weil , Valérie Bertin , Etienne Closse , Michel Poize , Patrick Venier , Jacques Pulou, Efficient compilation of ESTEREL for real-time embedded systems, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.2-8, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354882]
• 73: Compositional Software Synthesis of Communicating Processes, Proceedings of the 1999 IEEE International Conference on Computer Design, p.646, October 10-13, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Code generation; Compilers; Optimization

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

General Terms:
Languages

Keywords:
Compilation, Esterel, Lustre, Petri nets, Verilog, code generation, communication, concurrency, dataflow, discrete-event, partial evaluation, sequential