Task generation and compile-time scheduling for mixed data-control embedded software

ABSTRACT

The problem of optimal software synthesis for concurrent processes to be implemented on a single processor is addressed. The approach calls for the representation of the concurrent processes with Petri nets that give a theoretical foundation for the scheduling algorithm that sequentializes the concurrent processes and for the code generation step. The approach maximizes the amount of static scheduling to reduce the need of context switch and operating system intervention. Experimental results show the potential of our method to reduce software design time and errors.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: S. Amellal and B. Kaminsl~. Functional synthesis of digital systems with TASS. IEEE Trans. CAD, 13(5), 1994.
• 3: Shuvra S. Battacharyya , Edward A. Lee , Praveen K. Murthy, Software Synthesis from Dataflow Graphs, Kluwer Academic Publishers, Norwell, MA, 1996
• 4: Joseph Tobin Buck , Edward A. Lee, Scheduling dynamic dataflow graphs with bounded memory using the token flow model, 1993
• 5: Hassan Gomaa, Software Design Methods for Concurrent and Real-Time Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 6: G. Lakshminarayana, K. Khouri, and N. Jha. Wavehead" A novel scheduling technique for control-flow intensive designs. IEEE Trans. CAD, 18(5), 1999.
• 7: Bill Lin, Software synthesis of process-based concurrent programs, Proceedings of the 35th annual conference on Design automation, p.502-505, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277182]
• 8: T. Murata. Petri nets" properties, analysis, and applications. Proceedings of the IEEE, 74(4), April 1989.
• 9: 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]
• 10: 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]
• 11: the same authors. Task generation and compile-time scheduling for mixed data-control embedded software. Technical Report LSI-99-47- R, Dept. of Software, Universitat Polit~cnica de Catalunya, 1999.
• 12: 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]

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Petri nets
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Compilers
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

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