Software synthesis of process-based concurrent programs

ABSTRACT

We present a Petri net theoretic approach to the software synthesis problem that can synthesize ordinary C programs from process-based concurrent specifications without the need for a run-time multi-threading environment. The synthesized C programs can be readily retargeted to different processors using available optimizing C compilers. Our compiler can also generate sequential Java programs as output, which can also be readily mapped to a target processor without the need for a multi-threading environment. Initial results demonstrate significant potentials for improvements over current run-time solutions.

REFERENCES

• 1: G. Berry et al. "The synchronous approach to reactive and real-time systems'', IEEE Proceedings, 1991.
• 2: J. T. Buck et al. "Ptolemy: A framework for simulating and prototyping heterogeneous systems", International Journal on Computer Simulation, January 1994.
• 3: R. Camposano and W. Wolf (editors), Trend,' in High-Level Synthesis, Kluwer Academic Publishers, 1993.
• 4: Gjalt G. de Jong , Bill Lin, A communicating Petri net model for the design of concurrent asynchronous modules, Proceedings of the 31st annual conference on Design automation, p.49-55, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196272]
• 5: H. De Man, F. Catthoor, G. Goossens, J. Vanhoof, J. Van Meerbergen, S. Note, J.A. Huisken, "Architecture-driven synthesis techniques for VLSI implementation of DSP algorithms", Proceedings t~' IEEE, vol.72, no.2, pp.319-335, February 1990.
• 6: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 7: R. K. Gupta. "Hardware-software cosynthesis of microcontrollers", Proc. Code,t/CASHE, 1996.
• 8: M. Hack. Analysis (~'production schemata by Petri net,'. M.S. Thesis, MIT, February 1972.
• 9: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 10: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 11: 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
• 12: B. Morgan. l//sua/J++ Unleashed. Sams. Net, 1996.
• 13: J. Morse, S. Hargrave. 'The increasing importance of software". Electronic Design, vol. 44, no. 1, Jan. 1996.
• 14: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 15: Todd A. Proebsting , Gregg Townsend , Patrick Bridges , John H. Hartman , Tim Newsham , Scott A. Watterson, Toba: Java For Applications: A Way Ahead of Time (WAT) Compiler, University of Arizona, Tucson, AZ, 1997
• 16: R.L. Rivest. 'TheRC5 Encryption Algorithm", Proceedings of the 1994 Leuven Work,~hop on Algorithms, Springer-Verslag,1994.
• 17: R. M. Stallman, Using andporting GNU CC, FreeSoftwareFoundation, June 1993.
• 18: Filip Thoen , Marco Cornero , Gert Goossens , Hugo De Man, Real-time multi-tasking in software synthesis for information processing systems, Proceedings of the 8th international symposium on System synthesis, p.48-53, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224496]
• 19: Steven Vercauteren , Diederik Verkest , Gjalt de Jong , Bill Lin, Derivation of formal representations from process-based specification and implementation models, Proceedings of the 10th international symposium on System synthesis, p.16-23, September 17-19, 1997, Antwerp, Belgium

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Petri nets
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C
      D.3.4 Processors
          Subjects: Compilers

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Design, Languages, Measurement, Performance, Theory

Keywords:
MPEG4, codec, design automatian, flip-flops, level converters, low power, placement, synthesis, voltage scaling