Synthesis of time-constrained multitasking embedded software

ABSTRACT

In modern embedded systems, software development plays a vital role. Many key functions are being migrated to software, aiming at a shorter time to market and easier upgrades. Multitasking is increasingly common in embedded software, and many of these tasks incorporate real-time constraints. Although multitasking simplifies coding, it demands an operating system and imposes significant overhead on the system. The use of serializing compilers, such as the Phantom compiler, allows the synthesis of a monolithic code from a multitasking C application, eliminating the need for an operating system. In this article, we introduce the synthesis of multitasking applications that execute in a timely manner. We incorporate the notion of timing constraints into the Phantom compiler, and show that our approach is effective in meeting such constraints, allowing fine-grained concurrency among the tasks. As an additional case study, we present the implementation of a software-based modem and show that real-time applications such as the modem have guaranteed performance in the serialized code generated by the Phantom compiler.

REFERENCES

• 1: John Aycock, A brief history of just-in-time, ACM Computing Surveys (CSUR), v.35 n.2, p.97-113, June 2003 [doi>10.1145/857076.857077]
• 2: Balarin, F., Chiodo, M., Giusto, P., Hsieh, H., Jurecska, A., Lavagno, L., Sangiovanni-Vincentelli, A., Sentovich, E., and Suzuki, K. 1999. Synthesis of software programs for embedded control applications. IEEE Trans. Comput. Aid. Des. Integrat. Circ. Sys. 18, 6 (June), 834--849.
• 3: 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]
• 4: Monica Besana , Michele Borgatti, Application Mapping to a Hardware Platform through Automated Code Generation Targeting a RTOS: A Design Case Study, Proceedings of the conference on Design, Automation and Test in Europe: Designers' Forum, p.20041, March 03-07, 2003
• 5: BusyBox. 2005. Go online to http://www.busybox.net.
• 6: Jordi Cortadella , Alex Kondratyev , Luciano Lavagno , Claudio Passerone , Yosinori Watanabe, Quasi-Static Scheduling of Independent Tasksfor Reactive Systems, Proceedings of the 23rd International Conference on Applications and Theory of Petri Nets, p.80-100, June 24-30, 2002
• 7: 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]
• 8: Cortés, L. A., Eles, P., and Peng, Z. 2004. Quasi-static scheduling for real-time systems with hard and soft tasks. In Proceedings of DATE. 1176--1181.
• 9: Luis Alejandro Cortes , Petru Eles , Zebo Peng, Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), p.422-428, August 17-19, 2005 [doi>10.1109/RTCSA.2005.72]
• 10: Alexander G. Dean, Efficient Real-Time Fine-Grained Concurrency on Low-Cost Microcontrollers, IEEE Micro, v.24 n.4, p.10-22, July 2004 [doi>10.1109/MM.2004.27]
• 11: Stephen A. Edwards, Compiling Esterel into sequential code, Proceedings of the seventh international workshop on Hardware/software codesign, p.147-151, March 1999, Rome, Italy [doi>10.1145/301177.301514]
• 12: Edwards, S. 2002. An esterel compiler for large control-dominated systems. IEEE Trans. Comput.-Aid. Des. Integrat. Circ. Syst. 21, 2 (Feb.), 169--183.
• 13: Stephen A. Edwards, Tutorial: Compiling concurrent languages for sequential processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.141-187, April 2003 [doi>10.1145/762488.762489]
• 14: Andreas Ermedahl , Friedhelm Stappert , Jakob Engblom, Clustered Worst-Case Execution-Time Calculation, IEEE Transactions on Computers, v.54 n.9, p.1104-1122, September 2005 [doi>10.1109/TC.2005.139]
• 15: Fisher, J., Faraboschi, P., and Young, C. 2002. Embedded Computing: A VLIW Approach to Architecture, Compilers, and Tools. Morgan Kauffman, San Francisco, CA.
• 16: Gauthier, L., Yoo, S., and Jerraya, A. 2001. Automatic generation and targeting of application-specific operating systems and embedded systems software. IEEE Trans. Comput.-Aid. Des. Integrat. Circ. Syst. 20, 11 (Nov.), 1293--1301.
• 17: Andreas Gerstlauer , Haobo Yu , Daniel D. Gajski, RTOS Modeling for System Level Design, Proceedings of the conference on Design, Automation and Test in Europe, p.10130, March 03-07, 2003
• 18: Ashvin Goel , Luca Abeni , Charles Krasic , Jim Snow , Jonathan Walpole, Supporting time-sensitive applications on a commodity OS, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060305]
• 19: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 20: F. Herrera , H. Posadas , P. Sanchez , E. Villar, Systemic Embedded Software Generation from SystemC, Proceedings of the conference on Design, Automation and Test in Europe, p.10142, March 03-07, 2003
• 21: Pao-Ann Hsiung , Trong-Yen Lee , Feng-Shi Su, Formal Synthesis and Code Generation of Real-Time Embedded Software using Time-Extended Quasi-Static Scheduling, Proceedings of the Ninth Asia-Pacific Software Engineering Conference, p.395, December 04-06, 2002
• 22: Intel Corp. 1997. Using the RDTSC instruction for performance monitoring. Intel Application Notes. Intel, Santa Clara, CA.
• 23: Ireneusz Karkowski , Henk Corporaal, Exploiting Fine- and Coarse-grain Parallelism in Embedded Programs, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.60, October 12-18, 1998
• 24: Raimund Kirner , Peter Puschner, Classification of WCET Analysis Techniques, Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'05), p.190-199, May 18-20, 2005 [doi>10.1109/ISORC.2005.19]
• 25: MicroC/OS-II: the real-time kernel, CMP Media, Inc., 2002
• 26: 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
• 27: Measurement Computing, Inc. 2005. PCI-DAS4020/12 Specifications, Rev 1.2. Available online at http://www.mccdaq.com.
• 28: Microsoft Corporation. 2003. The C# 2.0 Specification. Available online at http://msdn.microsoft.com/vcsharp.
• 29: R. Le Moigne , O. Pasquier , J-P. Calvez, A Generic RTOS Model for Real-time Systems Simulation with SystemC, Proceedings of the conference on Design, automation and test in Europe, p.30082, February 16-20, 2004
• 30: José E. Moreira , Dale Schouten , Constantine D. Polychronopoulos, The Performance Impact of Granularity Control and Functional Parallelism, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.581-597, August 10-12, 1995
• 31: A. C. Nacul , T. Givargis, Code partitioning for synthesis of embedded applications with phantom, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.190-196, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382569]
• 32: Andre C. Nacul , Tony Givargis, Lightweight Multitasking Support for Embedded Systems using the Phantom Serializing Compiler, Proceedings of the conference on Design, Automation and Test in Europe, p.742-747, March 07-11, 2005 [doi>10.1109/DATE.2005.197]
• 33: Nacul, A. and Givargis, T. 2005b. Phantom compiler 0.8. Go online to http://www.ics.uci.edu/~nacul/phantom.
• 34: RedHat Inc. 2005. Embedded configurable operating system (ecos). Go online to sources. redhat.com/ecos.
• 35: Wolfgang Reisig , Peter Schnupp , S. S. Muchnick, Primer in Petri Net Design, Springer-Verlag New York, Inc., Secaucus, NJ, 1992
• 36: Dale Allan Schouten, Efficient scheduling of parallel tasks in a multiprogramming environment, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
• 37: The Open SystemC Initiative. 2005. Go online to www.systemc.org.
• 38: Henrik Theiling , Christian Ferdinand , Reinhard Wilhelm, Fast and Precise WCET Prediction by Separated Cache andPath Analyses, Real-Time Systems, v.18 n.2-3, p.157-179, May 2000 [doi>10.1023/A:1008141130870]
• 39: Steven Vercauteren , Bill Lin , Hugo De Man, A strategy for real-time kernel support in application-specific HW/SW embedded architectures, Proceedings of the 33rd annual conference on Design automation, p.678-683, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240646]
• 40: Vincent Colin de Verdière , Sébastien Cros , Christian Fabre , Romain Guider , Sergio Yovine, Speedup Prediction for Selective Compilation of Embedded Java Programs, Proceedings of the Second International Conference on Embedded Software, p.227-239, October 07-09, 2002

INDEX TERMS

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

General Terms:
Design

Keywords:
Code serialization, multitasking, real-time embedded software, software synthesis