Je Remercie

M Reinhard

Von Hanxleden

M Saddek

M Robert

Mme D E Simone

Sophie Dupuy-Chessa

M Lionel Lacassagne

LENORMAND M Eric

Qui M'ont

Jérome Martin

Diego Puschini

Julien Mottin

Thierno Barry

Fayc ¸al BENAZIZ Suzanne Lesecq

Henri-Pierre Charles

Vincent Olive

Anca Molnos

Frédéric Heitzmann

Maxime Louvel

Yeter Akgul

Lionel Vincent

Olivier Debicki

Nhat Minh L Ê

Adrian Guatto

Marie Pierre

Ivan Llopard

Programming Embedded Manycore: Refinement and Optimizing Compilation of a Parallel Action Language for Hierarchical State Machines

Programmation de systèmes embarqués many-core : Raffinement et compilation optimisante d'un langage d'action parallèle pour machines à états hiérarchiques par Ivan LLOPARD Afin de gérer la complexité des systèmes embarqués modernes, les langages de modélisation proposent des abstractions et des transformations adaptées au domaine. Basées sur le formalisme de machines à états hiérarchiques, connu sous le nom de Statecharts, ils permettent la modélisation du contrôle parallèle hiérarchique. Cependant, ils doivent faire à deux défis majeures quant il s'agit de la modélisation des applications à calcul intensif: le besoin des méthodes unifiées supportant des actions avec parallélisme de donnée; flots d'optimisation et génération de code à partir des modèles trop généralistes. Dans cette thèse, nous proposons un langage de modélisation étendu avec une sémantique d'actions parallèles et machines à états hiérarchiques indexées, spécialement adapté pour les applications à calcul intensif. Avec sa sémantique formelle, nous présentons un flot de compilation optimisante pour le raffinement des modèles en vue d'une génération du code efficace avec parallèlisme de donnée.

We present the context for this work, our main motivations and goals, and we conclude by giving a brief overview of the thesis organization.

Context

Modern embedded systems integrate more sophisticated functionalities to meet hard performance requirements of today's applications. This integration power enabled the implementation of complete systems into a single chip, namely System on Chip (SoC). The step forward included many core architectures providing massively parallel computation units. The inherent parallelism of these architectures makes them suitable for applications showing, preferable in the most direct manner, parallel components. In particular, data-parallelism is essential to scalable and efficient parallel programming [START_REF] Fraguela | The Hierarchically Tiled Arrays Programming Approach[END_REF][START_REF] Fatahalian | Sequoia: Programming the Memory Hierarchy[END_REF][START_REF] Mueller | Hidp: A Hierarchical Data Parallel Language[END_REF][START_REF] Manuel | Data Parallel Haskell: a Status Report[END_REF]. Although, industrial programming practices use low-level languages to keep a precise control over the platform [START_REF] Stone | OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems[END_REF][START_REF] Sanders | CUDA by Example: An Introduction to General-Purpose GPU Programming[END_REF], and thus application developers need a deep knowledge of hardware features. On the other hand, adaptations of general purpose languages to address parallel issues cannot cope with the great number of platform-dependent tuning parameters at once. Therefore, code generation from such languages tends to be a challenging work. Both worlds need to be taken into account incrementally to get best performances. As a result, the design and development of embedded systems is becoming increasingly complex [START_REF] Sangiovanni-Vincentelli | Quo Vadis, SLD? Reasoning About the Trends and Challenges of System Level Design[END_REF]. To cope with the complexity, designers rely on multiple design methodologies and its supporting tools [START_REF] Henzinger | The Discipline of Embedded Systems Design[END_REF]. Recent trends push for unified model-based approaches that allow the modeling of both software and hardware [START_REF] Henzinger | The Embedded Systems Design Challenge[END_REF][START_REF] Riccobene | A Model-Driven Design Environment for Embedded Systems[END_REF][START_REF] Shih | A Model-Driven Multicore Software Development Environment for Embedded System[END_REF][START_REF] Wendell | Programming Massively Parallel Architectures using MARTE: a Case Study[END_REF][START_REF] Hili | Model-Based Platform Composition for Embedded System Design[END_REF]. The role of model-based techniques is to provide strong abstractions to handle in a modular manner a wide variety of system configurations.

The abstraction are iteratively refined in order to get closer to the final implementation taking into account different platform constraints step by step. Figure 1.1 shows the Highly Heterogeneous, Object-Oriented, Efficient Engineering HOE 2 methodology, which is thoroughly covered in [START_REF] Hili | Une méthode pour le développement collaboratif de systèmes embarqués[END_REF]. HOE 2 and other similar frameworks specify the system behavior using Statecharts, or Hierarchical State Machines (HSMs).

Statecharts were first introduced by Harel for the specification and design of complex discreteevent systems [START_REF] Harel | Statecharts: a Visual Formalism for Complex Systems[END_REF]. It is a graphical language providing natural and easy-to-grasp abstractions to express parallelism, hierarchy and compositions of state machines. Figure 1.2 shows the Statechart model of a car audio system. Modern modeling languages such as Unified Modeling Language (UML) incorporate Statecharts as their main formalism to model object behavior, extending them with object-oriented traits [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF].

Motivation

The motivation of this thesis is split on three complementary subjects: modeling of parallel computations, semantics of Statecharts and its exisiting compilation challenges.

Data Parallelism and Statecharts. If Statecharts are well-suited for the modeling of control decisions of cooperative components of a system, data-driven computations are hardly expressable in the formalism. Though modern embedded systems provides more and more parallelism at different granularity levels (data, thread, system), frequently presented in a hierarchical manner. On the other hand, hierarchy is one of the main properties of model-driven approaches to provide highly modular representations in addition to rigorous methodologies. A similar issue has been pointed out by Gamatié et al. where model-driven techniques are combined with a domain specific language to address the problem [8].

Semantics of Statecharts. The widely used modeling languages in the Model-Driven Engineering (MDE) community is UML [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF]. UML is mainly focused on modeling issues and, in favor of generality, let many semantical points of Statecharts open to specific implementations.

As a consequence, many research works propose formalizations of its rather imprecise informal semantics [START_REF] Seifert | An Executable Formal Semantics for a UML State Machine Kernel Considering Complex Structured Data[END_REF][START_REF] Liu | A Formal Semantics for Complete UML State Machines with Communications[END_REF][START_REF] Börger | On formalizing UML state machines using ASMs[END_REF][START_REF] Michael Von Der Beeck | A Structured Operational Semantics for UML-Statecharts[END_REF][START_REF] Ivan P Paltor | The Semantics of UML State Machines[END_REF]. Indeed, the complete formalization of UML Statecharts is a challenging work given the great number of proposed features and the already known non-constructive properties of Statecharts [START_REF] Michael Von Der Beeck | A Comparison of Statecharts Variants[END_REF]. A Statechart-based language should provide a well-founded semantics trying to avoid previous semantical complications in order to achieve a clear, scalable and customizable semantic implementation.

Compilation of Statecharts. The purpose of models is simulation or as a path to rapid implementations of software architectures. Even though Model-Driven Architecture (MDA) approaches push the idea of an iterative integration of hardware constraints into the initial parallel application (or model because of the unified view), the model is not subject to any kind of optimization and the code generation process is known for its faithfulness with respect to the input model. Recent research efforts focus on an executable and performance-aware compilation flow from models. The goal is to apply compilation techniques at the model level itself, by considering intermediate representations if necessary, in order to achieve high-performance and platform-specific implementations [START_REF] Reinhard Von Hanxleden | SCCharts: Sequentially Constructive Statecharts for Safety-critical Applications: HW/SW-synthesis for a Conservative Extension of Synchronous Statecharts[END_REF][START_REF] Schattkowsky | Transformation of UML State Machines for Direct Execution[END_REF][START_REF] Charfi | An Optimized Compilation of UML State Machines[END_REF][START_REF] Alras | Model-Based Design of Embedded Control Systems by Means of a Synchronous Intermediate Model[END_REF].

Objectives and Contributions

In this thesis, I propose an adapation of the already known Statechart formalism to the modeling of parallel computations. We propose a parallel action language and several key extensions to the formalism, which are compliant with plain objects.

Together with a new language, we introduce its semantics in a hierarchical manner. Compared to existing approaches, it allow us to some extent to separate semantical points in multiple layers while following the language structure in an operational way.

In order to produce efficient code from Statecharts, we introduce a new intermediate representation, which is more expressive than existing representations for Statecharts. We include object creation, struct-like variable accesses and indexing of associations while preserving most of the information coming from the front-end language. It allow us to reason about communication issues, inlining and unreachable states, among many other factors of performance.

Finally, we contribute a new compilation flow for HSMs closely following the data-parallel extensions of the input language, which are preserved at the intermediate representation. As mentioned earlier, the intermediate representation allow us to reason about particular semantical implications concerning communication, inlining, data dependences, loops and parallelization issues.

Thesis Organization

The thesis organization is as follows.

Chapter 2, 3, 4: State-of-the-art. We separate the state-of-the-art into three related chapters.

Concerning our main motivation, we look in Chapter 2 for inspiration into existing parallel languages. Going from very high-level languages to low-level ones, we show how the parallelism is presented to the programmer. Given that our approach is based on Statecharts, we review in Chapter 3 semantics of Statecharts to define the foundations of the language presented in this thesis. Naturally, we continue in Chapter 4 with the survey of related research work on efficient compilation of Statecharts.

Chapter 5: The HOE 2 Language. Our proposed extension to Statecharts. It is a complete language called HOE 2 , as our proposition fits into a more wide context of a model-driven methodology also named HOE 2 .

Chapter 6: The HOE 2 Language Semantics. We present a hierarchical approach for the formalization of our Statechart-based language.

Chapter 7: An Intermediate Representation. We introduce a new intermediate representation as a layer for the optimization and compilation of Statecharts.

Chapter 8: The Compiler. Upon the previous intermediate representation and many ideas of the HOE 2 language, we build the optimizing compiler. We present static analyses and optimizations that apply in the context of communicating objects and allows us to produce efficient code.

Chapter 9: Results. Finally, we prove that a generation of efficient code from our parallel extensions of Statecharts is possible. We stress the compiler with more complex models and show how it can greatly help the designer to achieve automatic model optimizations in the context of the HOE 2 methodology. We review in this chapter parallel programming techniques in a more general context than Model-Driven Engineering (MDE) and its Statecharts.

Part I

State of the Art

The Data-Parallel Paradigm

Different data and computational abstractions are used for parallel programming. The dataparallel paradigm is heavily used across many approaches [START_REF] Brodman | New Abstractions for Data Parallel Programming[END_REF]. In this paradigm, the data set is considered to be divided into regular blocks with different granularities on which common operations have parallel semantics. Therefore, operations have a degree of parallelism which depends on the data abstraction. Distributed computing systems pushed the evolution of existing languages looking for support of data-parallel operations over possibly distributed data [START_REF] Hummel | The Refinement of High-level Parallel Algorithm Specifications[END_REF][START_REF] Delves | [END_REF]. New custom directives were introduced for the specification of data distributions, as well as the underlying computing grid in some cases, in order to specify solutions for a complex problem: " mapping" or adaptation of parallel applications over a parallel architecture.

The Functional Style

Nested Data Parallel (NDP) is a key extension to the data-parallel paradigm. Originally proposed by Blelloch, it allows the programmer to hierarchically compose distinct data-parallel operations [START_REF] Blelloch | NESL: A Nested Data-Parallel Language (Version 2.6)[END_REF]. Among the most abstract implementations of NDP, we found two approaches based on functional languages: NESL [START_REF] Blelloch | NESL: A Nested Data-Parallel Language (Version 2.6)[END_REF] and Haskell Data-Parallel (HDP) [START_REF] Manuel | Data Parallel Haskell: a Status Report[END_REF].

The current implementations integrate this paradigm intuitively into the type system. In HDP, we find a new native type called parallel array, written as [:a:]. It allows the programmer to build hierarchical parallel expressions based on the idea that a parallel array is polymorphic and may be composed by itself. For instance, the following types denote parallel arrays of floating point values, Vector, and tuples of integer and floating point values, SparseVector. The construction of values with the above types is built in parallel. The listing below shows, using list comprehensions, the multiplication of a sparse vector and a full one. The multiplication accesses each element of the sparse vector, (i, x), and multiply it by the correct scalar position in the non-sparsed vector, x * (v:i)!. sumP folds the, possibly distributed, parallel array. In HDP, multiplications are grouped and performed by different gangs of execution threads.

Following this approach we can express nested parallel operations in an architecture-independent way which is relatively simple to understand with a concise complexity model [START_REF] Blelloch | NESL: A Nested Data-Parallel Language[END_REF]. For instance, the listing below builds another parallel array based on the parallel definition of dotp. On the other hand, the approach relies on complex compiler techniques to optimize all performance factors in order to produce efficient code under a fixed execution model (gang of threads). The code generation flow strictly based on the functional approach let the application

C = A + B FIGURE 2
.1: HTA type partitioning and operation mapping (Source [START_REF] Fraguela | The Hierarchically Tiled Arrays Programming Approach[END_REF])

developer focus on algorithmic issues while the architecture constraints are automatically taken into account. They consider a distributed memory. Nevertheless, the variety of embedded multicore architectures make the automatic pass from the HDP to code generation an ambitious and complex task. It is mainly described by rewriting rules with the introduction of new types to represent data distribution [START_REF] Manuel | Data Parallel Haskell: a Status Report[END_REF].

HTA: Hierarchically Tiled Arrays

In the class of imperative high-level parallel programming, we have the Hierarchically Tiled Arrays (HTA) approach proposed in [START_REF] Fraguela | The Hierarchically Tiled Arrays Programming Approach[END_REF]. Similar to HDP, parallelism is introduced by means of the new data type called HTA. The type representation differentiates primarily from that of parallel array by having additional information concerning the specification of data distribution as well as the computing grid.

Figure 2.1 shows the creation of tiled arrays. In addition to the chosen array partitioning, we can also specify the size of the available mesh of processors over which the array blocks are going to be mapped. We can see that the mesh of processors is replicated modulo its size over the partitioned array. The data-parallel operations are constrained to work on arrays with the same "shape" (type). The HTA model is an interesting contribution in terms of coding productivity and allows to control data distribution, something that is hidden in HDP. Apart from productivity reasons, the model does not propose formal optimization methods to achieve performance improvements and directly exposes to the programmer a specific architecture model based on a non-hierarchical distributed memory.

Hierarchical Tasks

The partitioning of data proved to be an efficient technique to provide parallel operations to the programmer in an intuitive manner. Another idea is to concentrate into the (hierarchical) partitioning of computation, which is implicit in previous approaches by the data type (excepting HTA), to map them into dedicated memory models or data-driven architectures.

The Sequoia Approach

Looking for performance of parallel programs, the abstraction level lowers and recent language trends follow specific architecture representations. Based on the fact that approaches focusing on non-hierarchical memory model are difficult to adapt to new memory hierarchies, Fatahalian et al. proposed a new language called Sequoia [START_REF] Fatahalian | Sequoia: Programming the Memory Hierarchy[END_REF].

Sequoia is based on the memory model named Parallel Memory Hierarchy (PMH), where the memory is modeled as a tree whose leaves represent computing nodes. The computation is specified through hierarchical, isolated and parametric tasks (see Figure 2.2). A task works on explicitly partitioned arrays and operations using data-parallel directives (map, reduce). A task may take parameters and may contain other tasks to which it communicates via input and output parameters. Therefore, communication between tasks is explicit. The task hierarchy is mapped to the memory hierarchy, leading to data transfers in the case where two tasks get mapped to different stages. The execution model allows the programmer to define task variants which are selected in the mapping process.

Unlike NDP, mapping choices such as data and computing distribution, among others parameters proposed by Sequoia, are specified by the programmer. The Sequoia approach is located at a lower abstraction level. It follows a programming approach in correspondence to a specific architecture in order to achieve better performance than previous solutions.

HiDP: Hierarchical Data Parallel Language

Recents trends for programming highly parallel embedded systems shows the need to expose a general enough architectural model. Similarly to Sequoia, Mueller and Zhang have developed a hierarchical data-parallel language for General-Purpose computing on Graphics Processing Units (GPGPU) called Hierarchical Data Parallel Language (HiDP) [START_REF] Mueller | Hidp: A Hierarchical Data Parallel Language[END_REF]. HiDP proposes a hierarchy of threads called map blocks, similar to the actual execution model in Sequoia.

Each map block definition introduces a set of iterators to defines its shape, where all iterations are intended to be parallel. For instance, Listing 2.1 describes the General Matrix Multiplication (GEMM) in HiDP. Map blocks are composable similar to NDP. The model is then analyzed and optimized following the compilation chain of Figure 2.3. For instance, multiple map blocks may be merged together according to their shape factor to get as much in-place computations as possible.

Low-level Trends

Finally, we found low-level approches such as OpenCL [START_REF] Stone | OpenCL: A Parallel Programming Standard for Heterogeneous Computing Systems[END_REF], CUDA [START_REF] Sanders | CUDA by Example: An Introduction to General-Purpose GPU Programming[END_REF] and OpenMP [START_REF] Chapman | Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation)[END_REF] where the programmer needs to handle almost everything: synchronization, data and computing distributions, etc. They do not offer data abstractions for parallel programming and are mostly implemented as libraries in low-level host languages such as C/C++. The amount of work to be done in order to have a ready-to-run parallel implementation is considerable and we must take into account device-specific operations and constraints such memory copies from host to device and viceversa, task partitioning.

Model-Driven Representations

The model-driven community made interesting progress towards the application of MDE techniques for the design and development of Embedded Systems (ESs) [START_REF] France | Model-driven Development of Complex Software: A Research Roadmap[END_REF]. It allows designers to model the system gradually by separating functionalities from its supporting platform. It pushes models everywhere as the abstraction method and model transformations as the path to final system implementation. For instance, Model-Driven Architecture (MDA) combines different models for the applicative and platform parts, called Platform-Indepedent Model (PIM) and Platform-Dependent Model (PDM) respectively, and proposes model transformations to progressively adapt the PIM to the given architecture model (PDM) to obtain a Platform-Specific Model (PSM) model. PSM contain platform specific information and it is ready for final code production.

Recent works explore different adaptations or extensions of MDE techniques to address dataparallel applications. A mature solution to modeling massively parallel ES is GASPARD [8].

Model based technologies like GASPARD have a great flexibility in terms of program specification because it is not tied to any particular architecture. For this reason, the system is described via two models based on abstractions proposed by MARTE and the Array Oriented Language (Array-OL) [START_REF] Boulet | Array-OL Revisited, Multidimensional Intensive Signal Processing Specification[END_REF][START_REF]UML Profile for MARTE: Modeling and Analysis of Real-Time Embedded Systems[END_REF]. Indeed, Gamatié et al. rely on Array-OL for the modeling of parallel computations [START_REF] Boulet | Array-OL Revisited, Multidimensional Intensive Signal Processing Specification[END_REF].

We show in Figure 2.4 the visual Array-OL formalism. The designer specifies tiling strategies for the input and output data via a fitting matrix F , a paving matrix P and an offset o such that

• Tiling repetition formula: ∀r, 0 ≤ r < s repetition , ref r = o + P • r mod s array • Iteration inside each tile: ∀i, 0 ≤ i < s pattern , e i = ref r + F • i mod s array
where s pattern is the pattern or tile size, s repetition its repetition and s array the array size. Both strategies are related by the repetition iterator r, which precisely determine data-dependences between input and output tiles. Therefore, Array-OL is used to partition the computations and define affine dependencies without any specific computational model attached to it. It is particuraly adapted to stream-like applications.

Compared to other parallel languages, MDE approaches separate application from platform related informations. Both models are combined iteratively following a specific methodology such that platform-specific constraints are introduced in an incremental manner. The embedding of Array-OL inside GASPARD makes it a powerful framework where domain-specific languages leverages from well-known high-level abstractions and rigorous processes of the MDE community.

Conclusion

In Figure 2.5, we classify reviewed approaches with respect to its abstraction level and how much hardware information they expose to the programmer. Bigger points indicate also higher In this chapter we will present the foundations of Hierarchical State Machines (HSMs), widely known as the Harel's Statecharts. Then, we will discuss its informal and formal semantics and its evolution into the Unified Modeling Language (UML). We will point out main drawbacks to achieve a complete formalization of HSMs and we will review some of the most influencial research work on this matter.

Harel's Statecharts

The formalism of HSM was originally proposed by Harel in [START_REF] Harel | Statecharts: a Visual Formalism for Complex Systems[END_REF]. It is an extension of the formalism of state machines for the specification and design of complex discrete-event and reactive Actually, the original Harel's Statechart is highly expressive. In addition to hierarchical compositions, it also integrates many more features:

1. History states: H . It represents the last visited state in a group of states, which allows to model resumption.

2. Inter-level transitions: Transitions may link states across the hierarchy. From a language point of view, the property is clearly non-constructive. However, it turns out to be a useful artifact for system modeling.

A P P' Q Q' B t 1 t 2 t 3
The syntax of transitions, as defined by STATEMATE [START_REF] Harel | Statemate: A Working Environment for the Development of Complex Reactive Systems[END_REF], is the following one:

α[C]/β;
The transition is sensitive to message α under condition guard C and performs action β (which may contain message sending). The actions can be separated by a semicolon which, contrary to the traditional sense, denotes parallel execution.

Semantics of Statecharts

We reviewed in the precendent section some of the visual features present in Statecharts as well as its intended semantics. The Statecharts informal semantics is detailed exhaustively in [START_REF] Harel | The STATEMATE Semantics of Statecharts[END_REF] and implemented in a system modeling tool called STATEMATE. Its semantics and tool support has evolved years later into a complete working environment for the development of complex reactive systems, Rhapsody [START_REF] Harel | The Rhapsody Semantics of Statecharts (or, On the Executable Core of the UML)[END_REF][START_REF] Ibm | Rational Rhapsody Family[END_REF].1

The STATEMATE Semantics

The system is a single state machine where its parallel components are supposed to describe different, and usually communicating, pieces of it. The behavior of a system is a set of possible runs or system responses to a given set of external stimuli coming from the environment. A sequence of status represents a run of the system. Such sequence is computed by the evaluation step algorithm. More precisely, the status is the global system context containing the current state, valuation of variables, generated events and information regarding the system's history.

Statecharts implement broadcast communications, i.e., the set of events is the same for the entire system. There are two kinds of events: internal and external. Internal events are generated by the state machine and are intended to be consumed by the state machine itself. For instance, entering and exiting states triggers internal events called en(s) and ex(s), which can be captured by any transition. External events comes from the system environment.

The system reaction depends on the HSM configuration, which is the maximal set of states the system can be in simultaneously. That is, the set of active states along the hierarchy. It depends on the state composition type, whether we have an OR (only one state can be active) or an AND composition (only one active state per parallel region). In any case, the current configuration can be determined from the active set C of basic, or leaf, states in the hierarchy. By transitive relation of containment, parents of state s : C must also be part of the active configuration. For instance, a possible active configuration of HSM in Figure 3.1(b) could be C = {S, A, G}.

From an active configuration, the evaluation step consists of finding an active and non-conflicting compound transition. Two transitions are in conflict if they share the same source state and are both enabled at the same instant. Harel defined a priority over transitions following the Statechart hierarchy (outside-in) to resolve conflicting transitions at different hierarchical levels. For instance, consider Figure 3.2 with current configuration C = {R, A}. We may either take t 1

or t 1 if both transitions have the same trigger. Then, the transitions are said to be in conflict.

The priority policy favors t 1 over t 1 such that we can safely take t 1 and quit state R no matter what the active substate of R was. This property gives to Statecharts a try-catch style semantics.

Conflicting transitions at the same hierarchical level introduce non-determinism.

The basic step algorithm performs the following actions:

The Inputs

• The status of the system, i.e., the current global context, which consists of -The state configuration.

-Valuations of variables.

-Relevant information on the history of states.

-List of events that were generated internally in the previous step.

-A list of external changes presented by the environment since the last step.

The Outputs: A new system status

• Stage 1:

Step preparation -Add the external events to the list of internally generated events.

-Execute all actions implied by the external changes. It implies for instance, the update of all variables, conditions.

-Execute scheduled actions and generate timeout events.

• Stage 2: Compute the contents of the step -Compute the set of enabled CTs.

-Remove conflicting transition by applying priorities.

-For each CT, compute the set of enabled SRs defined in states that are currently active but not being exited by any of the CTs in the set.

-If there are not enabled transition then the step is empty. Otherwise, this set of transitions consistutes the current step.

• Stage 3: Execute the CTs and SRs -From the set of enabled transitions computed in stage 2, execute its associated actions.

-Let Sx and Sn be the sets of exited and entered states from the current state, then: account in the current step -avoiding inifinte loops -but in the following one. The actions to execute are taken from the set of enabled transitions (CTs and SRs). Because the actions are supposed to run in parallel, they may introduce what the author called write-write racing situations. That is, two actions writing to the same variable.

Formal Semantics of Statecharts

