TinyGALS: a programming model for event-driven embedded systems

ABSTRACT

Networked embedded systems such as wireless sensor networks are usually designed to be event-driven so that they are reactive and power efficient. Programming embedded systems with multiple reactive tasks is difficult due to the complex nature of managing the concurrency of execution threads and consistency of shared states. This paper describes a globally asynchronous and locally synchronous model (TinyGALS) for programming event-driven embedded systems. Software components are composed locally through synchronous method calls to form modules, and asynchronous message passing is used between modules to separate the flow of control. In addition, a guarded yet synchronous model (TinyGUYS) is designed to allow thread-safe sharing of global state by multiple modules without explicitly passing messages. This programming model is structured such that all asynchronous message passing code and module triggering mechanisms can be automatically generted from a high-level specification. We have implemented the programming model and code generation facilities on a wireless sensor network platform known as the Berkeley motes. As an example, we have redesigned a multi-hop ad hoc communication protocol using the TinyGALS model.

REFERENCES

• 1: B. A. Akyol, M. Fredette, A. W. Jackson, R. Krishnan, D. Mankins, C. Partridge, N. Shectman, and G. D. Troxel, "Smart Office Spaces," USENIX Workshop on Embedded Systems, Cambridge, MA, USA, Mar 29--31, 1999.
• 2: Gregory R. Andrews, Concurrent programming: principles and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 3: F. Balarin, M. Chiodo, P. Giusto, H. Hsieh, A. Jurecska, L. Lavagno, A. Sangiovanni-Vincentelli, E. Sentovich, and K. Suzuki, "Synthesis of Software Programs for Embedded Control Applications," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 6, 1999, pp. 834--849.
• 4: Shuvra S. Battacharyya , Edward A. Lee , Praveen K. Murthy, Software Synthesis from Dataflow Graphs, Kluwer Academic Publishers, Norwell, MA, 1996
• 5: Albert Benveniste , Benoît Caillaud , Paul Le Guernic, From Synchrony to Asynchrony, Proceedings of the 10th International Conference on Concurrency Theory, p.162-177, August 24-27, 1999
• 6: 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]
• 7: M. Cornero, F. Thoen, G. Goossens, and F. Curatelli, "Software synthesis for real-time information processing systems," in P. Marwedel and G. Goossens, Eds., Code Generation for Embedded Processors, pp. 260--279. Kluwer Academic Publishers, 1995.
• 8: David E. Culler , Jason Hill , Philip Buonadonna , Robert Szewczyk , Alec Woo, A Network-Centric Approach to Embedded Software for Tiny Devices, Proceedings of the First International Workshop on Embedded Software, p.114-130, October 08-10, 2001
• 9: J. Eker, J. W. Janneck, E. A. Lee, J. Liu, X. Liu, J. Ludvig, S. Neuendorffer, S. Sachs, and Y. Xiong, "Taming Heterogeneity---the Ptolemy Approach," to appear in Proceedings of the IEEE.
• 10: D. Estrin, L. Girod, G. Pottie, and M. Srivastava, "Instrumenting the world with wireless sensor networks," in Proc. of ICASSP'2001, Salt Lake City, UT, May 2001, pp. 2675--2678.
• 11: Jack G. Ganssle, Art of Designing Embedded Systems, Butterworth-Heinemann, Newton, MA, 1999
• 12: P. Le Guernic, T. Gautier, M. Le Borgne, and C. Le Maire. "Programming real-time applications with Signal," Proc. of the IEEE, Vol. 79, No. 9, pp. 1321--1336, 1991.
• 13: Nicolas Halbwachs, Synchronous Programming of Reactive Systems, Kluwer Academic Publishers, Norwell, MA, 1992
• 14: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 15: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 16: Edward A. Lee, What's Ahead for Embedded Software?, Computer, v.33 n.9, p.18-26, September 2000
• 17: Edward A. Lee , Yuhong Xiong, System-Level Types for Component-Based Design, Proceedings of the First International Workshop on Embedded Software, p.237-253, October 08-10, 2001
• 18: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 19: Thomas J. Mowbray , William Ruh, Inside CORBA: distributed object standards and applications, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 20: Jens Muttersbach , Thomas Villiger , Wolfgang Fichtner, Practical Design of Globally-Asynchronous Locally-Synchronous Systems, Proceedings of the 6th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.52, April 02-06, 2000
• 21: Douglas C. Schmidt , Hans Rohnert , Michael Stal , Dieter Schultz, Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, John Wiley & Sons, Inc., New York, NY, 2000
• 22: Abraham Silberschatz , Peter Baer Galvin , Greg Gagne, Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 2001
• 23: David B. Stewart , Richard A. Volpe , Pradeep K. Khosla, Design of Dynamically Reconfigurable Real-Time Software Using Port-Based Objects, IEEE Transactions on Software Engineering, v.23 n.12, p.759-776, December 1997 [doi>10.1109/32.637390]
• 24: Pravin Varaiya, "Smart Cars on Smart Roads: Problems of Control," IEEE Trans. on Automatic Control, AC-38(2), 1993, pp. 195--207.
• 25: L. Wernli, Design and implementation of a code generator for the CAL actor language, Technical Memo UCB/ERL M02/5, University of California, Berkeley, CA 94720, March 2002.
• 26: F. Zhao, J. Shin, and J. Reich, "Information-Driven Dynamic Sensor Collaboration," IEEE Signal Processing Magazine, Vol. 19, No. 2, March 2002, pp. 61--85.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Languages

Keywords:
code generation, embedded systems, globally synchronous and locally asynchronous, programming models, sensor network