Transformational Embedded System Design

Abstract

Designing embedded systems has become increasingly challenging with the widespread adoption of heterogeneous multi-processor platforms. Raising the level of abstraction helps manage this complexity by allowing designers to focus on system behavior through formal, high-level specifications. However, this also widens the gap between abstract models and concrete implementations. In particular, capturing parallel behavior at a high level and refining it into fully orchestrated implementations that effectively exploit the parallelism inherent to multi-processor platforms remains a significant challenge. This thesis proposes a transformational design methodology that addresses the abstraction gap by providing a structured means of refining high-levelsystem models into implementation-ready representations through rule-based transformations. The methodology is structured around the RAMP view, which represents the system in terms of its requirements, application, mapping, and platform models. This representation offers a coherent foundation for reasoning about design refinements, making explicit how transformations affect different aspects of the system. System behavior is expressed using a library of process constructors and algorithmic skeletons, implemented as higher-order functions (HoFs), that define temporal semantics and recurring computation structures. This modeling style yields hierarchical concurrent process networks whose structure and parallel behavior can be analyzed and refined. Moreover, the algebraic properties of the underlying HoFs enable the derivation of transformation rules directly from known functional identities. To support automation of these refinements, the thesis represents the resulting process networks as attributed graphs that serve as a unified intermediate representation (IR) across all RAMP views. In this representation,traits attached to graph nodes and edges specify semantic roles, structural interfaces, and performance-related properties of the modeled elements. The resulting trait-annotated system graph provides the structural and semantic information required for automatic transformation. On top of this representation, the thesis develops a prototype transformation exploration tool that automates the identification, evaluation, and application of rule-based refinements. Transformation opportunities are detected through subgraph matching on the IR, and their impact is estimated using analytical performance models that approximate computation and com-munication costs. Selected transformations are then applied through graphrewriting operations designed to maintain structural consistency and adhereto the modeling conventions captured in the trait system. Together, these ca-pabilities establish an automated and systematic process for generating andassessing alternative application structures. The framework is evaluated through case studies that illustrate its ability to generate alternative application instances and meaningful design points. The results also show that the analytical models can predict performance trends and reduce the number of candidates requiring full system-level evaluation, lowering overall design space exploration (DSE) effort.

Link to DiVA