As shown in the precedent chapter, Statecharts as defined by Harel implies a quite involved semantics. Soon after its invention, many researchers dived into the question of defining a formal semantics and it turned out to be harder than excepted. As a consequence, many Statecharts variants appearead since then [START_REF] Michael Von Der Beeck | A Comparison of Statecharts Variants[END_REF]. However, none of them formalizes the Statecharts semantics as implemented in the industrial tool STATEMATE, till the work of Mikk et al.. They introduce in [START_REF] Mikk | On Formal Semantics of Statecharts As Supported by STATEMATE[END_REF] the official semantics as supported in STATEMATE by closely following [START_REF] Harel | The STATEMATE Semantics of Statecharts[END_REF].

The STATEMATE semantics defines a set of finite state labels, Σ, and the kind of states,

T Y P E AN D | OR | BASIC.
From these sets, it defines the mathematical structure StateTree, which consists of the following parts:

• root, a special state that it is intended to contain the actual Statechart

• init, an initial state • ρ : Σ → P(Σ), the state hierarchy partial function that maps a state to its contained substates • φ : Σ → T Y P E, the map kind partial function Above definitions provide enough information to formalize the state hierarchy and to introduce some correctness conditions. For instance, Definition 3.1 is an example of a correct hierarchy of states with respect to the root state as defined in [START_REF] Mikk | On Formal Semantics of Statecharts As Supported by STATEMATE[END_REF].

Definition 3.1. The root state is of kind OR and no state may contain it

dom(ρ) \ ran(ρ) = {root} ∧ φ(root) = OR
Based on the set of possible events EV , the allowed event expressions are defined as:

EE T RU E E | B EV | N OT E EE | AN D E EE × EE | OR E EE × EE
Equivalently, the set of valid conditions C is inductively defined as

C T RU E C | In Σ | N OT C EE | AN D C EE × EE | OR C EE × EE
Then, the transition expression is a LABEL with three parts 1. event expr : EE, an expression to validate according to the current set of events 2. condition : C, a guard expression for the transition to be executed 3. action : P(EV ), a set of events to be emitted

The transition itself t : T R is a structure containing a label and going from a non-empty set of states, source : P(Σ), to another non-empty set of states, target : P(Σ). Source and target states becomes sets because the state hierarchy has been flattened. The semantics defines evaluation functions to check if the transition is enabled.

The Statechart, SC, is formalized using the StateT ree structure that provides the state hierarchy and the set of labeled transitions T R that links them:

σ : StateTree τ : P(T R)
According to this semantics, the status s : STATUS of a Statechart contains

• csts : P(Σ), the set of active states or the state configuration.

• events : P(EV ), the current set of events.

• sc : SC, the actual Statechart.

Based on this status definition, the semantics instantiates a transition system

T S = (STATUS , INIT , STEP )
where STATUS is the universe of states, INIT the initial one and STEP ⊆ STATUS × STATUS the transition relation. The run of the system is an infinite sequence of formal statuses following relation STEP .

To give an idea about the complexity of the step relation, we cite hereafter its formal definition using Z notation [START_REF] Spivey | The Z Notation: A Reference Manual[END_REF]: Clearly, the semantics is too complex to maintain and hardly extensible. Furthermore, it still does not take into account the valuations of variables and history states.

let
We see two possible reasons for such complexity, whether some features of Statecharts are actually difficult to formalize or the approach taken in the STATEMATE formalization turned out to be too cumbersome. As we will see in next sections, the former seems to be the main cause. Features like parallelism, event handling, asynchronous compositions, lead to a nondeterminstic semantics. Non-deterministic properties of languages are frequently formalized using power-domains, to keep track of all possible runs of the system, or using a transition semantics [START_REF] Reynolds | Theories of Programming Languages[END_REF]. However, inter-level transitions, preemption and try-catch semantics are deeply non-modular and tend to require global and complex structures along the entire formalization.

Not surprisingly, such complexity reappears in recent research work on formal specifications of Statecharts in the context of UML. In the next section, we review the most important ones to us.

The Unified Modeling Language

The formalism of HSM has been successfuly adopted by the industry for system level modeling, simulation and code generation. It continues to be improved by a standard organization the Object Management Group (OMG), under the widely known name UML [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF]. UML is a unified and model-driven approach for the modeling of complex hardware/software systems. It proposes interesting features to manage and specify different system development aspects:

• Abstractions to classify relevant features of the system and how they relate to each other: Structured Classifiers.

• Activity graphs that allow the designer to organize the actions to perform for a given task.

• Modeling of each feature's behavior using hierarchical state machines: State Machine.

• A set of concrete actions to perform on the model by the state machine, such as communication primitives or structural updates.

• Models for the specification of use cases.

The UML specification is entirely model-based. For instance, Figure 3.3 shows the classifier implementation in UML v2.4.1 [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF]. The class is intended to model a particular component of the system. It contains properties that associates it to zero, one or more components, according to the specific multiplicity of the association. More precisely, it is the model view of the type definition of an object in Object-Oriented Programming (OOP) languages like C++ or Java. For instance, Figure 3.4 shows in a visual manner two instances of the class meta-model: an Image and a General-Purpose computing on Graphics Processing Units (GPGPU) class model.

In addition to structural features of a class, the UML classifier may provide a specific behavior using HSMs. Therefore, the language enables the modeling of a structured network of communicating Statecharts. pixels [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] y u v uchannel [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] blocks [8,8] pblocks [8,8] ublocks

Informal Semantics

In [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF], the OMG introduces an informal semantics of Statecharts where they specify the event processing algorithm for state machines, called the Run-To-Completion (RTC) step. The RTC informally describes the actions to perform in order to determine the set of enabled transitions to fire and how the compound transition is executed afterwards.

Contrary to traditional Statecharts, the state machine handles the arrival of events one at a time and it is not based on broadcast communications. That is, it exposes a message oriented, First In-First Out (FIFO)-like communication. Moreover, there is no difference between internal or external events, they are all considered external.

Following almost the same policies as Harel for the computation of enabled compound transitions, the actions of each fireable transition are executed sequentially -and not in-parallel as before. In UML Statecharts, the transition with higher priority is the more nested one (insideout).

At a given state configuration, the RTC step specifies the following actions to perform:

1. From the transition source state, all substates are exited and their corresponding exit actions are executed. Note that there is no internal events generated here.

2. The chain of state exits continues until the first region that contains, directly or indirectly, both the main source and main target states is reached. The region that contains both the main source and main target states is called their least common ancestor, or lca, and it constitutes the scope of the transition.

3. The target configuration of states is entered and theirs corresponding actions are executed starting with the outermost one.

Formal Semantics

A complete formal specification of UML is a challenging work. The OMG undertakes it on a subset of UML called foundational UML (fUML) [START_REF]Object Management Group. Semantics of a Foundational Subset for Executable UML Models (FUML)[END_REF]. However, their semantics does not cover the formalization of state machines, neither its communications. They map models to a particular "surface" language, such as Java, in order to concretize theirs semantics.

We found multiple formalizations of UML state machines in the literature [START_REF] Seifert | An Executable Formal Semantics for a UML State Machine Kernel Considering Complex Structured Data[END_REF][START_REF] Liu | A Formal Semantics for Complete UML State Machines with Communications[END_REF][START_REF] Börger | On formalizing UML state machines using ASMs[END_REF][START_REF] Michael Von Der Beeck | A Structured Operational Semantics for UML-Statecharts[END_REF][START_REF] Ivan P Paltor | The Semantics of UML State Machines[END_REF]. The most accomplished work to the best of our knowledge is due to Liu et al.. He introduces its own abstract syntax for HSM closely following the UML state machine specification. For instance, the state is a tuple of the following form: s = ( r, t def , α en , α ex , α do , en, ex, ex, cr, sm, t) where • r is the set of regions.

• t def , α en , α ex and α do are the set of deferred events, the entry, exit and do behaviors.

• en and ex are the set of entry point and exit point pseudostates.

• cr is the set of connection point references. sm is the owner state machine.

• t is the set of internal transitions.

The region is the cartesian product of vertex and transitions

r ( v, t)
where v ⊂ (S ∪ P S ∪ S f ), i.e., it is either a state, a pseudostate or a final state. Compared to the previous formal representation, here we have two mutually recursive definitions, region r and state s through v.

The transition is the tuple t = (sv, tv, tg, g, α, ι, tc) where • sv and tv are the source and target vertex, or states.

• tg, g, α and ι are the set of triggers, the guard, the behavior and the container of the transition.

• tc represents the special situation that a join or fork pseudostate connects multiple transitions to form a compound one.

The author defines an evaluation function A that takes the behavior part of the transitions and returns a set of events to be sent.

Then, the state machine is defined as sm ( r, cp). It contains a region (and by transitivity a set of states) and the entry and exit points of sm.

Finally, Liu et al. defines the system of n communicating state machines as

sys | C i∈[1,n] Sm i
where Sm contains the actual state machine, its events pool and a set of shared variables: Sm (sm, P, GV ). The operator | C synchronizes all state machines on events in C. This operator is needed because of the synchronous sending of messages as defined by UML. That is, state machine sm i sends a message to sm j and its RTC is not finished until the sm j has finished its own step.

Given a tuple of n configurations of state machines (k 1 , . . . , k n ), the semantics instantiates a Labeled Transition System (LTS). The configuration is defined as k = (ks, P, GV ) where ks is the set of active states of the state machine sm k . Then, it defines three main LTS rules:

| C i∈[1,n] Sm i , k j → k j (k 1 , . . . , k j , . . . , k n ) → (k 1 , . . . , k j , . . . , k n ) LTS1 | C i∈[1,n] Sm i , k j → k j , e = SendSignal (j , l ), M erge(e, EP l ) (k 1 , . . . , k l , . . . , k j , . . . , k n ) → (k 1 , . . . , k l , . . . , k j , . . . , k n ) LTS2 | C i∈[1,n] Sm i , k j → k j , e = Call (j , l ), e ∈ C, k l e - → k l (k 1 , . . . , k l , . . . , k j , . . . , k n ) → (k 1 , . . . , k l , . . . , k j , . . . , k n ) LTS3
We have asynchronous composition with special cases for asynchronous and synchronous sending of signals, encoded in LTS2 and LTS3 respectively.

The main advantage of this formalization resides on its completeness with respect to the UML specification. It defines mutually recursive structures to formalize the state machine and the author uses such recursive definitions to define elegant evaluators of entry and exit behaviors (not shown here though). Even if the state machine is defined recursively, the state configuration is still flattened. The action language is not specified but the author handles behaviors such as SendSignal and Call. If state machines are willing to pass valued signals, they must use shared variables. Similar to the formal semantics of Harel Statecharts, the lack of modularity leads to scalability issues. Nevertheless, it is clear that such complexity can be hardly avoided given the specifities of UML state machines such as deferred messages, synchronous messages sending and local transitions.

Another interesting formalization was done by Seifert where he followed an equivalent path in his work [START_REF] Seifert | An Executable Formal Semantics for a UML State Machine Kernel Considering Complex Structured Data[END_REF]. It defines an abstract syntax but instead of using recursion on states and regions, it specifies a state hierarchy similar to the STATEMATE formalization. One of the most important differences with respect to the work of Liu et al. is that events may carry parameters. It defines events as an indexed family of sets (P e ) e∈E where E is a set of events. Then, a parameterized event set E v with v ∈ E is defined as

E v = v P 1 × • • • × P n
Such definition enables the author to introduce the set of all event instances as

E = v∈E E v
For instance, a particular event set E = {a, b} with P a 1 = N, P a 2 = B and P b 1 = B gives the set of all event instances:

E = E a + E b = a N × B + b B = {a(0, true), a(0, false), . . . , b((true))}
Seifert distinguishes two kind of actions, event sending and updates of the binding context. Indeed, the state machine step depends on a global binding context of variables.

If his formalization works nicely on complex data structures as a binding context, it does not handle multiple communicating state machines as [START_REF] Liu | A Formal Semantics for Complete UML State Machines with Communications[END_REF] does.

Synchrounous Statecharts

Defining a suitable semantics for Statecharts is challenging as we have seen in the previous sections. Many problems arise concerning inter-level transitions, history states and asynchronous compositions, which are source of non-determinism. Harel and UML Statecharts are hence subject to racing conditions due to their asynchronous semantics. In the domain of safety-critical TEREL language [START_REF] Berry | The ESTEREL Synchronous Programming Language: Design, Semantics, Implementation[END_REF], but removes some of its limitations such as multiple variable assignments while keeping determinism. Quoting Harel's statement about Statecharts [START_REF] Harel | Statemate: A Working Environment for the Development of Complex Reactive Systems[END_REF], the author nicely states the evolution of all three formalisms: Statecharts = State-diagrams + Depth + Orthogonality + Broadcast Communications SyncCharts = Statecharts syntax + Esterel semantics SCCharts = SyncCharts + Sequential constructiveness + Extensions Figure 3.6 shows many of the Statecharts features supported in SCCharts. The formalism relies on a concrete language implementation, the SC Language (SCL), and its corresponding graphical elements. SCL has a very basic -yet expressive enough -kernel of language constructions: Based the above language, the author introduces its constructive semantics in an operational manner [START_REF] Von Hanxleden | Sequentially Constructive Concurrency: A Conservative Extension of the Synchronous Model of Computation[END_REF]. Essentially, it extends the synchronous Model of Computation (MoC) [START_REF] Benveniste | The Synchronous Languages 12 Years Later[END_REF] by allowing variables to be read and written multiple times as long as the sequential specification

s := x '='
of the program provides enough information to avoid race conditions. Because of the structured semantics, i.e., guided by the language constructions, the formalization is cleaner than the precendent ones, extensible and modular.

Conclusions

We UML, has given rise to many abstract implementations and their corresponding formalizations.

In contrast to graphical approaches, the structural approaches are mainly driven by a concrete language implementation (synchronous Statecharts) over which the semantics and, possibly, its type system are specified. From a well-founded concrete language, we can more easily found convenient visual elements and, more importantly, build a constructive semantics, which is modular and amenable to further extensions.

We show some common features between the reviewed semantics in Table 3 This chapter introduces the compilation of Statecharts "à la Harel". We will overview most used techniques for optimization and code generation in the industrial and research context.

Compilation of UML Statecharts

The Unified Modeling Language (UML) language is uniquely designed as a modeling/specification language and it is not tied to any particular compilation method or optimizing flow. UML favors model-based design at all levels of the development process. Furthermore, the standard left many semantic variation points open to specific implementations [START_REF] Chauvel | Code Generation from UML Models with Semantic Variation Points[END_REF]. Most Model-Driven Development (MDD) frameworks based on or inspired from UML, such as Rhapsody [START_REF] Gery | Rhapsody: A Complete Life-Cycle Model-Based Development System[END_REF] or GASPARD [8] [START_REF] Robert C Martin | UML Tutorial: Finite State Machines[END_REF] and the nested switch case statements [START_REF] Metz | Code Generation Concepts for Statecharts Diagram of UML v1.1[END_REF].

The most used technique for generating code from Statecharts relies on the state design pattern [START_REF] Dominguez | A Systematic Review of Code Generation Proposals from State Machine Specifications[END_REF] shown in Figure 4.1. Basically, each state is translated into a class of the host language that handles a certain number of events depending on its outgoing transitions. If an event arrives, the context calls the virtual method handle(), which returns the next state according to the encoded transition triggered by such event.

The STT approach creates a table describing the relation between states and events. The boost C++ Statechart library [START_REF] Huber | The Boost Statechart Library[END_REF] hides behind a heavy use of C++ metaprogramming a transition table to map efficiently states to transitions.

Finally, the Nested Switch Case method consists of, as its name implies, a set of nested switch case statements where the top ones filter the current state of the state machine and further nesting levels apply the final action following the received event.

The optimizations are frequently done by the backend-end compiler (C/C++, Java), which does not necessary know the original Statechart structure, and hence may miss interesting optimizations [START_REF] Charfi | Toward Optimized Code Generation Through Model-Based Optimization[END_REF]. On this direction, we reviewed different approaches for model transformations and optimizations either before code generation or all along the optimizing and code generation process.

Model-to-Model Optimizations

Certain research works handle optimization issues via Model-to-Model (M2M) transformations.

There are a good variety of dedicated tools, most of them based on the Eclipse Framework, for M2M transformations such as ATL [START_REF] Jouault | ATL: A Model Transformation Tool[END_REF], Epsilon Transformation Language (ETL) [START_REF] Kolovos | The Epsilon Transformation Language[END_REF],

Query/View/Transformation (QVT) [START_REF] Dvorak | Model Transformation with Operational QVT[END_REF] and many others. The concept of M2M is to specify the language transformations based on the language meta-model, within a meta-modeling seems to have a corresponding meta-model according to [START_REF] Reinhard Von Hanxleden | SCCharts: Sequentially Constructive Statecharts for Safety-critical Applications: HW/SW-synthesis for a Conservative Extension of Synchronous Statecharts[END_REF]. Using the Eclipse Metamodeling Framework (EMF) [START_REF] Steinberg | EMF: Eclipse Modeling Framework 2.0[END_REF], they write model-to-model transformations in plain Xtend language [START_REF] Bettini | Implementing Domain-Specific Languages with Xtext and Xtend[END_REF]. 1 We discuss in detail its compilation process in Section 4.3.

Optimizing Beyond the Back-end Language

In [START_REF] Charfi | An Optimized Compilation of UML State Machines[END_REF], Charfi et al. pointed out the recurrent problem of modeling frameworks concerning the gap between models and code production. A concrete specification of a convenient action language enables the production of executable models while providing validation and verification support. However, the early validation process and consequently the modeling effort are invalidated by hand-tuned code specializations, necessary to meet performance requirements of the given models.

To overcome the problem, Charfi et al. pass semantical information about the input model to the compiler, thus enabling further optimizations such as elimination of unreachables states, condition combining, etc.. Using a new representation called GUML, information concerning the structure of the original state machine is passed down to the C compiler via embedded GIMPLE nodes. GIMPLE is a language-independent tree representation used in GCC for SSAbased optimizations [START_REF] Merrill | GENERIC and GIMPLE: A New Tree Representation for Entire Functions[END_REF]. The approach enables high-level optimizations inside the intermediate representation of a compiler. Figure 4.4 show the compilation flow as proposed in [START_REF] Charfi | An Optimized Compilation of UML State Machines[END_REF]. They

Domain Specific Languages Supporting Model Based Design

The GASPARD modeling framework is the closest work to HOE 2 we found in the literature [8].

They propose a combination of MARTE for the modeling of embedded systems and the Array Oriented Language (Array-OL) [START_REF] Boulet | Array-OL Revisited, Multidimensional Intensive Signal Processing Specification[END_REF][START_REF]UML Profile for MARTE: Modeling and Analysis of Real-Time Embedded Systems[END_REF], which offers generation of efficient code for dataintensive applications. GASPARD provides a set of modeling concepts for the specification of Array-OL applications within the MARTE UML profile. They showed interesting results of an unified modeling of modern platforms (GPGPU) and video processing algorithms (H-263) [START_REF] Wendell | Programming Massively Parallel Architectures using MARTE: a Case Study[END_REF]. However, they focused on the data-driven part of the algorithm (filtering) because Array-OL does not support control dependent flow, as shown in Chapter 2. Therefore, they have to mix different formalisms for control and data-driven components. Array-OL is mainly a stream-oriented language, known to have good code generation properties [START_REF] Dumont | Spécification multidimensionelle pour le traitement du signal systématique[END_REF], although not a Statechart-like formalism.

We also found similar combinations in the world of synchronous languages [START_REF] Alras | Model-Based Design of Embedded Control Systems by Means of a Synchronous Intermediate Model[END_REF]. Alras et al.

pointed out the innefficient code generation process from models and tried to address this issue by supporting Model Based Design (MBD) with an intermediate representation based on LUSTRE [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF], which has a strong background on code generation methods.

Synchronous Statecharts Compilation

In contrast to UML, synchronous Statecharts are strongly guided by a concrete language implementation (and its semantics as well). The code generation of synchronous languages is a well-known subject in the research community since the LUSTRE and ESTEREL programming languages [START_REF] Edwards | Tutorial: Compiling Concurrent Languages for Sequential Processors[END_REF].

SCCharts [START_REF] Reinhard Von Hanxleden | SCCharts: Sequentially Constructive Statecharts for Safety-critical Applications: HW/SW-synthesis for a Conservative Extension of Synchronous Statecharts[END_REF], presented in Chapter 3, is a safe imperative extension to synchronous languages with a Statechart-like visual representation. The compilation of SCCharts is decoupled into different intermediate representations:

• Extended SCChart: the front-end language.

• Normalized SCChart: the extended SCChart is reduced through a series of model-tomodel transformations to primitive transitions only, which facilitates the mapping to the following representation.

• SC Graph: It is a directed graph that captures control dependencies in the form of a graph of basic blocks as well as data dependencies between parallel statements.

We show in Figure 4.6 the SCChart representations. For instance, note that the normalized one split transitions with more than one sequential statement into multiple states (transition

Init → W aitAB).
As explained above, the SC Graph decouples the normalized SCChart into basic blocks or "scheduling units". The green arrow denotes a concurrent data dependency.

In order to guarantee a deterministic behavior, writes are scheduled before reads, which split g 7 into two different scheduling units. The SC Graph relies on the SCL language introduced in Chapter 3 and it is from this language that the authors perform the software and hardware synthesis. SCL and its respective dataflow view make hardware synthesis almost straighforward.

However, they need extra software support to generate the "tick" function that computes each signal following the chosen scheduling. Indeed, there is another representation slightly different from SCL called SCL P , which consists of a subset of the sequential C core.

Conclusions

Current MDD frameworks based on UML Statecharts generally focus their code generation strategies for simulation purposes and they are known for the faithfulness of the initial model with respect to the generated code. Thus, it is not intended to consitute a final code production process. On this direction, MDD frameworks use Object-Oriented Programming (OOP) code generation techniques to improve readability of the generated code and provide a rapid software architecture to work further on. Looking for performance, recent works try to fill the gap between modeling techniques and final efficient generated code. Existing approaches take into account high-level semantics all along the compilation flow. we highlight two main drawbacks: the lack of a concrete action language and the multiple semantical variation points of Statecharts. To cope with the former, an initiative for the specification of a concrete syntax from UML exists [START_REF]Concrete Syntax for a UML Action Language: Action Language for Foundational UML (ALF)[END_REF]. However, it does not specify Statecharts notations. Meanwhile, industrial tools mixed foreign languages such as C/C++ or Java inside transition actions, with UML providing an object-oriented context. Reviewed research work built upon C/C++ as the main action language and adapted compliant compilers (gcc) to host and to optimize Statechart based applications.

Unfortunately, the compilation of UML Statecharts faces a number of open questions related to their semantics. As shown in Chapter 3, it led to multiple and complex formalizations and it will necessarily lead to different compiler implementations. 2The important semantical gap between high-level models and its supporting languages (C/C++) calls for intermediate representations to further optimize the model regarding different aspects: communications, computations and data structuring. Different works propose theirs internal representations (GUML, SCCharts/SCL, Lustre, Array-OL) based on which many strong optimizations can be achieved. However, they are either too specific and tied to a particular low-level language (GUML) or have limited expressiveness (SCCharts, Lustre, Array-OL).

To summarize, Figure 4.8 shows all different aspects studied so far. From languages that allow the modeling of parallel computations (Chapter 2), the semantics of Statecharts (Chapter 3) and its optimization and compilation methods, we conclude that a well-founded Statecharts formalism should provide • Modularity: The widely known object-oriented paradigm is well-suited to structure the communication between different Statecharts and provide a explicit context to the state machine. UML has strong foundations on this matter.

• A concrete language implementation with parallel actions: In order to be as precise as possible and to build the foundations for a structured semantics, we need an expressive action language to that can allow us to model parallel operations.

• A structured formal semantics: on the grounds of a concrete language, a structured semantics should enable a simpler and scalable specification. In order to fill the gap between the modeling objects and the expression of data-intensive and parallel computations, we introduce the Highly Heterogeneous, Object-Oriented, Efficient Engineering HOE 2 language. In HOE 2 , we take advantage of hierarchical representations with multi-valued associations to expose deep nested parallelism. Such parallelism is inherently available at the model structure but often not taken into account to represent primitive data.

We designed HOE 2 to be able to express, in an unified manner, fine-grain hierarchical parallelism relying on the structural parallelism already built-in into the model. With data-intensive applications in mind, we also looked to provide a path to the generation of efficient code by introducing a set of behavioral abstractions amenable for analysis and optimizations. We present the general structure of the HOE 2 language, its Statecharts, and, most importantly, the action language. We also recall some of the important features of the Unified Modeling Language (UML) class meta-model and its Hierarchical State Machine (HSM) definition.

Objects

The HOE 2 language borrows some of the important concepts from the widely-known modeling language UML. More precisely the concept of classes, associations, multiplicities and HSM. Figure 5.1 shows a simplified meta-model of the concept class defined in UML 2.4 [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF]. A class contains an indeterminate number of (structural) properties. Two properties are linked via an association, which at the model level is graphically represented by a straight line connecting two classes. In addition, properties inherit multiplicity information that allows to constrain the number of linked instances. In simpler words, we are able to declare arrays of different sizes. It is a particularity of UML-like modeling language that we will introduce later. Note that we use the keyword object instead of class. Formally, objects are defined as follows object ::= 'object' ID interface * association * SM It specifies a set of interface entries, a set of associations and a HSM. The allowed types of associations are either already defined objects or containers. A container is an ordered sequence of elements that allows duplicates. In the context of UML, the meaning of order is given with respect to the element position, i.e., independently of the implemented order policy. An element A is less than A' if A is located at a lower index position than A' in the container. Whether we have lists or arrays is implementation specific and it is automatically decided at code production time.

