Modular code generation from synchronous block diagrams: modularity vs. code size

ABSTRACT

We study modular, automatic code generation from hierarchical block diagrams with synchronous semantics. Such diagrams are the fundamental model behind widespread tools in the embedded software domain, such as Simulink and SCADE. Code is modular in the sense that it is generated for a given composite block independently from context (i.e., without knowing in which diagrams the block is to be used) and using minimal information about the internals of the block. In previous work, we have shown how modular code can be generated by computing a set of interface functions for each block and a set of dependencies between these functions that is exported along with the interface. We have also introduced a quantified notion of modularity in terms of the number of interface functions generated per block, and showed how to minimize this number, which is essential for scalability. Finally, we have exposed the fundamental trade-off between modularity and reusability (set of diagrams the block can be used in).

In this paper we explore another trade-off: modularity vs. code size. We show that our previous technique, although it achieves maximal reusability and is optimal in terms of modularity, may result in code replication and therefore large code sizes, something often unacceptable in an embedded system context. We propose to remedy this by generating code with no replication, and show that this generally results in some loss of modularity. We show that optimizing modularity while maintaining maximal reusability and zero replication is an intractable problem (NP-complete). We also show that this problem can be solved using a simple iterative procedure that checks satisfiability of a sequence of propositional formulas. We report on a new prototype implementation and experimental results. The latter demonstrate the practical interest in our methods.

REFERENCES

• 1: P. Aubry , P. Le Guernic , S. Machard, Synchronous Distribution of SIGNAL Programs, Proceedings of the 29th Hawaii International Conference on System Sciences Volume 1: Software Technology and Architecture, p.656, January 03-06, 1996
• 2: A. Benveniste, P. Caspi, S.A. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The synchronous languages 12 years later. Proc. IEEE, 91(1):64--83, January 2003.
• 3: A. Benveniste, P. Le Guernic, and P. Aubry. Compositionality in dataflow synchronous languages: specification & code generation. Technical Report 3310, Irisa - Inria, 1997.
• 4: 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]
• 5: Dariusz Biernacki , Jean-Louis Colaço , Gregoire Hamon , Marc Pouzet, Clock-directed modular code generation for synchronous data-flow languages, Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems, June 12-13, 2008, Tucson, AZ, USA
• 6: P. Caspi , D. Pilaud , N. Halbwachs , J. A. Plaice, LUSTRE: a declarative language for real-time programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.178-188, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41641]
• 7: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 8: Stephen A. Edwards , Edward A. Lee, The semantics and execution of a synchronous block-diagram language, Science of Computer Programming, v.48 n.1, p.21-42, July 2003
• 9: M. J. Fischer , A. R. Meyer, Boolean matrix multiplication and transitive closure, Proceedings of the 12th Annual Symposium on Switching and Automata Theory (swat 1971), p.129-131, October 13-15, 1971 [doi>10.1109/SWAT.1971.4]
• 10: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 11: M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, 1978.
• 12: Olivier Hainque , Laurent Pautet , Yann Le Biannic , Eric Nassor, Cronos: A Separate Compilation Toolset for Modular Esterel Applications, Proceedings of the Wold Congress on Formal Methods in the Development of Computing Systems-Volume II, p.1836-1853, September 20-24, 1999
• 13: Edward A. Lee , Haiyang Zheng, Leveraging synchronous language principles for heterogeneous modeling and design of embedded systems, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289927.1289949]
• 14: Roberto Lublinerman , Stavros Tripakis, Modular Code Generation from Triggered and Timed Block Diagrams, Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, p.147-158, April 22-24, 2008 [doi>10.1109/RTAS.2008.12]
• 15: Roberto Lublinerman , Stavros Tripakis, Modularity vs. reusability: code generation from synchronous block diagrams, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403736]
• 16: Oliver Maffeïs , Paul Le Guernic, Distributed Implementation of SIGNAL: Scheduling & Graph Clustering, Proceedings of the Third International Symposium Organized Jointly with the Working Group Provably Correct Systems on Formal Techniques in Real-Time and Fault-Tolerant Systems, p.547-566, September 19-23, 1994
• 17: S. Malik. Analysis of cyclic combinational circuits. IEEE Trans. Computer-Aided Design, 13(7):950--956, 1994.
• 18: P. Mosterman and J. Ciolfi. Interleaved execution to resolve cyclic dependencies in time-based block diagrams. In 43rd IEEE Conf. on Decision and Control (CDC04), 2004.
• 19: P. Raymond. Compilation separee de programmes Lustre. Master's thesis, IMAG, 1988. In French.
• 20: Thomas R. Shiple , Gerard Berry , Herve Touati, Constructive Analysis of Cyclic Circuits, Proceedings of the 1996 European conference on Design and Test, p.328, March 11-14, 1996
• 21: R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1:146--160, 1972.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

General Terms:
Algorithms, Design, Languages

Keywords:
block diagrams, clustering, code generation, embedded software, np-complete, synchronous languages