Generating fast code from concurrent program dependence graphs

ABSTRACT

While concurrency in embedded systems is most often supplied by real-time operating systems, this approach can be unpredictable and difficult to debug. Synchronous concurrency, in which a system marches in lockstep to a global clock, is conceptually easier and potentially more efficient because it can be statically scheduled beforehand.We present an algorithm for generating efficient sequential code from such synchronous concurrent specifications. Starting from a concurrent program dependence graph generated from the synchronous, concurrent language Esterel, we generate efficient, statically scheduled sequential code while adding a minimal amount of runtime scheduling overhead.Experimentally, we obtain speedups as high as six times over existing techniques. While we applied our technique to Esterel, it should be applicable to other synchronous, concurrent languages.

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: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 4: Stephen A. Edwards. An Esterel compiler for large control-dominated systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21(2):169--183, February 2002.
• 5: 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]
• 6: Stephen A. Edwards, Vimal Kapadia, and Michael Halas. Compiling Esterel into static discrete-event code. In Proceedings of Synchronous Languages, Applications, and Programming (SLAP), Barcelona, Spain, March 2004.
• 7: J. Ferrante , M. Mace , B. Simons, Generating sequential code from parallel code, Proceedings of the 2nd international conference on Supercomputing, p.582-592, June 1988, St. Malo, France [doi>10.1145/55364.55421]
• 8: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 9: Barbara Simons and Jeanne Ferrante. An efficient algorithm for constructing a control flow graph for parallel code. Technical Report TR--03.465, IBM, Santa Teresa Laboratory, San Jose, California, February 1993.
• 10: Bjarne Steensgaard. Sequentializing program dependence graphs for irreducible programs. Technical Report MSR-TR-93-14, Microsoft, October 1993.

INDEX TERMS

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

General Terms:
Languages

Keywords:
concurrent, esterel, program dependence graph, sequencial