In order to support multi-dimensional containers, we extend the multiplicity specification of UML with comma-separated list of ranges described by the following grammar:

T ::= t | '[' Range ']' t Range ::= Range ',' Range | INT | INT '..' INT | INT '..' ' * ' | ' * '
where t is a user-defined object type. The four leaf cases of Range have the usual meaning 1. Container with fixed size, e.g.

[256]T.

Container size has known lower and upper bound:

Unbounded number of elements:

[ * ]T.

Interface

As HOE 2 objects are communicating state machines, they interact with each other by means of message passing. The set of valid messages that objects may exchange depends on its interface definition. From the point of view of an object, the interface specifies the set of valid incoming and outgoing messages with respect to the external world. That is, it exports the set of input and output messages its users may observe. Everything else related to the message exchanges needed to fulfill the interface definition is not seen by the external users.

Listing 5.2 shows the definition of three accepted input messages getY, getU and getV, and three output messages takeY, TakeU and takeV. Input-output relations can also be defined. For instance, takeY is declared to be a consequence of the reception of getY. They are implicitly interpreted as input and output messages, respectively, and do not need to be in the set of ins and outs.

Imports

In order to improve the language modularity, it is possible to organize objects by modules. A module consists of a set of objects grouped in a single file. The module name is taken from the file name. Other object may import the module using the keyword import followed by the list of desired modules.

Hierarchical State Machines

The Model of Computation (MoC) is based on UML HSMs [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF], inspired from the Harel's Statecharts [START_REF] Harel | Statecharts: a Visual Formalism for Complex Systems[END_REF]. UML provides the HSM structure shown in The transition has three main components: zero or more triggers, a guard condition and its effect. The trigger specifies a list of valid messages to wait for and if the condition guard is true, the effect is executed. We will discuss about the semantic variations in Chapter 6. The effect is defined as a Behavior, which may be an opaque type so that the user is free to choose its preferred language. The behavior specification is known as the Action Language, which is one of our main contributions: the HOE 2 action language. Together with a new syntax to describe HSM, we introduce a new parallel action language to exploit the inherent parallelism of multi-valued associations in a data-parallel setting. 1 Before going into the details of our proposition, we present the general structure of the HOE 2 HSM and highlight particular differences with respect to the UML version. In contrast to UML, we defined two different concepts for simple and composite states represented by the keywords state and cstate, respectively, with transitions folded into the source state to improve code source readability. The simple state has an identifier and is followed by a list of outgoing transitions. In addition to outgoing transitions, composite states contain parallel regions (two regions in the presented example). Parallel regions contain in turn other states, building up the state machine hierarchy.

They are classified as follows:

Creation. Creation transitions provide a method to create object instances and determine the entry point of execution. They are similar to constructors in Object-Oriented Programming (OOP). In the same sense, they may take parameters. We allow the specification of creation transitions only at the top level of the state machine.

External. Standard transitions.

Initial. This transition indicates the initial state of regions.

Final. The final transition marks the end of its execution context, which is either a state machine or a region. In the following sections, we present the particularities of the HOE 2 action language.

Modeling Arithmetics

The action language separates arithmetic operations into three basic actions: (1) start computation, (2) receive the result and (3) store it. Point (1) represents a send primitive, (2) denotes a receive and (3) an update or assignment. Whereas the former two points are intrinsic to the state machine semantics, the latter is the additional most basic action to be defined. Figure 5.6

shows the structure of the proposed action language. We define the action, or behavior in UML terms, as a sequential composition of updates and sending primitives, separated by the token ':'.

Receive and guard specifications are defined at the beginning of the transition followed by the keyword on and enclosed in square brackets, respectively. Messages add(Int) and added(Int) are part of the object specification as we will see later.

They model the actual addition with r being the receiver of message add(Int) sent by a Pixel object with parameter g.

Parallel Actions

As pointed out in Chapter 2, the data parallel approach is a promising technique to make efficient use of parallel hardware. We will show that its more elaborated extension called Nested-Data Parallelism can be represented in a model-driven manner. The implementation of such paradigm relies on a new data structure called parallel array in the context of Haskell Data-Parallel (HDP) [START_REF] Manuel | Data Parallel Haskell: a Status Report[END_REF]. Similar to HOE 2 objects, parallel arrays are composable to allow the expression of hierarchical or nested data parallelism.

The data parallel approach is about performing the same operation on a set of grouped elements, which in our context it is called broadcasting. We take advantage of multi-valued associations to define data parallel operations using index domains, defined between braces. Based on the model example of In order to complete the parallel operation, the answers triggered by a data parallel broadcasting need to be captured precisely. Therefore, messages have an attached index value which is inspected using the notation presented in Listing 5.6.

Above listing shows the reception of an indexed message where, instead of passing index values around as message parameters, we expose indexes as a special field in the message structure.

The advantage of this approach is twofold:

• Given that the index domain concerns only the sender, the receiver does not need to know where it is stored in the sender context.

• As we will see in Chapter 8, we can analyze index sets to optimize the state machine and to produce efficient code.

After the reception of all indexed messages, we need to indicate the completion condition. Listing 5.7 shows the syntax that denotes broadcast termination. Using one the index variables, which has a corresponding index domain, we denote the condition "all messages have been received".

In addition to index domains with parallel semantics, we extend the language with parallel composition using the comma separator. • Upper/lower triangle of a two dimensional association:

{ i, j: 0 <= i < j and 0 <= j <= 255 }

We can iterate on both HOE 2 actions, updates and sending. Iterators in sending actions have additional semantics. The defined index variables can be used later in receive expressions so that the same domain applies there. As shown in Listing 5.6, the index domain of i defined at state A remains the same at the receive clause of state B.

We limit index constraints to the representation of affine expressions. That is, constraints are defined over the set of presburger formulas [START_REF] Presburger | On the Completeness of a Certain System of Arithmetic of Whole Numbers in Which Addition Occurs as the Only Operation[END_REF].

Association Slicing. The action language supports slicing of associations. The programmer can specify a closed range to select a list of values from a multi-valued associations in a single expression. As an example, consider the Image creator of Listing 5.9.

The Image creates pixel.len pixels using creator pixel and passing it a slice of the association rawImage containing three values.

Initiators

In section 5.4, we presented how to handle replies triggered by specific messages such as getY or Add and mult(Int) but we did not show how the corresponding replies were generated.

In HOE 2 , the receiver may send replies using the keyword initiator. For instance, consider the complete implementation of Pixel where the use of initiator is highlighted at line 24 of Listing 5.10.

The initiator allows objects to send replies without knowing the actual target.

Object Creation

Every object exposes a creation transition. For instance, consider the example of Listing 5.10

where Pixel defines a creation transition called RGB taking an association of three integers.

Then, Image creates Pixel instances using the following syntax

pixels[i] = new Pixel.RGB(rgb[3 * i..3 * i+2])
LISTING 5.11: Instantiating objects

Indexed Regions

Regions inside states represents parallel regions of code, modeled using state machines, hence the hierarchical composition. Whenever the state machine enters a composite state, it automatically jumps to the entry point of each of its internal regions.

We extend the HSM model with indexed regions where its graphical and textual notation is shown in Figure 5.8. It represents N parallel regions, each one indexed by i. The i-th region contains two states, S i and T i , where S i is the initial one. Indexed regions model forall block expressions, found natively in most parallel languages or introduced as parallel extensions to sequential languages [START_REF] Manuel | Data Parallel Haskell: a Status Report[END_REF][START_REF] Chapman | Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation)[END_REF].

We will show in Chapter 8 that the indexed region is a key concept to enable deep optimizations for efficient code generation, e.g. inlining of HSMs. As an illustration, consider objects O and O' related through a multi-valued association o' as shown in Figure 5.9(a). Under specific hypotheses for model and state machine transformations that we will introduce in detail in Chapter 8, we are able to inline object T into S featuring indexed regions as described by

Scalars

Every language provides a set of scalars as built-in types, e.g. int or float in C/C++ or Java.

In addition, pure functional languages like Haskell allow us to represent algebraic properties on scalars. They share an intrinsic property across all programming languages: immutability.

Furthermore, scalars usually denote the carrier set of some algebraic structure. Lots of compiler optimizations are built upon properties of scalars, e.g. constant propagation, strength reduction or value numbering [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF].

On the other hand, the behavior of built-in types strongly influence language design. For instance, let us consider the pure, non-strict functional language Haskell. Due to its lazy evaluation strategy, variables of any type, including primitives types, can be undefined until their values are required [START_REF] Scott | Toward a Mathematical Semantics for Computer Languages[END_REF]. The undefined value, noted ⊥, is part of all Haskell types and must be taken into account. Technically, the language calls the integer type Int a boxed type even though standard arithmetics is applicable on them and all known algebraic properties still hold.

A specific analysis called the strictness analysis tries to avoid boxed types as much as possible in order to improve performance trading-off its non-strict semantics at compilation time [START_REF] Brown | The Architecture Of Open Source Applications, volume II. lulu.com[END_REF].

Data-flow languages introduce another interesting example of built-in types [START_REF] Caspi | LUSTRE: A Declarative Language for Realtime Programming[END_REF][START_REF] Gamatié | Designing Embedded Systems with the SIGNAL Programming Language: Synchronous, Reactive Specification[END_REF]. In the Kahn denotational semantics of data-flow languages [START_REF] Kahn | The Semantics of Simple Language for Parallel Programming[END_REF], everything is a stream, even primitives values. A simple integer value in such programming language denotes a stream of values where all arithmetic operations are applied point-wise. This feature allow the programmer to easily write parallel programs, increasing the language expressiveness.

Inspired from these remarks and the intrinsic properties of scalars, we define an extended view of scalars as communicating state machines. where operator is would allow us to check whether the value of f has been properly divided or not. This construction can be seen as a pattern matching over set Dived + DivedByZero.

The main difference is that f does not need to be projected in order to be used once it has been matched. If it is an error, it cannot not be used at any of the reachable states starting from

ErrorState and if it is used, it is not an error. To see this claim, note that Listing 5.15 is the translation of Listing 5.14 after sends and receives have been folded. In the latter, no variable is defined when an error message is received and therefore, f does not exist at all states reachable from the second transition unless there is a path in the control flow which joins NextState and ErrorState, i.e., they share reachable states. If there is such a path and f is used, it must correspond to dived(Float) message.

Other interesting refinements can also be intuitively constructed based on this idea. For instance, the C implementation of floating-point numbers follow the standard IEEE754 [START_REF]IEEE Standard for Floating-Point Arithmetic. IEEE Std[END_REF] and can be translated as shown in Listing 5.16. In general, the operational transitions for any scalar T are of the form

optransition ::= 'on' input '->' output '~>' opid input ::= id '(' type * ')' output ::= output 'or' output | id '(' [ type ] ')'

Modeling Applications

The set of proposed features allow us to model data intensive applications in an intuitive manner. In order to show the use of some of the proposed features, we consider the computational intensive flow of the JPEG compression algorithm shown in Figure 5.10.

Starting from an image on RGB format, the algorithm transforms it into the Luminance and Chrominance color metrics (YUV). The luminance values are then tiled with a tile size of 8x8.

The Discrete Cosine Transform (DCT) is applied over all image blocks. Afterwards, the quantization phase divides each frequency value by specific values taken from an external quantization table. Finally, the Run Lenght Encoding (RLE) and Huffman encoding compress the resulting data, which is formatted into different sections to be stored. We briefly show here the proposed expressions of the HOE 2 language. We will cover it in depth at Chapter 9.

For instance, we can tile the image into 8x8 blocks via array slicing and launch parallel encoding using indexed messages after all Block8x8 has been constructed. The tiling and encoding operations are implemented inside the Image state machine as follows pixels [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] blocks [8,8] [8] dctlines zigzag [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] intensity [8] qtable [8,8] y u v ychannel [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] As we can see, the parallel sending actions and the new scalar abstraction allow us to express parallelism in an uniform way.

Contributions

Following the structure of modeling languages, such as UML, we proposed several important features together with a new action language for the modeling of data-itensive applications.

Our propositions can be classified into three categories: the action language, object related extensions and new state machine abstractions.

The HOE 2 action language. We proposed a minimal set of actions: update and send. Updates and sending actions are ordered sequentially where each one of them can be composed to form parallel expressions. Parallel expressions can be defined over an iteration domain and, more importantly, they allow the creation of indexed messages when it concerns sending actions. We also propose a well-defined reply action, the initiator semantics. Sending of messages to the initiator object denotes a reply, which may be indexed if the initial message of the current transaction was also indexed.

We provide more expressive trigger specifications in order to capture indexed messages. Index values inside messages are closely related to the initiator semantics as it result from an implicit forwarding of index values from the initiating message. Therefore, we relate send and receive actions through specific index values.

We introduced join semantics using all conditions over specific indexes. Indeed, the index has an associated domain when defined for parallel sending actions. This condition allow us to wait for the broadcast to be completed.

More expressive models. We extended the multiplicity specification to support the modeling of n-dimensional associations. In addition to richer multiplicities, we defined an object interface that captures incoming and outcoming messages, together with precedence relations between them.

A key proposition is the HOE 2 scalar. HOE 2 scalars allows the programmer to consider scalar values as plain objects. The idea is followed by the modeling of simple arithmetics in terms of message passing. The combination of index domains to model parallel sending actions and the HOE 2 scalar abstraction enabled the modeling of parallel operations.

State machine abstractions. We extend the Statechart formalism with the concept of indexed regions. Indexed regions provide forall semantics to traditional regions via an indexed domain.

It allows, among other things, the inlining of objects and fork/join fusioning, as we will see in the following chapters. In this chapter, we present the formalization of the Highly Heterogeneous, Object-Oriented, Efficient Engineering HOE 2 language. We propose a hierarchical semantics decoupled into three operational parts: semantics of actions, transitions and configurations. We use a combination of structured operational [START_REF] Plotkin | A Structural Approach to Operational Semantics[END_REF] and denotational semantics techniques to handle non-determinism of parallel actions and meaning of single HOE 2 statements, respectively. HOE 2 semantics is strongly inspired from the informal semantics of Unified Modeling Language (UML) Statecharts [START_REF] Omg | Unified Modeling Language (UML) V2.4.1[END_REF]. C 1 FIFO using send primitives whereas all replies, triggered by initiator, from C 1 to B 1 will write to the internal B 1 FIFO. Note that objects can be shared, and hence we may have multiple producers for the external or internal FIFO buffers. However, there is always one consumer per buffer.

The message reception procedure will look at the external FIFO if the required message belongs to the object interface. Otherwise, it looks at the internal FIFO for any available message. In

Γ A a → a ∈ Γ A Γ T a → a ∈ Γ A t 1 → t 1 ∈ Γ T t 2 → t 2 ∈ Γ T Γ K t → t ∈ Γ T k 1 → k 1 ∈ Γ K k 2 → k 2 ∈ Γ K sys ∈ S FIGURE 6
.2: Hierarchical semantics separation allow us to deal with each particular problem, initiator semantics, message send/reception, message dropping policy, etc., mostly in isolation.

Domains

According to the HOE 2 language presented in Chapter 5, the intuitive semantical domain is that of objects, references, array of references and indexes. Therefore, we define the following concepts:

• The finite set of references (or locations) R, the undefined reference Null together with the lifted version R Null .

• A store mapping references to object values A = R⊆R R → O.

• Indexes as integer values, Z.

• Given above definitions, we construct the generalized set of values V = R Null + Ā + Z.

Definition 6.1. The set of communicating objects forms the system, or simply the program state. We define the system as a memory mapping slots to objects. Formally, it is defined as S = (R, A), the current object reference and the mapping A = R → O from references to objects where R is the finite set of references (or memory slots). Note that mapping A may grow as new objects are created and, hence introduced into the system. Definition 6.2. An object is defined as O = ( sm , K, E, Φ, I) where

• sm is the state machine.

• K is the current state machine configuration, which will be precisely defined later.

• E denotes the event list.

• Φ = V V is a partial function corresponding to the object binding context where V is a set of variable identifiers.

• I = R Null is the initiator reference. Definition 6.3. The message M = (R, I, M, Ψ, B) contains the sender reference, a sequence of index values I = Z, a valid message identifier, a mapping to its ordered parameter references Ψ = N → V and a boolean value that is true if we have a reply message. 1Definition 6.4. We define the event pool E = M as a list of messages.

Semantics of Actions

Let us first introduce some useful notations.

• We note sys [r →o] the new system that maps reference r to object o and keeps everything else unchanged.

• We use α to range over the HOE2 syntax sets defined in Appendix A.1.

• List concatenation • The function update is noted as

f = [f | r → o], which is equivalent to build a new function f (r) = if r = r then o else f (r).
• We also define the conditional function update

f = [f | r → o] p where p ∈ B is a condition such that f = if p then [f | r → o] else f
• We note projections with subscripts, e.g. A sys is the mapping of system sys ∈ S.

• The binding extension operator : Φ → Φ → Φ is defined as

φ φ = λv.if v / ∈ dom(φ) then φ (v) else φ(v)
The implementation of v / ∈ dom(φ ) is not shown here. For completeness, we model partial functions with functor Partial (a) = a + Undefined . 2 • We will refer to an instance of a given syntax set S corresponding to the HOE 2 grammar as α S . For instance, α state is an instance of HOE 2 .

• We use classical notation for lists v = [v i ] and note the concatenation of lists as a • b.

• We note disjoint unions as S = A + B and we use ι to describe injections into S. For instance, ι A : A → S and ι B : B → S represent the injections of S.

In the following, we consider sys = (r, A) where r is the current reference and ô = A sys (r) is the object under evaluation.

Sequential and Parallel Composition

We define a transition semantics on Γ A = action × Φ × S + Φ × S where Φ : V → V represents the local context, i.e., the bindings at the transition level. The set of actions, action , implements comma-separated parallel update and send primitives, both sequentially ordered by the separator ':'. Non-determinism in case of parallel execution and sequentiality are simple to specify thanks to the operational semantics approach. Let α action = α update :α send , they are introduced by the following rules (α update , φ, sys) → (α update , φ , sys ) (α update :α send , φ, sys) → (α update : α send , φ , sys ) ASeq (α update , φ, sys) → (φ , sys ) (α update :α send , φ, sys) → (α send , φ , sys ) ASeqEnd where parallel compositions of updates (with equivalent rules for sends) are given below.

(α update , φ, sys) → (α update , φ , sys ) (α update , α update , φ, sys) → (α update , α update , φ , sys ) AParUL (α update , φ, sys) → (α update , φ , sys ) (α update , α update , φ, sys) → (α update , α update , φ , sys ) AParUR (α send , φ, sys) → (α send , φ , sys ) (α send , α send , φ, sys) → (α send , α send , φ , sys ) AParSL (α send , φ, sys) → (α send , φ , sys ) (α send , α send , φ, sys) → (α send , α send , φ , sys ) AParSR For instance, ASeqEnd gives a new relation if there exists an evaluation on Γ A of the action α update under context φ and system sys terminating into final context φ and system sys , then the sequential statement below evaluates to the send action under such new system. From there, we continue to evaluate such send using the new system. Non-determinism is cleanly expressed with rules AParUL and AParUR. In case of parallel updates, they allow both udpates to be evaluated without prior order. It can be shown that nondeterministic inference rules have an equivalent denotational semantics on power-domains [START_REF] Reynolds | Theories of Programming Languages[END_REF]. HOE 2 has three mains actions: update, send and receive. The interpretation of one transition involve all combinations of them. Given that the communication model is "single consumermultiple producers", then an object may modify other objects in the system by pushing new messages to their event pool or it may also add new objects to the system, hence new references.

Update

We start by defining a denotational semantics of updates. Let us consider the simple one with the following evaluation rule The left-hand side of updates, var , are single or array variables while the right-hand side may also contain "new" expressions denoting object creation. We define u : update → (Φ × S) → (Φ × S) for the particular case of single variables as

v = v' u (φ, sys) = (φ , sys [r →ô ] ) where r = (φ φ ô)(v') φ = [φ | v → r] v∈dom(φ) φ ô = [φ ô | v → r] v/ ∈dom(φ) ô = (sm ô, k ô, e ô, φ ô)
We build binding contexts depending on scoping conditions. We obtain the reference value r and we update the local context φ iff the defining variable is local. Otherwise, we update the object binding context. 3 Then, we return a new local binding and system.

As mentioned earlier, the new expression creates an object, and hence a new reference into the current system mapping. We define its denotation as follows

v = α new u (φ, sys) = (φ , sys [r →ô ] ) where (r, sys ) = α new n (φ φ ô, sys) φ = [φ | v → r] v∈dom(φ) φ ô = [φ ô | v → r] v/ ∈dom(φ) ô = (sm ô, k ô, e ô, φ ô)
and n : (Φ × S) → (R × S) creates a new object referenced by r on sys , which is an extension of sys. We build the new bindings as before and update sys with the updated object o. We detail hereafter the impliciations of the creation process.

Creation. As explained in Chapter 5, the creation transition points to the entry state of the state machine. We recall the definition of new and creator:

creator

::= 'creator' id '(' param * ')' ['/' update +] to new ::= 'new' id '.' id '(' var * ')'
In order to create a new object following Definition 6.2, we have to define the following components of our initial object o 0 = (α sm , k 0 , e 0 , φ 0 , r 0 ) where 1. The state machine implementation α sm ∈ sm .

2. An initial configuration k 0 ∈ K

3. An empty event pool e 0 =

4. An initial binding context φ 0 (v), which initialize associations with the undefined reference Null .

5. The initiator is a null reference r 0 = Null Note that α new = (α id , α id , α var ) provides all these informations. The first identifier α id corresponds to the object type to be created, from which we obtain the state machine implementation.

The second one α id corresponds to the creator identifier to be evaluated. Finally, the input parameter list α var provide the local binding context to evaluate the update action (defined at the creator transition) according to the transition semantics defined over Γ A .

The initial configuration k 0 concerns the state machine semantics, Γ K , and will be introduced in Section 6.5. We will show precisely how to construct k 0 from the initial HOE 2 state.

Send

Similar to updates, we define a denotational semantics of sends Unlike updates, sending actions will modify other objects in the system by pushing messages to their event pools. The message indexes are set to 0 because we are dealing with non-indexed sends. Notation 0 stands for a single element list of zeros.

Initiator. We also have an special case here, the initiator.

initiator.α msg s (φ, sys) = (φ , sys [r →o ] ) where φ = φ φ ô o = push(A sys (I ô), α msg m (0, true, φ , sys))

The sending action is done on the initiator reference I ô of the current object ô and a reply message is instantiated.

Indexed Actions

Indexed actions concerns update or send expressions under a specific index set domain. For instance, consider the HOE 2 syntax of indexed updates

iupdate ::= '{' indexset '}' supdate
Instead of specify a denotational semantics similar to [START_REF] Dechering | Semantics and Implementation of a Generalized Forall Statement for Parallel Languages[END_REF], we developed an operational view that takes advantage of the logical deduction on presburger formulas to derive a transition semantics.

Let c ∈ int n and ix : int → Z an vector of index constants and the denotation of index values, respectively. We also use the alpha conversion noted α indexset [a/b], which replaces all occurrences of a by b into the HOE 2 index set α indexset . In the following definition and in order to keep clear notations, we consider lifted versions of our index denotational function, alpha conversion and → to n-dimensional sets.

α indexset [i/c] (α update , [φ | i → c ix ], sys) → (φ , sys ) α indexset , i < c or c < i α indexset
({α indexset } α update , φ, sys) → ({α indexset } α update , φ , sys )

AForall

The above rule gives an operational view of the forall expressions in the HOE 2 language.

Essentially, we choose a constant c that belongs to the index set, we bind the indexes to the constant and evaluate α update under this new binding. After evaluation, the constant value should not belong to the set anymore. For this reason, we take advantage of the logical relation of presburger sets under new constraints to materialize the evaluation relation.

Indexed Messages. Indexed send expressions carry additional implications: indexed message instantiation. The surrounding index set gives the index values to the message to be instantiated (see Definition 6.3). Following above forall semantics, we instantiate a message with index value c by using function α msg m ( c ix , false, φ , sys). Note that non-indexed send semantics sets index values to 0 (see Equation 6.1).

Semantics of Transitions

Receive expressions control the evaluation of actions. Let t = (α trigger , α guard , α action , α to ) ∈ trn , we define a relation on

Γ T = trn × S + S (6.2)
Let a, a ∈ Γ A , we note a → * a the transitive closure of relation → on Γ A . We define rules that rely on the previous action semantics defined over Γ A .

1. Transitions are evaluated unconditionally if there is no trigger provided that guard is true.

α trigger = ∅ ∧ α guard g (φ ô, sys) ∧ (α action , φ , sys) → * (φ , sys ) (α trn , sys) → sys
TNoTrigger where φ is the empty binding. TTrigger Note that we must pop message m from event pool of ô to construct the new system from sys .

The message binding function mbind takes also into account indexed triggers. Indexed triggers are of the form "on msg{i}()" where i captures the index value of the incoming message. Therefore, mbind binds incoming index values from m to the corresponding index variables specified in α trigger .

