Modular Code Generation from Synchronous Block Diagrams Modularity vs. Code Size

摘要

We study modular, automatic code generation from hierarchicalblock diagrams with synchronous semantics. Such diagrams are thefundamental model behind widespread tools in the embedded soft-ware domain, such as Simulink and SCADE. Code is modular inthe sense that it is generated for a given composite block indepen-dently from context (i.e., without knowing in which diagrams theblock is to be used) and using minimal information about the inter-nals of the block. In previous work, we have shown how modularcode can be generated by computing a set of interface functionsfor each block and a set of dependencies between these functionsthat is exported along with the interface. We have also introduced aquantified notion of modularity in terms of the number of interfacefunctions generated per block, and showed how to minimize thisnumber, which is essential for scalability. Finally, we have exposedthe fundamental trade-off between modularity and reusability (setof diagrams the block can be used in). In this paper we explore another trade-off: modularity vs. codesize. We show that our previous technique, although it achievesmaximal reusability and is optimal in terms of modularity, may re-sult in code replication and therefore large code sizes, somethingoften unacceptable in an embedded system context. We propose toremedy this by generating code with no replication, and show thatthis generally results in some loss of modularity. We show that opti-mizing modularity while maintaining maximal reusability and zeroreplication is an intractable problem (NP-complete). We also showthat this problem can be solved using a simple iterative procedurethat checks satisfiability of a sequence of propositional formulas.We report on a new prototype implementation and experimental re-sults. The latter demonstrate the practical interest in our methods.