Remote specialization for efficient embedded operating systems

ABSTRACT

Prior to their deployment on an embedded system, operating systems are commonly tailored to reduce code size and improve runtime performance. Program specialization is a promising match for this process: it is predictable and modules, and it allows the reuse of previously implemented specializations. A specialization engine for embedded systems must overcome three main obstacles: (i) Reusing existing compilers for embedded systems, (ii) supporting specialization on a resource-limited system and (iii) coping with dynamic applications by supporting specialization on demand.

In this article, we describe a runtime specialization infrastructure that addresses these problems. Our solution proposes: (i) Specialization in two phases of which the former generates specialized C templates and the latter uses a dedicated compiler to generate efficient native code. (ii) A virtualization mechanism that facilitates specialization of code at a remote location. (iii) An API and supporting OS extensions that allow applications to produce, manage and dispose of specialized code.

We evaluate our work through two case studies: (i) The TCP/IP implementation of Linux and (ii) The TUX embedded web server. We report appreciable improvements in code size and performance. We also quantify the overhead of specialization and argue that a specialization server can scale to support a sizable workload.

REFERENCES

• 1: Stephen Adams , Thomas Ball , Manuvir Das , Sorin Lerner , Sriram K. Rajamani , Mark Seigle , Westley Weimer, Speeding Up Dataflow Analysis Using Flow-Insensitive Pointer Analysis, Proceedings of the 9th International Symposium on Static Analysis, p.230-246, September 17-20, 2002
• 2: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 3: Sapan Bhatia , Charles Consel , Anne-Francoise Le Meur , Calton Pu, Automatic Specialization of Protocol Stacks, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, p.152-159, November 16-18, 2004 [doi>10.1109/LCN.2004.28]
• 4: Sapan Bhatia , Charles Consel , Calton Pu, Remote customization of systems code for embedded devices, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017760]
• 5: Jeff Bonwick, The slab allocator: an object-caching kernel memory allocator, Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, p.6-6, June 06-10, 1994, Boston, Massachusetts
• 6: Charles Consel , Julia L. Lawall , Anne-Françoise Le Meur, A tour of tempo: a program specializer for the C language, Science of Computer Programming, v.52 n.1-3, p.341-370, August 2004 [doi>10.1016/j.scico.2004.03.011]
• 7: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 8: G. Denys , F. Piessens , F. Matthijs, A survey of customizability in operating systems research, ACM Computing Surveys (CSUR), v.34 n.4, p.450-468, December 2002 [doi>10.1145/592642.592644]
• 9: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 10: Evans Data Corporation. 2003. Embedded systems development survey.
• 11: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.38-51, October 05-08, 1997, Saint Malo, France
• 12: Hewlett-Packard. 1996. Netperf: A network performance benchmark.
• 13: Luke Hornof , Jacques Noyé, Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity, Theoretical Computer Science, v.248 n.1-2, p.3-27, October 2000 [doi>10.1016/S0304-3975(00)00048-7]
• 14: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 15: Julia L. Lawall , Gilles Muller , Luciano Porto Barreto, Capturing OS expertise in an event type system: the Bossa experience, Proceedings of the 10th workshop on ACM SIGOPS European workshop, July 01-01, 2002, Saint-Emilion, France [doi>10.1145/1133373.1133384]
• 16: Anne-Françoise Le Meur , Julia L. Lawall , Charles Consel, Specialization Scenarios: A Pragmatic Approach to Declaring Program Specialization, Higher-Order and Symbolic Computation, v.17 n.1-2, p.47-92, March-June 2004 [doi>10.1023/B:LISP.0000029448.02877.78]
• 17: Lee, H. B., Diwan, A., and Moss, J. E. B. 2004. Design, implementation, and evaluation of a compilation server. Technical rep. CU-CS-978-04, University of California at Boulder.
• 18: Linux Devices Magazine. 2003. Wind river's bruggeman defines Device Software Optimization (DSO).
• 19: Linux Devices Magazine. 2003. New linksys wireless ap runs 3rd-party embedded linux. http://www.linuxdevices.com/news/NS3238024255.html.
• 20: LXR. The LXR source-code cross-referencing system for Linux. URL: http://lxr.linux.no/.
• 21: M. Mathis , J. Mahdavi , S. Floyd , A. Romanow, TCP Selective Acknowledgement Options, RFC Editor, 1996
• 22: Dylan McNamee , Jonathan Walpole , Calton Pu , Crispin Cowan , Charles Krasic , Ashvin Goel , Perry Wagle , Charles Consel , Gilles Muller , Renauld Marlet, Specialization tools and techniques for systematic optimization of system software, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.217-251, May 2001 [doi>10.1145/377769.377778]
• 23: G. Muller , R. Marlet , E.-N. Volanschi , C. Consel , C. Pu , A. Goel, Fast, Optimized Sun RPC Using Automatic Program Specialization, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.240, May 26-29, 1998
• 24: J. Nagle, Congestion control in IP/TCP internetworks, RFC Editor, 1984
• 25: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 26: Owens, K. 2006. kbuild. URL: http://kbuild.sourceforge.net/.
• 27: PicoFreeBSD. Pico freebsd. URL: http://people.freebsd.org/picobsd/.
• 28: C. Pu , T. Autrey , A. Black , C. Consel , C. Cowan , J. Inouye , L. Kethana , J. Walpole , K. Zhang, Optimistic incremental specialization: streamlining a commercial operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.314-321, December 03-06, 1995, Copper Mountain, Colorado, United States
• 29: Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
• 30: TinyLinux. Tinylinux. URL: http://tiny.seul.org/en/.
• 31: Alistair C. Veitch , Norman C. Hutchinson, Kea - A Dynamically Extensible and Configurable Operating System Kernel, Proceedings of the 3rd International Conference on Configurable Distributed Systems, p.236, May 06-08, 1996
• 32: Michael J. Voss , Rudolf Eigenmann, A framework for remote dynamic program optimization, Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization, p.32-40, January 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design

General Terms:
Design, Experimentation, Performance

Keywords:
Remote specialization, compilers, performance analysis, specialization server