Actually, rule TTrigger is richer than the presented one. There are still two important facts to consider, one refers to message consumption, i.e., from which FIFO we are going to pop a message, and the other concerns the initiator setting.

State Machine Evaluation

We start by considering the non-indexed configuration model. A configuration indicates the current active states down the hierarchy of the Hierarchical State Machine (HSM). Therefore, it must model simple, composite and final conditions. The hierarchical state machine configuration is a functor K defined as follows:

K(a) = a + a × [K(a)] + End (6.3)
with injections for simple ι s : a → K(a), composite ι c : a → [K(a)] → K(a) configurations and ι end = End. For instance, if we take configurations over state identifiers K(String) then one possible configuration of the state machine shown in Figure 6.3 is:

k = ι c ('A', [ι s ('S1'), ι s ('T')]) (6.4)
Configuration (6.4) indicates that the state machine is at composite state A where its left region is at state S1 and its right one at state T.

We define the transition semantics of configurations as a relation on the lifted set state state

Γ K = K( state ) × S + S
which we note . Using the transition relation on (6.2), we introduce the set of evaluation rules shown in Figure 6.4 where α i trn is the i-th transition out of s ∈ state and the next state configuration function κn : sm → id → K( state ).

We defined two kind of inference rules and for each one of them we have two possibilities corresponding to the transition type to be evaluated. Rules KsExt and KsFinal handle simple configurations with external and final transitions, respectively. If applicable, KsExt evaluates transition α i trn and computes next configuration. KsFinal perform the same action on final transitions and evaluates to ι end . Rules KcExt and KcFinal follows the same pattern for composite configurations. The key observation is that they evaluate the transition iff all its composite configurations have terminated (ι end ). Finally, KcPar evaluates parallel regions in case KcExt and KcFinal are not applicable.

On the expressiveness of K. The functorial definition allow us to lift any function into the functor structure. For instance, let π trn : state → [ trn ] be the projection that takes a HOE 2 state and returns the list of its outgoing transitions. Given that K is a functor, we have for free the lifted version of π trn as K(π trn ) : K( state ) → K([ trn ]). That is, we can apply any function all over the hierarchal structure introduced by the functor.

In order to give a precise relation between state and K( state ), we define the entry configurator κ : state → K( state ) that given a state s returns the entry configuration down the hierarchy of states. Let L(a) be the list functor, then we define κ as follows κ(s) = ι s (s) s = state α id .α trn ι c (s, L(κr)(α region )) s = cstate α id .α region α trn and κr(region α initial α state ) = κ(s initial ) where s initial = lookInitial (α initial , α state )

Therefore, we build the entry configuration with two mutually recursive functions κ and κr. The entry configurator κ builds a simple configuration for simple states and a composite one, using κr to move across regions, in case of composite states. The function lookInitial simply returns the initial state pointed by the initial keyword.

For instance, consider state A of Figure 6.3. Entering a composite state like A from any transition implies entering all the initial states of its corresponding regions. This action applies recursively on the initial state of each particular region. Using κ, we can formally build the sample configuration shown at (6.4)

κ(A) = ι c (A, [ι s (S1), ι s (T )])
The expressive power of K also comes into play when we want to take all hierarchical outgoing transitions from κ(A):

K(π trn )(κ(A)) = ι c ([t A,B ], [ι s ([t S 1 ,S 2 ]), ι s ([t T ])])
Running example. As a running example, consider the state machine of Figure 6.3 at configuration (6.4). Let e ô = [m] be the message pool of the object under evaluation ô where message m contains the identifier M m = m1. We assume that system sys contains only one object, i.e., sys = (r, [r → ô]).

The state machine evaluation of ô starts at the configuration level, Γ K . We observe that the current configuration is composite ι c , then rule KPar applies. The rule asks to evaluate a particular region. Let us take the left region configuration of state A, i.e., ι s ( S1 ). The configuration of this region is a simple one where we see that rule KsExt applies. Such rule evaluates the configuration into another one providing that there exists an evaluation (relation) on Γ T such that we have an external transition which evaluates to sys .

