Efficient code generation from SHIM models

ABSTRACT

Programming concurrent systems is substantially more difficult than programming sequential systems, yet most embedded systems need concurrency. We believe this should be addressed through higher-level models of concurrency that eliminate many of the usual challenges, such as nondeterminism arising from races.The shim model of computation provides deterministic concurrency, and there already exist ways of implementing it in hardware and software. In this work, we describe how to produce more efficient C code from shim systems.We propose two techniques: a largely mechanical one that produces tail-recursive code for simulating concurrency, and a more clever one that statically analyzes the communication pattern of multiple processes to produce code with far less overhead. Experimentally, we find our tail-recursive technique produces code that runs roughly twice as fast as a baseline; our statically-scheduled code can run up to twelve times faster.

REFERENCES

• 1: Albert Benveniste, Paul Caspi, Stephen A. Edwards, Nicolas Halbwachs, Paul Le Guernic, and Robert de Simone. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1):64--83, January 2003.
• 2: 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]
• 3: Luca Cardelli , Rob Pike, Squeak: a language for communicating with mice, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.199-204, July 1985
• 4: 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]
• 5: Stephen A. Edwards , Olivier Tardieu, SHIM: a deterministic model for heterogeneous embedded systems, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086277]
• 6: Stephen A. Edwards and Olivier Tardieu. SHIM: A deterministic model for heterogeneous embedded systems. IEEE Transactions on Very Large Scale Integrated (VLSI) Systems, 2006. To appear.
• 7: Robert S. French , Monica S. Lam , Jeremy R. Levitt , Kunle Olukotun, A general method for compiling event-driven simulations, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.151-156, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217522]
• 8: Nicholas Halbwachs, Paul Caspi, Pascal Raymond, and Daniel Pilaud. The synchronous data flow programming language LUSTRE. Proceedings of the IEEE, 79(9):1305--1320, September 1991.
• 9: Nicholas Halbwachs, Pascal Raymond, and Christophe Ratel. Generating efficient code from data-flow programs. In Proceedings of the Third International Symposium on Programming Language Implementation and Logic Programming (PLILP), volume 528 of Lecture Notes in Computer Science, Passau, Germany, August 1991. Springer-Verlag.
• 10: Gilles Kahn. The semantics of a simple language for parallel programming. In Information Processing 74: Proceedings of IFIP Congress 74, pages 471--475, Stockholm, Sweden, August 1974. North-Holland.
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Compositional Software Synthesis of Communicating Processes, Proceedings of the 1999 IEEE International Conference on Computer Design, p.646, October 10-13, 1999

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
code synthesis, computed gotos, concurrency, embedded systems, the shim model