Transformational Embedded System Design

Abstract

Designing embedded systems has become increasingly challenging with thewidespread adoption of heterogeneous multi-processor platforms. Raising thelevel of abstraction helps manage this complexity by allowing designers tofocus on system behavior through formal, high-level specifications. However,this also widens the gap between abstract models and concrete implementa-tions. In particular, capturing parallel behavior at a high level and refining itinto fully orchestrated implementations that effectively exploit the parallelisminherent to multi-processor platforms remains a significant challenge. This thesis proposes a transformational design methodology that addressesthe abstraction gap by providing a structured means of refining high-levelsystem models into implementation-ready representations through rule-basedtransformations. The methodology is structured around the RAMP view,which represents the system in terms of its requirements, application, map-ping, 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 andalgorithmic skeletons, implemented as higher-order functions (HoFs), that de-fine temporal semantics and recurring computation structures. This modelingstyle yields hierarchical concurrent process networks whose structure and par-allel behavior can be analyzed and refined. Moreover, the algebraic propertiesof the underlying HoFs enable the derivation of transformation rules directlyfrom known functional identities. To support automation of these refinements, the thesis represents theresulting process networks as attributed graphs that serve as a unified inter-mediate representation (IR) across all RAMP views. In this representation,traits attached to graph nodes and edges specify semantic roles, structuralinterfaces, and performance-related properties of the modeled elements. Theresulting trait-annotated system graph provides the structural and semanticinformation required for automatic transformation. On top of this representation, the thesis develops a prototype transfor-mation exploration tool that automates the identification, evaluation, andapplication of rule-based refinements. Transformation opportunities are de-tected through subgraph matching on the IR, and their impact is estimatedusing 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 abilityto generate alternative application instances and meaningful design points. The results also show that the analytical models can predict performancetrends and reduce the number of candidates requiring full system-level eval-uation, lowering overall design space exploration (DSE) effort.

Link to DiVA