(
(ks i , sys ) (ι c (s, [• • • , ks i , • • • ]), sys) (ι c (s, [• • • , ks i , • • • ]), sys ) KcPar FIGURE 6

.4: Evaluation rules for configurations

Indeed, from state S1 we can go to S2 because message m1 is present into the message pool of the object under evaluation as stated earlier, then rule ETrigger applies. In this particular case we have no action. Nevertheless, we see that the idea applies hierarchically. That is, rule

ETrigger will try to evaluate the action on Γ A .

Finally, the new configuration will be ι s ( S2 ) under system sys . In sys , object ô will not contain message m1 anymore. Note that in general k and k may not have the same hierarchy.

Indexed Configurations

We extend the hierarchical configuration K defined in (6.3) as follows

K(a) = a × [IK (a)] + a + End IK (a) = K(a) + (Z n → K(a))
We model the indexed configuration IK (a) as a disjoint union of the classical configuration, Given the underlying model of Int and Definition 6.5, we denote scalars relying on such a model with P (Z). In consequence, we must extend the store mapping defined as

A = R⊆R R → O
to support scalar as well

A = R⊆R R → O + P
The operational transitions as described in the Int interface combined with the scalar model play a central role in the semantics of applyon.

Applyon Semantics

Although the applyon is defined inside the update action, we developed its semantics here as it is strongly related to the semantics of HOE 2 scalars. We recall its formal definition hereafter:

applyon ::= 'applyon' id '(' var * ')'

A valid instance of applyon inside Int is shown at Listing 6.3. The expression is only valid in the context of an scalar object, i.e., ô is an scalar, and takes HOE 2 scalars as parameters. The operation addOp, which is formally related to addition operation on Z, applies on the current object value v ô and its parameter value v p where p = φ(p). 4 We define the applyon semantics such that it returns a new scalar value defined as

s 0 = (α sm , k 0 , , Null , v ô + v p )
In the example of Listing 6.3, this value is binded through a new reference in the local binding context of ô and added to the system. It is then sent as a reply message to the corresponding initiator.

Contributions

In this chapter, we presented the formalization of the HOE 2 language in a layered and composable manner. Although not exhaustive, we showed how the approach let us formalize in a modular way almost all the particularities of an action language like HOE 2 based on communicating HSMs. In particular, we did not specify array value accesses, error conditions and all semantics.

We considered parallel and sequential compositions at the action and state machine level. HOE 2 supports object creation, detailed by our semantics at the action level. At this level, we also specified initiator semantics, which creates reply messages. The initiator is modified at the transition level. Such interaction between two stages demonstrates how the hierarchical approach enable the complete specification of an unique concept in a structured way.

The functor abstraction for the state machine configuration leads to a clear operational view of state machine steps. Moreover, the indexed region semantics turns into a natural and clear extension to the functor structure. function-like state machines. The approach allow us to make a clear distinction between structural definitions and execution tasks that implement the state machine. The tasks use the structure instances to communicate with other tasks. It is high-level enough and implementation independent, similar to the HOE 2 model itself, because it preserves the type definitions and the state machine hierarchy.

The IR exposes implicit information in HOE 2 such as initiator definitions, message types and variables, the "this" variable pointing to the owner object of the current state machine, etc.. For instance, an HOE 2 object cannot send messages to itself in an explicit manner. There is no such support as it may lead to undesirable conditions when considering actual implementations with bounded message channels. The IR, however, poses no restriction concerning self-sending actions as they are forbidden by the input language.

Overview

In order to present the general structure of the IR, we will introduce a simple -but still rich enough -translation example of the model shown in Figure 7.1 for the Pixel object.

The translation of Pixel type definition is shown in Listing 7.1. It is essentially the same with a slight change to the syntax of multi-valued association types.

While type constructors remain close to the HOE 2 ones, the state machine is divided into two top level block expressions, fsm and creator, where both of them are composed by imperative statements. The statements preserve the structure of the HSM and HOE 2 action language.

Creator

Consider the translation of Pixel creator RGB in Listing 7.2. The creator signature is preserved and implicit actions such as structural allocations (alloc) and state machine running are exposed UBB_ADDING:

this.y = _m5_added.res; reply this src takeY<Float> this.y; done this; LISTING 7.5: Reply (Pixel Part V)

Replying

Once the computation is done, Pixel state machine replies to the sender providing it the result inside message takeY as shown in Listing 7.5.

It stores the final computation result coming inside message variable _m5_added (issued by a Float object) and, using reply, build message takeY and specifies sender (this), destination (src), message type and parameters.

In conclusion, the intermediate representation separates type definitions from state machines based on the implementation idea of object-oriented paradigm. It keeps interface and association definitions, exposes object and message variables where the former are seen as channels and the latter are struct-like variables grouping message formal parameters. We found specific instructions implementing communication primitives and, most importantly, the parallelism is preserved. In the following sections, we introduce the IR specifics with meaningful examples.

Structure

Formally, the IR has the following top-level statements Because the IR handles explicit message variables, it also introduces message types.

Message types

Message types have a particular syntax. They are composed by an identifier followed by a list of parameter types. As discussed in previous section, we separated object type definitions from the state machine.

The latter being further decoupled into two different blocks: creator and fsm .

Creator

The creator, introduced by the keyword creator, must have an associated type and identifier and it may define a variable number of parameters.

creator ::= 'creator' ID '.' ID '(' param defs ')' '{' creator stmt '}'

The allowed statements inside creators are defined as follows We may have parallel statements, a start directive and forall block expressions. No communication primitive is allowed inside creators. Its main purpose is preserved: allocation, initialization and object running. As described earlier, before initializing the object we need to allocate the structure using directive alloc. Once the object is allocated and initialized, start runs the indicated state machine. It takes two arguments, the state machine name to run and its associated structure.

The forall block defines an index domain. Similar to index domains in the HOE 2 language, it is composed by a list of index variables and a constraint formula. It is a handy statement when initializating multi-valued associations. The Listing 7.2 shows a simple creator instance.

In the following, we explain extensively update and send statements within the context of state machines.

Hierarchical State Machine

The state machine is introduced using the token fsm.

| done

We have a list of, optionally labeled, imperative statements: parallel statements, variable declarations, wait and wait-in statements, unconditional branching goto and an object termination instruction done .

Parallel Statements

In contrast to HOE 2 , the IR mixes in a single parallel expression send and updates. Therefore, it is defined as follows Send and updates can be enclosed inside index domains providing forall semantics. We use an explicit keyword, forall, with its index sets between brackets.

Send

There are three kind of sending commands: single send, indexed send and reply. They are defined as follows: In order to send a message, sendfrom needs source and target objects, a message type and its required parameters. The indexed send is similar to the first one plus a list of arithmetic expressions between brackets. This notation allows the initialization of indexes when building indexed messages.

At the overview, we presented three parallel sending that we recall in Listing 7.6. In order to broadcast messages over multi-value associations, we make use of forall expressions. Listing below shows a simple example, which is taken from the translation of Image to Pixel broadcasting shown at Listing 7.7.

We found an indexed send that builds a one-dimensional message with sender this, destination this.pixels[i], message type get<> and index value i.

We send replies with command reply that serves to the implementation of HOE 2 initiator semantics. In the IR context, reply must have as a target object a variable defined at some receive expression. For instance, consider the following reply already introduced in Listing 7.5

reply this src takeY<Float> this.y;

Note that src was defined at the top receive expression wait this for (_m1_getY, Object src) = recv getY<> then when _m1_getY goto SBB_GET_Y;

Update

The update statements are defined as The first one is a classical update operation between two variables. It is followed by an association initializer, an object creation directive and a new expression applyon that denotes "in-place" operations. Therefore, we can create pixel objects from initialized variables in the following way

Int|3| inraw_slice = { rgb[3 * i] rgb[3 * i+1] rgb[3 * i+2] };
this.pixels[i] = create Pixel.RGB inraw_slice;

LISTING 7.8: Variable initialization and object creation

As shown in chapter 5, the scalar object abstracts away scalar operations via operational transitions. They are materialized as "in-place" operations at the IR level using command applyon.

It takes an object variable to apply a type of operation, which designed by the name of the operational transition, and its required parameters.

Int res_added = applyon i Int'add msg_add.a; LISTING 7.9: Apply an operational transition For instance, Listing 7.9 apply the operational transition Int'add on integer i with parameter coming from a certain received message called msg_add. We will discuss more about this instruction in chapter 8. Intuitively, given the type of operational transition, applyon is mapped directly to the corresponding operator that matchs the target language semantics at code generation time.

Branching

The IR supports conditional and unconditional branching. Both waits define message variables and have one then branch without guard. They wait on this until the indicated messages specified at when expressions are present. Additionally, the first one defines also a source variable object that represent the sender. After the object from which the wait statement is going to listen, we defined a comma-separated list of receive expres- The index variable i is available at all reachable statements. Message variables can only be declared and defined at receive expressions.

After introducing the list of receives, waitthen checks for message presence, evaluates a possible triggering condition and branches to the specified label.

waitthen

::= 'then' ['when' var +] ['if' guard ] 'goto' ID
Finally, waitin has the same structure as wait with additional support for parallel regions. We show in Section 7.5.5 an instance of this statement.

Regions

As mentioned earlier, the IR preseves the hiearchical structure of the original state machine. The statement waitin is composed by a list of regions, which can be either simple or indexed. They are defined as

region ::= sregion | iregion sregion ::= '{' fsmstmt '}' iregion ::= '[' indexset ']' '{' fsmstmt '}'
This definition closely follows the concept of indexed regions proposed by the HOE 2 language.

Translating HOE 2

As we have shown in previous sections, the IR preserves most of the information coming from HOE 2 while making them more explicit. We even found some equivalent constructions such as objects with only syntactic modifications. Indeed, objects together with its structural features are translated almost unchanged into object and/or scalar instances. In addition, container type constructors are also preserved. The fundamental change is found at the state machine level. We separate it into creator and fsm "functions". Most of these translations are relatively straightforward to perform as we have thoroughly shown with plenty of examples. However, some key characteristics of HOE 2 need more precision on how the translation is to be done. Therefore, we consider several points needing further explanation For the sake of clarity, we recall some notations already introduced in Chapter 6. We will refer to an instance of a given syntax set S corresponding to the HOE 2 grammar as α S . For instance, α state is an instance of HOE 2 state and its projection on transitions is noted π trn (α state ). We use classical notation for lists v = [v i ]. Given a disjoint union set S = A+B, we use subscripted injections ι A : A → S and ι B : B → S to represent elements of S.

Compilation of States and its Transitions

We presented two statements that allow to check for incoming messages: wait and waitin.

Both of them specify a group of messages to wait for and their corresponding then branches.

HOE 2 state translates into a wait statement and a set of sequential statements (basic blocks) concerning the different transition actions.

Actions

Let α state be a state and t ∈ π trn (α state ), we build a set of basic blocks BB state = {bb t } for each transition action a ∈ π action (t). We define the label of bb t as #bb t , which given that bb t ∈ fsmstmt it corresponds to the label of its first statement. BB state will be the set of all possible destination of then branches. All basic blocks resulting from external transition actions terminate with unconditional branches to target state identifiers. In case of final transitions, the basic block terminate with statement done this, which effectively finishes the current state machine.

Transition

We separate the translation of transitions into two steps: collection of triggers and computation of then branches.

Collecting triggers. We create a multiset from transition triggers M Set(π trg (t)) = (T rg, m), also noted M Set t , where T rg is the set of triggers and m : T rg → N the multiplicity of each trigger. We will refer to this multiset tuple as T rg t and m t . Then, we define a special multiset union where we take for each element the maximum number of elements between both sets. Its defintion is shown hereafter

M Set t M Set t = (T rg, m) T rg = T rg t ∪ T rg t m(trg) = max(m t (trg), m t (trg))
Above definition allow us to create a common set of receive expressions. Indeed, we define the final multiset W R of wait triggers as W R = t∈πtrn(αstate)

M Set t . To each wr ∈ W R, we associate a message variable rv i wr , which is the i-th trigger kind of wait wr. From this set of variables, we build the receive expression list recv = [rv i wr = recv wr] (7.1)

In order to build the message variable list for each transition t, we take M Set t and we proceed as before, i.e., building a list of message variables wv i wr for each trigger kind wv ∈ M Set t , such that wv i wr = rv i wr . It yields same variable names at recv and when expressions. The when expressions for transition t is when t = when wv i wr (7.2)

Compute "then" branches. Assuming a straightforward translation g t of guard condition for transition t, we build the list of then expressions as then = [then t ] (7.3) then t = then when t if g t goto #bb t (7.4)

Collecting definitions (7.1),(7.2) and ( 7.3), the wait statement is defined as waitstmt = π id (α state ): wait this for recv then (7.5)

We added a label corresponding to the state identifier such that the compilation of incoming transitions have consistent branch destinations. We did not take into account indexed receives but the translation procedure remains the same. Receive expressions coming from initiator conditions will be discussed later.

Propagation of Index Domains

There is a subtle difference between indexed receives at HOE 2 and IR. In the former, index domains at send and receive are syntactically linked whereas in the latter we have decoupled them. For instance, consider the following HOE 2 indexed send and receive pairs Therefore, the compilation procedure will propagate send domains to the generated indexed receives as shown by Listing 7.11.

Defining Initiators

According to the HOE 2 semantics, initiators are implicitly defined following the object interface. In the IR, we translate initiator semantics with concrete variable definitions as we informally presented in the overview 7.1. b. Given that sender variables can be defined using the same name at different receive expressions, we may have control-flow dependent senders.

A correct translation of initiator semantics asks for a data-flow analysis. The problem can be stated as follows

Reaching Definitions of Initiator. Given a HSM over the actions defined by the HOE 2 language, a set of transitions defining the initiator and replying transitions (initiator), we need to "structurally" find the correct initiator def-use chain. By structurally, we mean a solution that takes into account nested state machines. We have a special case of reaching definitions where we deal with only one variable [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF]. In order to develop the underlying translation process, we introduce a simple state machine model SM = (S, T ), where S is the set of states with transitions T ⊆ S ×S. We define its complement SM = (T, U ) where transitions become vertices of the graph and (t, t

) ∈ U iff ∀s 1 , s, s 2 ∈ S | t = (s 1 , s) ∧ t = (s, s 2 ).
The predecessors of t is preds(t). The complement state machine allow us to think of SM as a control-flow graph of statements. We introduce the reaching definition set on SM at the action of transition t as rd t ⊆ T and we formulate it in the following way.

rd t =    {t} if t reacts to an external message p∈preds(t) rd p otherwise (7.6)
That is, if transition t contains a trigger defined as an external input message by the interface then t will define the initiator, effectively "killing" any other incoming definition. Otherwise, we propagate the information. Clearly, the computation of rd t converges since it is a monotone function over the complete-lattice given by the powerset of T .

For instance, the Pixel state machine at Listing 7.1 and its complemented version are described at Figure 7.3. Given that t 1 is the only transition that triggers on an external message, namely getY(), we obtain the following trivial solution

rd t 0 = ∅ rd t 1 = {t 1 } rd t 2 = {t 1 } rd t 3 = {t 1 } rd t 4 = {t 1 }
Transition t 4 is the only transition to use on initiator and, by reachability condition, we should assign to the receive expression of getY() the same variable name as the reply statement generated from transition t 4 . This constraint is satisfied with sender variable src, as shown by In order to take into account the state machine hierarchy, we extend SM with hierarchical states, i.e., S = SS + CS where CS = [SM ] (a list of nested state machines). A key observation is that sender variables defined at nested states are not visible outside due to scoping. However, the converse is not true. We should be able to send replies on an initiator possibly defined at higher nesting levels. Roughly speaking, it means that our reaching definition can be applied per nesting level taking into consideration initializing conditions coming from upper ones.

Therefore, we redefine our complement state machine with hierarchical nodes HT = ST + CT where CT = [SM ], i.e., we preserve compositional information. We compute the complement as follows SM = (HT, U )

• For each t = (s, s ) ∈ T , we have ht ∈ HT defined as

ht = ι CT ([sm]) if s = ι CS ([sm]) ι ST if s = ι SS Note that ι CT ([sm]
) means that we apply the computation recursively.

• We build the relation U as before:

(ht, ht ) ∈ U iff ∀s 1 , s, s 2 ∈ S | t = (s 1 , s) ∧ t = (s, s 2 )
Let sm i be some complemented state machine with initial transition ht i and let ht = ι CT ([sm i ]).

That is, we have a hierarchical node from another complement state machine sm on which sm i is nested. Then, we add to the reaching definition formulation the initializing condition rd ht i rd ht before solving into nested levels.

As a result, the proposed defuse chain solution allow the translation procedure to name sender variables correctly over hierarchical state machines.

"all" Condition

The "all" keyword refers to the HOE 2 condition that is true when all messages have been received (see section 5.4). The IR preserves such information by attaching it to message variables instead of indexes. For instance, Figure 7.4 shows the translation of an indexed receive together with its all condition. According to the compilation of states presented earlier, the indexed receive at line 7 contains two possible branches, one to the basic block of the translated transition action and a second one to the final basic block. The compilation process attachs the all condition of second branch to the message variable associated to message takeY<Float>.

Indexed Regions

As pointed out early in this section, the hierarchy of HSM is provided by waitin statements.

The equivalent IR expression of an indexed region is shown in Figure 7.5.

semantics in the same way HOE 2 does, flexible communication primitives and indexed regions, among other features.

In order to give a precise idea of the HOE 2 view at the IR level, we showed some equivalencies through program examples and completed it with specific translation procedures for more evolved concepts coming from the HOE 2 language. We will show in the following chapter how to take advantage of the IR constructions to build an state machine optimizer.

Based on the Intermediate Representation (IR) of Chapter 7, we developed the optimizing compiler. The compiler takes advantage of the proposed Highly Heterogeneous, Object-Oriented, Efficient Engineering HOE 2 features, preserved at IR, to optimize the model and produce highly efficient code.

Challenges

In the context of optimizations for communicating automata, we face a certain number of difficulties. One challenge concerns data dependencies. Efficient code generation of data-intensive applications calls for an accurate knowledge of data dependencies. Unfortunately, they are decoupled as asynchronous message exchanges between concurrent objects. That is, messages have a dual purpose, synchronisation and data carriers. The former imposes a precedence relation between computations of concurrent objects and the latter add a layer of input-output data relations on the precedence one. Ideally, we would like to find the data-flow of a dynamic network of communicating automata. 1 However, it is widely known that even in the case of static networks the problem is undecidable [START_REF] Peng | Data Flow Analysis of Communicating Finite State Machines[END_REF]. In [START_REF] Peng | Data Flow Analysis of Communicating Finite State Machines[END_REF], Peng and Puroshothaman formulate the problem of communicating automata as a set of recurrence equations over the domain of infinite streams of messages. The show that given two objects A and B we will not be able to link a certain computation outcome from A to its corresponding use in B. It is equivalent to saying that the chain of data definitions and uses cannot be precisely determined, which is a major issue when looking for performance in computationally intensive applications based on state machines. On this context, we consider the hypothesis of instantaneous reaction to enable strong optimizations.

Instantaneous Reaction

We introduced in Chapter 5 the definition of the object interface. In addition to input and output messages accepted by the object from the user perspective, we can add a precedence relation between them. The precedence relation allows us to assume that an exported input-output message relation will hold under all program contexts. That is, it ensures that a given response will eventually come back. However, it does not specify precisely when. The handling of such a request may not be atomic and external objects may undertake other actions in the meantime.

For instance, let A and B be two objects where A is the user of B, and B exposes the relation

m 1 → m 2 , i.e.
, message m 2 will be sent as a response to the reception of m 1 . Since the interface level exposes a transactional semantics, the compilation flow can be made modular and rely on the instantaneous reaction hypothesis. That is, among the possible orderings, one may safely assume that when object A sends message m 1 to B, B will handle it and send back the result according to its interface definition at the same logical instant from A's perspective (in the absence of deadlocks among internal transitions of B).

Mutability

Another issue is mutability, directly related to escaping conditions. When looking for optimiza- We may reformulate (a) and ask whether object B escapes from the context of A. If it escapes, then B is a shared object otherwise it is not. Therefore, we must define when an object escapes from the context of another, which leads to the classical escape analysis heavily used in languages like Java to guide stack allocations, inlining and scalar replacements [START_REF] Blanchet | Escape Analysis for Java TM : Theory and Practice[END_REF][START_REF] Kotzmann | Escape Analysis in the Context of Dynamic Compilation and Deoptimization[END_REF]. Let us rather define when an object does not escape. In the context of HOE 2 , we have a set of particular conditions 1. The inlinee is an scalar object: according to properties introduced in Chapter 5, any action on scalar objects (communication for instance) does not have internal side-effects.

2. The inliner creates the inlinee and never shares it. Note that there are two ways to share an object in HOE 2 , either send it via message passing or create another object that accepts it as its creator parameter.

The Optimizing Compiler

The optimizing compiler chain is shown in Figure 8.1. The basic idea of the compilation flow is to transform the IR code to reach patterns for which we know that an efficient translation to the target language exists. Starting from the IR, the compiler builds a Hierarchical Control-Flow In contrast to other traditional branch schemes of imperative code compilers, the control flow cannot be reduced to two successors per basic block (see wait and waitin branches at Section 7.4.4). We apply all transformations recursively on the control-flow structure, i.e., across regions.

Once the model is fully optimized, the C/OpenCL backend generates code with specific runtime calls for object creation, termination, state machine running, send and receive. In addition to these runtime routines, it also needs to know how to translate native operations modeled as operational transitions. For this reason, a mapping between IR operations and target operations is provided separately (source.cc) as it concerns only code generation.

Before getting into the explanation of transformation passes, we introduce some terminology and notations used through this chapter.

Notations. We define a Hierarchical Control-Flow Graph as a graph HCF G = (BB, E)

where BB ∈ fsmstmt and E ⊆ BB × BB. We call it hierarchical because of composite statements such as waitin containing nested control-flow graphs. Branch instructions wait, waitin and goto, as well as done terminate basic blocks and thus we called them terminators.

Analyses

In this section, we present our specific analyses used by most of the transformations passes in the compilation chain.

DefUse Chain: Structured Analysis of Reachable Definitions

The variables in the IR can be local to the object, i.e., defined as object associations, or private, declared inside creators or state machines. By design choice, the declaration of arbritrary global variables is not allowed. Instead, they result from escaping conditions: shared local variables are considered to be global.

The object defines the local context of variables, or associations. Local variables allow the object to pass definitions from creator to its related state machine, which provides an initial set of definitions at the fsm entry. In the same way, the fsm provides an initialized set of definitions to its lower layers, or regions (waitin). Figure 8.2 describes pictorically the visibility layers of definitions with classical scoping constraints. Only local variables are visible at all levels of the hierarchy.

We obtain the chain of variable definitions and uses, namely the DefUse Chain, by solving the problem of reaching definitions in the form of data-flow equations. In order to show the structured approach of our analysis in the IR, we define a forward data-flow problem on the HCFG with a higher order transfer function φ:

ins(bb i ) = p∈preds(bb i ) outs(p) (8.1) outs(bb i ) = φ(bb i )(ins(bb i )) (8.2)
and we define φ inductively on basic blocks (α f smstmt ) as follows

φ(α f smstmt ; α f smstmt )(d) = φ(α f smstmt ) • φ(α f smstmt ) (8.3) φ(α f smstmt , α f smstmt )(d) = φ(α f smstmt )(d) ∪ φ(α f smstmt )(d) (8.4) φ(s)(d) = DEF s ∪ (d \ KILL s ) (8.5)
In (8.5), we have the basic kernel of data-flow equations. We defined φ such that it returns our transfer function over the complete lattice of sets of defining statements for each statement s. DEF s correspond to s if s is a definition and KILL s is composed by all other statement defining the same variable that s defines. On the way, we consider sequential composition (8.3) and, a missing term in classical formulations, parallel statements (8.4).

The structured approach comes into play when we want to account for the effect of structured statements such as waitin with nested regions. First of all, we need to be able to input any initial condition coming from upper layers. Therefore, we extend (8.1) as

ins(bb i ) = ins 0 (bb i ) ∪ p∈preds(bb i ) outs(p) (8.6)
The term ins 0 (bb i ) accounts for initial conditions of each basic block, which can be seen as having another basic block entering bb i .We note the data-flow solution under initial conditions I as ins(bb)| I and outs(bb)| I .

A more subtle extension concerns Equation (8.5), which we extend as follows.

φ(s)(d) = DEF s (d) ∪ (d \ KILL s (d)) (8.7)

| id

In the formulation, we handle different granularities of variable definitions. Considering fine grain definitions, i.e., inside object associations (or fields), allow us to optimize out dead definitions of associations when dealing with non-global variables. Figure 8.3 describes three granularity levels concerning variable definitions where we handle the first two ones while being pesimistic over the last one. That is, a definition of an element inside a multi-valued association, v.f3[range] for instance, is considered to kill any incoming definition of such association, v.f3, regardless of the indexing access. However, a definition of v.f3 does not kill other definitions of v.

Message Dependency Analyzer

In Chapter 5, we presented the definition of interfaces where we indicate valid input and output messages as well as precedence relations between them. The IR preserves such information and the message dependency analyzer relies on it to build a set of related send and receive expressions inside the state machine. For instance, consider the running example of Listing 8.1. At Line 3, we have three parallel sending actions to scalar Int and according to its interface, it sends back three multed<Float> messages. Two of them are captured in wait expression at Line 6 and the last one is taken at Line 11. Which mult<Int>, and hence which sending expression, is related to which multed<Float> is not specified; it is actually not necessary to do so in the computation being modeled.

Another related question concerns incoming FIFO states. Consider an object A communicating only with object S, where S defines a set of single input-single output operational transitions

T S = {(m i , n i )} such that message n i is a response to m i . Let ← - m S i = n i iff (m i , n i ) ∈ T S
and HCF G A = (BB A , E A ) the control flow of A's state machine. Figure 8.4 shows the FIFO state problem when trying to relate send and receive expressions. It describes an HCF G A of object A communicating with S where (m 1 , m 2 ) ∈ T S . In 8.4(a), the FIFO of A is an empty list and we can safely assume that sendfrom m1 is related to the next wait expression according to T S . On the other hand, if the FIFO already contains a copy of m2 generated by a response to another sendfrom, the described one is not going to be related to next wait anymore (see 8.4(b)). Therefore, whether sendfrom m1 is related to the next receive expression or not will depend on the incoming FIFO state.

In order to relate send and receive expressions, we need to precisely track the FIFO state of two communicating objects. Given that it is an undecidable problem in general as explained earlier, we narrow the analysis to objects comunicating with other objects that specify precedence relations for all of its valid input messages.

We propose to build a set F of terms (or equations) for each branch of the HCF G A in the state machine such that each equation f represents a possible FIFO state. The set F describing such state is inductively defined as follows:

• Message m ∈ F • Variable v ∈ F sendfrom m1 ... ... wait ... when m2 goto bb2 f A = ∅ (a) Empty FIFO sendfrom m1 ... ... wait ... when m2 goto bb2 f A := m2 f A := m2 • m2 ... f A := m2 • m2 f A = m2 X (b) Initialized Incoming FIFO FIGURE 8.4: Send-receive problem • Concatenation: If f, f ∈ F then f • f ∈ F • Alternation: If f, f ∈ F then f + f ∈ F • Multiset union: If f, f ∈ F then f f ∈ F • Receive: If f, f ∈ F then f ← f ∈ F
The meaning of above operators is the standard one with the exception of operator receive, f ← f . It is intended to represent an element-wise matching operation between two FIFO states where f represents a waiting state and f the input state. Under the hypothesis of instantaneous communications introduced in section 8.1, we are going to consider wait and sendfrom statements as generating expressions of waiting lists of messages and input list of messages, respectively. Definition 8.1. Given F, we define a suffix partial order on FIFO states. An empty state is lower than any other: ∅ ≤ f . By induction, we define the ordering as follows ∀f, f , m, m ∈ F,

f • m ≤ f • m iff m = m and f ≤ f . Remark 8.2. The suffix partial order is preserved under right concatenation: f ≤ f ⇒ f • g ≤ f • g for any g.
We start by defining an abstraction function working on basic blocks that looks only on sending simple sends (8.11) while ignoring everything else that does not involve communication (8.12).

actions ψ : BB → F ψ(α f smstmt ; α f smstmt ) = ψ(α f smstmt ) • ψ(α f smstmt ) (8.9) ψ(α f smstmt , α f smstmt ) = ψ(α f smstmt ) ψ(α f smstmt ) (8.
Then, consider a statement terminator wait w = wait this recv then where then = [then i ] and when i (w) gives a multiset of messages corresponding to the triggers listed in the when clause of then i .

Given ψ and a wait terminator w bb i of basic block bb i , we define a term for each

f ij ∈ E A such that f ij = when j (w bb i ) ← bb h ∈preds(bb i ) f hi • ψ(bb i ) (8.13)
Definition (8.13) establishes the expression value of all output branches of basic block bb i following the FIFO state changes that bb i introduces by itself plus all possible incoming branches.

Figure 8.5 sketches the analysis. At the entry of bb3, we do not know the incoming FIFO state.

Therefore, we consider alternatively both of them, f 13 and f 23 . The first sendfrom of bb3 will push the response to m4 to the current unknown state. The only output branch of bb3 will forward such state after having consumed message m5. We proceed this way for all edges of the control flow as described by (8.13).

The analysis is based on the idea that receive equations can be reduced. That is, we can apply the receive operator recursively according to the following rules

(m • f ) ← (m • f ) = f ← f if m = m (m • f ) ← (m • f ) = (m • f ) ← f if m = m ∅ ← f = f otherwise (8.14)
The first rule of (8.14) matches head messages of waiting and input FIFO states. The second one implements the dropping semantics proposed in Chapter 6 and the last one says that if there is nothing to wait for then we forward the input state as is. We recall that each message has a generating expression, for instance sendfrom m4 generates ←m 4 . A matching between two messages will imply a relation between two generating expressions. For the sake of clarity, generating expressions are not shown in the analysis. There is a missing rule not shown in (8.14): f ← ∅. It stands for dead-lock as we are waiting on a empty input state.

Remark 8.3. The partial function f (x) = cst ← x is monotone and decreasing: g = cst ← f ⇒ g ≤ f . It follows directly from its definition (8.14).

Algebraic rules. Some basic algebraic properties hold on F

(a + b) ← c = (a ← c) + (b ← c) c ← (a + b) = (c ← a) + (c ← b) (a + b) • c = (a • c) + (b • c) c • (a + b) = (c • a) + (c • b) (8.15)
meaning that the alternation can be pushed upwards in order to reach a canonical form.

Lemma 8.4. We note F to the set F not containing terms of the form f + f . Then, from the system of equations given by (8.13) and using rules (8.15), f ij can be rewritten to the following form

c = i f i called canonical such that f i ∈ F.
Proof. By applying the second rule on (8.13), we directly obtain the canonical form of f ij

f ij = when j (w bb i ) ← bb h ∈preds(bb i ) f hi • ψ(bb i ) = bb h ∈preds(bb i ) when j (w bb i ) ← f hi • ψ(bb i )
Lemma 8.5. The canonical form is preserved under variable replacement.

Proof. We replace f hi by its defining equation into (8.13)

f ij = when j (w bb i ) ← bb h ∈preds(bb i )   when i (w bb h ) ← bbg∈preds(bb h ) f gh • ψ(bb h )   • ψ(bb i )
By applying the second rule, we obtain

f ij = bb h ∈preds(bb i ) when j (w bb i ) ←   bbg∈preds(bb h ) when i (w bb h ) ← f gh • ψ(bb h )   • ψ(bb i )
and third rule give us

f ij = bb h ∈preds(bb i ) when j (w bb i ) ← bbg∈preds(bb h ) (when i (w bb h ) ← f gh • ψ(bb h )) • ψ(bb i )
to finally apply second rule again

f ij = bb h ∈preds(bb i ) bbg∈preds(bb h ) when j (w bb i ) ← (when i (w bb h ) ← f gh • ψ(bb h )) • ψ(bb i )
By induction hypothesis we have that f gh has also a canonical form under variable replacement.

Following the same reasoning as before, we achieve again a canonical form. Therefore, f ij has a canonical form under variable replacement.

An additional rule holds under the guarantee of state machine progress

(f ← f ) • f = f ← (f • f )
Assuming progress we have g = f ← f such that g ≤ f (suffix partial order) because receive applies on head messages of f only, by receive rules (8.14). Then f ← (f • f ) is also going to apply on head messages of f only and both expressions will yield the same result, g • f .

There are still two important questions around this analysis. The first one is related to type correctness of equations. The last one concerns the resolution of F = {f i } equations in presence of control-flow loops, which implies solving of recurrence equations.

Type correct receives. According to equations (8.9) and (8.10), ψ should output a list of a multiset of messages. However, the application rule of receive operator is defined to work on lists of messages. Therefore, we transform multisets of messages to the combinatorial alternation of lists before evaluation. Recurrence in FIFO states. Given the system of equations F = {f ij } obtained from the HCF G, we solve F in topological order if there is no loop in the control-flow. Otherwise we need to deal with recurrence equations and initialization issues.

Consider a rewritten version of equation (8.13)

f ij = w ij ← bb h ∈preds(bb i ) f hi • ψ i
where w ij = when j (w bb i ) and ψ i = ψ(bb i ). Figure 8.6 shows a simple looping instance where we get the following set of equations

f 12 = w 12 ← (f 31 + f 01 ) • ψ 1 = w 12 ← f 31 • ψ 1 + w 12 ← f 01 • ψ 1 f 23 = w 23 ← f 12 • ψ 2 f 31 = w 31 ← f 23 • ψ 3 (8.16)
Solving for f 31 , we have

f 31 = w 31 ← (w 32 ← (w 12 ← (f 31 + f 01 ) • ψ 1 ) • ψ 2 ) • ψ 3
and using rules (8.15) to move up alternation

ep = w 31 ← (w 32 ← (w 12 ← f 01 • ψ 1 ) • ψ 2 ) • ψ 3 lp = w 31 ← (w 32 ← (w 12 ← f 31 • ψ 1 ) • ψ 2 ) • ψ 3 f 31 = ep + lp
Naturally, f 31 accounts for both paths in the loop, the loop itself lp and its entry ep. To solve the looping term lp, we have to find an initialisation value for f 31 . The initalising value cannot be randomly taken. Both terms impose a set of constraints on the values of f 31 . In general, we will always obtain the alternation form under variable replacement as shown by lemma (8.5).

By using remark (8.3), we deduce from (8.16) the following constraints

f 31 < f 23 • ψ 3 f 23 < f 12 • ψ 2 f 12 < f 31 • ψ 1 f 12 < f 01 • ψ 1 Applying (8.2) to f 23 < f 12 • ψ 2 , we obtain f 23 • ψ 3 < f 12 • ψ 2 • ψ 3
and given that f 31 < f 23 • ψ 3 we deduce that

f 31 < f 12 • ψ 2 • ψ 3
Following this reasoning, we get

f 31 < f 31 • ψ 2 • ψ 3 • ψ 1 f 31 < f 01 • ψ 2 • ψ 3 • ψ 1
The first inequality corresponds to the loop path and the last one to its entry. We can see that the former holds for any n ≥ 1 such that

f 31 < ψ n 231
where

ψ 231 = ψ 2 • ψ 3 • ψ 1 .
We note the initial value of f as f 0 . If f 31 is less than both terms, i.e., f 31 < f 31 ψ n 231 ∧ f 31 < f 01 ψ 231 , then it is necessarily lower than its greater lower bound on the semi-lattice of suffix partially ordered FIFO states

f 0 31 = ψ n 231 f 01 ψ 231
Note that f 01 is a constant value. Finally, we can safely take this value as its initial one to solve F .

Generalizing this result, we define the initialization value f 0 ij as

f 0 ij = ψ n p h∈preds(j)∧h =i f hj • ψ p
where p is a specific loop path of basic blocks in the backwards direction starting at bb j .

In order to show a running instance of the analysis, we consider the control-flow of Pixel shown in Figure 8.7 where we highlighted all communication primitives. We extract the following constant definitions where we denote lists with square brackets

ψ 1 = [{(s 1 , multed), (s 2 , multed), (s 3 , multed)}] ψ 3 = [{(s 5 , added)}] ψ 2 = [{(s 4 , added)}] w 12 = [{(r 1 , multed), (r 2 , multed)}] w 34 = [{(r 5 , added)}] w 23 = [{(r 3 , multed), ( r 4 , added)}]
Here we expose generating expressions, which are not shown in the analysis to facilitate its presentation. For instance, we have three parallel sends s 1 , s 2 and s 3 , in basic block bb1 and the next two ones s 4 and s 5 in basic blocks bb2 and bb3, respectively. Writing down receive expressions (see (8.13)), it follows

f 12 = w 12 ← ψ 1 f 23 = w 23 ← f 12 • ψ 2 f 34 = w 34 ← f 23 • ψ 3
Before solving, we need to make type correct receives. Given that operands of a receive operator must be a list of messages and we have instead a list of multisets of messages, we convert them to corresponding combinatorial alternation of message lists as discussed earlier. For instance, w 23 is rewritten to

w 23 = (r 4 , multed) • (r 5 , added) + (r 5 , added) • (multed, r 4 )
We show hereafter an alternative obtained by rewriting w 12 and ψ 1 in f 12

f 12 = [(r 1 , multed), (r 2 , multed)] ← [(s 2 , multed), (s 1 , multed), (s 3 , multed)] = [(s 3 , multed)]
By matching messages, we deduce the following set SR of related expressions from f 12 SR = {(s 2 , r 1 ), (s 1 , r 2 )} and we get the remaining input messages f 12 = [(s 3 , multed)] as an input to solve f 23 . In this example, the resolution gives us the following set

SR = {s 1 , s 2 , s 3 } × {r 1 , r 2 } ∪ {s 1 , s 2 , s 3 } × {r 3 } ∪ {(s 4 , r 4 ), (s 5 , r 5 )} (8.17)
SR materialize all possible related send and receive expressions. It is the work of the Transaction Selector to choose a certain relation over another one. For instance, from SR we know that (s 1 , r 1 ) ∈ SR will relate first sendfrom to the first recv expression in bb1. But we also have (s 1 , r 3 ) ∈ SR, which is also valid because a parallel send operation does not specify any arrival order of responses -even under the hypothesis of instantaneous communications -and we may receive the message triggered by s 1 at receive expression of basic block bb2.

Transaction Selector

The transaction selector uses the result of our message dependency analyzer to make a deterministic choice between non-deterministic relations of send-receives. We briefly discussed the result of the analysis on the example of Figure 8.7. Due to non-determinstic properties of parallel send, we may have to choose between a certain subset of relations. Consider again the result (8.17). We observe that there are receive expressions related to more than one sending actions, s 1 for instance, but according to Pixel code flow s 1 can only be related to only one receive if we need to generate code with deterministic behavior. However, in some cases keeping all relations from sends to receives may be a valid situation. In the example of Figure 8.8, we assume SR = {(s 1 , r 1 ), (s 2 , r 1 )} where s 1 and s 2 correpond to sendfrom at bb1 and bb2, respectively, and r 1 represents the receive at bb3. In this particular case, even if we have a single receive related to two sending actions, we do not need to choose between both pairs as they are controlflow dependent. For this reason, we refer to control-based dependencies in the traditional Single Static Assignment (SSA) sense, i.e., as a φ dependency, and to dependencies introduced by nondeterminism as a π dependency. Note that the converse situation may also exist in a control-flow dependent manner, i.e., sending expressions with multiple related receives, which we described in Figure 8.9.

Therefore, the Transaction Selector needs to decide whether a subset of relations are controldependent or not. If they are, we must preserve them, otherwise we need to choose between one of them to produce a deterministic behavior. m s according to (8.10). If there exists an r on message m related to s, by the alternation term and our algebraic rules (8.15), it must also be related to s .

Following this lemma, we have a complete bipartite graph between any set of parallel sends and its respective receives.

From Corollary (8.7), we can see each particular receive as a "shared" resource among parallel sends that form a π dependency. However, it does not say anything about the other direction, i.e., a single send related to more than one receive. If we come back to the example of Figure 8.7, we see that there must be a bijective relation between senders expressions of mult<Int> and receivers of multed<Float> because each reply message, consequence of a particular send, becomes unavailable once it has been consumed by one receive. In other words, receivers do not share sending actions.

On the other hand, Figure 8.10 shows the converse situation, which is a slightly different version of Figure 8.9. We have an additional sending action s 2 in parallel with the first one s 1 . Assuming an empty FIFO state at bb1, we have that both receives at bb2 and bb3, r 1 and r 2 , are π related to s 1 and s 2 , respectively. Here, we can let receives connected to the same sending action after having removed π dependencies. Thus, s 1 and s 2 are shared between them. In conclusion, we need to distinguish between what we called concurrent receives from the sending perspective.

We introduce this notion in the following definition.

Definition 8.9. Let r 1 , r 2 ∈ R be two different receives. They are concurrent iff r 2 ∈ dom(r 1 )∨ r 1 ∈ dom(r 2 ) where dom : R → 2 R is the dominance set of receives.

We say that a receive r dominates r if all control-flow paths from the state machine root to the wait statement that contains receive r , pass through the wait of r. Clearly, if one receive dominates the other then common parallel sending actions related to both receives cannot be shared as the first one will pick an available send and make it unavailable for the following one.

Based on Corollary (8.7) and given Lemma (8.8) combined with Definition (8.9), we imple- 8.1 where each step corresponds to one receive (and its associated parallel sends) of results (8.17). At the first step, we pick receive r 1 with related parallel sending s 1 , s 2 and s 3 , we choose relation (s 1 , r 1 ) and remove (s 2 , r 1 ), (s 3 , r 1 ). Afterwards, we look at r 2 , choose (s 3 , r 2 ) and remove (s 3 , r 3 ). Finally, r 3 gets related to the last send s 2 . Note that the final set of relations is a one-to-one relation between send and receives because

Scalar Constants

As introduced in Chapter 5, HOE 2 scalars are objects that communicate through messagepassing in the same manner that user-defined objects. The scalar constant analysis tracks constant associations wherever they are defined, either inside fsm or creator. It simply detects create expressions of scalar objects as the following Receive / ParSend T r 1 / (s 1 , s 2 , s 3 ) {(s 1 , r 1 )} ∪ {s 2 , s 3 } × {r 2 , r 3 } ∪ {(s 4 , r 4 ), (s 5 , r 5 )} r 2 / (s 2 , s 3 ) {(s 1 , r 1 ), (s 3 , r 2 )} ∪ {s 2 } × {r 3 } ∪ {(s 4 , r 4 ), (s 5 , r 5 )} r 3 / (s 2 ) {(s 1 , r 1 ), (s 3 , r 2 ), (s 2 , r 3 )} ∪ {(s 4 , r 4 ), (s 5 , r 5 )} r 4 / {(s 1 , r 1 ), (s 3 , r 2 ), (s 2 , r 3 )} ∪ {(s 4 , r 4 ), (s 5 , r 5 )} r 5 / {(s 1 , r 1 ), (s 3 , r 2 ), (s 2 , r 3 )} ∪ {(s 4 , r 4 ), (s 5 , r 5 )} We show in the next section that constants can be made local to the state machine and automatically unboxed if possible. Using local variables instead of associations may produce unused associations that can be optimized out afterwards.

Transformations

Based on the analyses presented in the previous section, we built a set of transformations to achieve IR patterns that are known to have efficient code translations. Before introducing our transformations, where most of them rely on the presented analyses, let us start by presenting required mathematical tools and notations concerning the representation of HOE 2 index sets.

Index Sets

We define the denotation of an indexset , . : indexset → Σ → S where S = i S i is the finite union of labeled parametric polyhedral sets S i : We define also the polyhedral relation

Z n → Σ × 2 Z d represented as follows S i (s) = { i (x) | x ∈ Z d ∧ ∃z ∈ Z e : Ax + Bs + Dz ≥ c} with A ∈ Z m×d , B ∈ Z m×n , D ∈ Z m×e , c ∈ Z m
R = i R i where R : Z n → Σ × 2 Z d 1 × Σ × 2 Z d 2 ,
which is the union of basic relations

R i R i (s) = { 1 (x 1 ) → 2 (x 2 ) | x 1 ∈ Z d 1 , x 2 ∈ Z d 2 , ∃z ∈ Z e : A 1 x 1 + A 2 x 2 + Bs + Dz ≥ c}

| id

Let s be an statement with associated index domain D(s) = S(x) and R i :

Z n → i Σ × 2 Z d 1 ,
we define an interpretation I : var expr → R i of accessed variables such that the relation between s and the access is the labeled polyhedral n-ary relation A = S(x) → I(v). then we have that D(s) = {s(i) : 1 ≤ i ∧ i < 32} with read associations

I(v) = {v()} (
A 1 = D(s) → I(this) = {s(i) → this() | 1 ≤ i ∧ i < 32} A 2 = D(s) → I(this.a[i-1]) = {s(i) → this() → a(i 0 ) | 1 ≤ i ∧ i < 32 ∧ i 0 = i -1} A 3 = D(s) → I(this.a[i]) = {s(i) → this() → a(i) | 1 ≤ i ∧ i < 32}
For the manipulation of polyhedral sets and relations and its operations, we used the Integer Set Library (ISL) [START_REF] Verdoolaege | ISCC Tutorial[END_REF]. Structural accesses like A 2 or A 3 can be modeled in ISL using nested spaces.

Dead Code Elimination

This pass removes unused definitions which are either performed at the creator or the fsm scope, regardless of their declaration scope (associations or local variables). Note that the only way to pass definitions from creator to fsm is through associations. Therefore, we should be able to follow definitions and its corresponding uses at different scopes. Data dependencies between different hierarchical scopes are handled by our data-flow analysis shown in Section 8.3.1.

Given that we also take into account structural accesses, we can easily detect unused associations by consulting the DefUse chain analysis. The encapsulation property of HOE 2 objects guarantees the correctness of this transformation. Associations are not exported to external objects which means that they cannot be used outside the context of the object under analysis.

Dead Associations Elimination

In this pass, we remove undefined associations from the object type definition. We rely on the same fact as before, object associations cannot be defined at the outside of the current object because of visibility constraints.

C = {i | i ≤ 0 ∧ i < 32}, then it follows two branching domains W 1 = {i | i < 16}, W 2 = {i | i ≥ 16}
, from which we can deduce the following indexed region domains

D 1 = C ∩ W 1 D 2 = C ∩ W 2
Additionally, we have that D

Basic Block Fusion

In this pass we merge two basic blocks linked through an unconditional jump. Given two basic blocks BB 1 and BB 2 , we merge them iff preds(BB 2 ) = {BB 1 } and BB 1 jump unconditionally to BB 2 , i.e., via a goto statement.

Loop Fusion

The loop fusion pass moves indexed statements into indexed regions. In order to move an indexed send we must be sure that, among other contraints discussed later, its domain is equivalent to the one of the indexed region. Let s 1 be an indexed send with iteration domain D(s 1 ). Assume, we have a waitin w 1 statement with only one indexed region w 1 = wait this in r 1 recv then with iteration domain D(r 1 ) and a basic block bb = s 1 ; w 1 . Then, we should be able to move s 1 into r 1 iff D(s 1 ) ⊆ D(r 1 ) ∧ D(r 1 ) ⊆ D(s 1 ). As an example, consider the transformation shown at Figure 8.12. Given that the marked sending is under the same index domain as the next indexed region, then we are able to move the former into the latter.

Applicability of the transformation

If this transformation seems straighforward a priori, in general we need to handle waitin statements with multiple indexed regions and different kinds of statements to move into. In addition to the number of statements to handle and given our computational model, an important fact to consider is concurrency. Let s be a statement containing only one indexed expression and a waitin statement with two indexed regions r, r such that D s = D r and D r ∩ D r = ∅. In this case, we should be able to move s into region r. The indexed expression s is concurrent by itself (forall semantics) and it will remain as such even inside region r. The point is that before the transformation, s and r, r were sequentially ordered but after the transformation, we put s in concurrency with all statements inside r . Moreover, each particular instance of region r, say r i , might also run into concurrency problems. This one is more subtle and relies on the fact that we do not specify any particular execution order between different instances of an indexed region, i.e., they are composed asynchronously. Thus inter-iteration data dependencies may not be safe in general without explicit synchronization through message passing. Assuming synchronized inter-iteration dependencies on s and r, we must guarantee that s i does not introduce non-synchronized inter-iteration dependencies. To illustrate the discussion with an example, consider the invalid transformation shown in Figure 8.13. The indexed region makes a simple parallel copy between two arrays, a and b. Note that if we naïvely insert the first sendfrom into the following indexed region, as shown in the transformed code, we may run into concurrency problems because sendfrom introduces an inter-iteration dependency, i → i -1. If region, say 2, is faster than 3, then we endup by sending message mult<Int> to the new value of a [START_REF] Fraguela | The Hierarchically Tiled Arrays Programming Approach[END_REF] in region 3, which is b [START_REF] Fraguela | The Hierarchically Tiled Arrays Programming Approach[END_REF], because the update statement in region 2 occured before sending in region 3. On the other hand, the region execution order i → 31i is guaranteed to preserve the initial behavior but we do not support scheduling hints into our current framework. In conclusion, we must check for inter-iteration dependencies before proceeding with the transformation to avoid race conditions.

Given the access relations introduced in Section 8.4.1, we can decide if two statements s 1 , s 2 have inter-iteration dependencies by computing, R 12 = A -1 s 1 (A s 2 ) and constructing the new delta set ∆R 12 = {xy | ∀x → y ∈ R 12 }. For instance, consider the read access this.a[i-1] of s 1 and the write one this.a[i] in s 2 . From both accesses, we have

A s 1 = {s 1 (i) → this() → a(i 0 ) | 1 ≤ i < 32 ∧ i 0 = i -1} A s 2 = {s 2 (i) → this() → a(i) | 1 ≤ i < 32} Then we apply A -1 s 1 (A s 2 ) = RW 12 = {s 2 (i) → s 1 (i 0 ) | 1 ≤ i < 32 ∧ i 0 = i + 1}
and compute the delta set ∆RW 12 = {1}, which provides a proof of an inter-iteration dependency. for all α i iexpr . Then, each parallel expression can be distributed among all the indexed regions assuming that it does not introduce any inter-iteration dependency among them. Algorithm 2 describes the copy of parallel statements into multiple indexed regions.

We show in Figure 8.12 a running example of the loop fusion transformation.

Inlining

This pass inlines one object state machine into another, called inlinee and inliner. In the context of state machines, the inlining procedure depends on multiple factors: precise knowledge of the current state of the inlinee from the inliner perspective, known send-receive relations and well delimited sub-state machine to inline.

Well delimited sub-state machine. Let A be a IR object with an input-output message relation at its interface level: on m1() -> m2(). Necessarily, there is at least one closed sub-state machine of A containing a wait statement with a receive expression on m 1 and a reachable reply statement on m 2 . We call such path a wait-reply path. Note that it is the role of the interface to indirectly guarantee its existence. Figure 8.14 sketches the case of a single wait reaching multiple replies. We see that the wait dominates both receives, and hence it defines a well-delimited sub-state machine that encloses the actions needed to fulfill the exposed transaction. Although closely related, the general case concerning arbritrary wait-reply paths is a problem of interface verification rather than inlining. We did not go further into it and limit our current implementation to one wait and one reply paths.

Dead Wait Rewriter

The Transaction Folding pass removes send and receives statements and adds the corresponding in-place operation. As a consequence, the transformation may produce dead waits. Dead waits have only one then branch without receive nor guard specifications. We transform them into its equivalent, and simpler, statement goto as shown hereafter.

wait this then goto NextBB; goto NextBB;

Afterwards, the basic block fusion pass may eliminate them if the Control-Flow Graph (CFG) meet the necessary conditions. More optimization possibilities may be discovered after fusioning basic blocks, such as Loop Fusion.

Unboxing Types

We say that HOE2 scalars represents boxed primitive types because they provide state machine semantics, equivalent to other objects, to simple scalar values. Boxed scalar types guarantees a clean and homogeneous interaction within the language with other objects. However, it implies a state machine for every single scalar value in the language runtime implementation, which is clearly too cumbersome if we want to improve HOE 2 application performances. In general, we aim to have as much unboxed scalars and operations as possible in the final state machine model. 2 In our IR, boxing and unboxing operations are implicit and concern exclusively applyon operations. That is, the applyon operator requires unboxed types as operands and returns unboxed types. Thus, their operands are implicitly unboxed before applying the operation, and its output is boxed depending on the type of the target variable.

This pass is decoupled into two steps: Scalar Constant Unboxing and Unboxing of Definitions.

First of all, we try to use unboxed constants if possible. For instance, the scalar creation

Int cst = create Int.int 10;
is unboxed to

int cst = 10;
iff all uses of cst require an unboxed scalar, i.e., they correspond to operands of applyon.

Here, we rely on two key analyses: the DefUse chain (Section 8.3.1) and Scalar Constants (Section 8.3.4).

The next step is more general. We look for definitions where the left-hand side is an unboxed type but its right-hand side is not. The constraints remain the same, we verify that all uses of the applyon output require an implicit unboxing by consulting our DefUse chain analysis. We are able to unbox definitions such as those presented in Figure 8.6 and rewritten hereafter. iff all uses __new_var_1 and __new_var_2 turn to be unboxed.

Contributions

We presented the IR optimizing compiler, its analyses and optimizations. The goal of our optimizing compiler is to achieve specific IR patterns, which are known to have efficient implementations in the target language. For this purpose, we introduced a set of analyses and transformations with some of them as extensions to already known analysis in the compilation domain, e.g.

the structural reaching definition analysis. This analysis solves the reaching definition problem over structural, or hierarchical, statements. It allows us to keep the hierarchical information coming from the frontend language, HOE 2 , while enabling classical optimizations along the hierarchy of the state machine such as dead code and association elimination, automatic unboxing.

Based on the interface concept introduced in the HOE 2 language, we developed a new analysis to relate send and receive communication primitives in a modular manner. The analysis takes into account the specification of many messages per transition, of different kind and multiplicity.

On the way, it also allows us to detect dead-lock conditions under well-defined hypotheses. We also exposed its algebraic properties, on which we root the next analysis called the Transaction Selector. The Transaction Selector detects non-deterministic relations between send and receives in order to choose one valid deterministic behavior. We introduced the equivalent concept of φ nodes at the message exchange level and a new dependency kind called π to maintain nondeterminsitic relations.

One of the main contributions of the HOE 2 language is the introduction of indexed messages and regions. Using polyhedral analysis, we developed transformations to rewrite traditional HOE 2 broadcasts made of wait-all loops into indexed regions. Afterwards, we study the problem of loop fusioning in the context of asynchronous composition of indexed regions. Enabling loop fusion allowed us to optimize further and fold indexed message exchanges into in-place operations, according to the operational view of transactions presented in Chapter 5. We also developed an automatic unboxing pass on the context of the IR language.

In the following chapter, we validate our optimizing compiler and show experimental results. In order to provide a clear interpretation of our experimental results, we first describe the underlying message-passing runtime and its interaction with Highly Heterogeneous, Object-Oriented, Efficient Engineering HOE 2 objects. We will then discuss the optimizations and code generated for a simple model, followed by a detailed analysis of a more complex one. In the process, we will consider multiple optimization levels to highlight the impact of the optimizing compiler, and to demonstrate the generated code quality. We conclude our experiences with an adaptation of our optimizing chain to support General-Purpose computing on Graphics Processing Units (GPGPU) code generation.

Runtime

The compiler toolchain emits one C file per HOE 2 object and this file embodies the optimized code of this object. The generated C code can call back the runtime for multiple purposes, like creating or destroying objects, sending messages, waiting for incoming messages, and initialization and termination of objects. Listing 9.1 shows the main callback routines. Our runtime implementation is based on a widely available thread library called QThreads [START_REF] Wheeler | Qthreads: An API for Programming with Millions of Lightweight Threads[END_REF]. Qthreads is a lightweight locality-aware user-level threading runtime. Each HOE 2 object has its own userland thread and communicates through runtime callbacks. Currently, the C backend uses this implementation to manage a large number of concurrent objects.

The runtime starts the application by calling the main constructor of a root HOE 2 object defined by the programmer. This root object represents the system that creates all the initial objects of the HOE 2 application. The basic template for the entry point of an HOE 2 application is shown in Listing 9.2. Then, an object providing a main creator is called by the runtime entry to start the application. We associate to each HOE 2 object a simple C structure that exposes

Code Generation

Most IR statements have fixed translation rules, such as updates, object creation, message send and receive, except for applyon expressions. HOE 2 models defining operational transitions must provide a mapping between applyon operations and their corresponding translation. The mapping is controlled by the programmer via a "cc" mapping file (see Figure 9 While the generation of a for loop from index domain

{(i, j) : 0 ≤ i < 256 ∧ 0 ≤ j < 256}
is straightforward because loop bounds and stride are given, we may expect more complex expressions. For instance, consider the domain given by the zigzag traversal (discussed later in this chapter)

{(i, j) : 2 i + j 2 = i + j ∧ i + j ≤ 7 ∧ 0 ≤ i < 8 ∧ 0 ≤ j < 8}
where . returns the integer part of its argument. This domain comes from a modulo constraint between i and j, i + j % 2 = 0.

In consequence, we implemented a simple version of the algorithm presented by Bastoul in [START_REF] Bastoul | Code Generation in the Polyhedral Model Is Easier Than You Think[END_REF].

Recent advances in code generation from polyhedra would be of great benefit to improve detection of loop bounds and strides and, hence avoiding complex control statements in our translation of indexed regions [START_REF] Grosser | Polyhedral AST Generation Is More Than Scanning Polyhedra[END_REF].

Exercising the Optimizing Flow

We exercised the flow over our motivating model example shown at Figure 9 Given that Image is the main object of our running program, its associations are preserved (considered as side-effect actions) and we found remaining boxing and unboxing operations of scalar objects at assignement and computation points of associations, respectively. As defined in Chapter 8, we say that HOE 2 scalars are boxed primitive types because they provide state machine semantics similar to other objects. For instance, Line 6 shows an unboxing operation of an HOE 2 Int scalar-implemented as pointer accesses. Line 11 shows a boxing operation necessary to store values on Image associations. For performance reasons, using unboxed values over boxed ones is always preferred.

Metrics and Results

Our optimizing flow aims at optimizing-out as much messages as can be: If we achieve deep inlining of objects we should expect a reduction on sent and received messages, hence a reduction of application/runtime communications that slow down the HOE 2 application. In order to show the impact of our optimizing chain, we define three transformation levels: (0) No optimiza- dctlines zigzag [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] intensity [8] qtable [8,8] y u v ychannel [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF] We show in Listing 9.6 the tiling update and the sending action of message encode() to all blocks. The Block8x8 object does such computation as a composition of two 8-point 1D DCT, The two top loops correspond to the iteration domain of blocks, while the two more nested ones come from the inlining transformation together with the intersection of zigzag domain and one of the guard conditions. We use polyhedral code generation to produce C for-loops from our index domains [START_REF] Bastoul | Code Generation in the Polyhedral Model Is Easier Than You Think[END_REF]. To get an idea on how powerful high-level models allow the programmer to handle the complexity of deeply nested operations, we show in Listing 9.9 the C for loop structure of the application model automatically generated by the compiler.

Even though the number of messages has been aggressively optimized, the compiler failed to unbox all scalar types. Figure 9.7 compare both results. The results show that there are still too many object creations even at the highest optimization level: 129152 objects at O0, 29121 objects at O1 and 23937 objects at O2. If we take a ratio between different optimizations, we note that O1 improves O0 in terms of object creation by 77% and O2 improves O1 by 17%.

The first improvement is due to in-place computations. After send/receive operations has been folded, we create applyon operations that may enable type unboxing aftewards, thus fewer creation of objects. The 17% at O2 comes from the inlining operation. Indeed, if we inline objects then we do not need to create them anymore. Still more than 23k objects are inserted into the runtime with no-communication at all. Taking a closer look at the problem, we found the following generated code snippet: Line 6 is a definition coming from a folded send/receive combined with an automatic unboxing.

The next line is translated from an applyon operation, which is implemented as a C addition.

Then, we have a boxing operation to store the final value in the association. This is necessary because we did not unbox association variables yet. That is, we do not modify the object definition itself, excepting the pass that removes dead associations. Ideally, we should be able to greatly reduce the number of created objects if we follow the idea of unboxed associations.

Thereby, an object with unboxed associations could be used unboxed as well by composition.

In conclusion, the automatic unboxing optimization is fundamental in our language in order to pass from message-driven to in-place operations with efficient structure accesses.

Application Development: The HOE 2 Approach

In order to give the Model-Driven Development (MDD) aspect on which our HOE 2 language is embedded, we introduce the HOE 2 development process and methodology. The HOE 2 development process was extensively studied in [START_REF] Hili | Une méthode pour le développement collaboratif de systèmes embarqués[END_REF]. It is composed by four phases: Requirement Analysis, System Analysis, Design and Implementation. Figure 9.8 shows the HOE 2 methodology and describes how these phases are combined together following a full MDD flow with an innovative, recursive usage of modern Model-Driven Architecture (MDA) techniques.

Several meta-models support each phase, thoroughly explained in [START_REF] Hili | Une méthode pour le développement collaboratif de systèmes embarqués[END_REF]. From a language perspective, which is the preferred view in this thesis, Hili proposes different grammar concepts to support concurrent co-design, i.e., hardware and software, of embedded systems.

The system requirement analysis consists in the specification of several use cases of the system, or scenarios. As a descriptive example of the methodology, we defined a color converter system with a single use case shown in Figure 9.9. The "User" is intended to model, through message exchanges (and its respective state machine), the interactions with the system, it is an HOE 2 objet by itself. In other words, it might be seen as the root object of our HOE 2 application, which is equivalent to the main entry in widely known languages like C/C++ or Java. Given

Towards GPGPU Code Generation

The distribution phase introduces a new interaction between objects of differents worlds. The state machine rewriting is guided by the HOE 2 method. In our particular case, the object at the CPU side will send a run() request to the GPU object, which will then answer with a completed(Float[512]) message carrying the computed result. Figure 9.11 describes both scenarios, before and after the rewriting, and Listing 9.12 shows the state machine of ImageGPU where we highlighted the increment with respect to Image object. As we can see, all the work has been transfered to the GPU and its CPU counterpart is there to preserve the interface among its users. Currently, this transformation is not performed automatically and needs user intervention on the model.

The GPU world is more constrained than the CPU one, hence we need to follow certain platform constraints.

(1) We cannot follow pointers inside the structure Having fulfilled all the backend requirements, the OpenCL backend generates a kernel that performs the computation modeled at ImageGPU and, according to (2), it does not communicate.

Therefore, objects hosted by the CPU world cannot communicate with the GPU ones anymore.

As a consequence, the scenario shown at Figure 9.11(b) is to be transformed.

Extending the Optimizing Chain

We call objects like ImageCPU OpenCL master objects. Instead of communicating, the OpenCL master need to access directly the corresponding association(s) returned by the GPU root object.

Based on constraint (c) and the message dependency analyzer presented in Section 8.3.2, we build a new transformation pass that replaces the send/receive relation by an in-place access. 3For instance, ImageGPU in our example (see Listing 9.12) stores the computation result in association ychannel and sends its content to ImageCPU via message completed(Float[512]).

After the transformation, the latter will access directly association ychannel of the former. We call this pass the Access Folding transformation. Figure 9.12 show the integration on the generic optimizing chain.

OpenCL Code Generation

We show the generated host and OpenCL kernel code in Listing 9.13. In this implementation, we can see how the ImageGPU creator at Line 32 sets up the OpenCL kernel, run it and read its results from device memory. It is worth to note the interface between HOE 2 objects and unboxed ones. Because ImageGPU is still created from an array of HOE 2 objects, we found unboxing operations to set GPU associations (see Line 41).

The kernel corresponds to the indexed region introduced by the compiler transformations as required by (a) and it runs on the unboxed ImageGPU object (see Line 1). The OpenCL backend maintains the same unboxed type at both worlds, the kernel and the host one (though not shown here), respectively. Note that the creator returns the host-side structure such that ImageCPU can access it safely thanks to the Access Folding transformation introduced in the precedent section.

Conclusions

Under a custom runtime environment for communicating state machines, we stressed the proposed optimizing chain. We started by testing it on a simple object model where we showed encouraging results in terms of generated code quality. We managed to produce efficient C for loops from very high-level models taking into account many different notions of the HOE 2 language: scalars, indexed regions, indexed messages, interface specification and replies.

We stressed the flow at different optimization levels against a complex model that implements part of the JPEG algorithm. The most aggressive optimization level achieves interesting results in term of messages: they are all optimized out. However, the number of live objects in the application runtime remains relatively high. The compiler did not manage to remove some boxing operations, though 77% of objects are removed from O0 to O1 and 17% from O1 to O2 resulting in a total of 88% eliminated boxing operations. Indeed, the store of an unboxed object into an association requires a boxing operation. There is still work to be done in automatic unboxing of associations in order to obtain yet more efficient implementations.

Despite of the number of objects, we showed that the language expressivity and modularity allow the programmer to write very high-level and composable expressions while obtaining efficient implementations with deep loop nesting levels computing over hierarchical structures.

We continue our experimentations on the methodology foundations of the HOE 2 language.

We presented the HOE 2 methodology, which have been thoroughly studied in [START_REF] Hili | Une méthode pour le développement collaboratif de systèmes embarqués[END_REF], and based on it we show the flexibility of our optimizing compiler. The GPGPU code generation would not have been possible in an semi-automatic fashion without the analyses developed at Chapter 8 and, technically very important, the compiler infrastructure. On the other hand, the number of char * iregion_4594355024_src = "struct Pixel {" " int r;" " int g;" " int b;" " float y;" " float rcst;" " float gcst;" " float bcst;" "};" "typedef struct Pixel Pixel;" "struct ImageGPU {" " struct Pixel pixels[512];" " float ychannel[512];" "};" "typedef struct ImageGPU ImageGPU;" "kernel void iregion_4594355024(global struct ImageGPU * this)" "{" " int i = get_global_id(0);" " float __new_var_6 = 0.299;" " float __new_var_7 = 0.587;" " float __new_var_8 = 0.

Main Results and Contributions

This thesis is embedded into model-driven approaches for the design and development of Embedded System (ES). On this context, we highlighted interesting works pointing the need of new methodologies and supporting languages to exploit the parallelism offered in recent parallel architectures.

Object Modeling & Statecharts. Our first contribution addressed data parallel issues inside the Statechart itself, a widely known formalism to model behavior in the MDE community. In order to model parallel operations, we propose an original view of scalars as communicating state machines and its arithmetics operations being modeled by means of message passing semantics. Also, the parallelism is directly exposed in the model structure through multi-valued associations, over which parallel messages sending -thus denoting arithmetic operations -is possible. We combined this idea with interesting Statechart extensions and parallel constructions in the action language: indexed messages and indexed regions, parallel updates and parallel sending actions.

The message-based arithmetics exposes a different view of scalars, making them functionally equivalent to generic objects. From the MDE point of view, the modeling activity becomes homogeneous, i.e., there is no need for different languages in the modeling framework to express control and data driven operations. This set of features allowed us to address data-intensive applications (JPEG) in a Statechart-based modeling style.

Statechart Formal Semantics. The second contribution is the specification of a formal semantics for Statecharts following a hierarchical and modular structure. This formalization takes into account the action language, the Statechart structure and communications between them in an object-oriented setting. We avoid semantical complications due to non-constructive semantics of Statecharts while still supporting asynchronous communications and composition of state machines. If not exhaustive, we showed how the formalization approach allows us to separate different semantical points in order to handle them layer by layer. Thus reducing the complexity of a flattened formalization as we have seen in existing approaches.

Intermediate Representation. The next contribution concerns the compilation of Statecharts.

We proposed a compilation chain based on an expressive intermediate representation. This representation preserves most of the information coming from the front-end language, notably the state machine hierarchy. We support dynamic Statecharts, asynchronous communications, arrays, struct-like accesses and indexed domains, among other features. From this representation, we can reason about the hierarchy and the asynchrounous communications between different objects. Given the nature of index domains, we enabled powerful polyhedral analyses for automatic parallelization and code generation.

Static Analyses and Transformations. On the context communicating Statecharts, we extended the static analysis of reaching definitions to take into account the nesting structure of regions in the state machine. In the set of static analyses, we also proposed two complementary passes, Message Dependency Analyzer and Transaction Selector, that find send/receive relations enabling the folding of transitions and the inlining of objects.

In the Transaction Selector analysis, we introduced the notion of concurrent dependencies called π dependency. A π dependency exposes concurrent data-dependencies introduced by send and receive relations corresponding to a transaction between two objects. It allowed us to safely propose a deterministic behavior for code generation. Compiler for Embedded Architectures. The generation of efficient code from high-level models is a challenging task. We showed results concerning the quality of the generated code from a simple example and we extended it to cover a part of the JPEG algorithm. It resulted in complex generated code showing how powerful our model abstractions are to handle hierarchical implementations in case of data-intensive applications. The produced code is competitive with respect to hand-coded implementations. Moreover, we proved the flexibility of our compilation flow by adpating it to target parallel embedded architectures (General-Purpose computing on Graphics Processing Units (GPGPU) platforms).

A Look Back to the Thesis Motivations

This work started on the basis of multiple challenges concerning parallel programming of manycore embedded architectures. We observed that modern parallel languages and its corresponding compilers cannot follow complex constraints of embedded platforms anymore. We certainly need abstractions to handle this complexity. The iterative integration of platform constraints into a given application makes of MDE techniques an attractive approach to consider them in an abstract manner.

We addressed parallelism, formal semantics and code generation issues of Statecharts as the necessary and non-trivial steps towards a well-founded Statechart-based modeling language. As shown by our results, the parallel action language we proposed allowed us to generate efficient code and target parallel architectures such as GPGPU platforms.

However, the compiling challenge of taking into account complex platform constraints in an MDE fashion is still open. Platform-specific operators and its corresponding types, cache sizes, scheduling and mapping constraints are some of the performance factors that we should integrate into the optimizer via new model abstractions. In conclusion, we proposed a modern view of object-oriented Statecharts adapted for parallel programming. Figure 10.1 shows a comparison of our approach to reviewed parallel languages of Chapter 2. We remark the lack of formal platform constraints on the modeling approach we propose. However, it offers interesting abstractions in an unified setting and, most importantly, shows higher expressivity than other languages (dynamic Statecharts, array-like accesses, index domains).

As we will show in the following section, we distinguish several research directions gravitating around Statecharts that may guide new approaches to handle platform specific optimizations from a MDE perspective.

Future Research Directions

In this thesis, we lay the ground of a modeling language entirely based on Statecharts, even for arithmetic operations, with parallel support for data and control driven actions. However, there is still a lot of work to be done in this direction.

From methodology to final code generation issues, we highlighted in Figure 10.2 several interesting points to develop further concerning different Statechart aspects.

Methodology. We place at the methodology process, the formalization of multiple hardware specific constraints. As shown in Chapter 9, the current state of the Highly Heterogeneous, Object-Oriented, Efficient Engineering HOE 2 methodology allows us to take user-driven decisions concerning the distribution of our application. However, we need specific metrics to be able to reason about different application distribution strategies. Platform specific types can be abstracted using models. The compiler optimizations should be able to feedback the designer to spot relevant uses of platform-specific types. For instance, it may perform automatic indexed region tiling to find vectorization opportunities if the platform supports vector types and its respective operations.

Object-Oriented. The object oriented support of HOE 2 leverages modular and composable designs. Modularity is the key for strong optimizations such as Statechart inlining. During our work, we proposed an external interface of objects that exposes message interactions between the object and its owners -closely related to initiator semantics. The Message Dependency Analyzer pass currently supports simple transaction entries. In order to capture send/receive relations with complex reply expressions, the analysis must be extended. Concerning association kinds, the compiler handles fixed size multiplicities. An extension to variable sized multiplicities of associations is necessary to widen the spectrum of supported input models. Moreover, we believe that types can be refined, i.e., from variable sized or unbounded to fixed or bounded ones, through specific static analyses.

Semantics. A natural future direction of the formal semantics concerns verification. Indeed, existing semantics of Statecharts are followed by formal verification methods, frequently based on model checking.

Transformation Passes. As shown in Chapter 9, the automatic type unboxing is the key to avoid unnecessary HOE 2 object creation. Currently, the type unboxer do not unbox association types, which is the root of many boxing operations and hence the large number of live objects.

Code Generation. The current code generation strategy of parallel and indexed regions is based on a lexicographic scheduling through a classical polyhedral code generation algorithm.

We make sure that no inter-iteration and no inter-region dependencies exists in order to safely generate the scanning code. Cross regions synchronization dependencies should be taken into account to feed the polyhedral model and produce safe schedules.

Every single branch of Figure 10.2 opens a great number of questions and lead to specific research works. Several branches may be also related at some extent. For instance, certain optimizations passes could discover new opportunities and feedback methodological related actions.

The set of optimizations are necessary driven by a specific semantics of the object-oriented Statecharts.

Glossary HOE 2 Highly Heterogeneous, Object-Oriented, Efficient Engineering.

Array-OL Array Oriented Language.

CFG Control-Flow Graph.

DCT Discrete Cosine Transform.

DSL Domain-Specific Language.

EMF Eclipse Metamodeling Framework.

ES Embedded System.

ETL Epsilon Transformation Language.

FIFO First In-First Out.

fUML foundational UML.

GEMM General Matrix Multiplication.

GPGPU General-Purpose computing on Graphics Processing Units.

GPU Graphical Processing Unit.

HCFG Hierarchical Control-Flow Graph.

HDP Haskell Data-Parallel.

HiDP Hierarchical Data Parallel Language.

HSM Hierarchical State Machine.

HTA Hierarchically Tiled Arrays.

IR Intermediate Representation.

ISL Integer Set Library.

LTS Labeled Transition System.

M2M Model-to-Model.

MBD Model Based Design.

MDA Model-Driven Architecture.

MDD Model-Driven Development.

viii 6 . 1 3 1. 3

 6133 Functional view of communicating HOE 2 objects . . . . . . . . . . . . . . . 6.2 Hierarchical semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Non-Indexed model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Evaluation rules for configurations . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Pixel model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Translation of initiators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 SM model of Pixel state machine . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Translating all condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Translation of Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 Compilation Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Definitions layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Granularity levels of variable definitions: object, association and element levels 8.4 Send-receive problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Message dependency analysis: FIFO equations . . . . . . . . . . . . . . . . . 8.6 Loop in the control-flow and its FIFO equations . . . . . . . . . . . . . . . . . 8.7 Pixel control-flow with communication primitives only . . . . . . . . . . . . . 8.8 φ dependency of sending-receive pairs . . . . . . . . . . . . . . . . . . . . . . 8.9 Splitting of sending actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.10 Shared send action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.11 General case of wait-all loops . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.12 Loop fusion: Fusioning broadcast into indexed region . . . . . . . . . . . . . . 8.13 Invalid loop fusion because of concurrent inter-iteration dependencies . . . . . 8.14 Wait-reply paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.15 Image object model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.16 Inlining Pixel object into Image . . . . . . . . . . . . . . . . . . . . . . . . . 9.1 Optimizing pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Image object model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Phases of the JPEG algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4 Image object model implementing JPEG till zigzag traversal . . . . . . . . . . 9.5 Descriptive state machines inside objects of the JPEG model . . . . . . . . . . 9.6 Number of messages at optimization levels O0 and O1 (O2 eliminates all messages) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.7 Number of messages and created objects messages at optimization levels O0, O1 and O2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.8 The HOE 2 methodology for the development of embedded systems . . . . . 9.9 System requirements: Color converter use case . . . . . . . . . . . . . . . . . 9.10 HOE 2 methodology: Distribution . . . . . . . . . . . . . . . . . . . . . . . . 9.11 New interaction after distribution . . . . . . . . . . . . . . . . . . . . . . . . . 9.12 OpenCL-specific extension of the optimization pipeline . . . . . . . . . . . . . 10.1 The HOE 2 approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Future directions and extensions (in red) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Objectives and Contributions . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

  fl ows enabling fl ows enabling fl ows enabling fl ows enabling fl ows enabling fl ows enabling fl ows enabling platform platform platform platform platform platform platform composition. composition. composition. composition. composition. composition. composition. . . .

FIGURE 1 . 1 :

 11 FIGURE 1.1: The HOE 2 methodology for the development of embedded systems

FIGURE 1 . 2 :

 12 FIGURE 1.2: Modeling a car audio system with Statecharts (Source: [1])

  Data-Parallel Paradigm . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 The Functional Style . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 HTA: Hierarchically Tiled Arrays . . . . . . . . . . . . . . . . . . . 11 2.2 Hierarchical Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 The Sequoia Approach . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.2 HiDP: Hierarchical Data Parallel Language . . . . . . . . . . . . . . 12 2.3 Low-level Trends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Model-Driven Representations . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

type

  SparseVector = [: (Int, Float) :]

  dotp :: SparseVector -> Vector -> Float dotp sv v = sumP [: x * (v!:i) | (i, x) <-sv :]

type

  SparseMatrix = [: SparseVector :] smvm :: SparseMatrix -> Vector -> Vector smvm sm v = [: dotp row v | row <-sm :]

FIGURE 2 . 2 :

 22 FIGURE 2.2: Hierarchy of tasks in Sequoia (Source [3])

#

  FIGURE 2.3: Optimizing compiler of HiDP (Source [4])

FIGURE 2 . 4 :

 24 FIGURE 2.4: Array-OL visual formalism (Source [5])

FIGURE 3 . 1 :

 31 FIGURE 3.1: Hierarchical state machines

Figure 3 .

 3 1(b) is an AND composition with two regions where only one state can be active at each region. By active, we refer to the current state of the state machine at execution time.

3 . 4 .

 34 Synchronous transitions: Harel Statecharts extend the automata product with synchronous transitions, i.e., two active states in an AND composition waiting for the same message may progress at the same logical time. For instance, the Figure below shows an AND composition where both regions progress at the same logical time at reception of message α. Constrained asynchronous compositions, also known as in-state conditions: In terms of the automata product, it allow us to consider only a subset of the transition set given by the product of two parallel automata.

  ET == {tr : sc.τ | enabled(tr, csts, events)} let HP T == {etr : ET | (∀tr : ET • ¬SAnc(scope(tr, sc.σ), {scope(etr, sc.σ)}, sc.σ) let M N S == (µ ncs : P(P(HP T )) | (∀set : ncs • ¬conf licting(set, csts, sc.σ)) ∧(∀set : ncs; tr : HP T • ¬conf licting({tr} ∪ set, csts, sc.σ) ⇒ tr ∈ set)) •(#M N S == 0 ⇒ csts = csts ∧ events = ∅) ∧(#M N S = 0 ⇒ (∃EN : M N S• let Exited == {tr : EN • exit(tr, csts, sc.σ)}; Entered == {tr : EN • enter(tr, csts, sc.σ)}• (csts = (csts \ Exited) ∪ Entered) ∧events = {tr : EN • tr.label.action} ∪{st : Exited • exited(st)} ∪{st : Entered • entered(st)}

FIGURE 3 . 5 :

 35 FIGURE 3.5: Simplified Meta-model of UML Statecharts

FIGURE 3 . 6 :

 36 FIGURE 3.6: Visual syntax overview of SCCharts (Source: [6])

FIGURE 4 . 2 :FIGURE 4 . 3 :

 4243 FIGURE 4.2: Model-to-Model transformations

FIGURE 4 . 4 :

 44 FIGURE 4.4: GUML code generation flow

FIGURE 4 . 5 :

 45 FIGURE 4.5: GASPARD internal transformations (Source [8])

Figure 4 .

 4 Figure 4.5 shows the transformation flow of GASPARD where we precisely see different models for Embedded System (ES) co-design. We remark multiple underlying representations generated from the final Platform-Specific Model (PSM) model. However, Array-OL is the chosen one for the modeling of massively parallel computations.

FIGURE 4 . 6 :

 46 FIGURE 4.6: SCChart representations during compilation (Source: [6])

Figure 4 .

 4 Figure 4.7 shows the evolution of the UML compiling flow. In the context of UML Statecharts,

• 5 HOE 2

 52 An intermediate representation for optimization and code generation: if we look for performance, an intermediate representation more expressive than previous works exposing communications, computations and type definitions is necessary. Chapter Language Contents 5.1 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Imports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Hierarchical State Machines . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Modeling Arithmetics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Parallel Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Initiators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Object Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Indexed Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Scalars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Modeling Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

FIGURE 5 . 2 :

 52 FIGURE 5.1: UML class and associations

object

  Image has [128..256]Pixel as pixels object Pixel has Image as image LISTING 5.1: Image model in HOE 2 For instance, Figure 5.2 shows an image model as an instance of the UML meta-model 5.2(a). The Image instance contains a property called pixels allowing between 128 and 256 Pixel instances. By reusing graphical notations of meta-models, we draw the particular instance as shown in Figure 5.2(b). The meta-model of Figure 5.1 may be concretized by means of a grammar definition where each object represents a grammar rule. The key observation is that the inheritance relation denotes alternation and a group of associations denote concatenation. The language (or textual) representation of meta-models translates classes into record type constructors with properties representing named and typed fields inside the record. The intermediate concept of association is folded in both properties, becoming just a type reference. Following the concrete syntax of HOE 2 (detailed in appendix A), we write down the equivalent program of Figure 5.2(b) as presented in Listing 5.1.

LISTING 5 . 2 :

 52 [4..6]T. object Pixel interface ins GetU(), GetV() outs TakeU(Float), TakeV(Float) on GetY() -> TakeY(Float) has Float as r, g, b has Float as y, u, v Interface entries of Pixel 3. Fixed lower bound and unknown upper bound: [4.. * ]T.

Figure 5 . 3 .FIGURE 5 . 4 :

 5354 FIGURE 5.3: Meta-model of UML Hierarchical State Machine

Figure 5 .

 5 [START_REF] Mueller | Hidp: A Hierarchical Data Parallel Language[END_REF] shows an example of a HSM and Listing 5.3 its corresponding HOE 2 program.

FIGURE 5 . 6 :

 56 FIGURE 5.5: Image model

Figure 5 .

 5 Figure 5.5 shows an enriched image model and its corresponding HOE 2 program on which we will develop all our examples troughout this chapter in order to show the main features of HOE 2 language.

  state A. on / : r.add(g) to B state B. on added(v: Int) / b = v LISTING 5.4: Addition state GETY. on /: { i: 0..pixels.len -1 } pixels[i].getY() to GETTING_Y LISTING 5.5: Data parallel broadcasting Listing 5.4 shows the arithmetic operation b = r + g on the object model of Figure 5.5(a), decoupled as a combination of our three basic actions where the dot notation means message sending.

Figure 5 . 5 ,

 55 Listing 5.5 shows the luminance computation of all pixels in a data parallel fashion. The above example introduces three new concepts: indices, index domains and indexed messages. The definition is composed by a list of indexes and a set of constraints. The domain is equivalent to the closed range constraint 0 ≤ i ≤ pixels.len -1. The sending expression inside an index domain instantiates a set of indexed messages where each index value is taken from its enclosing domain. state GETTING_Y. on takeY{i}(y: Float) / ychannel[i] = y to GETTING_Y LISTING 5.6: Reception of indexed messages state GETTING_Y. on takeY{i}(y: Float) / ychannel[i] = y to GETTING_Y endon [i.all] LISTING 5.7: Broadcast completion state A. on / : r.add(cstr), g.mult(cstg), b.mult(cstb) to B state B. on multed(v1: Int), multed(v2: Int), multed(v3: Int) / r = v1, g = v2, b = v3 LISTING 5.8: Parallel multiplications

Listing 5 .FIGURE 5 . 7 :

 557 FIGURE 5.7: Nested parallel operations

Figure 5 .

 5 Figure 5.9(b). Note that the multiplicty range is compliant with the indexed region domain.

  FIGURE 5.9: Inlining objects

Figure 5 .

 5 Figure 5.11 shows the object model for the JPEG implementation of an image with 64x64 pixels.

2 FIGURE 6 . 1 :

 261 FIGURE 6.1: Functional view of communicating HOE 2 objects

  The set of array values Ā = a∈N [0, a) → V , where [0, a) denotes the product of rightopen interval and V the set of values.

  (φ , sys ) = α supdate u (φ, sys) (α update , φ, sys) → (φ , sys ) ASUpdate where we take a simpler definition of its grammar supdate ::= var '=' ( var | new )

  (φ , sys ) = α ssend s (φ, sys) (α send , φ, sys) → (φ , sys ) ASSend where the grammar of simple sends is defined hereafter ssend ::= var '.' msg Let push = λo, m.(sm o , k o , e o • [m], φ o ) be the function that pushes message m into object o, and m : msg → Z → B → (Φ → S) → M the function that takes a message definition, index values, a boolean indicating if it is a reply, a binding context and a system to give us a new message m ∈ M . Then, the denotation of send, s : send → (Φ × S) → (Φ × S) which for the case of single variables is defined as v.α msg s (φ, sys) = (φ, sys [r →o ] ) where φ = φ φ ô r = φ (v) o = push(A sys (r ), α msg m (0, false, φ , sys)) (6.1)

2 .

 2 If there is a trigger, we check if the first message in the event pool matchs it (match) and guard evaluates to true under the local binding context, which is constructed from the input message by mbind : M → trigger → Φ. ô = (sm ô, k ô, m :: e , φ ô) match(m, α trigger ) φ m = mbind(m, α trigger ) α guard g (φ m φ ô, sys) (α action , φ m , sys) → * (φ , sys ) ô = A sys (r) (α trn , sys) → sys [r →(sm ô ,k ô ,e ,φ ô )]

KLISTING 6 . 3 :Definition 6 . 5 .

 6365 (a), and the indexed one, Z n → K(a). The indexed configuration is a function from indexes to configurations. The configuration value End allow us to view such function as a partial one. Let ι k : K(a) → IK (a) and ι i : Z n → K(a) → IK (a) be the injections for classical and indexed regions, respectively. Considering first region of Figure 6.3 to be indexed with index state Operating. on add(p: Int) / Int result = applyon addOp(p): initiator.added(result) to Operating Applyon usage inside state machine of Int The scalar is a parametric structure P (v) = ( sm , K, E, I, v) where v is instantiated to the mathematical model indicated by model.

  stmt ::= import | object | scalar | creator | fsm Import, object and scalar expressions follow the same constructions as their HOE 2 counterparts. They introduce new type definitions, objects and scalars, implementing an interface and a set of associations and a denotational model, respectively. object ::= 'object' ID '{' interface associations '}' scalar ::= 'scalar' ID '{' interface model '}'

  parstmt ',' parstmt | update expr forall block ::= 'forall' '[' indexset ']' '{' creator stmt '}' start ::= 'start' ID 'of' ID

  fsm ::= 'fsm' ID '.' ID '(' vardecl ')' '{' fsmstmt '}'where its statements are fsmstmt ::= fsmstmt ';' fsmstmt

  send ::= 'sendfrom' varexpr varexpr msg type param * | 'sendfrom' '[' arith exprs ']' varexpr varexpr msg type param * | 'reply' varexpr varexpr msg type param *

  update ::= var '=' varexpr | var '=' '{' param * '}' | var '=' 'create' ID '.' ID param * | var '=' 'applyon' varexpr applyon type param *

  goto ::= 'goto' ID wait ::= 'wait' varexpr [ waitfor ] waitthen + waitin ::= 'wait' varexpr 'in' region + [ waitfor ] waitthen + The expression goto unconditionally jumps to a labeled location. Instructions wait and waitin represent conditional branches with multiple target locations, differing from traditional intermediate representations for imperative languages where conditional branching schemes have two possible destinations. The wait clause requires an object to listen from, a list of accepted messages to wait for ( waitfor ) and a list of waitthen branches to jump to under specific conditions. This statement groups all the information concerning outgoing transitions of states. For instance, consider again the wait statements of Listing 7.3 and 7.4, which we present again below. wait this for (_m1_getY, Object src) = recv getY<> then when _m1_getY goto SBB_GET_Y; wait this for _m1_multed = recv Float'multed<Float>, _m2_multed = recv Float'multed<Float> then when _m1_multed, _m2_multed goto UBB_MULTING;

  sions as follows waitfor ::= 'for' recvexpr + recvexpr ::= recvdef '=' 'recv' ['[' indexset ']'] msg type recvdef ::= var | '(' var ',' var ')' Essentially, the receive expression provides a way to access grouped parameters, sender and indexes separately from the incoming message. Indexes are captured by indexed receives. We defined an optional indexset rule between brackets at receive expressions. This notation allows us to capture and bind indexes from the incoming message. For instance, consider the indexed reception shown at Listing 7.10 wait this for msg_takeY = recv[i: 0 <= i and i < 512] takeY<Float> then when msg_takeY goto UPDATE_CH then if msg_takeY.all goto FINAL; LISTING 7.10: Indexed receive It waits for the reception of a single message whos index value satisfies the specified constraint.

Figure 7 .

 7 2 summarises such translation. It describes a receive expression that captures the sender src to perform a reply on it. The reply semantics has two important implications a. Index-forwarding: By tracking which receive has defined the sender the IR compiler automatically transfers index values from the incoming message into the new reply message.

Figure 7 . 2 .

 72 Figure 7.2.

FIGURE 8 . 1 :

 81 FIGURE 8.1: Compilation Flow

  FIGURE 8.2: Definitions layers

FIGURE 8 . 3 :

 83 FIGURE 8.3: Granularity levels of variable definitions: object, association and element levels

  10) ψ(sendfrom sender target m param) = { ←m S } (8.11) ψ(s) = ∅ otherwise (8.12)

bbf 3 : 2 FIGURE 8 . 5 :

 3285 FIGURE 8.5: Message dependency analysis: FIFO equations

f 12 , w 12 f 23 , w 23 f 31 , w 31 FIGURE 8 . 6 :

 12122323313186 FIGURE 8.6: Loop in the control-flow and its FIFO equations

Algorithm 1 :

 1 mented a simple algorithm to eliminate concurrent dependencies from any send-receive graph M . Let us first define the equivalence class of parallel sends and concurrent receives as follows s = {s ∈ S | parallel(s, s )} r = {r ∈ R | r ∈ dom(r) ∨ r ∈ dom(r )} We show in Algorithm 1 the implementation of the π dependency elimination. Basically, for each receive r ∈ R, we take its incoming parallel send classes and we choose one send for each class. Then, we remove concurrent relations according to Corollary (8.7) and Definition (8.9). Remove π dependencies Data: Send-Receive graph M = (S R, T ) Result: Graph M without π dependencies for r ∈ R do P arallels ← { s | (s, r) ∈ T }; for P ∈ P arallels do if |P | ≤ 1 then / * No π dependencies here * / continue; end s ← choice(P ); / * From Corollary (8.7), P × {r} are π dependencies, hence we must remove relations from r to any other concurrent send s in P * / CS ← {(s , r) | s ∈ P ∧ s = s }; / * From Lemma (8.8) and Definition (8.9), we need to remove concurrent receives to the chosen s * / CR ← {(s, r ) ∈ T | r ∈ r ∧ r = r }; T ← T \ (CS ∪ CR); end end We show a running example in Table

and 2 Z

 2 d the power set of Z d and Σ a finite set of labels. That is, we have m inequations with parameters s, existentially quantified variables z and constants c.

  Using polyhedral sets, we define the index domain of certain IR statements. The index domain of a parallel IR statement D : parstmt → S is defined asD(α parstmt ,α parstmt ) = D(α parstmt ) ∪ D(α parstmt ) D(forall[ α indexset ] α send ) = α indexset α send D(forall[α indexset ] α update ) = α indexset α update D(α) = ∅ otherwiseusing a shorthand notation . for the denotational function. Additionally, we define the polyhedral union set of a waitin statement as the union of all its indexed region domains. Let w be a waitin statement of the form w = wait this in region recv then and we note D r ∈ S the polyhedral set of region r ∈ region such that D r ([α indexset ] {α f smstmt }) = α indexset r if we have an indexed region, or D r = ∅ otherwise. In addition, we model read and write accesses using polyhedral relations for send, receive and update statements following theirs operands. An access refers to a certain IR variable. Therefore, let us consider again the grammar of variables varexpr ::= varexpr '.' var | var var ::= id '[' arithexpr + ']'

FIGURE 8 . 14 :

 814 FIGURE 8.14: Wait-reply paths

FIGURE 9 . 1 :

 91 FIGURE 9.1: Optimizing pipeline

FIGURE 9 . 2 :

 92 FIGURE 9.2: Image object model

LISTING 9 . 5 :

 95 Image object model: Generated C code (b) The broadcast sending of getY() to all pixels is translated into an indexed region -Section 8.4.4. (c) The sendfrom operation is inserted into the new indexed region -Section 8.4.6. (d) The Pixel's state machine are inlined into each indexed region thanks to the interface entry Pixel, on getY() -> takeY(Float) -Section 8.4.7. (e) Finally, the indexed region created at (b) is translated into an efficient C for-loop.

IntFIGURE 9 . 4 :

 94 FIGURE 9.4: Image object model implementing JPEG till zigzag traversal

FIGURE 9 . 6 :FIGURE 9 . 7 :

 9697 FIGURE 9.6: Number of messages at optimization levels O0 and O1 (O2 eliminates all messages)

1

  for (int a = 0; (a <= 7); (a += 1)) { 2 for (int b = 0; (b <= 7); (b += 1

( 2 )FIGURE 9 . 11 :LISTING 9 . 12 :

 2911912 FIGURE 9.11: New interaction after distribution

FIGURE 9 . 12 :

 912 FIGURE 9.12: OpenCL-specific extension of the optimization pipeline

  114;" " float __new_var_5 = this->pixels[i].r * __new_var_6;" " float __new_var_3 = this->pixels[i].g * __new_var_7;" " float __new_var_4 = this->pixels[i].b * __new_var_8;" " float __new_var_1 = __new_var_4 + __new_var_3;" " float __new_var_2 = __new_var_5 + __new_var_1;" " this->pixels[i].y = __new_var_2;" " this->ychannel[i] = this->pixels[i].y;" "}" "" ; struct ImageGPU * __obj_new_ImageGPU_RGB(struct Int * rgb[1536]) { struct ImageGPU * this = (struct ImageGPU * ) malloc(sizeof(struct ImageGPU)); for(int i = 0; ((i >= 0) && (i < 512)); (i+=1)) { struct Int * inraw_slice[3] = { rgb[(3 * i)] , rgb[((3 * i) + 1)] , rgb[((3 * i) + 2)] }; this->pixels[i].r = inraw_slice[0]->value; this->pixels[i].g = inraw_slice[1]->value; this->pixels[i].b = inraw_slice[2]->value; } hoe2cl_platform * plt = hoe2cl_platform_new(, &kernel->input , this, sizeof(struct ImageGPU)); hoe2cl_kernel_run(kernel, 512); hoe2cl_kernel_read( kernel, &kernel->input , this, sizeof(struct ImageGPU)); return this; } LISTING 9.13: GPGPU generated codeconstraints introduced to get GPGPU code generation may wrongly seem to lack of genericity or, in other words, driven by the specific example. It remains to develop more interesting model examples to run on GPGPU and show that the approach applies broadly. Results and Contributions . . . . . . . . . . . . . . . . . . . . . . . 161 10.2 A Look Back to the Thesis Motivations . . . . . . . . . . . . . . . . . . . 163 10.3 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . 164 In the domain of Model-Driven Engineering (MDE), we studied in this thesis a new path for the modeling of parallel computations based on communicating Statecharts. The path led us to specific parallel extensions of the Statecharts formalism well-suited for data-intensive applications on recent parallel architectures.

FIGURE 10 . 1 :

 101 FIGURE 10.1: The HOE 2 approach

FIGURE 10 . 2 :

 102 FIGURE 10.2: Future directions and extensions (in red)

6 .

 6 Static reactions (SR), or internal transitions in the UML dialect: They are simply reactions that do not enter or exit the current state.7. Compound transitions:A compound transition represents a group of transitions to be executed at the same logical instant. For instance, in the left state machine t 1 and t 2 form a single compound transition and are executed atomically and in parallel. The right state machine implements a fork compound transition t = {t 1 , t 2 , t 3 }, which are also parallel

	and atomic.
	A	t1	t2	B

TABLE 3

 3

	.1: Supported Statechart features of reviewed research work

  The initiator value is directly related to the interface definition. Only the input messages exposed by the interface will set the initiator variable with the corresponding sender. For instance, given the relation exposed in the interface of Pixel, we see that initiator corresponds to the sender of message

	CompositeState
	cstate CompositeState.
	region { i: 1..N }
	initial S
	state S. on / to T
	state T. endon /
	endregion
	FIGURE 5.8: HOE 2 indexed regions

getY at line 32. This setting is clearly control flow dependent. The compilation process via our intermediate representation, presented in Chapter 7, makes definitions explicit.

S T

i: 1..N

  As another example, see the interface entry of scalar Float in Listing 5.13.For instance, let f1 and f2 be two Float scalars and, following HOE 2 notations, the send action f1.div(f2). Then, we should have the following transitions to collect all possible answers.

	scalar Int scalar Float
	interface interface
	on Add(Int) -> Added(Int) ~> AddOp on Div(Float) -> Dived(Float)
	on Mult(Int) -> Multed(Int) ~> MultOp or NaN()
	or Inf() model Z with (+): AddOp, ( * ): MultOp or nInf() ~> DivOp LISTING 5.12: Integer scalar LISTING 5.16: Extended Float scalar
	scalar Float
	interface
	on Div(Float) -> Dived(Float) or DivedByZero() ~> DivOp
		LISTING 5.13: Float scalar
	state Divided.
	on dived(f: Float) to NextState
	setting, scalar values follow the same semantics as generic immutable objects. This has a lot of on divedByZero() to ErrorState
	advantages in modeling languages.	LISTING 5.14: Message operations

To preserve the algebraic properties of scalars, including referential transparency, we choose a functional semantics for these state machines: a transition results in the construction of a fresh machine in a new state. As a result, in a functional For instance, consider again the state machine of Pixel object shown in listing 5.10. It extracts the luminance information from a Pixel in RGB format interacting with scalars. Note that interactions with scalars, at ComputeY for instance, are explicitly parallel and equivalent to generic objects from the modeling perspective. As a side-effect, it introduces a natural notation for (data) parallelism. The representation of scalars is compliant with the message passing semantics of HOE 2 , providing a consistent and homogeneous abstraction to the language.

The scalar defines operations in the form of message exchanges. It has an underlying carrier set that provides an intrinsic meaning to the type and its operations in the form of message exchanges. For instance, consider the Int scalar of Listing 5.12. The denotation of scalar Int is the set Z, which is built-in in the compiler and equivalent to Z, together with the denotation of message exchanges (addition and multiplication). The interface has a new kind of entry that we call operational transitions. Int has two operational transitions AddOp and MultOp. They model the beginning of an operation and its ending in an asynchronous manner.

Besides a clean integration on the modeling framework, this representation has interesting implications. We will show in Chapter 8 that operational transitions are foldable in the context of the intermediate representation. It means that send and receive pairs can be transformed into an in-place operation, which is exactly what the scalar interface captures. Formally, one may simply think of AddOp as the function AddOp : Z × Z → Z.

DivOp operator is a partial function (not defined when dividing by zero) but we can make it total by taking DivOp : R×R → (Dived+DivedByZero), where Dived R and DivedByZero models the return value on error condition. Therefore, message replies become values of the Scalar type being defined. Now, suppose we are able to find that send and receive expressions are actually related and that a language construct applyon which takes an object, an operation and a variable number of object parameters exists. In that case, we do not need to use message passing semantics and we can safely apply DivOp operator in-place as follows f = applyon f1 DivOp f2 [...] state Divided. [f is dived] to NextState [f is divedByZero] to ErrorState LISTING 5.15: Inlined operation

  Given that we may add new values (or reply types) to any scalar set and associate sum type as a return type of a given operator, could we have an operator such as DivOp : R+ N aN + Inf → R?The answer is no. The programmer cannot manipulate Inf or NaN values because there is no variable associated to them as they are the result of message matching at receive expressions -though we can send message named NaN if the scalar supports it.

	Image RGB	Color Transformation	Image YUV	Image Tiling
	Zigzag traversal	Quantization	DCT	Tiled Image (8x8)
	Stream 64ints	RLE and Huffman encoding
	FIGURE 5.10: JPEG algorithm phases

  α i trn , sys) → sys ∧ isExtT (α i trn ) ∧ ks = κn(sm, α i to ) (ι s (s), sys) (ks , sys )

					KsExt
	(α i trn , sys) → sys ∧ isEndT (α i trn ) (ι s (s), sys) (ι end , sys )	KsFinal
	(α i trn , sys) → sys ∧ isExtT (α i trn ) ∧ ks = κn(sm, α i to ) ∧ (ι c (s, kl), sys) (ks , sys )	kl i ∈kl	kl i = ι end	KcExt
	(α i trn , sys) → sys ∧ isEndT (α i trn ) ∧	kl i ∈kl	kl i = ι end
	(ι c (s, kl), sys)	(ι end , sys )

KcFinal

(ks i , sys)

  Two messages with same identifier but different parameter types are considered to be distinct. For instance, mult<Float> and mult<Int> are two different message types. The

	set of message types is defined as
	msg type	::= simple msg type
		| qualified msg type
	simple msg type	::= ID '<' obj type list '>'
	qualified msg type	::= ID ''' simple msg type

Given that two objects may define same message types, qualified message types allow us to disambiguate such naming collision when necessary. For instance, Float'mult<Float> and Int'mult<Float> define the same message, which models multiplications, under different sets of values.

  At the indexed receive of line 6, we know exactly the domain of i, which has been declared at line 2. In contrast to the IR, we introduce a new index variable with its associated domain each time we declare an indexed receive.

		state ComputeY. on getY() / : r.mult(0.299)
		, g.mult(0.587)
		, b.mult(0.114)
		to Multing
		[...]
		state Adding. on added(result: Float) / y = result: initiator.takeY(y)
		to ComputeY
		(a) HOE 2 Initiator
		wait this for (_m1_getY, Object src) = recv getY<>
		then when _m1_getY goto SBB_GET_Y;
		[...]
		UBB_ADDING:
		this.y = _m5_added.res;
		reply this src takeY<Float> this.y;
		(b) Initiator-like IR code
		FIGURE 7.2: Translation of initiators
	1	state GETY.
	2	on /: { i: 0..pixels.len -1 } pixels[i].getY()
	3	to GETTING_Y
	4
	5	state GETTING_Y.
	6	on takeY{i}(y: Float) /
	7	ychannel[i] = y to GETTING_Y
	8	endon [i.all]
	wait this for
		msg_takeY = recv[i: 0 <= i and i < 512] takeY<Float>
		LISTING 7.11: Rebinding index domain

  tion opportunities in presence of concurrent objects, say A and B, we would like to know at some instant the possible state(s) of B for a given state of A. Because data is wrapped inside messages, data-flow translates into concurrency. Many questions arise when compiling concur-

rent objects a. Is A the only producer from B's perspective? In other words, is B a shared object? b. Is A waiting for a response from B which is a direct consequence of a certain message m? c. On which state is B after consuming message m from A?

  s 1 : sendfrom ... mult<Int>, s 2 : sendfrom ... mult<Int>, s 3 : sendfrom ... mult<Int>; w 12 : wait ... m1 = recv multed<Float>, m2 = recv multed<Float> then when m1, m2 goto bb2;

		bb1
		bb2
	s 4 :	sendfrom ... add<Float>;
	w 23 :	wait ... m3 = recv multed<Float>, m4 = recv added<Float>
		then when m3, m4 goto bb3;
		bb3
		s 5 : sendfrom ... add<Float>;
		w 34 : wait ... m5 = recv added<Float>
		then when m5 goto bb4;
	FIGURE 8.7: Pixel control-flow with communication primitives only

TABLE 8 .

 8

	1: Selecting between non-deterministic send-receive relations
	this.cst = create Int.int 10;

  Definitions(8.18) and(8.19) are known access models in existing polyhedral tools[START_REF] Bondhugula | A Practical Automatic Polyhedral Program Optimization System[END_REF][START_REF] Verdoolaege | Polyhedral Parallel Code Generation for CUDA[END_REF], while(8.20) allow us to model structural accesses. We extract read and write accesses out of fsm statements in terms of labeled polyhedral relations. For instance, let s be the following statement

	forall[i: 1 <= i and i < 32]
	sendfrom this this.a[i-1] mult<Int> this.a[i];
		8.18)
	I(v[α arith exprs ]) = {v(x) | x = α arith exprs }	(8.19)
	I(α var expr .α var ) = I(α var expr ) × I(α var )	(8.20)

  To illustrate the general case, we show a simple looping example in Listing 8.4. Here we jump to different basic blocks, UPDATE_L and UPDATE_R, according to guards of then branches and store the message content on an association called new_table. The receive gives us a context domain

			#Entry	#Exit
	#Entry	#Exit
			i ∈ D1	#Header	i ∈ Dn
	#Header		#Body1	#BodyN
	#Body			#Body2	...
	i ∈ D			i ∈ D2
	(a) Wait-all with single	(b) Wait-all with multiple body
	body
	FIGURE 8.11: General case of wait-all loops
	forall [i: 0 <= i and i < 32]
	sendfrom[i] this this.table[i] Float'fadd<Float> this.cst10;
	goto DIVIDING;
	DIVIDING:
	wait this for m = recv[i: 0 <= i and i < 32] Float'fadded<Float>
	then when m if i < 16 goto UPDATE_L
	then when m if i >= 16 goto UPDATE_R
	then if m.all goto FINISHED;
	UPDATE_L:
	this.new_table[0, i] = m.res;
	goto DIVIDING;
	UPDATE_R:
	this.new_table[1, i -16] = m.res;
	goto DIVIDING;
		LISTING 8.4: Guarded branching
	where D i is the intersection of reception index domain and the corresponding transition guard
	leading to B ody i .

  1 ∩ D 2 = ∅ as required by the transformation. Therefore, we transform Listing 8.4 into two disjoint indexed regions with domains D 1 and D 2 , respectively.

	⇒forall[i: 0 <= i and i < 512]
	⇒ sendfrom[i] this this.pixels[i] getY<>;
	goto GETTING_Y;
	GETTING_Y:
	wait this in [i: 0 <= i and i < 512]
	{
	wait this for msg_takeY = recv[i] takeY<Float>
	then when msg_takeY goto UPDATE_CH;
	UPDATE_CH:
	this.ychannel[i] = msg_takeY.y;
	} then goto FINAL;
	Fusion
	GETTING_Y:
	wait img in [i: 0 <= i and i < 512] {
	⇒sendfrom[i] img img.pixels[i] getY<>;
	wait img for msg_takeY = recv[i] takeY<Float>
	then when msg_takeY goto UPDATE_CH;
	UPDATE_CH:
	img.ychannel[i] = msg_takeY.y;
	} then goto FINAL;
	FINAL:
	FIGURE 8.12: Loop fusion: Fusioning broadcast into indexed region

  Float __new_var_2 = applyon this.pixels[i].r multOp this.pixels[i].rcst;

	Float __new_var_1 = __new_var_2;
	into
	float __new_var_2 = applyon this.pixels[i].r multOp this.pixels[i].rcst;
	float __new_var_1 = __new_var_2;

  .2 where Listing 9.[START_REF] Mueller | Hidp: A Hierarchical Data Parallel Language[END_REF] shows its actual implementation. The Image object creates RGB pixels (Line 8) and uses parallel sending actions to get all gray values (Line 12). Underneath, the Pixel implements the actual gray conversion starting at creator RGB (Line 27). Everything is done through message pass-

	1 aligned_t __obj_Image_ImageSM(struct Image * this) { 2 for (int i = 0; ((i >= 0) && (i < 512)); (i+=1)) {
	3	float __new_var_8 = 0.114;
	4	float __new_var_6 = 0.299;
	5	float __new_var_7 = 0.587;
	object Image 6 float __new_var_1 = this->pixels[i]->r->value * __new_var_6; 7 float __new_var_2 = this->pixels[i]->g->value * __new_var_7; 8 float __new_var_4 = this->pixels[i]->b->value * __new_var_8; 9 float __new_var_5 = __new_var_4 + __new_var_1; has [512] Pixel as pixels 10 float __new_var_3 = __new_var_2 + __new_var_5; has [512] Float as ychannel 11 this->pixels[i]->y = __obj_new_Float_float(__new_var_3);
	12 sm ImageSM. this->ychannel[i] = this->pixels[i]->y; 13 } creator RGB(rgb: Int[1536]) / { i: 0..pixels.len -1 } 14 hoe2_object_done((struct hoe2_object * )this); 15 return 0; pixels[i] = new Pixel.RGB(rgb[3 * i..3 * i+2]) to GETY 16 }
	state GETY.
	on /: { i: 0..pixels.len -1 } pixels[i].getY()
	to GETTING_Y
	state GETTING_Y.
	on takeY{i}(y: Float) /
		ychannel[i] = y to GETTING_Y
	endon [i.all]
	object Pixel
	interface
	on getY() -> takeY(Float)
	has Int	as r, g, b
	has Float as y, u, v
	sm PixelSM.
	creator RGB(rgb: Int[3]) / r = rgb[0]
		, g = rgb[1]
		, b = rgb[2]
	to ComputeY / / Wait f o r getY and l a u n c h m u l t i p l i c a t i o n s
	state ComputeY. on getY() / : r.mult(0.299)
		, g.mult(0.587)
		, b.mult(0.114)
	to Multing / / C o l l e c t two m u l t i p l i c a t i o n s and l a u n c h t h e a d d i t i o n
	state Multing. on multed(v1: Float), multed(v2: Float) / : v1.fadd(v2)
	to MultAdding / / C o l l e c t l a s t m u l t i p l i c a t i o n s and l a u n c h a n o t h e r a d d i t i o n
	state MultAdding. on multed(v3: Float), fadded(v4: Float) / : v3.add(v4)
	to Adding / / Reply t o t h e s e n d e r o f getY ( ) by u s i n g keyword " i n i t i a t o r "
	state Adding. on fadded(result: Float) / y = result: initiator.takeY(y) ing, including basic arithmetics for which one message initiates the computation and another to ComputeY
	returns the result once computed. From such implementation, the compiler outputs the C code LISTING 9.4: Image model
	of Listing 9.5.
	We can see how optimizations explained at Chapter 8 are applied:

(a) The message-passing arithmetics are replaced by in-place operations -Section 8.4.8.

  tion, (1) Operational transition folding and indexed region generation and (2) Fully optimizing

	Image RGB	Color Transformation	Image YUV	Image Tiling
	Zigzag traversal	Quantization	DCT	Tiled Image (8x8)
	Stream 64ints	RLE and Huffman encoding
	FIGURE 9.3: Phases of the JPEG algorithm
		pixels
		[64, 64]
	[8, 8]	blocks
		[8]

  Image into two distinct objects, ImageCPU and ImageGPU, related by a new association, onGPU, From the language point of view of models, model transformations stands for HOE 2 source code transformations. The optimizing compiler proposed in this thesis tries to accomplish such work automatically at the IR level, or at the very least provide a set of wellfounded transformations to enable efficient code generation.

	import Converter world GP
	world GPU
	object User
	has Converter as system platform ImageProcessing
	has GP as gp
	sm UserSM has GPU as gpu / * Main a p p l i c a t i o n e n t r y : Create a " d e f a u l t " system * / creator main() / system = new Converter.default() to BootSystem LISTING 9.11: Platform description
	/ * Use c a s e " E x t r a c t gray component " * / state ExtractGrayComponent. on / : system.convert() to ExtractingGrayComponent underlying platform and the application to be distributed.
	state ExtractingGrayComponent. endon converted() / The implementation phase concerns platform-specific model transformations to ensure efficient
	code generation.		LISTING 9.10: Color converter source code
	Color converter		image	Image
					1			Image Processing
	raw Int 1536	512	ychannel Float	y 1		pixels Pixel 512	cpu GP 1	gpu GPU 1	System Platform
	rgb 3								World
	(a) Converter system analysis: Hierarchical Opening		(b) Platform model: GPGPU case
						Image Processing
			GP						GPU
	Converter		image	ImageCPU	onGPU	ImageGPU
			1				1
	raw Int 1536		512	ychannel Float		pixels Pixel 512
								1	rgb	1	y
								Int	Float	512
									ychannel ychannel
				(c) System design: Object distribution
			FIGURE 9.10: HOE 2 methodology: Distribution
	called platform and world. A platform may contain multiple worlds, which are capable of host-
	ing any applicative object. A particular distribution is given in Figure 9.10(c). We split object

in such a way that users and uses of Image may keep the same behavior as before. Clearly, the split object need to be rewritten according to the new implementation after distribution. Currently, the distribution and object splitting are ad-hoc tasks, guided by a good knowledge of the

(a) Filter block with fitting and paving matrices (b) Tiling the array

Owned by IBM.

In this thesis, we reviewed UML version 2.4.1, 2011.

Xtend is a flexible and expressive language that compiles into Java code.

We observe a similar issue between different C/C++ compilers due to undefined behaviors in the language specification.

A multi-valued association is an association with a multiplicity specification greater than one.

case we have an available message, we follow a message dropping policy. That is, if the popped message does not correspond to the current waiting one, then it is dropped.In the following sections, we present required notations and definitions. Then we develop our hierarchical approach where the semantics of HOE 2 actions, Γ A , form the bottom layer. On top of it, we define the semantics of transitions, Γ T , and finally the semantics of state machine configurations, Γ K . Figure6.2 describes the general mathematical view. A transition relation on Γ K depends on Γ T , which in turns depends on Γ A , hence forming a decoupled approach. This

Reply messages resides in the internal object buffer, otherwise they belong to the external one. It is a particular implementation of our double FIFO communications.

Note that Partial Maybe using the well-known Haskell type.

Note that the conditional function update returns the same function if the condition is false.

Note that φ corresponds to the local binding context and not the object one.

A model instance corresponds to a network of connected objects.

In case there is no native support, either at the language or architecture level, for the message passing semantics.

So far, we only replaced send/receive dependencies by in-place operations.

Remerciements

External and Internal FIFO. We detailed in Figure 6.1 the functional view of writes to the external and internal FIFOs of the state machine. However, we did not specify how the state machine decides from which one it is going to read. As for the writes, the choice is based on its interface. Naturally, the reads follows similar conditions. More precisely, if α trigger is exposed at the interface then we look for non-reply messages. Otherwise, we look for reply ones.

Initiator. According to Definition 6.2, the object has an initiator reference. We use it in the semantics of sending actions via the initiator keyword, as shown in Section 6.3.3. On the other hand, the message sender reference (as defined in 6.3) was never used yet. Let m ∈ M be a non-reply message, the initiator reference I ô is set to the message sender reference R m iff M m belongs to the object interface. That is, the object receives an external message. where

End otherwise

The indexed configuration (6.5) puts the state machine at state A, where its nested first region is at state S and the second indexed one is at T i , ∀i ∈ [0, 255].

Scalars

The semantics of scalars differs slightly from that of objects in the sense that they "hide" a concrete value belonging to a specified mathematical set, hence providing state machine semantics to scalar values. For instance, consider again the Int object shown at Listing 6.2.

In this particular case, the Int object wraps a value ∈ Z where Z is the denotation of Z.

Receiving

Listing 7.3 shows the entry point of the state machine. First of all, the state machine is introduced with fsm and its unique and mandatory argument plays the role of the "this" pointer found in other object-oriented programming languages (here it might have been called differently). The state machine contains a list of labeled statements. The first statement is a wait expression. It needs to know on which channel we want to wait together with a list of receives clauses, which in this case refers to the external message getY. In the IR context, we consider object as channels and use both terms indifferently. The receive clause allows us to extract all the information contained into the incoming message. It defines two variables _m1_getY and src which are of type Message and Object, respectively. The message is a struct-like variable enclosing all the formal parameters while src refers to the message sender. It follows a list of then test cases.

In above state machine, we branch to label SBB_GET_Y if message _m1_getY has been received. We will develop more about each statement in the following sections.

Parallel update and send

To continue with the overview of this particular example, Listing 7.4 shows the start of the luminance computation. We found parallel definitions of variables (rcst, gcst, bcst) and parallel sending actions (sendfrom). In order to have a close equivalence to the HOE 2 input language, the IR implements parallel statements that combine send and update actions. Note that dot notation no longer means message sending but structural access to object and message variables.

The statement create calls the creator of Float object with the corresponding value. Similar to the HOE 2 implementation, it sends three multiplication messages in parallel and waits for two of them afterwards. Throughout this section we informally showed the translation of HOE 2 to our IR. In the next chapter, we will present the optimizing compiler chain and code generation strategy.

Contributions

The IR is designed to be compiler-friendly, i.e., suitable for analysis and optimizations. Indeed, important compiler structures such as the control-flow of basic blocks can be constructed directly from it. It also offers a cleaner path to code generation. No matter which runtime the language is based on, we need to make a distinction between object creation (introduction into the runtime environment) and its main behavior (thread).

It provides specific instructions for communication primitives with an explicit chain of variable definitions and uses to build incoming messages and extract all the needed information. Most importantly, the IR preserves the state machine hierarchical information. It is also highly expressive as it supports arrays, dynamic creation of state machines, iterators, provides fork/join Let M = (S R, T ) be the output graph of our message dependency analyzer on the set of send S and receives R where T ⊆ S × R.

Lemma 8.6. A receive related to more than one send necessarily represents φ or π dependencies.

Proof. The only way for a receive to be related to more than one send is to have a term of the form

where the alternation can only come from (8.13), i.e. control-flow dependent, or the combinatorial expansion of multisets of messages introduced by parallel sends in (8.10), thus a nondeterminstic relation (see Type correctness of receives).

From the proof of Lemma (8.6), we deduce the following important corollary Corollary 8.7. Let (s, r), (s , r) ∈ T where s and s are parallel sends then r = π(s, s ).

Therefore, given any M we are able to discover π dependencies and as a consequence of Lemma (8.6) we have φ dependencies as well. The following lemma will help us expose the structure of M among parallel sends.

Rewriting Broadcasts

This pass transforms what we call wait-all loops into indexed regions. Wait-all loops are loops that wait for all indexed messages under a certain domain to arrive and quit the main loop afterwards. For instance, consider the loop of Listing 8.2 taken from the Image example. The loop groups basic blocks GETTING_Y and UPDATE_CH and it forms a wait-all loop. The wait branch at Line 7 waits for all takeY<> messages on the specified range of index values. Given that the arrival order of messages is not specified, the loop can be "parallelized" into an indexed region. Listing 8.3 illustrates the transformation where a new indexed region is introduced at Line 5. Note that parallel regions inside composite states receive their own copy of the incoming message. The message dropping semantics guarantees that regions not concerned by messages with wrong index values will drop them.

The loop pattern is shown in Figure 8.11(a) where D is the integer set denoted by the index domain at receive expression. We rapidly see that it can be extended to loops with multiple bodies as shown in Figure 8 Inlinee object never escapes. This constraint guarantees that the inliner is the only producer and inlinee its only consumer. Therefore, if the inlinee waits on a given message, which is exposed on its interface, it will only react to the inliner sending actions and no one else. This provides us a precise knowledge of the inlinee state at the beginning of the transaction.

The inliner completes the transaction. The inliner candidate must contain some send-receive relation. We rely on the Transaction Selector (see Section 8.

Folding of Operational Transitions

In Chapter 5, we presented the HOE 2 operational transitions and mentioned that they can be transformed into "in-place" operations. We built around this idea the HOE 2 scalar operations.

This pass concretizes such idea with the help of the Transaction Selector by folding operational transitions. We have shown in the precedent section that send-receive relations can be inlined and we show here that we can materialize them using the

is translated into the IR statement as

Int result = applyon this Int'addOp p which is then mapped to a native operation, addition in this particular case, that works on the unboxed type. 1 Int result = __obj_new_Int_int(this->value + p->value); Indexed Regions: AST Generation from Polyhedra. HOE 2 implements asynchronous indexed regions using affine constraints. We consider a coarse-grain asynchronous composition of regions, i.e., each region is viewed as an atomic indexed statement, which means that there is no specific execution order of each ith regions. Then, we generate for-loops in a lexicographic order, which is a valid order among all possible ones under asynchronous composition. Such scheduling is valid under a strong hypothesis: no explicit inter-iteration synchronization. In other words, the indexed region does not contain inter-iteration message dependences imposing a communication-dependent order. Thereby, if we have an indexed region such as wait this in [i, j: 0 <= i and i < 256 and 0 <= j and j < 256] { / / Indexed r e g i o n

(2)

Requirement analysis

Main activity : Requirement formalization

System analysis

Main activity : Hierarchical opening

System design

Main activity : Distribution

System implementation

Main activity : Implementation (1) First proposition of a specifi c platform topology that User and System are HOE 2 objects, they form more generally a closed system until future system releases. We concretized the system requirement view in Listing 9.10.

The system analysis phase involves a hierarchical opening of the system. That is, after defining a set of convenient use cases, the system designer concentrates on the required objects to meet such requirements. We show in Figure 9.10(a) a particular hierarchical opening of the system.

In the next phase, we proceed to the system design where its main activity concerns object distribution. The application is distributed over a predefined platform model. In order to show the main idea, we propose a simplistic model of a GPGPU platform depicted in Figure 9.10(b), and its equivalent source code view shown at Listing 9.11. We have two new meta-model concepts

Syntax

We present in the following sections the syntax of the HOE 2 language and its Intermediate Representation (IR). We use traditional grammar operators to denote zero or many elements * ,