...to my parents

Abstract

The advent of many-core platforms is nowadays challenging our capabilities for efficient and predictable design. To meet this challenge, designers need methods and tools for guaranteeing essential properties and determining tradeoffs between performance and efficient resource management.

In the process of designing a mixed software/hardware system, functional constraints and also extra-functional specifications should be taken into account as an essential part for the design of embedded systems. The impact of design choices on the overall behavior of the system should also be analyzed. This implies a deep understanding of the interaction between application software and the underlying execution platform.

We present a rigorous model-based design flow for building parallel applications running on top of many-core platforms. The flow is based on the BIP -Behavior, Interaction, Priority -component framework and its associated toolbox. The method allows generation of a correct-by-construction mixed hardware/software system model for manycore platforms from an application software and a mapping. It is based on source-tosource correct-by-construction transformations of BIP models. It provides full support for modeling application software and validation of its functional correctness, modeling and performance analysis of system-level models, code generation and deployment on target many-core platforms.

Our design flow is illustrated through the modeling and deployment of various software applications on two different hardware platforms; MPARM and platform P2012. MPARM is a virtual ARM-based multi-cluster manycore platform, configured by the number of clusters, the number of ARM cores per cluster, and their interconnections. On MPARM, the software applications considered are the Cholesky factorization, the MPEG-2 decoding, the MJPEG decoding, the Fast Fourier Transform and the Demosaicing algorithm. Platform 2012 (P2012) is a power efficient manycore computing fabric, which is highly modular and based on multiple clusters capable of aggressive fine-grained power management. As a case study on P2012, we used the HMAX algorithm.

Experimental results show the merits of the design flow, notably performance analysis as well as correct-by-construction system level modeling, code generation and efficient deployment.

Résumé

L'objectif du travail présenté dans cette thèse est de répondre à un verrou fondamental, qui est "comment programmer d'une manière rigoureuse et efficace des applications embarquées sur des plateformes multi-coeurs?". Cette problématique pose plusieurs défis : 1) le développement dune approche rigoureuse basée sur les modèles pour pouvoir garantir la correction; 2) le "mariage "entre modèle physique et modèle de calcul, c'est-à-dire, l'intégration du fonctionnel et non-fonctionnel; 3) l'adaptabilité. Pour s'attaquer à ces défis, nous avons développé un flot de conception rigoureux autour du langage BIP. Ce flot de conception permet l'exploration de l'espace de conception, le traitement à diffèrent niveaux d'abstraction à la fois pour la plate-forme et l'application, la génération du code et le déploiement sur des plates-formes multi-coeurs. La méthode utilisée s'appuie sur des transformations source-vers-source des modèles BIP. Ces transformations sont correctespar-construction.

Nous illustrons ce flot de conception avec la modélisation et le déploiement de plusieurs applications sur deux plates-formes différentes. La première plate-forme considérée est MPARM, une plate-forme virtuelle, basée sur des processeurs ARM et structurée avec des clusters, o chacun contient plusieurs coeurs. Pour cette plate-forme, nous avons considéré les applications suivantes: la factorisation de Cholesky, le décodage MPEG-2, le décodage MJPEG, la Transformée de Fourier Rapide et un algorithme de demosaicing. La seconde plate-forme est P2012, une plate-forme multi-coeur, basée sur plusieurs clusters capable d'une gestion énergétique efficace. L'application considérée sur P2012 est l'algorithme HMAX.

Les résultats expérimentaux montrent l'intérêt de notre flot de conception, notamment l'analyse des performances ainsi que la modélisation au niveau du système, la génération de code et le déploiement.

Part

Context

-Chapter 1 -

Introduction -From Programs to Systems

General Context Embedded systems have become essential part of our daily lives. In contrast to general purpose computer systems, embedded systems integrate software and hardware, and are specifically designed to perform particular predefined tasks, which are often critical. Usually, they are not standalone devices, but they constitute the computerized part of a larger device. Mainly, we divide embedded systems in two categories: the reactive systems that continuously interact with the environment and the transformational systems that compute a function and terminate. Embedded systems appeared in the market in the early 1960s and since then they have become ubiquitous. Applications can be found in a tremendous variety of domains covering medical equipment, telecommunications, military applications, household appliances and consumer electronics, wireless sensor networks, transportation and avionics. The complexity of embedded systems varies from single micro-controller chip to multiple units and networks incorporated inside a larger system.

Efficiency of embedded systems is of paramount importance. To construct efficient systems optimizations are eligible upon design for energy cost, code size, execution time, weight and dimension, performance and reliability for both the software and the hardware part.

Embedded systems require a synergistic function between software and hardware design and development. The software is specific and often executed in a repeated fashion. However, for reusability reasons software application are often platform independent and immaterial. Conceptually, it is developed based on a high-level model which is decomposed into multiple components for the sake of complexity. A component-based model is normally well structured and is ideally characterized by formal semantics.

A software application is designed to execute on a logical time rather than on a realtime axis. Specifically, abstractions are considered about the behavior such as concurrent execution, instantaneous computation and communication steps, atomicity of actions and zero delays. The above abstractions should consider the functional constraints imposed by the program specifications such as deadlocks, throughput and jitter. Along with the software design, the hardware design should also be considered as a part of an efficient embedded system design. Small homogeneous processing units connected by a Networkon-Chip tend to succeed the complex superscalar architectures nowadays. The number of cores to be integrated in a single chip is expected to rapidly increase in the coming years, moving from multicore to manycore architectures. This leads to investigate new approaches for embedded systems design. Many-core computing architectures require correct design and programming methodologies which exploit parallelism, thus increasing the performance, the scalability and the flexibility of the system. A correct design should also include successful resource allocation and run-time power management. It should also exploit the innovative capabilities of dynamic extension and reconfiguration, at run-time, of the architecture template depending on a possible variable workload and an interactive environment.

In the process of designing a mixed software/hardware system, functional constraints and also extra-functional specifications should also be taken into account as an essential part for the design of embedded systems. The extra-functional specifications concern the use of resources of the execution platform such as time, shared memory, semaphores, queues, energy, distribution and communication of tasks and scheduling policies. Interacting with the platform is real-time. Therefore, it becomes non-trivial the task of evaluating if a software/hardware system preserves the timing properties of its application software. It requires analysis of the impact of design choices on the overall behavior of the system. It also implies a deep understanding of the interaction between application software and the underlying execution platform. We currently lack approaches for modeling mixed hardware/software systems. There are no rigorous techniques for deriving global models of a given system from models of its application software and its execution platform.

System Level Design System design is the process leading to a mixed software/hardware system meeting given specifications. It involves the development of application software taking into account features of an execution platform. The latter is defined by its architecture involving a set of processors equipped with hardware-dependent software such as operating systems as well as primitives for coordination of the computation and interaction with the external environment. A simplified view of a system design is illustrated in Figure 1.1. Design approaches are developed based on the experience and expertise of the design teams. They tend to re-use, extend and improve existing solutions proven efficient and robust. This favors increased productivity since design methodologies are re-used. Reusability of components is an important issue. Systems are built by reusing and assembling components that are simpler sub-systems. This is the only way to master complexity and to ensure correctness of the overall design, while maintaining or increasing productivity. However, a design methodology may turn to be counter-productive and result to low adaptivity upon new system requirements. Better solutions may be a priori excluded because they do not fit the designers know-how. The main goal of a system design, albeit the heterogeneity of the assembling components and the difficulties upon integration of different technologies, is the efficient prediction of the behavior of a software application running on an execution platform.

Program SW

A system design flow consists of steps starting from specifications and leading to an implementation on a given execution platform. It involves the use of methods and tools for progressively deriving the implementation by making adequate design choices.

We consider that a system design flow must meet the following essential requirements:

Functionality and Performance. The design flow must allow the satisfaction of both functional and extra-functional properties. This means that functional properties such as deadlock freedom, jitter, throughput and resources such as memory, time and energy are first class concepts encompassed by formal models. Moreover, it should be possible to analyze and evaluate efficiency in using resources, which conform with the functional requirements, as early as possible along the design flow. Lack of adequate semantic models does not allow consistency checking for timing requirements, or meaningful composition of features.

Correctness. This means that the designed system meets its specifications. Ensuring correctness requires that the design flow relies on models with well-defined semantics. Semantics should be defined at both the execution and the interaction level of the models. The models should consistently encompass system description at different levels of abstraction from application software to its implementation. Correctness can be achieved by application of verification techniques. It is desirable that if some specifications are met at some step of the design flow, they are preserved in all the subsequent steps. This can be achieved by transforming the application software model to include the important physical aspects of the target platform.

Heterogeneity and Adaptivity. Heterogeneity in systems design can be supported by developing high level domain-specific languages ease of expression. System model semantics should encompass heterogeneity in computation, interaction and abstraction level to facilitate modeling mixed hardware/software systems. This should be accompanied by reusability allowing the definition of libraries of components to be reused and the development of component-based solutions. The design flow should not enforce any particular programming or execution model. Specific programming models or implementation principles may a priori exclude efficient solutions and parallelism. For instance, programming multimedia applications in plain C may lead to designs obscuring the inherent functional parallelism and involving built-in scheduling mechanisms that are not optimal. It is essential that designers use adequate programming models. The above characteristics along with a tool integration for programming, validation and code generation perceive a productive design flow.

We call rigorous a design flow which allows guaranteeing essential properties of the specifications. Most of the rigorous design flows privilege a unique programming model together with an associated compilation chain adapted for a given execution model. For example, synchronous system design relies on synchronous programming models and usually targets hardware or sequential implementations on single processors [START_REF] Halbwachs | Synchronous Programming of Reactive Systems[END_REF]. Alternatively, real-time programming based on scheduling theory for periodic tasks, targets dedicated real-time multitasking platforms [START_REF] Burns | Real-Time Systems and Programming Languages[END_REF].

A rigorous design flow should be characterized by the following:

• it is model-based, that is, both application software and mixed hardware/ software system descriptions are modeled by using a single, semantic framework. As stated in [BBB + 11], this allows maintaining the coherency along with the flow by proving various transformations used to move from one description to another while preserving essential properties. This means that the semantic model is expressive enough to directly encompass various types of component heterogeneity arising along the design flow [START_REF] Henzinger | The Embedded Systems Design Challenge[END_REF].

• it should be component-based, that is, it should provide primitives for building composite components as the composition of simpler components. The use of components reduces development time by favoring component reuse and provides support for incremental analysis and design, as introduced in [BBNS08, BBNS09, BBL + 10].

• it should be correct-by-construction, that is, all design flow steps concerning the synthesis of the final model should be proven to guarantee the preservation of all properties of the initial input model.

• it should be tool-supported, that is, all steps in the design flow should be realized automatically by tools ensuring significant productivity gains.

System Design Flow

We propose a system construction method that is both rigorous and allows fine-grain analysis of system dynamics. It is rigorous because it is based on formal models described in BIP [START_REF] Basu | Modeling heterogeneous real-time components in bip[END_REF], with precise semantics that can be analyzed by using formal techniques.

A system model in BIP is derived by progressively integrating constraints induced on an application software by the underlying hardware architecture. In contrast to ad hoc modeling approaches, the system model is obtained, in a compositional and incremental manner, from BIP models of the application software and respectively, the hardware architecture, by application of source-to-source transformations that are proven correctby-construction. The system model describes the behavior of the mixed hardware/software system and can be simulated and formally verified using the BIP toolset [bip]. The method for the construction of mixed hardware/software system models is illustrated in Figure 1.2. It takes as inputs: (i) the application software model, the hardware architecture and (iii) the mapping between them. It proceeds in four main steps. The first step is the generation of the application software model in BIP. This is achieved by an automatic translation of the input application software model which should be described in a process network with a well defined structure. The translation preserves intact the behavior and the characteristics of the initial application software.

The second step is the synthesis of the hardware architecture model in BIP. A library of BIP atomic components that characterize manycore architectures is defined, including models for hardware components (e.g., processor, memory) and for hardware-dependent software components (e.g., FIFO channel read/write, bus controllers, schedulers). Combining the hardware architecture specifications and the suitable BIP library components, we synthesize the hardware architecture model in BIP. The model is parametrized and allows flexible integration of specific target architecture features, such as arbitration policy, latency for buses and memories, scheduling policy etc.

The third step is the construction of the mixed software/hardware system model. This model represents the behavior of the application software running on the hardware architecture according to the mapping, but without taking into account execution times for the software actions. This step consists in progressively enriching the application software model by doing: (1) Application of a sequence of source-to-source transformations to synthesize hardware dependent software routines implementing communication by using the hardware components. (2) Integration of hardware components used in the system model. The transformations are proved correct-by-construction, that is, they preserve functional properties of the application software.

In the final step, the (bounds for) execution times are obtained by analysis or simulation of the run of every software process in isolation on the platform. These bounds are injected into the system model and lead to the calibrated system model. This final model allows accurate estimation through simulation of real-time characteristics (response times, delays, latencies, throughput, etc.) and indicators regarding resource usage (bus conflicts, memory conflicts, etc.).

The above design flow sticks to the general principles of rigorous design introduced in the previous section. Namely, it is model-based, component-based, correct-by-construction and tool-supported.

Related Work in System Design

To the best of our knowledge, the BIP design flow is unique as it uses a single semantic framework to support application modeling, validation of functional correctness, performance analysis on system models and code generation for manycore platforms. Building faithful system models is mandatory for validation and performance analysis of concurrent software running on manycore platforms.

Synchronous languages [START_REF] Benveniste | The synchronous approach to reactive and real-time systems[END_REF] such as Esterel [START_REF] Berry | The esterel synchronous programming language: Design, semantics, implementation[END_REF], Lustre [START_REF] Halbwachs | The synchronous dataflow programming language lustre[END_REF] and Signal [START_REF] Benveniste | SIGNAL : a data flow oriented language for signal processing[END_REF] offer strong formal semantics that facilitate by construction verification and code generation, but they have remained limited to safety-critical domains such as aviation and automotive.

Simulink [Mat] and Stateflow [Sta] are synchronous formalisms that are mainly used to generate quickly an input for an FPGA prototype implementation through Verilog and VHDL.

Many of the frameworks, which we present below, follow the Y-chart design principle [BCG + 97, KDVvdW97] as we do in our design flow. Namely, these are DOL, SPADE, Sesame, Polis, Metropolis, Artemis, Octopus and CoFluent. This means that they decouple application from architecture by recognizing two distinct models for them. According to the Y-chart approach, an application model -derived from a target application domaindescribes the functional behavior of an application in an architecture-independent manner. The principle is illustrated in Figure 1 DOL [START_REF] Thiele | Mapping applications to tiled multiprocessor embedded systems[END_REF] introduces a framework for specifying and mapping parallel applications onto heterogeneous multiprocessor platforms. It defines abstraction models for the application and architecture, as well as a format for the mapping specification. They integrate an analytic performance analysis strategy to replace modeling and analyzing a multiprocessor system using other methods. The system level performance analysis is based on formal analysis techniques using Real Time Calculus [START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF].

Polis [BCG + 97] is considered as a pioneer method for platform-dependent design as it set the separation of concern principle for architecture and function, communication, and computation. Polis supports one model of computation described in finite-state machines (FSM). It is focused on automotive application domain supporting architecture based on a single microprocessor and peripherals. The supported tools were simulation, architectural exploration with accurate and fast code execution time evaluation using automatically generated from the FSMs model. However, Polis is considered limited both the model of computation and in the target architecture.

Metropolis [BLP + 02, BWH + 03] is a framework which follows the mapping of function to architecture paradigm in the Y-chart organization. Architectures are represented as computation and communication services. The association of functionality to architectural services allow Metropolis to evaluate characteristics (such as latency, throughput, power, and energy) of an implementation of a particular functionality with a particular platform instance. Metropolis has back-end tool connection with a SystemC simulator and to verification of LTL and LOC constraints. MetroII [START_REF] Abhijit | A next-generation design framework for platformbased design[END_REF] is a framework extending Metropolis to import heterogeneous IPs, to facilitates performance analysis and design space exploration.

Artemis workbench [Pim08, PHL + 01] begins with a Simulink representation of the functionality of the design that is converted in Kahn Process Networks (KPN). KPNs are also used to capture the architecture based on a set of virtual processors. Eventually, Artemis generates VHDL to obtain an FPGA implementation.

Ptolemy [EJL + 03, Lee09] develops another approach analyzing the behavior of interfaces to find whether two models can be composed in a semantic framework that support this form of heterogeneity. In fact, interfaces are finite-state machines used for hetero-geneous modeling. Ptolemy uses Java as an imperative language and is more embedded software oriented rather than dealing with hardware architectures.

CoFluent Studio [CoF] is developed for system architecting. It supports the MCSE methodology (Méthodologie de Conception des Systémes Electroniques). It follows the mapping of function to architecture in the Y-chart paradigm. The approach is dual: one for the software developer to satisfy the functional specifications and one for the architecture designer. Simulation and platform prototyping is supported.

Octopus [START_REF] Twan | Model-driven design-space exploration for embedded systems: The octopus toolset[END_REF] is specifically designed to support Design-Space Exploration (DSE). It allows the independent specification of applications, platforms, and mappings, following the Y-chart approach, and aims to integrate existing formal analysis and simulation tools in the DSE process.

SystemCoDesigner [START_REF] Haubelt | Systemcodesigner: automatic design space exploration and rapid prototyping from behavioral models[END_REF] is tool for Design Space Exploration (DSE) and prototyping. SystemCoDesigner starts from a behavioral SystemC model and generates hardware accelerators and hardware/software solutions for DSE. It also provides the capability for prototyping on an FPGA basis constructing a link between Electronic System Level (ESL) and Register Transfer Level (RTL).

LusSy [MMMcMc] is a tool for the analysis of SystemC transactional models. Starting from the source code of a SystemC design, it uses GCCs C++ front-end and the SystemC library itself for parsing, then transform it into a set of automata, and finally dump it in the Lustre language. Thus, it provides a way to express safety properties directly in SystemC, by using identifying operational semantics for TLM models written in full Sys-temC. Although the method has a working connection to verification tools, the semantics remain abstract because Lustre is less expressive than a general-purpose language which deals with dynamic data structures.

VISTA [START_REF] Moussa | Exploring SW Performance Using SoC Transaction-Level Modeling[END_REF], based on SystemC [START_REF] Grotker | System Design with SystemC[END_REF], provides a methodology and tool for modeling SoC virtual platform for SW development and system level performance analysis and exploration. The SoC provides a cycle-accurate functional model of the architecture using the basic SystemC Transaction Level Modeling (TLM) components provided by VISTA. It supports cross-compilation on the target processor and back annotation, therefore bypassing the use of an Instruction Set Simulator (ISS). However, it may hardly be used for other purposes than performance analysis due to the lack of a formal specification of the system.

A simulation based method is presented in [START_REF] Kienhuis | An approach for quantitative analysis of application-specific dataflow architectures[END_REF]. The authors specify software applications as Kahn graphs and they textually instantiate different architectures from an architecture template. They obtain performance numbers by using a configurable simulator in C++ that has been constructed for the architecture template, using multithreading and object oriented programming techniques. Even though the model is at a high level of abstraction, the simulator can efficiently execute different types of dataflow architectures at a level that is clock-cycle accurate.

The Sesame [START_REF] Erbas | A framework for system-level modeling and simulation of embedded systems architectures[END_REF] modeling and simulation environment facilitates performance analysis of embedded media systems architectures according to the Y-chart design principle [BCG + 97, KDVvdW97]. Sesame aims at early system evaluation and design space exploration using model calibration and trace-driven cosimulation.

Daedalus [NTS + 08] offers a fully integrated tool-flow in which design space exploration (DSE), system-level synthesis, application mapping, and system prototyping of Multi-Processor System on Chips (MP-SoCs) are highly automated. It is based on Sesame framework [START_REF] Erbas | A framework for system-level modeling and simulation of embedded systems architectures[END_REF] and automatically extends it to VHDL implementations of the MP-SoC platform architecture generated by the ESPAM tool [START_REF] Nikolov | Automated integration of dedicated hardwired ip cores in heterogeneous mpsocs designed with espam[END_REF][START_REF] Nikolov | Multi-processor system design with espam[END_REF]. The Daedalus high-level MP-SoC models aim at the accurate prediction of the overall system perfor-mance.

SPADE [START_REF] Lieverse | System level design with SPADE: an M-JPEG case study[END_REF] is a method and tool for architecture exploration of heterogeneous signal processing systems used to evaluate alternative multi-processor architectures. It follows the Y-chart paradigm for system level design, on which the application and architecture are modeled separately and mapped onto each other in an explicit design step. SPADE uses a trace-driven simulation technique and permits architectures to be modeled at an abstract level using a library of generic building blocks.

SymTA/S [Hea05] is a system-level performance analysis approach based on formal scheduling analysis techniques, event streams [RE02, RZJE02] and symbolic simulation. The tool supports heterogeneous architectures and determines system-level performance data such as end-to-end latencies, bus and processor utilization, and worst-case scheduling scenarios.

In [START_REF] Abdeddaim | Scheduling with Timed Automata[END_REF] the authors suggest a method of timed automata, for solving optimal scheduling problems. They demonstrate that the timed-automata-based methods can be used to synthesize scheduling strategies for applications with uncertain task durations. In [START_REF] Ben Salah | Compositional Timing Analysis[END_REF] the authors developed a methodology for automatic abstraction of systems modeled by timed automata allowing them to analyze timed automata of greater size and complexity. In [START_REF] Cotton | Multi-criteria optimization for mapping programs to multi-processors[END_REF], trade-offs between communication cost and computational workloads are modeled addressing the problem of mapping applications to processors in a multicore environment.

A hybrid approach for system level performance evaluation of embedded systems that combines formal analysis methods with a simulation framework in presented in [START_REF] Künzli | Combining simulation and formal methods for system-level performance analysis[END_REF]. However, the current approach is limited to small systems.

Organization of the Document

This document is composed of four parts, the first presenting the context of the work (Chapter 1 and Chapter 2), the second describing the system designer method which is the thesis contribution (Chapters 3, 4, 5, 6, 7 and 8), the third presenting the results of implementation and experimentation (Chapters 9, 10 and 11) describing the tool developed and applying the methodology presented in the contribution, and the last part (Chapter 12) drawing the conclusion and perspectives. The details of all Chapters are as follows. Chapter 2 describes the BIP component-based framework which is the foundation of this work. Chapter 3 presents the BIP Language Factory and the construction of software model in BIP using well structured models. The synthesis of HW Platforms in BIP and the library of HW components is provided in Chapter 4. In Chapter 5 we analyze the method and the necessary transformations used to efficiently map an application software model in BIP with the HW Platform model. Chapter 6 presents the mixed software/hardware system in BIP integrating all the HW platform constraints. Chapter 7 describes the two methods of integration the run-time HW/SW constraints which are the execution times of every software process in isolation. The method used for performance analysis and the comparison with related work is found in Chapter 8. Chapter 9 described the whole tool-flow developed to automatically generate an accurate system model in BIP. Chapter 10 and Chapter 11 present the two case studies considered in this work which respectively concern two different HW platforms. Chapter 12 draws the conclusion of this work and the futures perspectives.

-Chapter 2 -

The BIP Framework

The BIP -Behaviour/Interaction/Priority-framework [START_REF] Basu | Modeling heterogeneous real-time components in bip[END_REF] is aiming at design and analysis of complex, heterogeneous embedded applications. BIP is a highly expressive, component-based framework with rigorous semantical basis. It allows the construction of complex, hierarchically structured models from atomic components characterized by their behavior and their interfaces. Such components are transition systems enriched with data. Transitions are used to move from a source to a destination location. Each time a transition is taken, component data (variables) may be assigned new values, computed by user-defined functions (in C/C++). Atomic components are composed by layered application of interactions and priorities. Interactions express synchronization constraints and define the transfer of data between the interacting components. Priorities are used to filter amongst possible interactions and to steer system evolution so as to meet performance requirements e.g., to express scheduling policies. This chapter is structured as follows. The abstract model of BIP is described in Section 2.1 as an abstract formalization of the layers of Behavior, Interactions and Priorities. Section 2.2 describes the concrete model of BIP extended with data. We introduce the concepts of Components and Connectors to build system models and we define the operational semantics of all three layers (behavior, interaction, priorities). Section 2.3 describes the basic constructs of the BIP Language. Section 2.3 presents the BIP Tool-chain, the BIP execution engines and the Distributed Implementation. Conclusions are given in the last section.

Priorities Interactions

B E H A V I O R Figure 2.1: Structure of a BIP Model

Abstract Model of BIP

We provide a formalization of the BIP model focusing on the individual layers of behavior, interaction and priority glue (see Figure 2.1). In this section, we provide for each layer its abstract model.

Modeling Behavior

An atomic component is the most basic BIP component which represents behavior. A formal definition for the behavior of an atomic BIP component is given below:

Definition (Behavior)

A behavior B is a labeled transition system represented by a triple (Q, P, →), where:

• Q is a finite set of control states,

• P is a set of communication ports,

• →⊆ (Q × P × Q) is a set of transitions, each labeled by a port.
For a pair of states q, q ∈ Q and a port p ∈ P , we write q p -→ q ⇐⇒ (q, p, q ) ∈→ and we say that p is enabled at q. If such q does not exist, we say that p is disabled at q.

Modeling Interactions

We compose a set of n atomic components behaviors

{B i = (Q i , P i , → i )} n i=1
, by using interactions. We assume that their respective sets of ports and sets of states are pairwise disjoint, i.e., for all i = j, we have P i ∩ P j = ∅ and Q i ∩ Q j = ∅. We define the set P = n i=1 P i of all ports in the system.

Definition (Interaction)

An interaction α is a non-empty subset α ⊆ P of ports. When we write α

= {p i } i∈I , I [1, n]. For each i ∈ I , p i ∈ P i .
The interaction model is specified by a set of interactions γ ⊆ 2 P . Interactions of γ can be enabled or disabled. An interaction α is enabled if f , for all i ∈ [1, n], the port α ∩ P i is enabled in B i . That is, an interaction is enabled if each port that is involved in this interaction is enabled. An interaction is disabled if there exists i ∈ [1, n], for which the port α ∩ P i is disabled in B i . That is, an interaction is disabled if there exists at least a port involved in this interaction, that is disabled.

Modeling Priorities

In a behavior, more than one interaction can be enabled at the same time, introducing a degree of non-determinism. This can be restricted with priorities by filtering the possible interactions based on the current global state of the system.

We compose a set of n atomic components behaviors

{B i = (Q i , P i , → i )} n i=1 .

Definition (Priority)

A priority is a partial order ≺ γ × γ, where:

• γ is the set of interactions, For α ∈ γ and α ∈ γ, the priority (α, α ) ∈≺ is denoted as α ≺ α . That is, interaction α has less priority than α .

Composition of Abstract models

For a set of components

{B i = (Q i , P i , → i )} n
i=1 , an interaction model γ and a priority model π, the compound component is obtained by application of a glue GL.

The glue GL is composed of the two previous models γ and π and defined as GL = πγ, where the interaction model γ is a set of interactions and the priority model π is a set of priorities.

Definition (Composition for Interactions Model)

The composition of a set of atomic components {B i } n i=1 , parametrized by a set of interactions γ ⊆ 2 P , is a transition system B = (Q, γ, → γ ), where:

• Q = n i=1 Q i ,
• γ is the set of interactions γ ⊆ 2 P , where P = n i=1 P i ,

• For α = {p i } i∈I ∈ γ, we have (q 1 , . . . , q n ) α -→ γ (q 1 , . . . , q n ) in B if and only if, q i p i
-→ i q i in B i for all i ∈ I, and q i = q i for all i / ∈ I.

The obtained behavior B can execute a transition (α = {p i } i ∈ I) ∈ γ, if and only if, for each i ∈ I, port p i is enabled in B i .

Definition (Composition restricted from the Priority Model)

Given a behavior B = (Q, γ, → γ ), its restriction by the priority model π is the behavior B = (Q, γ, → π ), where for α ∈ γ, we have q α -→ π q in B if and only if, q α -→ γ q in B and for all α ∈ γ such that α ≺ α , α is disabled.

The obtained behavior B can execute a transition α ∈ γ if and only if, each transition α ∈ γ, with higher priority than α is disabled.

Concrete Model of BIP

Atomic Components

In BIP, atomic components are automata equipped with a set of ports and a set of variables. Each transition is guarded by a predicate on the variables, triggers an update function, and is labelled by a port. Ports are used for communication among different components and are associated with variables of the component.

Definition (Port)

Each port is a pair (p, X p ), where p is the label and X p is the set of variables associated with p. For the sake of simplicity we denote a port (p, X p ) by p. We refer to internal ports using the β character instead of p, which refers to communication ports.

Definition (Atomic Component: Syntax)

An atomic component is a labelled transition system extended with data B = (L, X, P, T ) where:

• L = { 1 , 2 , ..., k } is a set of control locations, • X = {x 1 , x 2 , ..., x n } is a set of variables,
• P is a set of communication ports. Each port is a pair (p, X p ), where p is a label and X p ⊆ X is the set of variables associated with p. For the sake of simplicity we denote a port (p, X p ) by p and we refer to port p that belongs to component B by B.p,

• T is a set of transitions of the form τ = ( , p, g, f, ) or ( , β, g, f, ), where , ∈ L are control locations, p ∈ P is a communication port, β is an internal port, g is a guard, a predicate on X which can be true or false, and f (X, X ) is an update relation, a predicate on X (current) and X (next) state variables. We represent concretely update relations as sequential programs operating on data X. We use the term skip to denote f (X, X ) as empty, where X = X .

Let D be a universal data domain. Given a set of variables X, we define valuations for X as functions v : X → D. The set of valuations is denoted as D X . Given two valuations u : X → D and v : Y → D, we define the substitution u v : X ∪ Y → D as a valuation defined by:

(u v)(x) = u(x) :if x ∈ X \ Y v(x) :if x ∈ Y 8 Definition (Atomic Component: Semantics)
The semantics of B = (L, P, X, T ) is a transition system (Q, Σ, → B ) such that:

• Q = L × D X , • Σ = {p[v ]|p ∈ P, v ∈ D Xp } ∪ {β} is the set of labels. A label p[v ]
marks instantaneous data change through the port p.

• → B is the set including transitions

-(( , v), p[v ], ( , v )) such that g(v)∧f (v v , v ) for some τ = ( , p, g, f, ) ∈ T . As usual, if (( , v), p[v ], ( , v )) ∈→ B we write ( , v) p[v ] ---→ B ( , v ), -(( , v), β, ( , v )) such that g(v) ∧ f (v, v ) for some τ = ( , β, g, f, ) ∈ T . As usual, if (( , v), β, ( , v )) ∈→ B we write ( , v) β -→ B ( , v ).
For a model built from a set of n atomic components {B i = (L i , P i , X i , T i )} n i=1 ,we assume that their respective sets of ports and variables are pairwise disjoint, i.e. for any two i = j in {1...n}, we require that P i ∩ P j = ∅ and X i ∩ X j = ∅. Thus, we define the set P = n i=1 P i of all ports in the model as well as the set X = n i=1 X i of all variables.

1 Example Figure 2.2 shows a graphical representation of two atomic components in BIP, the Sender and the Receiver. The behavior of Sender is described as a transition system with control locations 1 and 2 . It communicates through ports tick and out. Port out exports the variable x. Initially, the Sender communicates through port out exporting the variable x.

Then, it ticks through the tick port at a maximum number of ten times. Finally, the guard [10 ≤ c] enables the internal transition β. At the execution of the β transition the variable x is reevaluated depending on a user-defined function f (). Respectively, the behavior of Receiver has control locations 5 and 6 and communicates through port tick and port in, which exports the variable z. Initially, the Receiver ticks through the tick port at a maximum number of twenty times. Then, the guard [c ≤ 20] enables the communication port in which exports the variable z. Finally, the internal transition β is enabled returning the component to the initial state. At the execution of the β transition the variable x is reevaluated depending on a user-defined function f (). An interaction α is a triple (P α , g α , f α ), where P α ⊆ P is a set of ports, g α is a guard, and f α is a data transfer function. We restrict P α so that it contains at most one port of each component, therefore we denote P α = {p i } i∈I with p i ∈ P i and I ⊆ {1...n}. g α and f α are defined on the variables available on the interacting ports p∈α X p .

Composition of components allows to build a system as a set of components that interact by respecting constraints of an interaction model. Connectors are used to specify possible interaction patterns between the ports of components.

Definition (Connector)

A connector γ defines sets of ports of atomic components B i which can be involved in an interaction. It is formalized by γ = (P γ , A γ , p) where:

• P γ is the support set of γ, that is the set of ports that γ may synchronize.

• A γ ⊆ 2 Pγ is a set of interactions α each labeled by the triple (P a , G a , F a ) where:

-P a is the set of ports p i , i ∈ I, I ⊆ [1, n] that takes part at interaction α, -G a is the guard of α, a predicate defined on variables p i ∈α V p i , -F a is the data transfer function of α, defined on variables p i ∈α V p i .

• p is the exported port of the connector γ.

In BIP, we distinguish two models of synchronization on connectors:

• Strong synchronization or rendezvous, where the only feasible interaction of γ is the maximal one, i.e., it contains all the ports of γ. We note A γ = P γ .

• Weak synchronization or broadcast, where all feasible interactions are those containing a particular port p trig which initiates the broadcast. We note A γ = {α ∈ γ|α ∩ {p trig } = ∅} where p trig ∈ P γ is the port that initiates the broadcast.

There is a graphical notation for interactions. In a rendezvous interaction all ports (known as synchrons) are denoted by bullets. In a broadcast interaction, the port that initiates the interaction, also called trigger, is denoted by a triangle and all the rest with bullets.

Hierarchical connectors

We have seen that a connector has an option to define a port and export it. This allows a connector to be used as a port in other connectors, and create structured connectors. The representation of structured connectors require connectors to be treated as expressions with typing and other operations on groups of connectors. This led to a formalization of the algebra of connectors defined in [START_REF] Bliudze | The algebra of connectors -structuring interaction in bip[END_REF][START_REF] Bliudze | A notion of glue expressiveness for component-based systems[END_REF]. The Algebra of Connectors is a compact notation for algebraic representation and manipulation of connectors and formalizes the concept of connectors supported by the BIP component model.

Priorities

Definition (Priority)

A priority is a tuple (C, ≺) where C is a state predicate (boolean condition) characterizing the states where the priority applies and ≺ gives the priority order on the set of interactions A γ .

For α 1 ∈ A γ and α 2 ∈ A γ , a priority rule is textually expressed as C → α 1 ≺ α 2 . When the state predicate C is true and both interactions α 1 and α 2 specified in the priority are enabled, the higher priority interaction, i.e., α 2 is selected for execution. A state of πγ(B 1 , ..., B n ) is defined by a pair ( , v), where = ( 1 , ..., n ) is the control state of each component and v = (v 1 , ..., v n ) is a valuation of component variables.

Composition of Components

Definition (Composite Component: Semantics)

The behavior of a composite component πγ(B 1 , ..., B n ) without priority, where

B i = (L i , X i , P i , T i ), is a labeled transition system (Q, γ, → γ ), where Q = n i=1 L i × n i=1 D X i .
We define → γ the least transition relation containing the interleaving of internal βtransitions from components B i and moreover, satisfying the interaction rule:

α = ({p i } i∈I , g α , f α ) ∈ γ g α ({v i } i∈I ) {v i } i∈I = f α ({v i } i∈I ) ∀i ∈ I( i , v i ) p i [v i ] ---→ B i ( i , v i ) ∀i ∈ I. ( i , v i ) = ( i , v i ) (( 1 , . . . , n ), (v 1 , . . . , v n )) α -→ γ (( 1 , . . . , n ), (v 1 , . . . , v n ))
Intuitively, this inference rule specifies that a composite component B = γ(B 1 , ..., B n ) can execute an interaction α ∈ γ, iff(1) for each port p i ∈ P α , the corresponding atomic component B i allows a transition from the current state labelled by p i (i.e. the corresponding guard g i evaluates to true), and (2) the guard g α of the interaction evaluates to true. If these conditions hold for an interaction α at state ( , v), α is enabled at that state. Execution of α modifies participating components' variables by first applying data transfer function f α on variables of all interacting components and then update functions inside each interacting component. The (local) states of components that do not participate in the interaction remain unchanged. In order to comply with the trace equivalence terminology we can simply refer to interactions as actions.

We define the behavior of the composite component B = πγ(B 1 , . . . , B n ) with priority, as the labeled transition system (Q, γ, → πγ ) where → πγ is the least set of transitions satisfying the rule:

( , v) α -→ γ ( , v ) ∀α ∈ γ. α ≺ α ( , v) α -→ γ ( , v) α -→ πγ ( , v )
The inference rule filters out interactions which are not maximal with respect to the priority order. An interaction is executed only if no other one with higher priority is enabled. priority : We define:

π 1 : tick2 < io1 π 2 : tick2 < io2
• A run θ is a finite sequence of transitions:

q 0 a 1 -→ γ q 1 a 2 -→ γ q 2 a 3 -→ γ ... an -→ γ q n , with a i ∈ γ ∪ {β}
We say that for each run θ

• Runs(C) is the set of all runs observed on a composition model in BIP, such as C = πγ(B 1 , . . . , B N ).

• Runs(q 0 ) is the set of all runs started from q 0 .

• A run is maximal if q n has no successor.

• trace(θ) is the sequence of labels a 1 .a 2 . . . a n for a given run θ.

• T races(C) is the set of all traces which correspond to the set of Runs(C), for a given composition model in BIP, such as C = πγ(B 1 , . . . , B N ).

The BIP Language

The BIP language represents components of the BIP framework [START_REF] Basu | Modeling heterogeneous real-time components in bip[END_REF]. BIP language is a user-friendly textual language which provides syntactic constructs for describing systems. It leverages on C style variables and data type declarations, expressions and statements, and provides additional structural syntactic constructs for defining component behavior, specifying the coordination through connectors and describing the priorities. The basic constructs of the BIP language are the following:

• atomic: to specify behavior, with an interface consisting of ports. Behavior is described as a set of transitions.

• connector: to specify the coordination between the ports of components, and the associated guarded actions.

• priority: to restrict the possible interactions, based on conditions depending on the state of the integrated components.

• compound: to specify systems hierarchically, from other atoms or compounds, with connectors and priorities.

• model: to specify the entire system, encapsulating the definition of the components, and specify the top level instance of the system.

Example

The BIP descriptions of the Sender atomic component of Figure 2 A port type DataPort associates a port to an integer variable i. Variables associated to ports may be modified when executing the interaction in which the port participates. The port out is an instance of the type DataPort. A port type EventPort is an event port and it is not associated with any variable. The port tick is an instance of the type EventPort. All ports are exported at the interface of the component. Initially, the state of the component is at the place 1, the only place with token. The BIP code uses the constructs on...from...to to represent transitions from one place to the other. The construct provided is used when the execution of a transition is restricted by a guard. Moreover, if the transition is associated with a function, the C code inside the constructs do {...} is executed .

Components are composed by using connectors. A connector defines the set of possible interactions between ports of components and the corresponding data transfer between the variables associated with the ports. The BIP language allows the definition of connector types.

Example

Below is presented the syntax of two different types of connectors, RendezVous-Data and BroadcastEvents connector. The RendezVousData connector defines a strong synchronization between two ports of type DataPort, in and out. The value i is copied from the port in to the port out each time the connector is executed. The BroadcastEvent connector defines a weak synchronization between the ports e1 and e2 of EventPort type. At least one of the ports is required to initiate the interaction. This interaction is exported to the environment through the EventPort e.

connector
A compound component is a new component type defined from existing components by creating their instances, instantiating connectors between them and specifying the priorities. A compound offers the same interface as an atom, hence externally there is no difference between a compound and an atomic component.

Example

The The three atomic components that constitute the Send/Buffer/Receiver model are instantiated. For example component Sender sender, creates an instance of Sender component named sender. Connectors are also instantiated, associating the ports of instantiated components through the interactions defined by the connector type. Finally, priorities are defined specifying an order between a pair of interactions.

The BIP Tool-Chain

This section presents the implementation of the BIP framework, formally described in the previous sections, in the form of a tool-chain called the BIP tool-chain. The BIP Toolchain provides a complete implementation, with a rich set of tools for the modeling, the execution and the verification (both static and on-the-fly) of BIP models. The overview of the BIP tool-chain is shown in Figure 2.4. It includes the following tools:

• The BIP language. It is used to build models using components, connectors and priorities and describes components architecture. It is used for the BIP description source. -Model-to-model transformation tools. They are used in order to perform useful static transformations for systems optimizations including run-time. The transformations use a set of correct-by-construction models and preserve functional properties. Moreover, they can take into account extra functional constraints. There exist three types of transformations, architecture optimizations, such as flattening the hierarchy and transforming structured connectors to flat connectors [START_REF] Bozga | Source-to-source architecture transformation for performance optimization in bip[END_REF], distributed implementation [BBJ + 10], such as the replacement of atomic multiparty interactions by protocols using asynchronous message passing (send/receive primitives) and memory management.

HW Components Library

-The code generator. It generates C++ code from the model produced by the parser. The code generator has options for generating application code for the single-threaded BIP Engine, the multi-threaded BIP Engine and the distributed BIP implementation.

• D-Finder. It is a compositional verification tool for deadlock detection and generation of invariants [BBN + 09, BGL + 11]. Verification is applied only to high level models for checking safety properties such as invariants and deadlock-freedom.

• The BIP Execution engines. They are middleware responsible for the coordination of atomic components, that is, they apply the semantics of the interaction and priority layers of BIP. Execution engines are used for execution, simulation, run-time verifications, debug or state-space exploration( i.e. all traces) of BIP models. There are currently three engines available, the single-threaded engine, the multi-threaded engine and the engine supporting the distributed implementation of BIP.

The BIP Execution Engines

The BIP execution Engines and the distributed BIP implementations directly implement the BIP operational semantics. It plays the role of the coordinator in selecting and executing interactions between the components, taking into account the glue specified in the input component model. It monitors the state of the components and considering the interaction model, finds all the enabled interactions. It then applies the priority rules to eliminate the interactions with low priority, and selects one amongst the maximal enabled, for execution.

Here is the presentation of the current Engines.

The Single-Threaded BIP Engine

From a BIP model, a compiler is used to generate C++ code for atomic components and glue. The code is orchestrated by a sequential engine that interprets the BIP operational semantic rules. The Engine computes from the set of ports for each atomic components and defined by connectors, the set of enabled interactions. It chooses an interaction α = {α i |i ∈ I} ∈ γ s enabled at state s. The choice of α depends on the considered scheduling policy. For instance, EDF (Earliest Deadline First) scheduling policy can be used. It executes α that corresponds to the execution of all atomic components involved in the interaction α i , i ∈ I, followed by the execution of the data transfer function F α and the update of control locations.

Algorithm 1 gives an implementation of the Execution Engine for the composition of BIP models. It basically consists of an infinite loop that first computes enabled interactions at current state s of the composition. It stops if no interaction is possible from s (i.e. deadlock). Otherwise, it chooses an interaction α, executes the data transfer function F α associated to it and executes α. Finally, the state s is updated in order to take into account the execution of α.

Algorithm 1 Single Threaded Execution Engine

Require: Model M i = (Q i , → i ), 1 ≤ i ≤ n, initial control location (q 1 0 , . . . , q n 0 ), set of interactions γ s = (q 1 , . . . , q n ) ← (q 1 0 , . . . , q n 0 )

loop γ s = EnabledInteractions(s) if ∃α ∈ γ s then α = {α i |i ∈ I} ← EDF Scheduler(γ s ) ExecuteDataT ransf er(F α ) for all i ∈ I do Execute(α i ) q i ← q i end for else exit(DEADLOCK) end if end loop
The Multi-Threaded BIP Engine

The implementation of the multi-threaded implementation with centralized engine is based on the notion of partial state semantics where interactions are allowed to fire as soon as only the involved components are stable [BBB + 08]. Each atomic component is assigned to a different thread (process), the engine being assigned to a thread as well. Each atomic component performs its computations locally and then, when it reaches a stable state, it notifies the engine about the ports on which it is willing to interact. It waits for the engine to select the port to be executed upon the chosen interaction.

The Engine is parametrized by an oracle. As depicted in Algorithm 2, the engine computes feasible interactions available on state components. Then, if such interactions exist and the oracle allows them, the engine selects one for execution and notifies the involved components.

Iteratively, the Engine receives the sets of ports and the local states of components ready to interact. Depending on this information, the engine computes the feasible interactions. It chooses a feasible interaction, which is allowed by the oracle O. If such an interaction exists, the engine executes it by notifying sequentially, in some arbitrary order, all the involved components. Otherwise, it is a deadlock.

Algorithm 2 Multi-Threaded Execution Engine

Require:

Model M i = (Q i , → i ), 1 ≤ i ≤ n,
initial control location (q 1 0 , . . . , q n 0 ), set of interactions γ s = (q 1 , . . . , q n ) ← (q 1 0 , . . . , q n 0 ) loop wait(P i )

γ s = EnabledInteractions(P i ) γ o = restriction(γ s , O) if ∃α ∈ γ o then α = {α i |i ∈ I} ← EDF Scheduler(γ s )
ExecuteDataT ransf er(F α ) for all i ∈ I do notif y(M i , α i ) q i ← q i end for else exit(DEADLOCK) end if end loop

The Distributed BIP Implementation

Currently, powerful hardware platforms are needed for executing applications on multicore or many-core platforms. The application code should be optimally distributed over the platform to take advantage of its computing power. Although distributed systems are widely used nowadays, their implementation is still time-consuming and an error-prone task. The distributed implementation in BIP provides a method for automatic generation of efficient and correct-by-construction distributed model from a given application software in BIP. Coordination in BIP is achieved through multi-party interactions (i.e., those across multiple components), and scheduling by using dynamic priorities. Transforming the semantics of BIP, which is based on a global state model, into a distributed implementation is clearly a non-trivial task.

A generic framework allowing the transformation of high-level BIP models into distributed implementations has been recently developed [BBJ + 10]. The method involves BIP to BIP transformations preserving observational equivalence. It transforms multiparty interactions into asynchronous message passing, that is, send/receive primitives.

The target Send/Receive BIP model is structured in three layers (see Figure 2.5): (i) the component layer corresponds to a modified behavior of the components of the original model; (ii) the interaction protocol consists of a set of components such that each component detects enableness of a subset of interactions of the original model using partial-state knowledge, and executes them after resolving conflicts (e.g., regarding which interaction to execute when there is more than one involving the same port) either locally or by the help of the third layer; (iii) the reservation protocol resolves conflicts between components of the interaction protocol layer using committee coordination algorithms such as the token-ring distributed algorithm or the distributed dining philosophers algorithm. Notice that the obtained Send/Receive BIP model depends on a user-defined partition of the interactions of the original model, associating subsets of interactions to components of the interaction protocol layer. A C++ code generator has been developed. Given a user-defined mapping of the components of a Send/Receive BIP model, it generates the distributed implementations using communication mechanisms offered by the platform. We have the following backends: Unix processes communicating through TCP sockets, MPI, and threads using semaphores and shared memory. Efficient monolithic code can be produced by merging components using another BIP to BIP transformation, according to the mapping of the components.

N T E R T O I A C I N C O P O N M E N T R E S E R T O N I V A B 1 B 2 B 3 IP 1 : interactions α and β α : B 3 , B 4 α : B 1 , B
The method has been fully implemented in a toolset allowing the automatic generation of distributed implementations from BIP models. It is parametrized by the partitioning of interactions, a committee coordination algorithm, and the mapping of components.

Conclusion

BIP [START_REF] Basu | Modeling heterogeneous real-time components in bip[END_REF] (Behavior, Interaction, Priority) is a general framework encompassing rigorous design. It uses the BIP language and an associated toolset supporting the design flow. The BIP language is a notation which allows building complex systems by coordinating the behavior of a set of atomic components. Behavior is described as a finite-state automaton extended with data and functions described in C/C++. The transitions of the automata are labeled with guards (conditions on the state of a component and its environment) as well as functions that describe computations on local data. The description of coordination between components is layered. The first layer describes the interactions between components. The second layer describes dynamic priorities between the interactions and is used to express scheduling policies. The combination of interactions and priorities characterizes the overall architecture of a component. It confers BIP strong expressiveness that cannot be matched by other languages [START_REF] Bliudze | A notion of glue expressiveness for component-based systems[END_REF]. BIP has clean operational semantics that describe the behavior of a composite component as the composition of the behaviors of its atomic components. This allows a direct relation between the underlying semantic model (transition systems) and its implementation.

The BIP design flow uses a single language to ensure consistency between the different design steps. This is mainly achieved by applying source-to-source transformations between refined system models. These transformations are proven correct-by-construction, that means, they preserve observational equivalence and consequently essential safety properties. Functional verification is applied only to high level models for checking safety properties such as invariants and deadlock-freedom. To avoid inherent complexity limitations, the verification method applies compositionality techniques implemented in the D-Finder tool. BIP has been successfully used to model complex systems and software applications like the DALA robot [dal], the Heterogeneous Communication System (HCS) [BBB + 12], the NesC/TinyOS applications [BMP + 07] and others which we refer in the next chapter. In the next chapters we analyze the method of designing complex mixed hardware/software systems using the BIP component-based framework.

-Chapter 3 -

BIP Language Factory

In this chapter, we present the methods for generating BIP models out of languages and various programming models. The ensemble of these methods consists the BIP Language Factory. Most importantly, we describe the generation of Kahn Process Network (KPN) software models in BIP. These models are used to model the software application part of our system design.

The chapter structure is as follows. In Section 3.1, we epigrammatically present the methods developed in Verimag which generate BIP models using different programming models. In Section 3.2, we describe the KPN models using BIP. In the final Section 3.3, we provide the method that we used to automatically generate KPN models in BIP and then, we conclude the chapter.

Construction of Software Models

A general method for generating BIP models from languages is developed in Verimag laboratory. The method is illustrated in Figure 3.1. The BIP semantic model is used to structurally represent different programming models or domain specific languages and enable the available analysis and verification techniques provided by the BIP toolchain [bip]. In this section, we provide an overview of the set of languages and programming models translated into BIP models and analyzed by the BIP toolchain. From AADL to BIP AADL (Architecture Analysis and Design Language) [START_REF]Architecture analysis and design language (aadl) (standard sae as5506)[END_REF] is a language dedicated to modeling and specification of complex Real-time embedded systems. It is used to describe component-based systems, where each component represents the physical hardware or the application software. There are several types to describe, on the one hand, the physical hardware such as processors, memories, buses and devices, and on the other, the application software, such as processes, threads, data and functions. In [START_REF] Yassin Chkouri | Translating aadl into bip -application to the verification of real-time systems[END_REF] the authors provide a translation from AADL to BIP. The BIP framework provides a series of advantages compared to AADL. Such as concrete operational semantics, an execution environment and formal verification techniques.

From Lustre to BIP Lustre [HCRP91] is a dataflow language for programming synchronous reactive systems. In [START_REF] Bozga | Modeling synchronous systems in bip[END_REF] the authors present a modular translation of Lustre into modal flow graphs described in synchronous BIP. The modal flow graphs are acyclic graphs representing three different types of dependency between two events p and q: strong dependency (p must follow q), weak dependency (p may follow q), conditional dependency (if both p and q occur then p must follow q). Synchronous BIP is a subset of BIP which describes systems of components which are strongly synchronized by a common action that triggers the execution steps. The advantage is that the translation is modular and exhibits not only data-flow connections between nodes but also their synchronization by using clocks.

From MATLAB/Simulink to BIP MATLAB/Simulink [Mat] is a simulation environment developed by Mathworks for analysis and model-based design of dynamic and embedded systems. In [STS + 10] a discrete-time fragment of Simulink is used to develop a method for translation into synchronous BIP. There are several advantages, concerning both MATLAB/Simulink to BIP and Lustre to BIP translations, related to the obtained modal flow graphs in BIP. They are well-triggered, a property of modal flow graphs that expresses consistency between the three types of dependency. It guarantees deadlock freedom and deterministic behavior under some conditions of non interference of concurrent computations. The translations of these two synchronous formalisms open the way for exploring problems regarding relations between synchronous and asynchronous systems. They allow integration of synchronous systems theory in an all encompassing component framework without losing advantages such as correctness-by-construction and efficient code generation. This makes possible modeling mixed synchronous/asynchronous systems without artifacts.

From LAAS/GeNom applications to BIP LAAS [ACF + 98] is a framework used to describe both the functional and the execution control level of a robot. The LAAS framework is based on the componentization of GenoM [START_REF] Fleury | Genom: A tool for the specification and the implementation of operating modules in a distributed robot architecture[END_REF] Functional Modules. Each module can integrate synchronous and asynchronous processes. It has a predictable behavior and standard communication interfaces. A module description language is associated with an automatic module generator according to GeNom generic model. In [BGL + 08], the modeling of the functional part of a robotic system into a BIP model and the synthesis of an execution controller are presented. Both the functional and the execution control level of the robot are described with the LAAS [ACF + 98] framework and the GenoM [START_REF] Fleury | Genom: A tool for the specification and the implementation of operating modules in a distributed robot architecture[END_REF] Functional Modules. The goal of the above construction methodology is the verification and validation of essential "safety" properties.

From NesC/TinyOS applications to BIP TinyOS [Tin] is an embedded operating system and platform written in the NesC programming language, which is a subset of the C language optimized for sensor networks with strict memory limits. It is designed as a set of cooperating tasks and processes and it targets low-power wireless devices. In [BMP + 07], the authors present a methodology for construction, analysis and verification of network system models in BIP using the TinyOS operating system. The corresponding BIP model is constructed based on the modeling of a NesC program describing the application and based on models of TinyOS components. Different types of BIP connectors are used to model the composition of components into network models. The use of BIP opens the way for enhanced analysis and early error detection by using verifications techniques.

From C language to BIP A translation process from C code to a BIP model is developed. The translator currently supports the C language. Any C function can be translated into a BIP atomic component. The BIP component that models the function call uses a BIP port and a BIP connector that interacts with the BIP component modeling the body of the invoked function. This translation is used as a building block for the Kahn Process Network to BIP model language factory described in the following sections.

From Kahn Process Networks to BIP

A Kahn Process Network (KPN) model [START_REF] Kahn | The semantics of simple language for parallel programming[END_REF] is a set of autonomous processes that communicate through unidirectional software channels. The channels are first-in first-out (fifo) queues with blocking read and non-blocking write operations. The read operation is blocking since the process suspends if the fifo queue is empty. Assuming that the queue has an infinite size, the write operations are non-blocking. The communication through the channels must occur in a finite and unspecified amount of time. A Kahn Process Network program is deterministic; the result of a computation is independent from execution order. Sequential or parallel executions produce the same outcome. Determinism separates the functionality of the application from the target hardware platform. Moreover, a KPN model provides separate analysis of computation and communication and exposes functional parallelism. More restrictive models can be derived from KPNs such as Synchronous Data Flows (SDF) [START_REF] Lee | Synchronous data flow: Describing signal processing algorithm for parallel computation[END_REF] [LP95], Marked Directed Graphs [START_REF] Commoner | Marked directed graphs[END_REF] and SW/HW Integration Medium (SHIM) [START_REF] Edwards | Shim: a deterministic model for heterogeneous embedded systems[END_REF].

In the next section, we present a construction of Kahn Process Networks using BIP models. We consider KPNs with bounded size queues where both read and write operations are blocking. The derived BIP model consists of process components and FIFO channel components connected via send/receive data connectors.

BIP Process Component

A process component in BIP models the behavior of a KPN process. It contains Read and Write communication primitives modeled as interactions with external components. A Read operation retrieves the top most value stored in a the queue. The Write operation stores a value in the next available cell of the queue. A process component in BIP uses a set of ports P w for Write, which are associated with the variable wr data and a set of ports P r for Read associated the the variable rd data. A generic process component is defined below.

Definition (Process Component)

We define the process component G = (L, X, P, T ), with Read and Write communication primitives where:

• L = { ini }∪{ 1 , 2 , ..., k }∪L f in
is the set of control locations, where ini is the initial control location, { 1 , 2 , ..., k } are the intermediate control locations and L f in the set of possible final control locations such that:

L f in = ∅ :if process never terminates { k+1 , k+2 , ..., k+m } :if process terminates • X = {wr data, rd data} ∪ {x 1 , x 2 , ..., x n } is a set of variables,
• P = P w ∪ P r , where P w the set of ports used for Write and P r the set of ports used for Read respectively, for each w ∈ P w , w are associated with {wr data} and for each r ∈ P r , r are associated with {rd data}

• T is the set of transitions of the form τ = ( , w, true, skip, ), τ = ( , r, true, skip, ) or ( , β, g, f, ),

Example (Producer Component)

We assume a Producer Component that generates an integer value and sends it to an other component. We define the BIP Producer Component

G P = (L G P , X G P , P G P , T G P ),
C = (L G C , X G C , P G C , T G C ), with one Read communication prim- itive as it is illustrated in Figure 3.2.
There are two control locations 1 , 2 , the rd data variable to store an integer value, a Read port r associated with rd data and two transitions, r and β. On transition r, the Consumer exports the rd data variable and on transition β it reads the rd data variable.

BIP FIFO Component

A FIFO channel in KPN is characterized by its size k, that is the maximal number of values that can be stored. It has ports w (write) and r (read), and a single control location .

The component contains an array of values buf f parametrized by k. The variable wr data is associated with the port w and the rd data with r. On w, the received value is inserted into buf f . On r, the least recent value is sent and removed from the buffer. The variable count records the number of values stored in the buffer. It is increased on a w (write) and it is decreased on a r (read), respectively. The FIFO policy is implemented by using two indices i and j, for respectively insertion/deletion into/from the (circular) buffer buf f . A formal definition is given below.

Definition (FIFO Component)

We define the FIFO atomic component F = (L F , X F , P F , T F ), where the behavior is described in Figure 3.3. Finally, we have:

• L F = { },
• X F = {wr data, rd data, buf f, i, j, k, count},

• P F = {w, r}, where w and r associated with {wr data} and {rd data} respectively.

• T F = {τ w = ( , w, g w , f w , ), τ r = ( , r, g r , f r , )}
with g w : [count < k] and f w defined as a sequence of functions f w = f wm ; f wn ;, where:

• f wm : buf f [i] = wr data; • f wn : count = count + 1; i = (i + 1)%k;
and with g r : [count > 0] and f r defined as a sequence of functions f r = f rm ; f rn where:

• f rm : rd data = buf f [j];
• f rn : count = count -1; j = (j + 1)%k;

A write operation always precedes the read operation on a given buffer place.

BIP KPN model

Using the Process Component and the FIFO Component in BIP, defined above, we describe below the composition of a Process Network in BIP modeling Kahn Process Network. We will also further refer to the Process Network in BIP as application software model in BIP.

Definition (Process Network Composition)

We define a Process Network in BIP as the composition N of Process Component G and FIFO Components F such that N = πγ(G 1 , . . . , G n , F 1 , . . . , F k ), where π is the priority rule applied in the interactions γ, where the set γ contains two categories of interactions such that γ = (α r , α w ):

• read interactions α r of the form: ({F.r, G.r k }, true, f r ), with r k ∈ P r (G), f r : F.rd data = G.rd data;

• write interactions α w of the form:

({F.w, G.w k }, true, f w ), with w k ∈ P r (G), f w : G.wr data = F.

wr data;

Every read/write port in the FIFO/processes are used in only one interaction and moreover, every internal transition β has higher priority than any other interaction α ∈ γ.

Example (Producer-Consumer Composition)

We construct a composition using the Producer

G P = (L G P , P G P , X G P , T G P ), the Con- sumer G C = (L G C , P G C , X G C , T G C ) and the FIFO F = (L F , X F , P F , T F )

Distributed Operation Layer (DOL) Framework

DOL (Distributed Operation Layer) [START_REF] Thiele | Mapping applications to tiled multiprocessor embedded systems[END_REF] is a framework devoted to the specification and analysis of mixed software/hardware systems. DOL provides languages for the representation of particular classes of applications software, multi-processor architectures and their mappings. In addition, DOL provides tools for performance analysis and design-space exploration based on a combination of analytical and simulation-based techniques [START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF][START_REF] Künzli | Combining simulation and formal methods for system-level performance analysis[END_REF]. In DOL, application software is defined using a variant of Kahn process network model [START_REF] Kahn | The semantics of simple language for parallel programming[END_REF]. It consists of a set of deterministic, sequential processes communicating asynchronously through FIFO channels. The hardware architecture is described as interconnections of computational and communication devices such as processors, buses and memories. The mapping associates application software components to devices of the hardware architecture, that is, processes to processors and FIFO channels to memories.

Application Software in DOL The application software in DOL consists of three basic entities: Processes, FIFO channels, and Connections. The network structure is described in XML. Each Process has input, output ports and sequential behavior. Processes communicate by using FIFO channels. Each FIFO has a single input port and a single output port, uniquely associated with ports of processes.

Example

We present in Figure 3.5 the process network model derived from the right-looking variant of Cholesky factorization. The Cholesky application is an algorithm for solving numerically linear equations and it is thoroughly described later in Section 10.7. It contains processes Splitter, Joiner and three "block" computational processes P 11 , P 21 and P 22 . Process Splitter splits the initial matrix into blocks and dispatches them to computational processes. Each process P ij implements the computation required on a corresponding matrix block A ij . The final matrix is re-constructed by process Joiner. Explicit communication between P ij processes is used to enforce data dependencies. In this model, a dedicated FIFO (F ) is used for every pair of dependent processes to transfer the result block from the source to the target process. In Figure 3.6, we present a fragment of the DOL specification of the Cholesky process network in XML. For each process, we specify the name of the process, the number of input and output ports, the names of the ports, the respective types and the location of the source C code describing the process behavior. For each software channel (F ) we specify the name, the type the maximum capacity of data and the input and output port. Finally, we define the connections between the processes and the software channels by specifying the input and output ports which contribute in each connection. Process behavior is described using sequential C programs with a particular structure (see Figure 3.7 for a concrete example). For a process P, its state is defined as an arbitrary <processnetwork> <process name="splitter" basename="splitter"> <port name="OUT_0_0" type="output" basename="OUT" range="2;2"/> <port name="OUT_0_1" type="output" basename="OUT" range="2;2"/> <port name="OUT_1_0" type="output" basename="OUT" range="2;2"/> <port name="OUT_1_1" type="output" basename="OUT" range="2;2"/> <source location="splitter.c" type="c"/> </process> . . . <process name="joiner" basename="joiner"> <port name="IN_0_0" type="input" basename="IN" range="2;2"/> <port name="IN_0_1" type="input" basename="IN" range="2;2"/> <port name="IN_1_0" type="input" basename="IN" range="2;2"/> <port name="IN_1_1" type="input" basename="IN" range="2;2"/> <source location="joiner.c" type="c"/> </process> <sw_channel name="FIFO_GEN_1_1" type="fifo" size="72000" basename="FIFO_GEN_1_1"> <port name="0" type="input" basename="0"/> <port name="1" type="output" basename="1"/> </sw_channel> . . . <sw_channel name="FIFO_2_1_2_2" type="fifo" size="72000" basename="FIFO_2_1_2_2"> <port name="0" type="input" basename="0"/> <port name="1" type="output" basename="1"/> </sw_channel> <connection name="g-f_gen_1_1"> <origin name="splitter"> <port name="OUT_0_0"/> </origin> <target name="FIFO_GEN_1_1"> <port name="0"/> </target> </connection> . . . <connection name="f-p_2_1_2_2"> <origin name="FIFO_2_1_2_2"> <port name="1"/> </origin> <target name="p_2_2"> <port name="INx1x0"/> </target> </connection> </processnetwork> C data structure named P state and its behavior as the program P init(); while (true) P fire(); where P init(), P fire() are arbitrary functions operating on the process state. The initial call of the P init() function is followed by an endless loop calling the P fire() function. Communication is realized by using two particular primitives, namely write and read for respectively sending and receiving data to FIFO channels. A read operation reads data from an input port, and a write operation writes data to an output port. Moreover, the P fire() method invokes a detach primitive in order to terminate the execution of the process.

Example

The description of the process P 22 is shown in Figure 3

DOL based representation in BIP (DOL to BIP translation)

The construction of the application software model in BIP requires the translation of the software processes, FIFO channels and their connections. The construction is structurepreserving: each process and each FIFO are independently translated to atomic components in BIP and then connected according to their connections in the process network.

Translation of Software Processes

The translation converts each software process to an atomic component in BIP. Each atomic component port corresponds to a port in the process. The translation requires the extraction of a control-flow graph from the C code. It starts by parsing the process code into an intermediate, annotated abstract syntax tree (AST). The translation to BIP is then completed in two steps.

1. In the first step, the interaction points in the AST are identified, that is, each call to a read/write primitive is registered as an interaction point.

2. The second step involves the construction of an explicit control flow graph and its representation as a finite state automaton extended with data in BIP. For each interaction point, a control location is created. An outgoing transition is added from this location, labeled by the port used in the read/write call. The transition models the primitive call and requires synchronization with a FIFO channel.

The port of the transition is associated with data that is read/written by the primitive invocation. Additional assignment statements are added to load/store the data into the local variables in the function.

A block statement that contains interaction points is transformed into sequence of control locations and transitions in the automaton. For such statements, e.g., conditional (if-else, switch) or loop (for, while) or control statement (break, continue, return), additional control locations are created and internal transitions guarded by the control condition are added to model the control automaton.

For a conditional statement, a new control location is created with an incoming transition where the branch condition evaluation action is added. Outgoing transitions, one for the positive branch and another for the negative branch are created. The branches are finally merged to a new control location.

For a loop statement, a new control location is created with an incoming transition where the loop initialization action and exit condition are added. Outgoing transitions, one for the positive exit condition and the other for the negative exit condition are created. For the negative exit branch, a transition back to the starting location of the loop is added, with the exit condition action.

From the last control location generated in the automaton, a transition to the starting control location is added. This models the invocation of the process behavior in a loop at run-time. The termination of the process behavior is modeled as a move to a deadlocked location, that corresponds to the detach primitive call.

Notice that functions that contain read/write calls (either directly or through nested calls) are inlined in the BIP behavior. Consequently, the translation is restricted to programs without communication calls occurring within recursive functions. Additional restrictions are: no use of global variables, and no goto statements. and obtains the result from P 21 . On the β transition from 4 to 5 , it performs the actual computations. Finally at 5 , it awaits synchronization through out join corresponding the write primitive call. At 1 , the guarded outgoing internal transitions β models the conditional (if) statement. Exit of the process on the detach is modeled by the final location 6 .

Translation of FIFO Channels and Connections

A FIFO channel in DOL is translated into a predefined BIP atomic component, as presented in Section 3.2.2. Each connection in the application software is translated into a BIP interaction which strongly synchronizes the corresponding ports. Interactions provide the transfer of data implementing the read and write operations. An interaction implementing write transfers data from a process to a FIFO, whereas the one implementing read transfers data from a FIFO to a process.

Conclusion

In this chapter, we presented the methods for generating BIP models out of languages and various programming models. The ensemble of these methods consists the BIP Language Factory. The semantic models of BIP preserve the structural representation of the input models and provide analysis and verification techniques included in the rich BIP toolchain. We analyzed the generation of KPN software models in BIP. The method receives as input a KPN application software model described in DOL and produces the equivalent representation in a BIP model. The construction is automated and fully preserves the behavior of the software application. The characteristic of determinism of KPN process networks enable separate analysis of computation and communication, exposes functional parallelism and separates the functionality of the application from the target hardware platform.

In the next chapter, we describe the hardware platform models used as the target platforms which the application software will be mapped and run on.

-Chapter 4 -

Modeling of HW Platforms in BIP

In the previous chapter, we presented the methods for generating BIP models out of languages and various programming models. In this chapter we focus on the hardware platforms by describing the Abstract Model of HW Platform in BIP. A BIP Hardware Model should integrate both computation and communication constraints in a unified model. The computation constraints are added with the use of processor components and the profiling of the software processes. The communication constraints are integrated with the use of cluster components modeling the communication paths using interconnects, buses, Network-on-Chips and memories.

The chapter is structured as follows. First, we provide an introductory text describing abstract models of manycore platforms in Section 4.1. Second, we specify the abstract models of hardware platforms in BIP in Section 4.2. We describe the BIP components needed to cover both computational and communication aspects of the hardware platforms. In the final section, we conclude the chapter.

Abstract Model of Manycore Platforms

The growing need of efficient and fast execution of parallel applications has led to the development of HW platforms designed to extend the capability of high parallelism in both computation and communication level. These high performance platforms are composed of multicore clusters which can be used as standard processing units or specific accelerators. The construction of the platforms is realized by a synthesis of HW/SW resources. These resources can be homogeneous or heterogeneous including clusters, shared memories, I/O devices or sensors.

The clusters are computational units of the platform containing many processing elements (PE). According to the specification and the characteristics of a cluster, the number of PEs can vary. In addition, there are different types of cluster buses, including the local bus, the crossbar switch and the multiplexing interconnect. There are also local memories for data and instruction caching. The interconnecting structure needed for exchanging information on a chip is a major characteristic. In the current work, we focus on the description of a Network-on-Chip (NoC) composed by homogeneous manycore cluster IPs, as depicted in Figure 4

Abstract Models of HW Platforms in BIP

A HW platform consists of computational resources interconnected according to communication paths. Resources are used for computation (processors, memories) or for communication (buses). Communication paths define the connections between computational resources. More formally, we consider the family of HW platforms that can be represented by the following grammar:

HW-NI . HW-Cluster-InterConnect

The BIP model constructed from the HW platform represents explicitly, in an operational manner, the interconnect between the different resources as defined by the communication paths. This model is organized as a collection of interconnect, network interface, router, bus, processor and memory components.

The goal of the HW model in BIP is to capture the HW constraints which arise upon the execution of a software application on a given platform. More specifically, these constraints are characterized as non-functional and can include parameters such as time delays, temperature and energy consumption. They are all affected by scheduling policies, conflicts, throughputs and response times. Therefore, the constraints exist both on computation and on communication level. In the current model, we focus on integrating non-functional constraints concerning time delays.

On the computation level, accurate measurements on the effects of a software application running on a HW platform demand fine-grained analysis of the executable code and the underlying processing elements of the platform. Initially, the executable code should be analyzed at the instruction level. A pipeline model should be constructed along with instruction and data caches. The above model will permit cycle-accurate performance analysis of the basic operations of the processing element and the cache hit/miss costs. In addition, the scheduling policies applied on the different processes can dramatically affect the performance. The computation measurements are achieved with the use of a Processor model described in the next section and the profiling of the software processes with the corresponding timing delays as described in Chapter 7.

On the communication level, significant constraints derive from the use of buses, interconnects and memories. Namely, we have bus conflicts, bus throughputs and scheduling, routing delays, routing policy and network throughput, memory data access, memory access response and memory conflicts. The communication constraints are integrated with the use of components modeling the communication paths from PEs towards the platform memories and via versa. These components are crossbar switches, shared memories, multiplexing interconnects and multi-banked memories used to model intra-cluster communication and components such as network interfaces and routers for off-cluster communication.

Processor Abstract Model for Computation Constraints and Scheduling

A Processor is a composite placeholder component with ports wr begin, wr end, rd begin, rd end, corresponding to the initiation and termination of write and read operations. It is composed by a set of software processes connected to the Processor Scheduler Component, as it is illustrated in Figure 4.4. Although, it is filled with the software processes during the next step, that is, the construction of the system model, we present below the Processor Scheduler Component and its functionality. The Processor Scheduler is responsible for modeling the processor resource. It uses the acq (Acquire), rel (Release) ports to grant and remove the control from the different processes which operate on the Processor. Initially, the Processor Scheduler uses the acq port to authorize a software process to run. Each β transition of the process is profiled with a delay to correspond with the amount of computational workload executed. Using the get d (Get-Delay) port the Processor Scheduler measures the computational delay and continues to the next β transition through the next port. Finally, the software process reaches the point where the scheduler can release the control and allow another process to run. The formal Definition 18 is given below.

18 Definition (Processor Scheduler Component)

We define the Processor Scheduler Component as SC = (L SC , X SC , P SC , T SC ) with Acquire and Release scheduling transitions, where the behavior is illustrated in Figure 4.5: • X SC = {count, delay}, the set of variables,

• L SC = { 1 , 2 , 3 },
• P SC = {acq, rel, get d, next, tick}, the set of ports,

• T SC = { τ acq = ( 1 , acq, true, f acq , 2 ), τ rel = ( 2 , rel, true, skip, 1 ), τ d = ( 2 , get d, true, skip, 3 ), τ next = ( 3 , next, g next , skip, 2 ), τ tick = ( 3 , tick, g t , f t , 3 ), τ rel = ( 3 , rel, g rel , skip, 1 ) } .
, with f acq : count = 0; g rel , g next : [count == delay]; g t : [count < delay], f t : count + +;

HW Components for Communication Constraints

Crossbar Switch Bus and Memory

A Crossbar Switch Bus Component is concretely defined as a scheduled collection of communication path components, as it is shown in Figure 4.6. That is, for each write/read path going on an interconnect, we consider the path fragment defined by the Bus Path Component, which is responsible for the following operations:

• controlling the access of the communication path on the bus and initiates the write/read operation.

• modeling effectively the transfer of data over the bus, from the processor once it gets access to the bus, towards the memory.

• receiving data either from some software processes executing inside the processor or from the previous path segment, depending on its position on the path. It acts like a buffer and is needed to connect further either to the next path fragment or to the memory.

The component is a timed BIP component [START_REF] Basu | Modeling heterogeneous real-time components in bip[END_REF]. It is equipped with a set of counters to measure the timing delays of all the operations. The delays counted are:

• the bus conflict, the time elapsed between the write/read request and the start of the data transfer,

• the bus delay, the data transfer delay over the bus

• the next operation conflict, the conflict time passed until the next path fragment or the memory becomes available.

There are used for observation purposes, as explained in Chapter 8.

For the transport of data the ports req (Request), ack (Acknowledge) are used to connect with upper components, and op begin (Operation-Begin), op end (Operation-End) to connect with lower components on the path. In addition, the ports acq (Acquire) and rel (Release) are used to interact with the Bus Scheduler. The component is predefined and belongs to the BIP hardware library. The formal definition is found below. We define the Bus Path Component as BP = (L BP , X BP , P BP , T BP ), where:

• L BP = { 1 , 2 , 3 , 4 , 5 , 6 , 7 },
• X BP = {count, bus delay, bus conf lict, op conf lict, proc id},

• P BP = {req, ack, acq, rel, tick, op b , op e }, where the port op e is binded with the proc id variable.

• T BP = { τ = ( 1 , req, true, f req , 2 ) ,f req : bus conf lict = 0; τ = ( 2 , tick, true, f t 1 , 2 ) ,f t 1 : bus conf lict + +; τ = ( 2 , acq, true, f b , 3 ) f b : count = 0; τ = ( 3 , tick, g t 2 , f t 2 , 3 ) ,g t 2 : [count < bus delay] , f t 2 : count + +; τ = ( 3 , β, g β , f β , 4 ) ,g β : [count == bus delay] , f β : op conf lict = 0; τ = ( 4 , tick, true, f t 3 , 4 )
, f t 3 : op conf lict + +; τ = ( 4 , op b , true, skip, 5 ) τ = ( 5 , op e , true, skip, 6 ) τ = ( 6 , rel, true, skip, 7 ) τ = ( 7 , ack, true, skip, 1 ) }.

Each connection is realized using BIP connectors which strongly synchronize the corresponding ports. The behavior of the connector implements the transfer of data, its address and size between the successive components, corresponding to the write and read operations.

All the paths segments going over the same bus must share its transport capabilities according to some predefined bus policy. The scheduling can be of one of fixed-priority, round-robin or TDMA (Time Division Multiple Access). We model it explicitly by using a Bus Scheduler Component, which interacts with all the Bus Path Components and ensures exclusive access for transmission of data, according to the selected policy. The Bus Scheduler acts as an arbiter to resolve the bus access conflicts. A simplified Bus Scheduler Component is given below. It implements the basic mutual exclusion scheduling policy. We define the Bus Scheduler Component as BS = (L BS , X BS , P BS , T BS ), where:

• L BS = { 1 , 2 },
• X BS = ∅,

• P BS = {acq, rel},

• T BS = {τ = ( 1 , acq, true, skip, 2 ), τ = ( 2 , rel, true, skip, 1 )}.
The Memory is a timed component used to model the write/read memory operations and measure the memory access delay. It is a component with ports op b (Operation-Begin), op e (Operation-End) corresponding respectively to the beginning and ending of the write/read. The use of Memory Component in the HW platform is shown in figure 4.9. Formally, the component is defined as: We define the Memory Component as M = (L M , X M , P M , T M ), where:

count++; [count<mem_delay] count=0; [count==mem_delay]
• L M = { 1 , 2 },
• X M = {count, mem delay}, For each α ∈ γ, the priority rule π implies that the tick interaction α tick has lower priority than any other interaction α. We export the tick port of the α tick interaction to dynamically enable synchronization with other tick interactions. We will further refer to the α tick interaction as M C.tick.

• P M = {op b , tick, op e }, • T M = { τ op b = ( 1 , op b , true, f op b , 2 ), τ tick = ( 2 , tick, g t , f t , 2 ), τ ope = ( 2 ,

Example

Figure 4.10 shows the BIP model of a 4-processor (P) HW Platform and a shared memory. Communication paths between the processors and the memory are implemented using the previously defined set of bus components.

Multiplexing Interconnect and MultiBank Memory

Another type of cluster bus is the Multiplexing Interconnect Component. The component is designed to connect processors to a multi-banked memory. Data are forwarded using routing and arbitration techniques. Based on address decoding, the requested address may correspond to the intra-cluster multi-banked memory or the off-cluster NoC environment.

In case of simultaneous accesses in contiguous data, the number of the observed memory conflicts is reduced due to fine-grained address interleaving. The Multiplexing InterConnect is a composite component synthesized by a set of Bus Interface Components and a set of connectors towards the multi-banked memory. An abstract illustration is provided in Figure 4.11. The number of the Bus Interface Components is the same as the number of processors used on the cluster. The Bus Interface Component is intended to receive the write/read requests to the memory and carry out the routing towards the corresponding Memory Bank. This is done with the use of address decoding, as mentioned above. In the formal definition found below, we use a random routing algorithm to forward the requests to the memory banks. The delay posed by the interconnect is taken into account by the memory bank components described next. The Bus Interface Component has the following four ports: the req rec (Request-Receive), req send (Request-Send) to receive and forward the memory access requests to the memory, and the ack rec (Acknowledgment-Receive), ack send (Acknowledgment-Send) to forward the executed requests back to the processor. We define the Bus Interface Component as BI = (L BI , X BI , P BI , T BI ), where:

• L BI = { 1 , 2 , 3 , 4 },
• X BI = {proc id, mem id, memBanks, dest id, cluster id},

• P BI = {req rec, req send mb, req send og, ack rec, ack send},

• T BI = { τ = ( 1 , req rec, true, f req , 2 )
,f req : mem id = rand()%(memBanks); τ = ( 2 , req send mb, g mb , skip, 3 ) ,g mb : dest id == cluster id τ = ( 2 , req send og, g og , skip, 3 )

,g og : dest id! = cluster id τ = ( 3 , ack rec, true, skip, 4 ) , τ = ( 4 , ack send, true, skip, 1 ) }.

The Memory Bank is a timed component used to synthesize the Multi-Bank Memory Component, as illustrated in Figure 4.13. It is used to model the write/read memory operations and measure the interconnect and the memory access delay. It is a component with ports op b , op e corresponding respectively to the beginning and ending of the write/read and port tick for time synchronization. It can receive multiple requests from the Multiplexing InterConnect. The requests are stored to a buffer in case of conflict and upon execution operation end acknowledgment is sent back to the local bus or the off-cluster NoC.

op
• L M B = { 1 , 2 },
• X M B = {buf req, mem conf lict, count, mem delay, interconnect delay, proc id, proc id , mem id}, We assume a platform where there are k processors, one multiplexing interconnect and a multi-banked memory. For each α ∈ γ, the priority rule π implies that the tick interaction α tick has lower priority than any other interaction α. We export the tick port of the α tick interaction to dynamically enable synchronization with other tick interactions. We will further refer to the α tick interaction as M C.tick.

• P M B = {op b , tick, op e }, • T M B = { τ op b = ( 1 , op b , true, f op b , 1 ), τ op b = ( 2 , op b , true, f op b , 2 ), τ tick 1 = ( 1 , tick, g t 1 , f t 1 , 2 ), τ tick 2 = ( 2 ,

Network On Chip

We model the network-on-chip in BIP using a composition of network components. These components are network interface components, routers and the connections between them. A network interface component is responsible for establishing a connection between the intra-cluster bus and the off-cluster Network on Chip. It is modeled by two different components: the Network Interface Outgoing Controller and the Network Interface Incoming Controller, as shown in Figure 4.16.

The Network Interface Outgoing Controller Component receives write/read requests or acknowledgments from the cluster bus and encapsulates them into packages. It forwards them to the local router modeling the packaging and the forwarding delays. The ports

• L OG = { 1 , 2 , 3 , 4 },
• X OG = {count, pack delay, ni id, proc id, package, dest id, pack inf o},

• P OG = {req, tick, send, inf o, ack}, where the ports send, inf o are binded with the package variable. The Network Interface Incoming Controller Component receives packages from the external network, extracts the important information and forwards the write/read requests or acknowledgments to the cluster bus. The package reception from the NoC is realized through the rec (Receive) port. The ports ack proc (Acknowledgment to Processor), req mem (Request to Memory) forward the acknowledgment to the processor and respectively, the request to the memory. The info port provides the Network Interface Outgoing Controller with the packaging information needed to encapsulate the acknowledgments received from the memory.

• T OG = { τ = ( 1 ,

Definition (Network Interface Incoming Controller Component)

We define the Network Interface Incoming Controller Component as IC = (L IC , X IC , P IC , T IC ), where:

• L IC = { 1 , 2 , 3 },
• X IC = {count, pack delay, proc id, package, pack inf o, mem id, memBanks},

• P IC = {rec, tick, ack proc, req mem, inf o}, where the ports rec pack, inf o are binded with the package variable. We independently define the Cluster Components below. At the end of the current section, we provide the complete definition of a NoC BIP model. We assume a HW platform where there are k processors, one crossbar switch, a shared memory and a network interface. For each α ∈ γ, the priority rule π implies that the tick interaction α tick has lower priority than any other interaction α. The Shared Memory Cluster Compound Component exports the ports OG.send as send, the IC.rec as rec and the α tick interaction export the port tick.

• T IC = { τ = (
We assume a HW platform where there are k processors, a multiplexing interconnect, a multi-banked memory and a network interface. For each α ∈ γ, the priority rule π implies that the tick interaction α tick has lower priority than any other interaction α. The Multi-Banked Memory Cluster Compound Component exports the ports OG.send as send, the port IC.rec as rec and the α tick interaction export the port tick.

In The key component which the NoC functionality is based on are the network routers. The routers read the information contained inside a package and they are charged with the task of routing and arbitrating the packages inside the NoC. We model the routers in BIP using a composite component called Router. The Router is composed by a set of coupled Router Incoming and Router Outgoing Port Components, as illustrated in Figure 4.20. There is one couple Incoming and Outgoing Port Component for each routing direction. The directions are North, South, East, West and local cluster. The port components are all connected with all the other directions. That is, each Router Incoming Port Component is connected with all the Router Outgoing Port Components of all the other directions. The connection is modeled with a connector controlled by a guard depending on the routing information of the package.

The Router Incoming Port Component uses the rec port to receive the incoming packages in the router. It simply forwards the packages to the guarded connectors sending explicitly the routing information to it along with all the package through the fwd port. The component is also timed, measuring the Router Outgoing Port conflict delays.

Definition (Router Incoming Port Component)

We define the Router Incoming Port Component as IR = (L IR , X IR , P IR , T IR ), where:

• L IR = { 1 , 2 },
• X IR = {package, port id)},

• P IR = {rec, f wd}, where port rec is binded with the package variable and f wd port is binded with the package and port id variables.

• T IR = { τ = ( 1 , rec, true, skip, 2 )}, f rec : port id = route(package) τ = ( 2 , f wd, true, skip, 1 )} }.
The standard routing delay of a package is modeled by the Router Outgoing Port Component. Apart from the routing delay the link latency is also considered. The link latency derives from the links connecting the routers on the NoC. This latency is integrated in the Router Outgoing Port Component along with the routing delay. The ports rec and send interact with the Incoming Port and the next Router Component respectively.

Definition (Router Outgoing Port Component)

We define the Router Outgoing Port Component as OR = (L OR , X OR , P OR , T OR ), where:

• L OR = { 1 , 2 },
• X OR = {package, count, routing delay, link latency, port id)},

• P OR = {rec, tick, send}, where port rec is binded with the package and port id variables and send port is binded with the package variable.

• T OR = { τ = ( 1 , rec, true, f r , 2 )} , f r : count = 0;, τ = ( 2 ,
γ = {α N S , α N E , α N W , α N L } ∪ {α SN , α SE , α SN , α SL } ∪ {α EN , α ES , α EN , α EL }∪ {α W N , α W S , α W E , α W L } ∪ {α LN , α LS , α LE , α LW } ∪ {α tick }, α xy = ({IR x .f
γ = {γ R1 , γ R2 , γ R3 , γ R4 } ∪ {α tick },
where, For each α ∈ γ, the priority rule π implies that the tick interaction α tick has lower priority than any other interaction α. We export the tick port of the α tick interaction to dynamically enable synchronization with other tick interactions. We will further refer to this interaction as N oC.tick.

γ R1 = {α in CL1 , α out CL1 , α in R1 , α out R1 }, γ R2 = {α in CL2 , α out CL2 , α in R2 , α out R2 }, γ R3 = {α in CL3 , α out CL3 , α in R3 , α out R3 }, γ R4 = {α in CL4 , α out CL4 , α in R4 , α out R4 }, α in CL = {R.

Conclusion

In this chapter, we described the Abstract Model of HW Platform in BIP. A BIP Hardware Model should integrate both computation and communication constraints in a unified model. The computation constraints are added with the use of a Processor Scheduler Components and the profiling of the software processes with the corresponding timing delays as described in Chapter 7. The communication constraints are integrated with the use of Cluster Compound Components modeling the communication paths from PEs towards the platform memories and via versa. There are two types of Cluster used:

1. the Shared Memory Cluster using crossbar switch as a bus and shared memories.

2. the Multi-banked Memory Cluster using multiplexing interconnect as a bus and an efficient multi-banked memory.

The clusters include network interface to be capable to interact with off-cluster interconnect. The off-cluster interconnect modeled is a 4 × 4 network-on-chip. The NoC is implemented using Router Components modeling routing and arbitration policies. To compose the HW Platform models, we defined a library of atomic and compound components. These components can be parametrized, in order to model specific manycore platforms as we present in Sections 10.1 and 11.1. The correct-by-construction synthesis of the complete HW/SW model is analyzed in Chapter 6 considering the mapping of the SW application on the HW platform introduced in the next Chapter 5.

-Chapter 5 -

Binding BIP SW Model to HW Platforms

In the previous chapter, we specified the target HW platforms which we consider in our work. We defined the abstract HW platform models in BIP and all the components types needed for them. In this chapter, we introduce the mapping definition and the refinement of the software application model in BIP in order to conform with the mapping specification, thus accurately modeling the deployment on the HW platform. The refined software application model in BIP is obtained by a series of correct-by-construction transformations. We use a notion of trace equivalence, based on the principle of observational equivalence [START_REF] Milner | A Calculus of Communicating Systems[END_REF], to prove the correctness of the refined model. The aim is to show the equivalence between the trace of the initial software application model and the final mixed SW/HW System model which we define in Chapter 6.

The chapter is structured in two sections. In the first section, we describe the mapping specification and in the second section, we define the refined software application model, the intermediate refinement steps and we prove the correctness of the transformed model.

Mapping Specification

Given an Application-Software and a HW-Platform, a Mapping associates the software processes to hardware processors and the software channels to hardware memories. Moreover, the mapping also defines the scheduling policies for processors, formally: As presented in Section 3.2.2 the FIFO Components contain behavior which controls the data buffer. In order to deploy the application software on the HW platform, we need a low level implementation model for the SW-Channels where the control and the data are dissociated and moreover, the Write/Read operations are no longer atomic, since they involve more than one component. As a result, we decompose the FIFO Component in BIP, which models the SW-Channels, into three new components: the FIFO-Write, the FIFO-Read and the FIFO-Buffer Component.

The FIFO-Write and FIFO-Read Components are used to model the Write/Read FIFO access routines which control the buffer indices, the buffer size and the data counters. Therefore, the FIFO-Write and FIFO-Read Components are binded with the Process connected to them, and will be referred to as FIFO-Routine Components. The FIFO-Buffer Component is used to model the store and load operations on the buffer. As a consequence of the above decomposition, the Write/Read operations are no longer atomic, since they involve more than one component.

A more detailed Mapping associates a FIFO-Routine with the same hardware processor as the Process which is connected to and associates each FIFO-Buffer with a hardware memory.

Application-Software Model Refinement

Given an Application-Software model, the adjustment for connection with a hardware model is performed in a series of transformations:

1. Breaking the atomicity of Write/Read operations. In the BIP implementation of the Application-Software, the Write/Read are blocking operations. Since the next transformation decomposes the SW-Channels to three different components, we need to ensure the non-atomicity of the Write/Read operations, in order to preserve the blocking functionality.

2. Decomposing the SW-Channels into Write/Read FIFO access routines and data buffers to accurately map them to hardware processors and hardware memories.

3. Modifying Process and FIFO-routines Components to enable interaction with a hardware processor.

The above transformations refine the Application-Software model in a correct-by-construction manner and are described in the next Section 5.2.1.

Breaking Atomicity -Refinement

The first transformation consists in breaking atomicity of write and read operations. Every transition involving an input/output port x is split into two transitions, labeled by fresh ports, respectively x b (i.e., x-begin) and x e (i.e., x-end). This is obtained by adding new control locations for each read/write operation in the behavior of a process and a FIFO Component. The transformed components are called Refined and their formal definition is given below.

34 Definition (Refined Process Component) Given a Process Component G = (L, P, X, T ) as defined in Definition 15, we define the Refined Process Component G R = (L R , X, P R , T R ) with broken atomicity on the Read, Write transitions, where the behavior is described in Figure 5.1:

• L R = L ∪ { |τ ∈ T, port(τ ) = β},

Definition (Refined FIFO Component)

Given a FIFO Component F as defined in Definition 16, we define a Refined FIFO Component as a BIP component

F R = (L F R , X F , P F R , T F R )
, where the behavior is described in Figure 5.2:

• L F R = { , w , r },
• X F R = {wr data, rd data, buf f, i, j, k, count}, • T F R = { τ w b = ( , w b , g w , f wm , w ), τ we = ( w , w e , true, f wn , ), τ r b = ( , r b , g r , f rm , r ), τ re = ( r , r e , true, f rn , ), }.

• P F R = {w b , w e ,
We replace each transition τ labeled by a port p with two consecutive transitions τ b , τ e labeled respectively by ports p b , p e . After evaluating the guard, the first transition executes the Write or Read actions on the buffer. The second, increases or (resp. decreases) the FIFO counter and adjusts the buffer indices.

Definition (Refined Process Network Composition)

For a Process Network N = γ(G 1 , . . . , G n , F 1 , . . . , F k ) as defined in Definition 17, we define the Refined Process Network We split every interaction α into two consecutive interactions α b , α e , which depend on the initial interaction type. If it is a Write interaction α w , the α w b will preserve the behavior of the initial α w , and respectively for Read interactions α r , the α r e transition will execute the data transfer.

N R = γ R (G R 1 , . . . , G R n , F R 1 , . . . , F R k ),

Example (Producer-Consumer Refined Composition)

Given a Producer-Consumer Process Network P C as defined in Example 8, we break the atomicity of the interactions which belong to P C and we define the Refined Process

Network P C R = γ R (G R P , F R , G R C ), where γ R = {α w b , α r b , α w e , α r e }, α w b = ({G R P .w b , F R .w b }, true, f α w ), α r b = ({F R .r b , G R P .r b }, true, f α r ),

Correctness

In this section, we prove trace equivalence between the above Refined Process Network Composition and the initial Process Network.

Definition (Complete Run)

For a given composition C = γ(B 1 , B 2 , . . . , B N ), a run θ is called complete, if the number of begin events equals the end events.

Definition (Trace Restriction of a Refined Process Network N R ) For a Refined Process Network N R :

• The restriction of a run θ R to end events is defined by:

trace R (θ R ) =      ,if θ R : β.trace R (θ R ) ,if θ R : q β -→ q .θ R α.trace R (θ R ) ,if θ R : q α b -→ q αe -→ q .θ R ,
where α ∈ γ and α b , α e use the same FIFO.

Let N R be the Refined Process Network for N .

Theorem

For each run θ in the Process Network N :

θ : q 0 a 1 -→ γ q 1 a 2 -→ γ q 2 a 3 -→ γ ...
an -→ γ q n There exists a complete run θ R in the Refined Process Network N R :

θ R : q 0 a R 1 --→ γ R q R 1 a R 2 --→ γ R q R 2 a R 3 --→ γ R ... a R m --→ γ R q R m such that: • q n = q R m • trace(θ) = trace R (θ R ) Theorem For each complete run θ R in the Refined Process Network N R : θ R : q 0 a R 1 --→ γ R q R 1 a R 2 --→ γ R q R 2 a R 3 --→ γ R ... a R m --→ γ R q R m
There exists a run θ in the Process Network N :

θ : q 0 a 1 -→ γ q 1 a 2 -→ γ q 2 a 3 -→ γ ... an -→ γ q n such that: • q n = q R m • trace R (θ R ) = trace(θ)

Lemma

For each complete run θ in the Refined Process Network N R : θ : q 0 → • • • → q n There exists a complete run θ in the Refined Process Network N R starting from q 0 : θ : q 0 → • • • → q n such that:

• q n = q n
• in θ any begin interaction is followed immediately by the corresponding end interaction.

Proof (Theorem 1)

We consider a run θ :

q 0 α 1 -→ γ q 1 α 2 -→ γ ... α n
--→ γ q n in a Process Network N . Based on the Definition 36 of the Refined Process Network, we break the atomicity of the Write and Read interactions and we replace them with begin/end-Write/Read interactions. Since we do not modify the β transitions we consider them hidden from the run. Thus, we obtain a run θ R :

q 0 α 1 b -→ γ R q R 1 α 1 e -→ γ R q R 2 α 2 b -→ γ R q R 3 α 2 e -→ γ R ... α R m --→ γ R q R
m , which belongs in the Refined Process Network N R . According to the Definition 36 of the Refined Process Network Composition as it is illustrated in the Example 15 and the Figure 5.3, we conclude that q n = q R m . In addition, we have trace(θ) = α 1 .α 2 . . . α n and trace(θ

R ) = α 1 b .α 1 e .α 2 b .α 2 e . . . α n b .α n e .
Based on the Definition 38, we restrict the trace θ R such that trace R (θ R ) = α 1 .α 2 . . . α n . So, we conclude that trace(θ) = trace R (θ R ).

Proposition

Let a complete run θ

R : q 0 α 1 -→ γ R q 1 α 2 -→ γ R q 2 .
θ , which belongs in the Refined Process Network N R and trace(θ R ) = α 1 .α 2 .trace(θ ). Suppose that the interactions α 1 , α 2 modify independent variables which do not impact the evaluation of any transition guard. Thus, we can reverse their execution order:

θ R : q 0 α 2 -→ γ R q 1 α 1 -→ γ R q 2 .
θ and trace(θ R ) = α 2 .α 1 .trace(θ ), preserving the equality of the ending states q 2 = q 2 . The proof is evident and thus not required.

Proof (Lemma 1) Let a complete run θ R : q 0 α 1 -→ γ R q 1 α 2 -→ γ R q 2 .θ , which belongs in the Refined Process Network N R and trace(θ R ) = α 1 .α 2 .

trace(θ ). Based on Proposition 1 we can reverse the execution order of interactions

α 1 , α 2 : θ R : q 0 α 2 -→ γ R q 1 α 1 -→ γ R q 2 .θ .
As we can see in Example 15 the traces of a Refined Process Network contain α w b , α w e , α r b , α r e interactions. The order of execution of begin and end events is respected provided that the Write/Read operate on the same FIFO. If the FIFOs are different we can have interleavings of Write/Read and begin/end events. However, based on the Proposition 1 we can recursively relocate the execution order of begin events of the interactions which operate on different FIFOs, so that they are followed immediately by their corresponding end interaction. Thus, we can conclude that:

• the ending state of the new run is equal to the ending state of the old run

• in θ R any begin interaction is followed immediately by the corresponding end interaction

3 Proof (Theorem 2) We consider a run θ R : q 0 α 1 -→ γ R q 1 α 2 -→ γ R . . . α m --→ γ R q m in
a Refined Process Network N R . Based on Lemma 1, we consider θ R in N R such that any begin is immediately followed by the corresponding end interaction θ R : q 0

α 1 b -→ γ R q 1 α 1 e -→ γ R . . . α m b --→ γ R q m-1 α m e --→ γ R q m .
As a consequence of Lemma 1, we have q m = q m . Additionally, based on the Definition 36 of the Refined Process Network as it is illustrated in the Example 15 and the Figure 5.3, we replace the consecutive begin/end interactions with a single Write or Read interaction. Thus, we obtain a run θ :

q 0 α 1 -→ γ q 2 α 2 -→ γ . . . α m --→ γ q m such that θ belongs in Process Network N . We have, trace(θ) = α 1 .α 2 . . . α m and trace(θ R ) = α 1 b .α 1 e .α 2 b .α 2 e . . . α m b .α m e .
Based on the restriction of traces in Definition 38, we also have trace R (θ R ) = α 1 .α 2 . . . α m . So, we conclude that trace R (θ R ) = trace(θ).

FIFO Decomposition -Refinement

Every SW-Channel in the application software is replaced by a composition of FIFO-Write, FIFO-Read and a FIFO-Buffer atomic components (see Figure 5.5). The two former components represent the control part of the software channel, that is, the hardware dependent software routines implementing the read/write operations. The latter component simply represents the buffer of data.

All the three components FIFO-Read, FIFO-Write, FIFO-Buffer are predefined BIP components and belong to the BIP hardware dependent software library. The FIFO-Read Component, illustrated in Figure 5.5, implements the read operation on channels. It has the ports r b (Read-Begin), r e (Read-End) for its interaction with a software process read operation, and ports mr b (Memory Read-Begin), mr e (Memory Read-End) for its interaction with the buffer. The FIFO-Write Component implements the write action in a similar manner.

Let us notice that the two routines, FIFO-Write and FIFO-Read, require extra synchronization with each other in order to maintain a coherent value for the used space within the buffer. This is realized by using strong synchronization between two control ports, w u (Write Update)and r u (Read Update) and the Memory-End interactions.

Definition (FIFO-Write Component)

We define the FIFO-Write Component as a BIP Component F W = (L F W , X F W , P F W , T F W ), where the behavior is described in Figure 5.5.

• L F W = { 1 , 2 , 3 , 4 }, • X F W = {wr data, i, k, count, buf f },
• P F W = {w b , mw b , mw e , w u , w e }, where w b associated with {wr data},

• T F W = { τ w b = ( 1 , w b , true, skip, 2 ), τ mw b = ( 2 , mw b , g w , skip, 3 ), with g w : [count < N ], τ mwe = ( 3 , mw e , true, f wn , 4 ),
with f wn : count + +; i = (i + 1)%N ; buf f [i] = data;, τ we = ( 4 , w e , true, skip, 1 ), {τ u = ( , w u , true, f rc , )| ∈ L F W }, with f rn : count --; }.

Definition (FIFO-Read Component)

We define the FIFO-Read Component as a BIP component F R = (L F R , X F R , P F R , T F R ), where the behavior is described in Figure 5.5.

• L F R = { 1 , 2 , 3 , 4 }, • X F R = {rd data, j, k, count, buf f },
• P F R = {r b , mr b , mr e , r u , r e }, where r e associated with {rd data},

• T F R = { τ r b = ( 1 ,

Definition (FIFO-Buffer Component)

We define the FIFO-Buffer Component as a BIP component F B = (L F B , X F B , P F B , T F B ), where the behavior is described in Figure 5.5.

• L F B = { 1 , 2 , }, • X F B = ∅, • P F B = {op b , op e },
• T F B = { τ op b = ( 1 , op b , true, skip, 2 ), τ ope = ( 2 , op e , true, skip, 1 ). }.

Definition (Split-FIFO Process Network Composition)

Given a Refined Process Network N R as defined in Definition 36, we define a Split-FIFO Process Network

N D = γ D (G R 1 , . . . , G R n , F W 1 , F R 1 , F B 1 , . . . , F W k , F R k , F B k ),

Correctness

In the current section, we prove the trace equivalence of a Split-FIFO Process Network N D with a Refined Process Network N R . That is, the composition is a refined model of the SW-Channel which fully preserves the input/output behavior of the software channel.

Definition (Trace Restriction of a Split-FIFO Process Network N D )

For a Split-FIFO Process Network N D , the restriction of a trace of a run θ D to nonmemory events is defined by:

trace D (θ D ) =      ,if θ D : β.trace D (θ D ) ,if θ D : q β -→ q .θ D trace D (θ A ).trace D (θ B ) ,if θ D : θ A .q α m b --→ q α m e --→ q .θ B
Let N D be the Split-FIFO Process Network for N R .

Theorem

For each run θ R in the Refined Process Network N R :

θ R : q 0 a R 1 --→ γ R q R 1 a R 2 --→ γ R q R 2 a R 3 --→ γ R • • • a R n --→ γ R q R n
There exists a complete run θ D in the Split-FIFO Process Network N D :

θ D : q 0 a D 1 --→ γ D q D 1 a D 2 --→ γ D q D 2 a D 3 --→ γ D • • • a D m --→ γ D q D m
such that:

• q R n = q D m
, where q D m concerns the Process Components,

• trace(θ R ) = trace D (θ D )
Theorem For each complete run θ D in the Split-FIFO Process Network N D :

θ D : q 0 a D 1 --→ γ D q D 1 a D 2 --→ γ D q D 2 a D 3 --→ γ D ... a D m --→ γ D q D m
There exists a run θ R in the Refined Process Network N R :

θ : q 0 a R 1 --→ γ R q R 1 a R 2 --→ γ R q R 2 a R 3 --→ γ R • • • a R n --→ γ R q R n such that: • q R n = q D m
, where q D m concerns the Process Components,

• trace D (θ D ) = trace(θ R )

Lemma

For each complete run θ in the Split-FIFO Process Network N D : θ : q 0 → • • • → q n There exists a complete run θ in the Split-FIFO Process Network N D starting from q 0 : θ : q 0 → • • • → q n such that:

• q n = q n
• in θ any α w b or α r b interaction is followed immediately by the series of interactions α mw b , α mw e , α w e and α mr b , α mr e , α r e respectively.

Proof (Theorem 3)

We consider a complete run θ R in a Refined Process Network N R . Based on Lemma 1, we re-order any begin interaction so that it is immediately followed by the corresponding end interaction. Since we do not consider the β transitions, we have θ R : q 0

α 1 b -→ γ R q R 1 α 1 e -→ γ R q R 2 α 2 b -→ γ R q R 3 α 2 e -→ γ R ... α n e --→ γ R q R .
We refine the FIFO Component by replacing it with FIFO-Write, FIFO-Read and FIFO-Buffer Components. We obtain a run θ D : q 0

α 1 b -→ γ D q D 1 α m1 b --→ γ D q D 2 α m1 e --→ γ D q D 3 α 1 e -→ γ D q D 4 α 2 b -→ γ D q D 5 α m2 b --→ γ D q D 6 α m2 e --→ γ D q D 7 α 2 e -→ γ D ...
α n e --→ γ D q D . According to the Definition 42 of the Split-FIFO Process Network as it is illustrated in the Example 16 and the Figure 5.5, we have q R = q D , where q D concerns the Process Components.

In addition, we have 5 Proof (Lemma 2) Let a complete run θ D :

trace(θ R ) = α 1 b .α 1 e .α
q 0 α 1 -→ γ R q 1 α 2 -→ γ R q 2 .
θ , which belongs in the Split-FIFO Process Network N R and trace(θ D ) = α 1 .α 2 .trace(θ ). Based on Proposition 1 we can reverse the execution order of interactions α 1 , α 2 :

θ D : q 0 α 2 -→ γ R q 1 α 1 -→ γ R q 2 .θ .
As we can see in Example 15 the traces of the Split-FIFO Process Network contain α w b , α mw b , α mw e , α w e , α r b , α mr b , α mr e , α r e interactions. If interleavings of the above interactions occur, we can recursively relocate the execution order according to Proposition 1. So, any α w b or α r b interaction is followed immediately by the series of interactions α mw b , α mw e , α w e and α mr b , α mr e , α r e respectively. Thus, we can conclude that:

• the ending state of the new run is equal to the ending state of the old run

• in θ d any α b interaction is followed immediately by the series of α m b , α m e , α e interactions.

Proof (Theorem 4)

We consider a run θ D :

q 0 α D --→ γ R q 1 α 2 -→ γ D . . . α k -→ γ D q k in
a Split-FIFO Process Network N D . Based on Lemma 2, we consider θ D in N D such that any α b interaction is followed immediately by the series of α m b , α m e , α e interactions such that θ D : q 0

α 1 b -→ γ D q 1 α m1 b --→ γ D q 2 α m1 e --→ γ D q 3 α 1 e -→ γ D . . . α k e
-→ q k . As a consequence of Lemma 2, we have q k = q k . Additionally, based on the Definition 42 of the Split-FIFO Process Network as it is illustrated in the Example 16 and the Figure 5.5, we replace the series of α b , α m b , α m e , α e interactions with the couple of α b , α e interactions. Thus, we obtain a run θ R : q 0

α 1 b -→ γ D q 1 α 1 e -→ γ D . . . α k e -→ q k such that θ R belongs in the Refined Process Network N R . We have, trace(θ R ) = α 1 b .α 1 e .α 2 b .α 2 e . . .

Mutual Exclusion and Computation Time Refinement

Several processes, together with their associated FIFO access routines, are potentially mapped on the same hardware processor and must use it in mutual exclusion. The ports acq and rel are added for interaction with the processor scheduler. The port acq is used for acquiring and rel is for releasing the processor. The first time when a process acquires the processor is the start of its execution. It releases the processor on its termination.

Processes that are mapped on the same processor cannot simultaneously utilize the processor's computational resource. Thus, we use a mutual exclusion scheduler with Acquire and Release primitives. We add to the process components Acquire and Release scheduling primitives as ports associated respectively with a new transition to the initial ini control location and with a new transition from each control location in L f in . f in states of the process component. The Read and Write operations of the processes can be blocked due to limited places of the FIFO buffer. Considering the above and the fact that the FIFO mechanism is managed by the FIFO Read/Write Components, we add Acquire and Release scheduling primitives in these components too. The modified process and FIFO Components are defined below.

In addition, all processes contain computational hidden transitions β. Every β transition is profiled with a computational cost. In every transition β a delay variable is filled with the computational cost of the executed f β function. The methods used to obtain the profiling value are explained in details in Chapter 7. This computational delay should be pushed to the processor scheduler, which is responsible for modeling the computational resource of the processor. We add the send d (Send Delay) and next primitives to the process components. The send d sends the delay to the processor and the next allows the process to continue to the next computational or communication step of the process. The send d and next transitions are placed immediately after the β transitions. The Scheduled Process Component is depicted in Definition 44.

Definition (Scheduled Process Component)

Given a Process Component G R = (L R , X R , P R , T R ), we define the Scheduled Process Component G s = (L s , P s , X s , T s ) with Acquire, Release scheduling transitions, where:

• L s = L R ∪ { 0 , n } ∪ { β p , β q |τ β ∈ T R },
where n -1 the number of states ∈ L R ,

• P s = P R ∪ {acq, rel, send d, next},

• X s = X R ∪ {delay}, • T s = T R ∪ {τ acq = ( 0 , acq, true, skip, ini ), τ rel = ( f in , rel, g exit , skip, n )} ∪ {τ = ( , β, g, f , d ), τ = ( d , send d, true, skip, n ), τ = ( n , next, true, skip, )|τ = ( , β, g, f, )}
, with g exit the exiting condition and f : f ; delay = prof value();.

Moreover, they also use the ports rel and acq for interaction with the processor scheduler. These ports are used to release (resp. acquire) the processor whenever the Read/Write operation is suspended (resp. resumed) due to lack (resp. presence) of available data (or available space) in the buffer.

The FIFO-Write and the FIFO-Read Components are also connected to the Processor Scheduler. At the point which a process initiates a Write or a Read call, the FIFO Components may be blocked due to the lack of availability of empty space in the buffer or due to the absence of data to read, the FIFO Components should release the control and re-acquire it when the buffer is in an utilizable state.

Definition (Scheduled FIFO-Write Component)

Given a FIFO-Write Component F W , we define the Scheduled FIFO-Write Component as

F W s = (L F W s , X F W s , P F W s , T F W s )
, where the behavior is described in Figure 5.7.

• L F W s = L F W ∪ { 5 }, • X F W s = X F W , • P F W s = P F W ∪ {acq, rel}. • T F W s = { τ w b = ( 1 , w b , true, skip, 2 ), τ mw b = ( 2 ,
{τ u = ( , w u , true, f rc , )| ∈ L F W s } }.

Definition (Scheduled FIFO-Read Component)

Given a FIFO-Read Component F R, we define the Scheduled FIFO-Read Component as

F R s = (L F R s , X F R s , P F R s , T F R s )
, where the behavior is described in Figure 5.7.

• L F R s = L F R ∪ { 5 }, • X F R s = X F R , • P F R s = P F R ∪ {acq, rel}. • T F R s = { τ r b = ( 1 , r b , true, skip, 2 ), τ mr b = ( 2 ,
mr b , g r , skip, 3 ), τ mre = ( 3 , mr e , true, f rn , 4 ), τ re = ( 4 , r e , true, skip, 1 ), τ acq = ( 5 , acq, g r , skip, 2 ),

τ rel = ( 2 , rel, !g r , skip, 5 ), {τ u = ( , r u , true, f wc , )| ∈ L F R s } }.

Correctness

This is an intermediate model, specifically modified to be connected with a Processor Scheduler Component introduced in Section 4.2.1. The derived model is intended to integrate the scheduling and computation delay constraints of the HW platform. The formal definition and correctness are given in Section 6.1 in the next chapter.

Conclusion

In this chapter, we analyzed the mapping as it is used in the construction of the System Model. We defined the refinement steps of the initial software application model in order to conform with the mapping, which models the accurate deployment on the HW platform. For each step, the intermediate models obtained are equivalent with the initial model. To prove the above, we used the notion of trace equivalence.

Integration of HW Constraints

In the previous chapter, we analyzed the refinement of the software application model in BIP according to a given mapping on a HW platform. The goal of the refinement is the accurate deployment on the HW platform. In this chapter, we focus on the integration of the HW constraints which arise upon the execution of a software application on a given platform. More specifically, we merge the refined software application model in BIP with the target abstract model of a HW platform in BIP.

HW Constraints For Computation

In Section 4.2, we listed the HW constraints which characterize a HW platform. In this section, we connect the HW computation model with the software application mode and we prove the correctness of the generated mixed HW/SW model.

47 Definition (Processor Scheduled Process Network Composition) -Addition of Mutual Exclusion Scheduler and Computational delays-Let a Split-FIFO Process Network N D as defined in Definition 42 and a HW platform using m processors. The processor resource is modeled by the Processor Scheduler Component defined in Definition 18. We define a Scheduled Process Network

N S = γ S (G S 1 , . . . , G S n , F W S 1 , F R S 1 , F B 1 , . . . , F W S k , F R S k , F B k , SC 1 , . . . , SC m )
, where the set of interactions γ S is defined as: We export the tick port of the α tick interaction to dynamically enable synchronization with other tick interactions. We will further refer to this interaction as N S .tick. ), we add computational delays and processor scheduling. We map the Producer and the Consumer processes on a single processor. Consequently, G P and F W , which is directly connected to G P , are connected to the Processor Scheduler SC 1 . Similarly, G C and F R are connected to Processor Scheduler SC 1 , such that we obtain: P C S = γ S (G S P , F W S , F R S , F B, G S C , SC 1 ) as illustrated in Figure 6.1, where

γ S = γ D ∪ {α tick } ∪ {α acq G , α rel G , α send d G , α next G |G ∈ N S } ∪ {α acq F W , α rel F W |F W ∈ N S } ∪ {α acq F R , α rel F R |F R ∈ N S }, α acq G = ({G
γ S = γ D ∪{α acq , α rel , α send d , α next |G ∈ N S }∪{α acq F W , α rel F W |F W ∈ N S }∪{α acq F R , α rel F R |F R ∈ N S }
The set of traces is represented as the interleavings in Figure 6 The restriction of a trace of a run θ S to β events is defined by:

trace S (θ S ) =      ,if θ S : β.trace S (θ S ) ,if θ S : q β -→ q 1 send d ----→ q 2 tick 1 ---→ • • • tickn ---→ q k next ---→ q .θ S trace S (θ A ).trace S (θ B ) ,if θ S : q 0 acq --→ q 1 .θ S A .q k rel --→ q k+1 .θ S B , with acq, rel / ∈ θ S A
Note that, θ S B always starts with an acq and ends with a rel, so that we can recursively apply the above rule.

Let N S be the Processor Scheduled Process Network Composition of N D .

Theorem

For each complete run θ D in the Split-FIFO Process Network N D :

θ D : q 0 a D 1 --→ γ D q D 1 a D 2 --→ γ D q D 2 a D 3 --→ γ D • • • a D n --→ γ D q D n
There exists a complete run θ S in the Processor Scheduled Process Network N S :

θ S : q 0 a S 1 -→ γ S q S 1 a S 2 -→ γ S q S 2 a S 3 -→ γ S • • • a S m --→ γ S q S m
such that:

• q D n = q S m , where q S m concerns the subsystem of the components which do not include the Processor Scheduler,

• trace(θ D ) = trace S (θ S ) Theorem For each complete run θ S in the Processor Scheduled Process Network N S :

θ S : q 0 a S 1 -→ γ S q S 1 a S 2 -→ γ S q S 2 a S 3 -→ γ S ... a S m --→ γ S q S m
There exists a complete run θ D in the Split-FIFO Process Network N D :

θ : q 0 a D 1 --→ γ D q D 1 a D 2 --→ γ D q D 2 a D 3 --→ γ D • • • a D n --→ γ D q D n such that: • q S n = q D m
, where q S n concerns the subsystem of the components which do not include the Processor Scheduler,

• trace S (θ S ) = trace(θ D )

Lemma

For each complete run θ in the Processor Scheduled Process Network N S : θ : q 0 → • • • → q n There exists a complete run θ in the Processor Scheduled Process Network N S starting from q 0 : θ : q 0 → • • • → q n such that:

• q n = q n
• each trace that contains interactions which concern a single process are always enclosed between the acq, rel interactions,

• in θ any α β interaction is followed immediately by the series of interactions

α send d , α tick 1 • • • α tickn Proof (Theorem 5)
We consider a complete run θ D in the Split FIFO Process Network N D . Based on Lemma 1, we re-order any begin interaction so that it is immediately followed by the corresponding end interaction. We have

θ D : q 0 α 1 -→ γ D q D 1 α 1 β --→ γ D • • • α 2 -→ γ D q D 2 α 2 β --→ γ D q D . We map each Process Component G D , along with the FIFO Routines F W D , F R D connected
to it, on a Processor Scheduler Component. We obtain a run θ D :

q 0 acq --→ γ S q S 1 α 1 -→ γ D q D 2 β 1 -→ γ S q S 3 send d ----→ γ S q S 4 tick 1 ---→ γ S • • • tickn ---→ γ S q S 5 next ---→ γ S • • • α 2 -→ γ D q D 6 β 2 -→ γ S q S 7 send d ----→ γ S q S 8 tick 1 ---→ γ S • • • tickn ---→ γ S q S 9 next ---→ γ S q S 10 rel --→ γ S q S .
According to the Definition 47 of the Processor Scheduled Process Network as it is illustrated in the Example 17 and the Figure 6.1, we have q D = q S , where q S concerns the subsystem of the components which do not include the Processor Scheduler.

In addition, we have: . So, we conclude that trace(θ D ) = trace S (θ S ).

trace(θ D ) = α 1 .β 1 .α 2 .
8 Proof (Lemma 3) Let a complete run θ S : q 0

α 1 -→ γ r q 1 α 2
-→ γ r q 2 .θ , which belongs in the Processor Scheduled Process Network N r and trace(θ S ) = α 1 .α 2 .trace(θ ). Based on Proposition 1 we can reverse the execution order of interactions α 1 , α 2 : In this case, we can recursively relocate the execution order according to Proposition 1. So, any α w b or α r b interaction is followed immediately by the series of interactions α mw b , α mw e , α w e and α mr b , α mr e , α r e respectively. In addition, any α β interaction is followed immediately by the series of interactions send d, tick 1 . . . tick n , next. Also, the traces that concern a single process are enclosed between the acq, rel interactions, due to the Processor Scheduler resource demand. Thus, we can conclude that:

θ S : q 0 α 2 -→ γ r q 1 α 1 -→ γ r q 2 .
• the ending state of the new run is equal to the ending state of the old run,

• each trace that contains interactions which concern a single process are always enclosed between the acq, rel interactions,

• in θ s any β interaction is followed immediately by the series of send d, tick We consider a run θ S :

q 0 α S --→ γ r q 1 α 2 --→ γ S . . . α k
--→ γ S q k in a Processor Scheduled Process Network N S . Based on Lemma 3, we consider θ S in N S such that:

• a trace that contains interactions which concern a single process are always enclosed between the acq, rel interactions,

• any α β interaction is followed immediately by the series of send d, tick

1 • • • tick n , next interactions such that θ S : q 0 β -→ γ S q 1 send d ----→ γ S q 2 tick 1 ---→ γ S . . . tickn ---→ γ S next ---→ γ S . . . α k e -→ q.
As a consequence of Lemma 3, we have q k = q.

Additionally, based on the Definition 47 of the Processor Scheduled Process Network as it is illustrated in the Example 17 and the Figure 6.1, we replace the series of β, send d, tick 1 • • • tick n , next interactions with only the β interaction and we omit the acq, rel interactions. Thus, we will obtain a run θ S : q 0

α 1 b -→ γ S q 1 α m1 b --→ γ S q 2 α m1 e --→ γ S q 3 α 1 e -→ γ S . . .

HW Constraints For Communication

Given a Processor-Scheduled Process Network

N S = γ S (G S 1 , . . . , G S n , F W S 1 , F R S 1 , F B 1 , . . . , F W S k , F R S k , F B k , SC 1 , . . . , SC m ),
we replace the F B Components with a hardware template communication model and the α m ∈ γ S connectors with new ones depending on the mapping such as,

N S = γ S (G S 1 , . . . , G S n , F W S 1 , F R S 1 , . . . , F W S k , F R S k , SC 1 , . . . , SC m ),
We assume a platform where there are k processors, with k ≥ 1, one Crossbar Switch Bus and a shared Memory.

Definition (System Model Processor-Scheduled Process Network)

-NoC with four Shared Memory Clusters-Given a Processor-Scheduled Process Network N S , we define N M = πγ(N S , N OC) as the System Model of a Process Network on a HW platform, where N S is defined above and N OC = π N OC γ N OC (CL 1 , . . . , CL For each interaction, tick has the lowest priority and the interactions acq, rel have the highest priority of all, in order to prevent infinite ticking.

Example (Processor-Scheduled Producer-Consumer Composition) -Shared Memory Cluster-Given a Processor Scheduled Producer-Consumer Composition P C S = γ S (G S P , F W S , F R S , F B, G S C , SC 1 ), we add communication delays. We map the FIFO-Buffer F B on the shared memory such that we obtain:

P C M = γ(G S P , F W S , F R S , G S C , SC 1 , BU S 1 , M 1
), as illustrated in Figure 6.4, where: BU S 1 = π bus γ bus (BP For each α ∈ γ, the tick interaction has the lowest priority and the interactions α acq , α rel have the highest priority of all, in order to prevent infinite ticking. A figure illustrating the current example with the use of a Network-on-Chip is provided in Figure 6.5.

Correctness Definition (Trace Restriction of a System Model Process Network Composition)

The restriction of a trace of a run θ M is defined by:

trace M (θ M ) =      ,if θ M : β.trace M (θ M ) ,if θ M : q β -→ q .θ M trace(θ A ).α m b .α m e .trace M (θ B ) , if θ M : θ A .q 0 α m b --→ q 1 .θ X .q 2 α m e --→ q 3 .θ B
where α m b α m e / ∈ θ X and all interactions in θ X concern communication such as usage of BUS, Memory and NoC. The restriction means that all the interactions which concern communication and take place between mw b /mr b and mw e /mr e can be omitted.

Let N M be the System Model Composition Composition of N S .

Theorem

For each complete run θ S in the Processor Scheduled Process Network N S :

θ S : q 0 a S 1 -→ γ S q S 1 a S 2 -→ γ S q S 2 a S 3 -→ γ S • • • a S n -→ γ S q S n
There exists a complete run θ M in the System Model Process Network N M : • q S n = q M m , where q M m concerns the subsystem of the components which do not include the communication model,

θ M : q 0 a M 1 --→ γ S q M 1 a M 2 --→ γ M q M 2 a M 3 --→ γ M • • • a M m --→ γ M q M m such that: count++; count++; count--; count--; [count>0] count++; [count>0] [count==0
• trace(θ S ) = trace M (θ M ) . . . . .

Theorem

For each complete run θ M in the System Model Process Network N M :

θ M : q 0 a M 1 --→ γ S q M 1 a M 2 --→ γ M q M 2 a M 3 --→ γ M ... a M m --→ γ M q M m
There exists a complete run θ S in the Processor Scheduled Process Network N S :

θ : q 0 a S 1 -→ γ S q S 1 a S 2 -→ γ S q S 2 a S 3 -→ γ S • • • a S n -→ γ S q S n
such that:

• q M n = q S m
, where q M m concerns the subsystem of the components which do not include the communication model,

• trace M (θ M ) = trace(θ S )

Lemma

For each complete run θ in the System Model Process Network N M : θ :

q 0 → • • • → q n
There exists a complete run θ in the System Model Process Network N M starting from q 0 : θ : q 0 → • • • → q n such that:

• q n = q n • θ : θ A .q 0 α m b --→ q 1 .θ X .q 2 α m e --→ q 3 .θ B ,with α m b α m e /
∈ θ X , and all interactions in θ X concern communication such as usage of BUS, Memory and NoC.

Proof (Theorem 7)

We consider a complete run θ S in the Processor Scheduled Process Network Composition N S , such that we have:

θ S : q 0 acq --→ γ S q S 1 α 1 b -→ γ S q S 2 α m1 b --→ γ S q S 3 α m1 e --→ γ S q S 4 α 1 e -→ γ S • • • rel --→ γ S q S
We map each FIFO Buffer Component F B upon the shared memory. We obtain a run:

θ S : q 0 acq --→ γ q 1 α 1 b -→ γ q 2 α m1 b --→ γ q 3 α tick 1 ----→ γ • • • α tickn ----→ γ q 4 acq bus ----→ γ q 5 α tick 1 ----→ γ • • • α tickn ----→ γ q 6 α BP.β ----→ γ q 7 α tick 1 ----→ γ • • • α tickn ----→ γ q 8 α op b --→ γ q 9 α tick 1 ----→ γ • • • α tickn ----→ γ q 10 α op e --→ γ q 11 rel bus ---→ γ q 12 α m1 e --→ γ • • • rel --→ γ q M .
We consider the Definition 49 of the System Model Processor-Scheduled Process Network on a Shared Memory Cluster, as illustrated in Example 18 and in Figure 6.3, At the point where a FIFO routine Component does a mw b or a mr b to access a specific address in the hardware memory, no other FIFO Routine can access the same hardware memory address. The FIFO mechanism prevents this from happening. Only after the corresponding mw e or a mr e has been executed, should this particular memory address be accessed again. Thus, all the communications interactions taking place between mw b /mr b and mw e /mr e that concern interconnects, memories and NoC can be omitted, since the functional behavior of the initial process network and the FIFO functionality is always respected. Thus, we conclude that q M = q S , where q M m concerns the subsystem of the components which do not include the communication model. In addition we have,

trace(θ S ) = acq.α 1 b .α m1 b .α m1 e .
trace M (θ M ) = acq.α 1 b .α m1 b .α m1 e .α 1 e . . .

rel

So, we conclude that trace(θ S ) = trace(θ M ).

11 Proof (Lemma 4) Let a complete run θ :

q 0 α 1 -→ γ r q 1 α 2
-→ γ r q 2 .θ , which belongs in the System Model Process Network N r and trace(θ) = α 1 .α 2 .trace(θ ). Based on Proposition 1 we can reverse the execution order of interactions α 1 , α 2 : . . rel, where n, l, j, h > 1. Interleavings of the above interactions occur due to multiple communication resources, such as interconnects, memories or NoC, that run in parallel. In this case, we can recursively relocate the execution order according to Proposition 1. So, any α mw b or α mr b interaction is followed immediately by the series of communication interactions such as tick, acq bus , α µ b , α µ b , rel bus , etc. and always ends with the α mw e or α mr e interaction respectively. Thus, we can conclude that:

θ : q 0 α 2 -→ γ r q 1 α 1 -→ γ r q 2 .
• the ending state of the new run is equal to the ending state of the old run,

• in θ any communication interaction, such as tick, acq bus , α µ b , α µ b , rel bus , etc., is enclosed between α mw b , α mw e or α mr b , α mr e interactions.

12 Proof (Theorem 7) Proof evident based on Lemma 4 and Theorem 8.

Conclusion

In this chapter, we analyzed the method of integrating hardware platform components in a given software application model. The hardware platform components are assigned to model important functional and non-functional hardware constraints. Specifically, in the current model we have focused on the timing delays imposed by the underlying hardware platform. These values vary in different implementations of the platform. They are strongly dependent on the characteristics of each individual component of the platform. Namely, these are the scheduling policies, interconnect throughput, routing protocols, processor frequency and computing speed. However, the model of the processor does not consider analysis of low-level assembly code and pipeline. Modeling the above would superlatively increase the system's complexity and considerably stall the performance analysis. Thus, in order to bypass the above problem, we propose an instrumentation technique of the software application process model. The instrumentation method is presented in the next chapter.

The overall performance outcome of the system is highly affected by the mapping specification. Currently, we consider static mapping of processes upon the platform processors. Important part of the future extension of this work would be to consider task migration and dynamic mapping. Task migration protocol should be aware of all critical performance metrics of the system leading to optimal mapping obtained on-the-fly. Except from timing constraints, thermal values, power consumption and dynamic scheduling policies should be considered. The latter properties of the hardware model should enrich the current models of hardware components attributing to an extensive performance analysis of our target system.

-Chapter 7 -Integration of Runtime HW/SW Constraints (software dependent)

In the previous chapter, we mentioned that the proposed hardware platform model does not include a detailed processor model which implements instruction-level analysis and pipelining. However, we have developed techniques to obtain cycle-accurate execution delay values of the code included in the software processes running on a given hardware processor. These values are integrated in the generated system model in order to calibrate it so that it accurately models the computational delays derived from the use of a processor CPU. In this chapter, we describe the system model calibration and the associated methods we developed.

System Model Calibration

The generic procedure of the system model calibration includes the following steps. Firstly, each block of code of the BIP Processes, except the read/write communication transitions, is instrumented. The instrumentation is done by inserting function calls at the beginning and at the end of the executable block of code which is associated with a transition. Secondly, these calls are used by a tool, depending on the methods given below, to provide accurate execution times. We integrate the executions delay values to the system model by profiling each transition code block with them, as it is illustrated in Figure 7.1. This results to a faithful model of the HW/SW dependent run-time computational constraints. Finally, the calibrated BIP system model is used as such by the BIP tool-chain for performance analysis. The latter is achieved through compilation and execution using the BIP simulator. The various measurements (i.e. execution time, delays) are recorded by dedicated observers. We enumerate the two different calibration methods below:

1. Instruction Weight Table .   2. Platform Dependent Code Generation.

Instruction Weight Table

The method and its supporting tool can provide simulation environment for performance estimation on a given BIP system model. We adopted a strategy to dynamically obtain accurate execution delay values based on fine-grained code analysis. The basic idea of this

1 p 1 p 2 4 3 2 1 p 1 p 2 4 3 2 1 p 1 p 2 4 3 2 end(f 3 ) ← [g 3 ] β p 1 [g 1 ] p 2 [g 2 ] f 3 f 2 f 1 [g 3 ] β f 3 [g 3 ] β p 1 [g 1 ] p 2 [g 2 ] f 3 f 2 f 1 t(f 3 ) ← t(f 2 ) ← t(f 1 ) ← Process Instrumented Process Process Profiled p 2 [g 2 ] f 2 begin() end() p 1 [g 1 ] f 1 begin() end() begin(f 3 ) ← Figure 7.1: Process Profiling steps
strategy is to use gcov, which is a tool in conjunction with GCC to recover code coverage information using BIP simulation and analyze the executable code of each line considering the target platform. In order to get the execution result, the whole process is composed of four stages: 1) instrumentation stage to generate C codes with API function calls; 2) cross compilation with target platform; 3) GCC compilation with coverage parameters; 4) analysis stage which combines target platform information, code coverage and performance weight table to derive the execution delay values for each block of code in the initial System model. An overview of the above stages is presented in Figure 7.2.

(

: Instruction Weight Table Profiling Flow

Instrumentation The SW Application part of the BIP system model contains blocks of C code used to describe the behavior of each transition inside the BIP automata. API functions calls are inserted in the beginning and at the end of each BIP transitions. These functions are critical for the analysis stage which we describe later. More specifically, there are four functions: wpapi init(), wpapi begin(), wpapi end() and wpapi over(). The analysis stage is triggered when function wpapi init() is called. At the beginning some necessary environment valuables are configured and initialized. When the API function wpapi begin() is called, we analyze the following block of C code to measure the execution delay on the target platform. The API function wpapi end() signals that the calculated execution value is inserted back to the BIP System model to calibrate it. The API function wpapi over() is used to terminate the process.

Cross compilation with target platform In the second stage, we cross compile the SW Application part of the BIP system model with the target platform compiler. The goal is to generate the corresponding low-level assembly codes which is necessary for the detection of the CPU arithmetic or load/store operations included in every line of C code.

GCC compilation with coverage As shown in Figure 7.2, the SW Application is compiled into an executable binary along with the API library with the use of GCC coverage parameters. There are also some extra files generated with suffix .gcov for line coverage statistics.

( Analysis For the analysis stage we instantiate a process which runs in parallel with the BIP simulation as shown in Figure 7.3. As soon as it receives the request from the application process, it starts to analyze performance on the given range C code. There are, mainly, four analysis steps in the analysis process. The first step is to receive the message of API call and get the information about which lines are about to be profiled. The second step is to analyze the C code with its coverage file (.gcov) and calculate its total instruction cost according to the assembly code generated by the target platform cross compiler. On the third step, we obtain the total cycle number of each given line of the C code. In this step, the total execution cycle number is analyzed by taking into account the instruction weight table. Other factors could also be considered such as the pipeline control, the data hazards and memory access conflicts. In the final step, the analysis process sends the profiling result back to the application process.

Platform Dependent Code Generation

The platform dependent code generation provides a method to obtain cycle-accurate execution times of SW-Processes by generating and deploying low level code on a virtual target platform. The method is based on an infrastructure developed in Verimag, for generating code from the system models in BIP. Seeking portability, the generated code targets a particular run-time that can be eventually deployed and run on different platforms, including P2012 (Section 11.1) and MPARM (Section 10.1). The run-time provides a generic API for thread management, memory allocation, communication and synchronization. The generated code is not bound to any particular platform and consists of the functional code and the glue code.

The functional code is generated from the application components consisting of processes and FIFOs. Processes are implemented as threads, and FIFOs are implemented as shared queue objects provided by the Native Programming Layer (NPL) library. The implementation in C contains the thread local data, queue handles and the routine implementing the specific thread functionality. The latter is a sequential program consisting of plain C computation statements and communication calls (e.g., queue API) provided by the run-time. A read transition is substituted by a pop API call on the respective queue handle. Similarly, a write transition is substituted by a push API call on its respective queue handle.

The glue code implements the deployment of the application to the platform, i.e., allocation of threads to cores and the allocation of data to memories. The glue code is essentially obtained from the mapping. Threads are created and allocated to cores according to the process mapping. Data allocation deals with allocation of the thread stacks and allocation of FIFO queues for communication. In particular, for MPARM deployment, every thread stack is allocated into the L1 memory of the core to which the thread is deployed. Queue handles and queue objects are allocated from the cluster shared L2 memory. All these operations are implemented by using the API provided by the run-time. The code generation flow is illustrated in Figure 7.4. The code generator, as a tool, has been fully integrated into a tool-chain and connected to the BIP system model generation flow. The code is linked with the run-time, hardware dependent library, to produce the binary executable(s) for execution on the platform. The execution results concerning the software applications computational results are used to calibrate the System Model in BIP. However, the overall performance results obtained by the execution on the virtual platform are also used as a means of comparison the performance results obtained by the simulation of the corresponding System model in BIP.

For our experiments, we have used the Native Programming Layer (NPL), a common run-time implemented for both P2012 and MPARM platforms. For P2012, the generated code has been run on virtual platforms available in the P2012 SDK 2011.1, namely GEPOP -the P2012 POSIX-based simulator -and the P2012 TLM simulator. For MPARM, the generated code is compiled by the arm-gcc compiler. The compiled code is linked with the run-time library to produce the binary image for execution on the MPARM virtual simulator.

Discussion

In this chapter, we presented the two methods we use to obtain accurate performance estimation of all C code in the application software. These methods are namely, the Instruction Weight Table and the Platform Dependent Code Generation.

The second method is considered more accurate than the first one, since it utilizes a dedicated virtual platform developed to simulate the functionality of a target hardware platform. The performance analysis results obtained from both methods are given in Chapter 10 and Chapter 11 with the experimentation upon different use cases.

In the next chapter, we present the performance analysis techniques we use to obtain performance results on the complete mixed hardware/software system model.

-Chapter 8 -

Performance Analysis

In this chapter, we focus on the performance analysis model incorporated in our system model generation dedicated to monitor the behavior of the target properties. In the next two sections, we describe the performance model developed in this work and more specifically the timed model in BIP extended with observers and we provide a discussion about performance models in general and the contribution of our own in the domain.

Performance Model

In our BIP design flow, system models are used to integrate the (extra-functional) hardware constraints into the software model according to some chosen deployment mapping. The system model is constructed through a series of transformations from the BIP models of respectively the application software and hardware platform. These two models are composed according to the mapping. The construction has been presented in the previous chapters. The transformations preserve functional properties of the application software model.

The system model is then calibrated by including timing constraints for execution on the chosen platform. These constraints define execution times for elementary functional blocks, that is, BIP transitions within the application software model. More precisely, the system model calibration is done by instrumenting the generated code with API function calls. The API provides cycle accurate estimates for executing a block of code in each processor. As analyzed in the previous chapter, the execution times are measured by two methods: the Instruction Weight Table and the Platform Dependent Code Generation method presented in the previous chapter. The Platform Dependent Code Generation is more accurate than the Instruction Weight Table method, since it utilizes a virtual platform to obtain the results.

The calibrated system model provides analysis of the non-functional properties such as contention for buses and memory accesses, transfer latencies, contention for processors, etc. All system properties are evaluated by simulation of the system model extended with observers. Observers are regular BIP components that sense the state of the system model and collect pertinent information with respect to the properties of interest i.e., the delay for particular data transfers, the blocking time on buses, etc. Actually, we provide a collection of predefined observers allowing to monitor and record specific information for most common non-functional properties. In the current work, we focus on observing the non-functional time properties. For this purpose, the generated system model in BIP is developed to incorporate a performance model equipped with accurate mechanisms to capture time.

The performance model is specifically a timed model in BIP extended with observers. We provide below the formal definition of the timed model which we consider.

Definition ( Timed Composition)

-Timing Model in BIP-We define a Timed Composition T composed by k number of B Components as T = γ H (B 1 , . . . , B k ), where the set of interactions γ H is defined as an hierarchical connector:

γ H = γ 1 ∪ . . . ∪ γ k-1
with, the initial connector γ 1 connected to the two first components such that:

γ 1 = ({B 1 .tick, B 2 .tick}, α 1 , tick) with α 1 = ({B 1 .tick, B 2 .tick}, true, skip)
and the rest of the connectors recursively connected with the first one such that: For all i ∈ [2, k -1] we define:

γ i = ({γ i-1 .tick, B i+1 .tick}, α i , tick) with α i = ({γ i-1 .tick, B i+1 .tick}, true, skip) For all connectors γ i , with i ∈ [1, k -1]
composing the hierarchical connector γ H , the corresponding description in the BIP language is given below.

connector type BroadcastTick(TickPort p 1 , TickPort p 2 ) define p 1 ' p 2 ' on p 1 on p 2 on p 1 p 2 export port TickPort tick end

The connector of type BroadcastTick can be triggered even if only one component is available for interaction.

Considering the γ H as a composite hierarchical connector, we assume that the exporting port of the connector is the exported port of the top-most connector of the hierarchy. Meaning, that the export γ k-1 .tick = γ H .tick.

Example

In Figure 8.1, we illustrate an example of a timed model in BIP. It is a composition of four BIP atomic components B and an hierarchical connector γ H as defined in the Composition Definition 51. Let us assume the Timed Composition as defined in Definition 51. We measure the maximum number of ticks that happened on the system by adding an Observer Component connected to the hierarchical connector.

γ 1 γ 2 γ 3 B 1 B 2 B 3 B 4

Definition ( Timed Composition with Observer)

Given a Timed Composition as defined in Definition 51, we define the Timed Composition with an Observer Component B ob as The connector of type ObserverTick implies strong synchronization between the Timed Model and the Observer Component enabling the latter to sense all ticks taking place. The hierarchy of the initial γ H connector is extended by the added connector γ ob . The latter can be connected further on with other Timed models synthesizing a larger Timed Composition.

T ob = γ(B 1 , . . . , B k , B ob ). γ = γ H ∪

Example

In Figure 8.2, we illustrate an example of a timed model with observer in BIP. We extend the timed model given in Example 19 by adding an observation connector (thick connector) on top of the hierarchical one. The observation connector strongly synchronized the timed model with an Observer Component which senses all ticks taking place.

000 000 000 111 111 111 The sub-model used to capture the computational constraints of the system model is given in Figure 8.3. Assuming a hardware platform with two processors, we connect each processor with a Processor Computational Observer via observation connectors. The latter are synchronized together with BroadcastTick type of connector, which eventually is synchronized with a Global Computational Observer capturing the total computational delay of the system.

γ 1 γ 2 γ 3 B 1 B 2 B ob B 3 B 4 γ ob
A generic Observer Component in BIP is illustrated in Figure 8.4. We provide below the formal definition.

Definition

We define the Observer Component as OB = (L ob , X ob , P ob , T ob ), where:

• L ob = { 1 , 2 , 3 },
• X ob = {count, LOG F ILE},

• P ob = {tick, begin, end},

• T ob = { τ = ( 1 , begin, true, f 1 , 2 ) ,f 1 : count = 0; τ = ( 2 , tick, true, f 2 , 2 ) ,f 2 : count = count + 1; τ = ( 2 , end, true, f 3 , 3 ) ,f 3 : write(LOG F ILE, count); }. count=0; count=count+1;
write(LOG\_FILE, count); The Observer Component has three control locations: the initial 1 , the intermediate observing location 2 and the final 3 location. Transitions begin and end signal the starting and ending observation points of the component. The variable count is responsible for capturing time and is stored in a given LOG FILE at the observation ending point. Transitions begin and end are usually connected to software application components to capture non-functional delay numbers concerning specific software application cycles.

Simulation is performed by using the native BIP simulation tool [bip]. The BIP system model extended with observers is used to produce simulation code that runs on top of the BIP engine, that is, the middleware for execution/simulation of BIP models. The outcome of the simulation with the BIP engine is twofold. First, the information recorded by observers can be used as such to gain insight about the properties of interest. Second, the same information can be used to build much simpler, abstract stochastic models. These models can be further used to compute probabilistic guarantees on properties by using statistical-model checking. This two-phase approach combining simulation and statistical model-checking has been successfully experimented in a different context [BBB + 10]. It is fully scalable and allows (at least partially) overcoming the drawbacks related to simulation-based approaches, that is, the long simulation times and the lack of confidence in the results obtained.

Discussion

In this chapter, we described the performance analysis model developed in the this work. The System Model in BIP is specifically a timed model extended with observers. All system properties are evaluated by simulation and can be further used to evaluate probabilistic guarantees with the help of statistical model-checking. The BIP design flow bridges the gap between simulation based and formal methods by presenting a complete framework based on BIP, which is a formal, rigorous and expressive language, and can be easily used both for native simulation and code generation for simulation on a virtual platform.

Related work focusing in performance analysis include methods based on simulation, trace-based co-simulation of different models, analytical models, analytical models with timed automata and methods that combine simulation and analytical approach. Simulation based methods use ad hoc executable system models such as [START_REF] Kienhuis | An approach for quantitative analysis of application-specific dataflow architectures[END_REF] or tools based on SystemC [START_REF] Moussa | Exploring SW Performance Using SoC Transaction-Level Modeling[END_REF]. The latter provide cycle-accurate results, but in general, they have long simulation time as a major drawback. As such, these tools are not adequate for thorough exploration of hardware platform dynamics, neither for estimating effects on real-life software execution. Alternatives include trace-based co-simulation methods as used in Spade [START_REF] Lieverse | System level design with SPADE: an M-JPEG case study[END_REF], Sesame [START_REF] Erbas | A framework for system-level modeling and simulation of embedded systems architectures[END_REF] or Daedalus [NTS + 08]. Additionally, there exist fast techniques that work on abstract system models such as DOL [START_REF] Thiele | Mapping applications to tiled multiprocessor embedded systems[END_REF], which is based on Real Time Calculus [START_REF] Thiele | Real-time calculus for scheduling hard real-time systems[END_REF], and SymTA/S [START_REF] Henia | System-level performance analysis -the SymTA/S approach[END_REF]. They use formal analytical models representing a system as a network of nodes exchanging streams. They often oversimplify the dynamics of the execution characterized by execution times. Moreover, they allow only estimation of pessimistic worst-case quantities (delays, buffer sizes, etc) and require adequate abstract models of the application software. Building such models entails an additional significant modeling effort. Similar difficulties arise in performance analysis techniques based on Timed-Automata [START_REF] Abdeddaim | Scheduling with Timed Automata[END_REF][START_REF] Ben Salah | Compositional Timing Analysis[END_REF]. These can be used for modeling and solving scheduling problems. An approach combining simulation and analytic models is presented in [START_REF] Künzli | Combining simulation and formal methods for system-level performance analysis[END_REF], where simulation results can be propagated to analytic models and vice versa through adequate interfaces.

In the forthcoming chapters of the document, we present the implementation and experimentation part which describes the whole tool-chain supporting the design flow and provides experimental results in two case studies targeting two different HW platforms.

Part

Implementation and Experimentation <variable value="3" name="N"/> <iterator variable="i" range="N"> <process name="square"> <append function="i"/> <port type="input" name="0"/> <port type="output" name="1"/> <source type="c" location="square.c"/> </process> </iterator> <iterator variable="i" range="N + 1"> <sw_channel type="fifo" size="10" name="F"> <append function="i"/> <port type="input" name="0"/> <port type="output" name="1"/> </sw_channel> </iterator> uniquely associated with the ports of processes. Each connection defines the association between the processes and the sw channels. A special element in the XML specification is the iterator. Its purpose is to iterate on the number of the above XML entities, namely, processes, sw channels and connections. An example of an XML code using iterators is given in Figure 9.2. The variable N is used to bound the iteration number. The corresponding process network is shown in Figure 9 Initially, the DOL2BIP tool flattens the Process Network XML description. The result is an XML file where the iterator element is omitted and all children entities of iterator are instantiated by evaluating the corresponding append elements. The flattened XML file is parsed and the elements are loaded to Java Classes. The tool also parses the Process C Source Code and builds up an AST (Abstract Syntax Tree).

After all the inputs are processed, the tool visits the C code of each process. It detects the function calls and sets the interaction points of each BIP process atomic component. These points are the DOL Write, DOL Read function call. For each one of them, a BIP port is defined. Since the BIP ports are defined the tool completes the BIP process atomic component.

At the next step, according to the process network specification, the tool instantiates each BIP process component, the BIP SW channel components according to the process network specification and creates the connectors between the above. The BIP SW model is now generated.

As we depict in Table 9.1, the DOL2BIP tool along with the C2BIP part consists of 12 Java files and a sum of approximately 5920 lines of code.

BIPWeaver

We present below the algorithm we use in our tool to generate the BIP System Model. The algorithm is divided in five sections.

Firstly, we parse and load the input BIP SW Model into Java classes, the Library of BIP System components, the Architecture XML and the Mapping XML specification. The corresponding XML Schemata are found in the DOL website 3 .

Secondly, we iterate on the Process Atomic Types breaking the atomicity of the DOL Read and DOL Write actions.

Thirdly, we instantiate the Software components. In order to do this, we iterate on each process creating the Process Components. For each port of the Process Components we create the corresponding FIFO Write or FIFO Read Component and we connect the process with them by creating BIP connectors. We complete this step by creating the control connectors between each pair of FIFO Write and FIFO Read Components.

Fourthly, we create the Hardware components based on the Architecture specification. For each cluster specified in the Hardware Architecture, we do the following: For each processor, we create a HW Processor Scheduler Component. Respectively, for each cluster memory we create a Memory Component and then, we create the Network Interface Components. We iterate on the cluster interconnects specified on the architecture XML and we instantiate the cluster interconnect models in BIP in two steps. In the first step, we detect the Memory Components connected to the cluster interconnect. In the second step, we iterate on the processors and for each one of them, we create the corresponding Cluster Interconnect Components, after having checked if the processor uses the current cluster interconnect or not. To complete this step, we create the connectors between the Cluster Interconnect Components, the target Memory Component and the Network Interface Components. After having completed the Cluster Interconnect model, we create a Router Component for each cluster and we connect the Cluster Component via the Network Interface Components with the Router Component. To complete the NoC interconnect model, we create the connectors between the routers based on the specified network topology.

Finally, based on the Mapping XML specification, we create the necessary connectors between the instantiated software and hardware BIP components. Each Process Component is connected to the Processor Component (Processor Scheduler) which is mapped to. Along with the process, the fifo rd and fifo wr associated with the process are also connected to the same Processor Component. To complete the System model, we connect the fifo rd and fifo wr components with the Cluster Interconnect Components which lead to the Memory (local cluster or external cluster memory) which the initial FIFO Components are mapped on.

As depicted in Table 9.1, the BIPWeaver tool consists of 25 Java files summing up 8873 lines of code. The BIP component Library which specifies the System Model Components, the Software Model Components (i.e. FIFO Components) and the Performance Observer Library is described by 4 files in 7200 lines of code. There are also 2 different files of 887 LoC, used for the XML description of HW Platform Architectures.

Weight Table Profiler Tool

In Section 7.1.1, we described the Weight Table Profiling method in details. In this section, we briefly provide the Weight Table Profiler Tool algorithm and the tool's complexity.

Code Generator Tool

As presented in Section 7.1.2, we developed a method for generating code for simulation on a virtual hardware platform. In this section, we describe the tool algorithm we used to implement the tool as given in Algorithm 6. Firstly, we load the SW part of the BIP System Model, the Architecture details and the Mapping information into Java classes. Secondly, we implement every process as a thread and every SW channel as shared queue object of the NPL Library. Finally, the final step, before the generated code is completed, is to allocate the threads to cores and the shared queues to memories. The generated code is described in C language. The tool is implemented in Java and it consists of approximately 12 files and 1744 lines of code, as seen in

Conclusion

In this chapter, we presented the complete tool-flow developed to generate a complete BIP System Model. The flow is completely automated and supported by a set of tools. These tools are the DOL2BIP, the BIPWeaver, the Weight Table Profiler and the Code Generator. DOL2BIP and BIPWeaver construct the BIP SW Model and the initial BIP System Model, respectively. Weight Table Profiler and Code Generator calibrate the System Model with accurate execution delay values of all the C code included in the BIP transitions. Although, these two tools were developed independently, Code Generator and specifically, simulation on the virtual hardware platform, has been proven more accurate in providing execution delay values for the transition blocks of code.

In the next chapters, we present the experimental results obtain with the use of the above tools. We applied the method in two different case studies: the MPARM and the P2012 Platform using a various set of running applications.

In the previous chapter, we described the tools developed to support the complete design flow from the high level software and hardware specifications to fine-grain performance analysis.

In this chapter, we present the MPARM Hardware Platform, the corresponding hardware model in BIP, and a set of software applications considered as case studies to run on the MPARM Platform.

MPARM Hardware Platform

The MPARM [BBB + 05, MPS] platform is a virtual ARM-based multi-cluster manycore platform. It is configured by the number of clusters, the number of ARM cores per cluster, and the interconnect between the clusters. The MPARM simulator allows experimentation with at most four clusters, each with eight ARM7-TDMI processors. The clusters are connected through a 2 × 2 NoC interconnect. The architecture is shown in Figure 10 Inside a cluster, each ARM core is connected with its private DRAM (L1) memory through a local bus. There is also a shared cluster memory SRAM (L2) which is connected with the cores through a AMBA-AHB cross-bar interconnect. Although the MPARM is highly parametrized, we present in Table 10.1, some typical MPARM settings. These features characterize the MRARM processor speed, the memory access delays and the cross-bar interconnect. A part of the description of an MPARM cluster in XML is given in Figure 10.2.

A NoC-based infrastructure is used for inter-cluster communication, which consists of a router, a link, and the network interface (N I) of the individual clusters. In Table 10.2, we describe the characteristics of the NoC which we considered. The data transfer is <cluster name="C1" type="MPARM"> <processor name="P1" type="ARMv7"> <memory name="Private" type="L1"> <configuration name="cycles" value="1"/> </memory> <hw_channel name="local" type="Bus"> </hw_channel> </processor> . . . <processor name="P8" type="ARMv7"> <memory name="Private" type="L1"> <configuration name="cycles" value="1"/> </memory> <hw_channel name="local" type="Bus"> </hw_channel> </processor> <hw_channel name="X-bar" type="CrossBar"> <configuration name="cyclesperbyte" value="1"/> </hw_channel> <memory name="Shared" type="L2"> <configuration name="cyclesperbyte" value="2"/> </memory> </cluster> Figure 10.2: Fragment of the DOL description of an MPARM cluster implemented using packages containing a set of flits in a specific order. There is a header flit with all the routing information, internal flits which carry all the data, and the tail flit which signals the end of a package. Consequently, important features are the packaging delay, the flit size, the router latency, the link latency and the router throughput. The MPARM simulator provides cycle-accurate measurements for the execution of the applications on the virtual platform. This is achieved via generation of low level code as described in Section 7.1.2. The execution times of the SW-Processes are used to calibrate BIP System Models to accurately model computational delays. Henceforth, we will use the term MPARM execution to denote execution on the MPARM virtual simulator.

Another technique, used to obtain cycle-accurate measurements for ARM platforms, is the Weight Table Profiling, described in Section 7.1.1. In order to model ARM7 processors, we utilize the arm-rtems-g++ cross compiler for generation of instruction-level assembly code and the ARM7 data sheet as an operation weight-table guideline.

MPARM Hardware Template Model in BIP

For the hardware model in BIP, we assumed all the local memories as DRAM with an access time of 2 cycles. The shared memory is a SRAM with an access time of 22 cycles. All It is configured using five identical cores and a shared memory, connected via a shared AMBA-AHB cross-bar interconnect.

In Table 10.3, we catalog the MPARM Cluster features used to parametrize the MPARM virtual platform simulator and incorporated in the MPARM System Models in BIP. These features are the CPU frequency, the memory and interconnect access delay and the number of cores per cluster. For the sake of simplicity, we present below a subset of the complete MPARM cluster model.

Example (MPARM Cluster Model in BIP)

Considering the parameters given in Table 10.3, we present an example of an MPARM architecture model of a single MPARM Cluster, configured with eight cores, one shared bus interconnect and one shared memory. Therefore, we firstly instantiate eight abstract components of the processors. These components will be filled with software processes, fifo routines and the processor scheduler, according to the given software application and the mapping specification. The software processes are calibrated, in advance, with accurate execution times with the instrumentation methods presented in Chapter 7. Secondly, we use one Bus Scheduler Component and eight Bus Path Components parametrized with the bus delay to model the Cross-bar interconnect. Lastly, the Bus Path Components are connected to the Shared Memory Component which is parametrized with the memory access delay. We illustrate the above in Figure 10.3.

The NoC parameters considered in both MPARM and P2012 platform models in BIP are given in Table 10.4. They characterize the packaging delay, the router and link delay, and the number of clusters and routers (network nodes).

In Figure 10. 100K lines of C code. The method used for calibrating the System model was the Weight Table Profiling, described in Section 7.1.1. The total computation and communication delays for decoding 5 frames for different mappings are shown in Figure 10.6. The MPEG-2 process network is characterized as computationally intensive. The more we distribute the computational load to different CPUs, the smaller is the computational delay. Since the FIFOs are few, there is small difference in the communication delays between the different mappings, except for mapping (1) where all processes and FIFOs are mapped on a single core. However, as we distribute the processes into more cores, the communication delay increases and more bus conflicts occur.

Regarding the overall performance, we observe that Mapping (2) results into the worst frame throughput due to high computational and communication delays. Although in mapping (4) we use more CPUs than mapping (3), the overall performance decreased due to higher occurrence of communication conflicts, as illustrated in Figure 10.7. The best throughput is achieved in Mapping (7) due to the usage of five CPUs and their local memories.

MJPEG Application on MPARM

The MJPEG decoder application software reads a sequence of JPEG frames and displays the decompressed video frames. The process network of the application software is shown To experiment on this case study we calibrated the BIP System model using both profiling methods described in Chapter 7. We quote the results below.

Weight Table Profiling

We analyzed the effect of eight different mappings on the total computation and communication delay for decoding a frame. The process and the FIFO mappings are illustrated on Table 10.8.

The total computation and communication delays for decoding a frame for different mappings are shown in Figure 10.9. Mapping (1) produces the worst computation delay as all processes are mapped to a single processor. Mapping (2) uses two processors, but still the performance does not improve much. Mapping (3) drastically improves performance as the computation load is balanced. The other mappings cannot further enhance performance as the load cannot be further balanced, even if more processors are used. The communication overhead is reduced if we map more FIFOs to the local memories of the processors. The bus and memory access conflicts are shown in Figure 10.9. As more FIFOs are mapped to the local memory, the shared bus contention is reduced. However, this might increase the local memory contention, as shown for (8). Memory conflict (cycles)

.9: Mjpeg Performance Analysis Results

Platform-Dependent Code Generation Profiling

The implementation generated for MPARM execution is approximately 3174 lines of code.

For the experiments, we mapped the application on a single MPARM cluster. Each computational process is deployed into an ARM processor and all the FIFO buffers are allocated to the L2 shared memory. The performance results per process obtained by simulation of the system model are depicted in Figure 10.10. We remark that process IqzigzagIDCT is the heaviest in terms of computation, while process MergeStream stays idle most of the time. The low values of memory conflicts highlights the restricted parallelism within the application.

At system level, we measured the total execution time needed for the decompression of a single frame. Using BIP system model simulation, this time is estimated at 472.88 Mcycles. This result is very near to the cycle-accurate value obtained by measuring the MPARM execution, which is 468.83 Mcycles. The relative error of our estimation is therefore less than 0.87%. Regarding analysis time, BIP system model simulation outperforms execution on (virtual) MPARM. The former completes in 9 46 and is approximately 5.2 times faster than the second, which completes in 50 48 . The above numbers are given in Table 10.9. Notably, BIP System Model calibration using Platform-Dependent Code Generation is time consuming, since it based on the MPARM execution on the virtual platform to obtain accurate execution time delays of the SW-processes. However, since the derived execution time delays involve pure computation parts of the processes and considering that the virtual platform is configured with each process running on an independent CPU, we assume that the calibration numbers remain the same for each mapping. Based on these numbers, we apply a set of various mappings to analyze, through BIP simulation, the performance of the System nodes on each case.

Fast Fourier Transform (FFT) Application on MPARM

A Fast Fourier transform (FFT) is an efficient algorithm to compute the Discrete Fourier transform (DFT) and its inverse. A DFT decomposes a sequence of values into components of different frequencies. This operation is useful in many fields but computing it directly from the definition is often too slow to be practical. An FFT is a way to compute the same result more quickly. The process network of the application software is shown in Figure 10.11. It contains a Generator and a Consumer process and twelve intermediate FFT processes aligned in a 3 × 4 matrix. The number of FIFO channels are 32. The process network is described in DOL using approximately 1616 lines of code.

As target platform we considered the complete MPARM platform, configured with four cluster and a NoC infrastructure. The generated System Model in BIP contains 168 atomic components, 706 interactions, and consists of approximately 9641 lines of BIP code. The above implementation characteristics are depicted in Table 10.10. The calibration method used for the System Model was the Platform Dependent Code Generation. We catalog the execution times of the SW-processes in Table 10.11. The code generated for the MPARM execution on the virtual platform is around 3986 LoC.

We analyzed the effect of five different mappings illustrated in Figure 10.12. Each process is mapped on an individual CPU located in different clusters and each FIFO is mapped on a L2 cluster memory. More specifically, each FIFO is mapped on the same cluster which the process reading from the FIFO is mapped on.

The performance results per process obtained by simulation of the system model are depicted in Figure 10.13. The high communication and idle time delays observed at the fft 2 2 0, fft 2 2 1, fft 2 2 0 and fft 2 2 2 processes are due to the blocking read operations, which particularly for these processes are the most time-consuming since data are not immediately available. Figure 10.14 illustrates the total communication delays per mapping,

Demosaicing Algorithm Application on MPARM

Demosaicing algorithm is a digital image processing algorithm used to reconstruct a full color image from the incomplete color samples output from an image sensor, overlaid with a color filter array (CFA). More specifically, the algorithm generates YUV components by transformations on the initial raw image.

Demosaicing application works on 5 × 5 matrices.The resulting pixels are the resulting averages of centered points of each matrix, which results to the loss of four lines and four columns of the initial image.

The process network of the application software is shown in Figure 10.15. It contains a Splitter and a Joiner process, a pre-demosaicing (Demo pre) and a post-demosaicing The number of FIFO channels are 28. The process network is described in DOL using approximately 1672 lines of code.

As target platform we considered the complete MPARM platform, configured with four cluster and a NoC infrastructure. The generated System Model in BIP contains 152 atomic components, 614 interactions, and consists of approximately 15366 lines of BIP code. The above implementation characteristics are depicted in Table 10.12. The calibration method used for the System Model was the Platform Dependent Code Generation. We catalog the execution times of the SW-processes in Table 10.13. The code generated for the MPARM execution on the virtual platform is around 3986 LoC. We analyzed the effect of three different mappings illustrated in Figure 10.16. Each process is mapped on an individual CPU located in different clusters and each FIFO is mapped on a L2 cluster memory. More specifically, each FIFO is mapped on the same cluster which the process reading from the FIFO is mapped on. The performance results per process obtained by simulation of the system model are depicted in Figure 10.17. The high communication and idle time delays observed at the Demo 00 and Demo 05 processes are due to the blocking write operations, which particularly for these processes are the most time-consuming. This is observed because the Demo 00 and Demo 05 processes complete their computations quicker than the other processes (see Table 10.13) and by the time they start writing the results to the Demo post process they are conflicting with the read operations of the rest processes These read operations are longer because they involve greater amount of data. Figure 10.18 illustrates the total communication delays per mapping, highlighting mapping 1 as the one with the lowest communication overhead. Mapping 1 is the only one with all the processes spread onto all four available cluster resulting to greater communication delays. In terms of total execution time, all mappings result at almost same value due to the significantly higher computation delay of the Splitter, Joiner and the pre and post demosaicing processes compared to the six internal demosaicing processes.

: A = L • L T , L lower triangular for k = 1 to B do L kk := seq-cholesky(A kk ) L -T kk := invert(transpose(L kk )) for i = k + 1 to B do L ik := A ik • L -T kk end for for j = k + 1 to B do L T jk := transpose(L jk ) for i = j to B do A ij := A ij -L ik • L T jk
end for end for end for solving L T x = y for x.

The sequential Cholesky factorization algorithm has computational complexity O(N 3 ) for matrices of size N × N . In this paper, our starting point is the sequential rightlooking block-based version [START_REF] O'leary | Data-flow algorithms for parallel matrix computation[END_REF] provided as algorithm 7 which provides immediate support for parallelization. In this algorithm, B denotes the number of blocks composing the original matrix A, that is A = (A ij ) 1≤j≤i≤B and every A ij is a block matrix of size K = N/B. The algorithm computes the matrix L, block by block, such that A = L • L T . Algorithm 7 is easily parallelizable by separating computations related to different ijblocks on different processes P ij . Nevertheless, interactions between these processes are highly non-trivial. There are complex patterns for data dependencies, as illustrated in Figure 10.19 for the cases B = 2, 3, 4. Moreover, the amount of computation carried by each process is different. That is, as factorization proceeds, processes with higher indexes (i, j) become computationally more intensive. Furthermore, both data dependencies and the local amount of computation are tightly related to the decomposition size B as well as to the block size K. Altogether, finding optimal implementation on multi-processor platforms with fixed communication and computation resources is a non-trivial problem. For every B, we denote by Cholesky(B) the Cholesky factorization using a B × B block decomposition. For our experiments, we implemented three versions in DOL, for respectively B = 2, 3, 4. In all cases, the process networks contain a Splitter process, a Joiner process and the computational processes for each block (P ij ) 1≤j≤i≤B . Process Splitter splits the initial A matrix into blocks and dispatches them to computational processes. Every process P ij implements the computation required on its corresponding matrix blocks A ij and L ij . As an example, the computational processes for Cholesky(4) are P 11 , P 21 , P 22 , P 31 . . . P 44 as shown in Figure 10.19. The final L matrix is re-constructed by the Joiner process. Explicit communication between P ij processes is used to enforce data dependencies. In these models, a dedicated FIFO is used for every pair of dependent processes to transfer the result block from the source to the target process. In the MPARM implementation, each computational process is deployed into an ARM processor and all the FIFO buffers are allocated to the L2 shared memory. It is to be noted that for B = 2, 3 the implementation fits into a single cluster, and for B = 4, two clusters have been used. The magnitude of the different representations produced along the BIP design flow (number of processes, FIFOs, components, interactions, lines of code) is depicted in Table 10.14. The calibration method used for the System Model was the Platform Dependent Code Generation. For every B = 2, 3, 4, we evaluate Cholesky(B) on 60 × 60 input matrices of double precision floating point numbers. Therefore, computational processes operate on matrix blocks of size 30 × 30, 20 × 20 and 15 × 15 for respectively B = 2, 3, 4. During the calibration phase, each computational routine on matrix blocks is characterized by the number of cycles required to execute it on an ARM processor. This is done by running the generated application code on MPARM and by accurate measurement of the number of cycles, for each routine. Table 10.15 reports the worst case execution times for different size of matrix blocks.

Table 10.16 presents an overview of the system-level performance analysis results obtained using two methods, respectively simulation of the system model vs. implementation and measurement of code execution on the MPARM platform. For both methods, we report the total execution time taken by the application to run on the platform and the analysis time, that is, the time taken by the methods to produce the results. We point out that simulation of BIP system models produces fairly accurate results (max 20.95% relative error with respect to the cycle-accurate MPARM execution) while significantly reducing the analysis time (up to 19 times, in some situations). Note that for B = 4, the MPARM simulation did not terminate in 72 hours and the simulation data is unavailable. However, an estimate is obtained from the BIP system model simulation. A higher cycle count reflects the communication overhead due to the presence of two clusters with the NoC interconnect.

Finally, Figure 10.20 presents a detailed view of execution times and communication delays for computational processes for Cholesky(4). For each process, the idle time denotes the waiting time spent before it gets access to read or write on FIFO channels. The communication time denotes the time effectively spent on reading or writing. The computation time denotes the total execution time without the idle and the communication Table 10.15: Execution times for computational routines on matrix blocks (in 10 6 cycles) time. The Figure 10.20 (left) confirms that processes with higher indexes (i, j) are indeed computationally more intensive than the others. Additionally, the same processes are also idle for longer time than the others. This happens because of an increased number of data dependencies from processes with lower indexes (i, j). Communication time is impacted by memory conflicts. Memory conflicts occur when two different processes try to access simultaneously FIFO buffers located in the same shared memory. Figure 10.20 (right) depicts the delays due to memory conflicts for each process.

B = 2 B = 3 B = 4 K = 30 K = 20 K =

Discussion

In this chapter, we presented the MPARM Hardware Platform, the corresponding hardware model in BIP, and a set of software applications considered as case studies to run on the MPARM Platform. The software applications were the MPEG-2 and the MJPEG decoders, the Fast Fourier Transform (FFT), the Demosaicing Algorithm and the Cholesky Decomposition. For each case study, we created mixed hardware/software System Models of the MPARM platform and the corresponding software application, based on different mappings. Both profiling methods were used to calibrate the System Models, as presented in Chapter 7. For the MPEG2, we used the Weight Table Profiling method. For MJPEG, we used both the Weight Table Profiling and the Platform Dependent Code Generation. For the rest, FFT, Demosaicing and Cholesky we calibrated the System Models using only the Platform Dependent Code Generation , since it is considered to provide more accurate execution times of the software processes. Both profiling methods are time consuming. However, they are applied once for every case study and the results are re-used for all mapping configurations.

The experiments show the capability of the BIP design flow for fine grain performance analysis on manycore platforms. It also shows the speedup compared to simulation based techniques, without adversely affecting the accuracy of the measurements.

-Chapter 11 -

Case Study on P2012 Hardware Platform

In the previous chapter, we experimented with the MPARM Hardware platform and a series of software applications as case studies.

In this chapter, we present the Platform 2012 Hardware Platform, the corresponding hardware model in BIP, and a software applications considered as case study to run on the Platform 2012 Hardware Platform.

P2012 Hardware Platform

Platform 2012 (P2012) [START_REF] Stmicroeletronics | Platform 2012: A many-core programmable accelerator for ultra-efficient embedded computing in nanometer technology[END_REF] is an area and power efficient manycore computing fabric, jointly developed by STMicroelectronics and CEA. The P2012 computing fabric is highly modular, as it is based on multiple clusters implemented with independent power and clock domains, enabling aggressive fine-grained power, reliability and variability management. Clusters are connected via a high-performance fully-asynchronous network-on-chip (NoC), which provides scalable bandwidth, power efficiency and robust communication across different power and clock domains. Each cluster features up to 16 tightly-coupled processors sharing multi-banked level-1 instruction and data memories, a multi-channel advanced DMA engine, and specialized hardware for synchronization and scheduling acceleration. P2012 achieve extreme area and energy efficiency by aggressive exploitation of domain-specific acceleration at the processor and cluster level. In the scope of this case study, each processor has been specialized with modular extensions dedicated to floatingpoint unit computation. Other extension such as vector units or other special-purpose instructions may also be chosen at design-time.

P2012 is based on a modular infrastructure as depicted in Figure 11.1. Fabric-level communication is based on an asynchronous NoC organized in a 2D mesh structure. The routers of this NoC are implemented in a Quasi-Delay-Insensitive (QDI) asynchronous (clock-less) logic. They provide a natural Globally Asynchronous Locally Synchronous (GALS) scheme isolating the clusters logically and electrically. The number of clusters is a parameter of the fabric. A configuration up to 32 clusters is supported in the current implementation. The exact type of NoC is used for the MPARM Platform, described in Chapter 10, where a set of important NoC features are given in Figure 10.2.

One significant characteristic of the fabric is that all local storage at the cluster level is visible in a global memory map, which also includes memory-mapped peripherals. In this non-uniform memory architecture (NUMA), remote memories (off-cluster or off-fabric) are expensive to access. For this reason, DMA engines are available for hardware-accelerated A P2012 cluster (Figure 11.2) aggregates a multicore computing engine, called Encore and a cluster controller. The Encore cluster includes a number of processing elements (PEs) varying from 1 to 16. Each PE is built with a highly configurable and extensible processor called STxP70-v4. It is a cost effective and customizable 32-bit RISC core supported by comprehensive state-of-art toolset. The Encore 16 PEs do not have private data caches or memories, therefore avoiding memory coherency overhead. Instead, the PEs can directly access a L1-shared program cache (P$) and a L1-shared Tightly Coupled Data Memory (TCDM). Each core therefore has two 64 bit-ports to the shared memories, a read-only instruction port and a read/write data port. The P$ cache is a 256 KB, 64bank, direct mapped cache memory while the TCDM is a 256-KB, 32-bank memory. The P$ and the TCDM have been architected with a banking factor of 4 and 2, respectively. The P$ can therefore support a throughput of one instruction fetch per PE on each clock cycle. Encore provides run-time acceleration by the means of the Hardware Synchronizer (HWS). Various synchronization primitives such as semaphores, mutexes, barriers, joins, etc. can be implemented using accelerated support of the HWS.

A logarithmic interconnect is used to access the TCDM memory. Data are forwarded using routing and arbitration techniques. Based on address decoding, the requested address may correspond to the intra-cluster, multi-banked memory or the off-cluster NoC environment. In case of simultaneous accesses in contiguous data, reduced memory conflicts are observed due to fine-grained address interleaving. The crossing latency of the interconnect consists of one clock cycle. In case of multiple conflicting requests, for fair access to memory banks, a roundrobin scheduler arbitrates access and a higher number of cycles is needed depending on the number of conflicting requests, with no latency in between. In case of no banking conflicts data routing is done in parallel for each core, thus enabling a sustainable full bandwidth for processors-memories communication. To reduce memory access time and increase shared memory throughput, read broadcast has been implemented and no extra cycles are needed when broadcast occurs.

A multi-ported, multi-banked, Tightly Coupled Data Memory (TCDM) is directly connected to the logarithmic interconnect. The number of memory ports is equal to the number of banks to have concurrent access to different memory locations. Once a read or write requests is brought to the memory interface, the data is available on the negative edge of the same clock cycle, leading to two clock cycles latency for conflict-free TCDM access. If conflicts occur there is no extra latency between pending requests, once a given bank is active, it responds with no wait cycles.

The cluster controller (CC) consists of a cluster processor subsystem, a DMA subsystem, a CC interconnect and several interfaces: one to the Encore 16 PEs and one to the asynchronous NoC. The cluster processor is designed around a STxP70-V4 dual-issue core without extension and with 16-KB P$ and 16-KB of local memory.

The Platform 2012 Development Kit provides support for several platform programming models (PPM). Standards-based programming models are based on industry standards that can be implemented effectively on P2012. The supported standards are OpenMP and OpenCL. Another supported PPM is called Native Programming Layer (NPL). NPL is an API which is closely coupled with the platform capabilities. It allows the highest level of control on application to resource mapping at the expense of abstraction and platform independence.

The P2012 SDK also features platform models for the execution and the simulation of applications running on the P2012 platform. For the scope of this paper, we used a mono-cluster simulator of the fabric and an Encore engine featuring 16 PEs. We targeted the NPL for fine-tuned control of the deployment of the application on the platform, and to achieve better performance.

Platform 2012 Hardware Template Model in BIP

In this section, we provide the P2012 architecture model in BIP, along with all the parameters which characterize the model.

The NoC model parameters are the same as those used for the MPARM NoC model presented in Table 10.4. The P2012 Cluster parameters, given in Table 11.1, specify the Logarithmic Interconnect Access Delay and the TCDM access delay, considering zero conflicts. Notably, the above parameters characterize the communication part of the P2012 Cluster. As for the computation part, the execution times which profile each software process of the given application is obtained via simulation on the P2012 Platform simulator based on the method described in Section 7.1.2. In Figure 11.4, we illustrate the complete P2012 Cluster model in BIP. There are eight cores (PEs), given as template components, which will be filled with the Processor Scheduler Components, the software processes and the FIFO routines, based on the given mapping. For the modeling of the logarithmic interconnect, there are eight Bus Interface Components, each one per core, parametrized by the processor ID and the number of memory banks. They are connected via a set of guarded connectors with all the Memory Bank Components of the TCDM memory and the Network Interface Components. The Memory Bank Components are parametrized by the memory bank ID and the communication access delays, namely, the interconnect access delay and the multi-banked memory access delay. Moreover, the Network Interface Components are parametrized by the packaging delay, the number of memory banks and the cluster ID.

HMAX application on P2012

HMAX is a powerful computational model of object recognition [START_REF] Riesenhuber | Hierarchical models of object recognition in cortex[END_REF] which attempts to model the rapid object recognition of human brain. Hierarchical approaches to generic object recognition have become increasingly popular over the years [SWP05, ML08], they indeed have been shown to consistently outperform flat single-template (holistic) object recognition systems on a variety of object recognition task. Recognition typically involves the computation of a set of target features at one step, and their combination in the next step. A combination of target features at one step is called a layer, and can be modeled by a 3D array of units which collectively represent the activity of set of features (F) at a given location in a 2D input grid. HMAX starts with an image layer of gray scale pixels (a single feature layer) and successively computes higher layers, alternating (S) and (C) layers:

• Simple (S) layers apply local filters that compute higher-order features by combining different types of units in the previous layer.

• Complex (C) layers increase invariance by pooling units of the same type in the previous layer over limited ranges. At the same time, the number of units is reduced by subsampling.

In our case study experiment, we only considered the two first layers of the HMAX model algorithm. In a pre-processing phase, the input raw image is converted to gray We restrict ourselves to the S1 layer of the HMAX models algorithm. The process network in DOL consists of 14 processes and 24 FIFO channels. This DOL model is about 700 lines of XML (defining the process network structure) and 1500 lines of C (defining the process behavior). The software model in BIP is constructed automatically from the DOL model. It consists of 38 atomic components interconnected using 48 connectors. The BIP software model is about 2000 lines of BIP code. The system model obtained by deploying the S1 layer on a single P2012 cluster consists of 125 atomic components interconnected using about 1500 connectors. The total BIP description totalizes about 13000 lines of BIP code. This description is compiled into about 50000 lines of C++ code, used for simulation and performance analysis.

The execution time of 2D-Gabor filters on P2012 PEs ranges from 220 • 10 6 to 0.68 • 10 6 cycles, depending on the size of the input image (ranging from 100 × 100 to 15 × 15 pixels). By using these values in the system model, the total execution time of the S1 layer is estimated as 225 • 10 6 cycles. This overall execution time is negatively impacted by the long access time (i.e., about 100 cycles) to the L3 memory (where all FIFOs are mapped) as well as by the bus contention. A slightly better result is obtained if the FIFOs are all mapped into the TCDM memory. In this case, the memory access time is about 1 cycle and there is no more contention. The total execution time reduces to about 220 • 10 6 cycles. However, such a mapping is not feasible due to memory size constraints, that is, FIFOs cannot fit all simultaneously within the TCDM memory.

Conclusion

In this chapter, we presented the P2012 Hardware Platform, the corresponding hardware model in BIP, and the HMAX software application to run on the MPARM Platform. We created mixed hardware/software System Model of the P2012 platform and the HMAX software application, based on different mappings. The Platform Dependent Code Generation method was used to calibrate the System Models, as presented in Chapter 7.

-Chapter 12 -

Conclusion and Perspectives

Introductive We developed a rigorous and automated design flow for generating a model which faithfully represents the behavior of a mixed hardware/software system from a model of its application software and a model of its underlying hardware architecture. The presented method allows generation of a correct-by-construction system model for manycore platforms from an application software and a mapping. The method is based on source-to-source correct-by-construction transformation of BIP models. It is completely automated and supported by the BIP toolset.

Method Firstly, we generate the application software model in BIP. This is achieved by an automatic translation of the input application software model which should be described in a process network with a well defined structure. The translation preserves intact the behavior and the characteristics of the initial application software.

Secondly, we model the hardware architecture in BIP. A library of BIP atomic components that characterize multi-processor architectures is defined. Combining the hardware architecture specifications and the BIP library components, we synthesize the hardware architecture model in BIP.

Thirdly, we construct the mixed software/hardware system model. This model represents the behavior of the application software running on the hardware architecture according to the mapping, but without taking into account execution times for the software actions. This step consists in progressively enriching the application software model by doing:

• Application of a sequence of source-to-source transformations to synthesize hardware dependent software routines implementing communication by using the hardware components.

• Integration of hardware components used in the system model.

The transformations are proved correct-by-construction, that is, they preserve functional properties of the application software.

Finally, the (bounds for) execution times are obtained by analysis or simulation of the run of every software process in isolation on the platform. These bounds are injected into the system model and lead to the calibrated system model.

Method Advantages and Comments

The above method sticks to the general principles of rigorous design as described in Chapter 1. Namely, it is model-based, componentbased, correct-by-construction and tool-supported.

The construction of the system model is incremental and structure-preserving. This ensures scalability as the complexity of system models increases polynomially with the size of the application software and of the target hardware architecture. Mastering system model complexity is achieved thanks to the expressiveness of the BIP modeling framework. All properties established for the initial model will hold for all the models obtained by transformations. The transformations are correct-by-construction, that is, they are proven to preserve a trace equivalence between the initial and the transformed model. The complexity of the transformations is linear with the size of the transformed models. So, correctness is ensured at minimal cost and by construction, thus overcoming obstacles of design flows involving different and not semantically related languages and models.

The method clearly separates software and hardware design issues. It is also parametrized and allows flexible integration of design choices related to resource management such as scheduling policies, memory size and execution times, etc. This allows estimation of the impact of each parameter on system behavior.

We have defined a library of BIP atomic components that characterize manycore architectures, including models for hardware components (e.g., processor, memory) and for hardware-dependent software components (e.g., FIFO channel read/write, bus controllers, schedulers).

Using BIP as a unifying modeling formalism for both hardware and software confers multiple advantages, in particular rigorousness. The obtained system models are correctby-construction. This is a main difference from other ad hoc model construction techniques. The use of a single modeling framework allows to maintain the overall coherency of the design flow by comparing different architectural solutions and their properties. This is a significant advantage of our approach. Semantically related models are used for verification, simulation and performance evaluation. Designers use many different languages e.g. programming languages, UML, SystemC, SES/Workbench. Code generation and deployment is often independent from validation and evaluation.

Toolset The method has been implemented and integrated in the BIP toolset. We used the DOL framework [START_REF] Thiele | Mapping applications to tiled multiprocessor embedded systems[END_REF] as a frontend to describe the application software, hardware architectures and mapping specifications. The backend of the tool produces the system model in BIP, which can be analyzed by the BIP tool chain for:

• Code generation for simulation/validation on a Linux PC.

• Code generation for simulation/validation on two Virtual Platforms, the MPARM and the P2012.

• Functional correctness using the D-Finder tool, checking for deadlocks.

• Performance analysis (e.g. delay computation) and design space exploration, based on simulation and statistical model checking.

Experimentation and Case Studies Experimental results show the feasibility of the system model for fine granular analysis of the effects of architecture and mapping constraints on the system behavior. The final model allows accurate estimation through simulation of real-time characteristics (response times, delays, latencies, throughput, etc.) and indicators regarding resource usage (bus conflicts, memory conflicts, etc.). The method is tractable and allows design space exploration to determine optimal solutions. We have experimented on two case studies, the MPARM and the P2012/STHORM Hardware Platform. We presented the MPARM hardware model in BIP, and a set of software applications to run on the MPARM Platform. The software applications were the MPEG-2 and the MJPEG decoders, the Fast Fourier Transform (FFT), the Demosaicing Algorithm and the Cholesky Decomposition. For each software application, we created mixed hardware/software System Models of the MPARM platform and the corresponding software application, based on different mappings. Both profiling methods were used to calibrate the System Models, as presented in Chapter 7.

The experiments show the capability of the BIP design flow for fine grain performance analysis on manycore platforms. It also shows the speedup compared to simulation based techniques, without adversely affecting the accuracy of the measurements.

Perspectives

Future work includes more experiments based on the P2012 hardware platform. In addition, formal verification using D-Finder could be applied at the level of software application model in BIP described as KPN process networks.

An other extension should be to explore different programming models for the application software and richer hardware architecture models that include DMA (Direct Memory Access) Controller, Bus Bridge, Network on Chip communication and three dimensional architectures.

Except from timing constraints, thermal values, power consumption and dynamic scheduling policies should be considered. The latter properties of the hardware model should enrich the current models of hardware components attributing to an extensive performance analysis of our target system.

Moreover, we plan to include statistical model checking on the generated system models consisting of multiple applications running on complex multicore architectures for performance analysis, as in [BBB + 10].

Finally, important part of the future extension of this work would be to consider task migration and dynamic mapping. Task migration protocol should be aware of all critical performance metrics of the system leading to optimal mapping obtained on-the-fly.

Figure 1 . 1 :

 11 Figure 1.1: Simplified View of a System Design

Figure 1 . 2 :

 12 Figure 1.2: System Model Design Flow

Figure 1 . 3 :

 13 Figure 1.3: Software Application -Hardware Platform mapping of a System Design

Figure 2 . 2 :

 22 Figure 2.2: Sender (left) and Receiver (right) BIP atomic components

  Definition (Composite Component: Syntax) A composite component is defined by a set of atomic components, composed by a set of interactions γ and a priority π ⊆ γ × γ. We denote by B def = πγ(B 1 , ..., B n ) the component obtained by composing components B 1 , ..., B n using the interactions γ and priority π. If π is the empty relation, then we may omit π and simply write γ(B 1 , • • • , B n ).

Figure 2 . 3 :

 23 Figure 2.3: Sender/Buffer/Receiver model as a composition of BIP atomic components

Figure 2 . 4 :

 24 Figure 2.4: The BIP Tool-Chain.

Figure 2 . 5 :

 25 Figure 2.5: Send/Receive BIP model obtained from BIP to BIP transformations.

Figure 3 . 1 :

 31 Figure 3.1: Translation method for a language in BIP

Figure 3 . 2 :

 32 Figure 3.2: Models of the Producer and Consumer Components in BIP

Figure 3 . 3 :

 33 Figure 3.3: Model of FIFO channel in BIP

Figure 3 . 4 : 3

 343 Figure 3.4: Producer-Consumer Composition in BIP

Figure 3 . 5 :

 35 Figure 3.5: Cholesky application in DOL

Figure 3 . 6 :

 36 Figure 3.6: Fragment of the DOL description of the Cholesksy process network

. 7 .Figure 3 . 7 :

 737 Figure 3.7: C code for the P 22 process

11 Example Figure 3 . 8 2 Figure 3 . 8 :

 1138238 Figure 3.8: C code and the corresponding BIP model of P 22 process

12 Example 1 F 4 F 2 F 3 F 5 F 6 F 7 P 21 Figure 3 . 9 :

 1214235672139 Figure 3.9: Cholesky(2) application software model in BIP

  Figure 4.1 illustrates an example of a crossbar switch interconnecting PEs with a shared memory.

  Figure 4.2 shows an example of a multiplexing interconnect attached to a multi-bank memory.

Figure 4 . 3 :

 43 Figure 4.3: NoC Description

  HW-Platform ::= HW-Resource + . HW-Comm-Path + HW-Resource ::= HW-Processor | HW-Memory | HW-Cluster-InterConnect | HW-NI | HW-Router HW-Comm-Path ::= HW-Processor . HW-InterConnect . HW-Memory HW-InterConnect ::= HW-Cluster-InterConnect | HW-Cluster-InterConnect . HW-NI . HW-Router + .

Figure 4 . 4 :

 44 Figure 4.4: Processor Abstract Model in BIP

Figure 4 . 5 :

 45 Figure 4.5: Processor Scheduler Component in BIP

  , 4.15. The above Processor model described in BIP, does not include pipeline model, instruction and data caches or DMAs. We chose not to provide a detailed model of the Processor, so that we avoid explosion in the complexity, the size of the model and the simulation time.

Figure 4 . 6 :

 46 Figure 4.6: Crossbar Switch BUS Model in BIP

Figure 4 . 7 :Figure 4 . 8 :

 4748 Figure 4.7: Bus Scheduler Component in BIP

Figure 4 . 9 :

 49 Figure 4.9: Memory Component in BIP

Figure 4 . 10 :

 410 Figure 4.10: BIP model of a HW platform with four processors and one shared memory

Figure 4 . 11 :

 411 Figure 4.11: Multiplexing Interconnect Model in BIP

Figure 4 . 12 :

 412 Figure 4.12: Bus Interface Component in BIP

Figure 4 .

 4 Figure 4.14: Memory Bank Component in BIP

  25 Definition (Multi-Banked Memory Cluster Compound Component) We define the Multi-Banked Memory Cluster Compound Component as M C = πγ(BU S, M ) as the Communication Model of a Cluster, where: BU S = {BI 1 , . . . BI k }, where k the number of processors, BI the Bus Processor Interfaces M = {M B 1 , . . . , M B l } the Multi-Banked Memory Component, where l the number of memory banks. The set of interactions γ is defined as: γ = {γ BI |BI ∈ BU S} ∪ {α tick }, where, γ BI = {α m b , α m e |M B ∈ M }, α m b = ({BI.req send mb, M B.op b }, g, f ), with g : [BI.mem id == M B.mem id], f : M B.proc id = BI.proc id; ) α m e = ({M B.op e , BI.ack rec}, g, skip), with g : [M B.proc id == BI.proc id] α tick = ({BI 1 .tick, . . . , BI k .tick, M B 1 .tick, . . . , BI l }, true, skip).

Figure 4 . 18 :

 418 Figure 4.18: Network Interface Incoming Controller Component in BIP

28

  Definition (Shared Memory Cluster Compound Component with a Network Interface) We define the Shared Memory Cluster Compound Component as CL SM = πγ(BU S, M, N I) as the Communication Model of a Cluster, where: BU S = {BP 1 , . . . BP k+k+1 , BS}, where k the number of processors, BP the Bus Paths and BS the Bus Scheduler. N I = {OG, IC}. M the Memory Component. The set of interactions γ is defined as: γ = {α acq , α rel |BP ∈ BU S} ∪ {α m b , α m e |BP ∈ {BP 1 . . . BP k+1 }}∪ {α out b , α out e |BP ∈ {BP k . . . BP k+k }} ∪ {α in b , α in e , α inf o , α tick }, with, α acq = ({BP.acq, BS.acq}, true, skip), α rel = ({BP.rel, BS.rel}, true, skip), α m b = ({BP.op b , M.op b }, true, skip), α m e = ({M.op e , BP.op e }, true, skip), α out b = ({BP.op b , OG.req}, true, skip), α out e = ({IC.ack proc, BP.op e }, [IC.proc id == BP.proc id], skip), α in b = ({IC.req mem, BP.req}, true, skip), α in e = ({BP.ack, OG.ack}, true, skip), α inf o = ({IC.inf o, OG.inf o}, true, skip), α tick = ({BS.tick, BP 1 .tick, . . . , BP k+k+1 .tick, M.tick}, true, skip).

  29 Definition (Multi-Banked Memory Cluster Compound Component with a Network Interface) We define the Multi-Banked Memory Cluster Compound Component as CL M B = πγ(BU S, M, N I) as the Communication Model of a Cluster, where: BU S = {BI 1 , . . . BI k }, where k the number of processors, BI the BUS Processor Interfaces, M = {M B 1 , . . . , M B l } the Multi-Banked Memory Component, where l the number of memory banks, N I = {OG, IC} the network interface. The set of interactions γ is defined as: γ = {γ BI |BI ∈ BU S} ∪ {α out b , α out e |BI ∈ BU S} ∪ {α in b , α in e |M B ∈ M } ∪ {α inf o } ∪ {α tick }, where, γ BI = {α m b , α m e |M B ∈ M }, α m b = ({BI.req send mb, M B.op b }, g, f ), g : [BI.mem id == M B.mem id], f : M B.proc id = BI.proc id;, α m e = ({M B.op e , BI.ack rec}, g, skip), g : [M B.proc id == BI.proc id], α out b = ({BI.req send og, OG.req}, true, f ), f : OG.proc id = BI.proc id; OG.dest id = BI.dest id;, α out e = ({IC.ack proc, BI.ack rec}, g, skip), g : [IC.proc id == BI.proc id], α in b = ({IC.req mem, M B.op b }, g, f ), g : [IC.mem id == M B.mem id], f : M B.proc id = IC.ni id;, α in e = ({M B.op end, OG.ack}, g, skip), g : [M B.proc id == OG.ni id], α inf o = ({IC.inf o, OG.inf o}, true, skip), α tick = ({BI 1 .tick, . . . , BI k .tick, M B 1 .tick, . . . , BI l , IC.tick, OG.tick}, true, skip).

Figure 4 .Figure 4 .

 44 Figure 4.19: BIP model of a HW platform with four processors, a multiplexing interconnect, a multi-banked memory and a network interface

Figure 4 .

 4 Figure 4.20: Router Component in BIP

Figure 4 .

 4 Figure 4.22: NoC Component in BIP

Mapping:

  := Mapping-Item + . Scheduling-Policy + Mapping-Item ::= SW-Process → HW-Processor | SW-Channel → HW-Memory

Figure 5 . 1 :

 51 Figure 5.1: Model of the Producer Component (left) and model of the Refined Producer Component in BIP (right).

  r b , r e }, where w b and r b paired with {wr data} and {rd data} respectively.

weFigure 5 . 2 :

 52 Figure 5.2: Model of the FIFO channel (left) and the Refined FIFO channel in BIP (right).

Figure 5 . 3 :

 53 Figure 5.3: Producer-Consumer Refined Composition in BIP

Figure 5 . 4 :

 54 Figure 5.4: Traces of the Refined Producer-Consumer Process Network.

  r b , true, skip, 2 ), τ mr b = ( 2 , mr b , g r , skip, 3 ), with g r : [count > 0], τ mre = ( 3 , mr e , true, f rn , 4 ), with f rn : count --; j = (j + 1)%N ; data = buf f [j];, τ re = ( 4 , r e , true, skip, 1 ),{τ u = ( , r u , true, f wc , )| ∈ L F R }, with f rn : count + +; }.The FIFO-Buffer represents a passive component modeling the data storage. It has ports op b (Operation Begin)) and op e Operation End for performing the write/read operations.

Figure 5 . 5 :Figure 5 . 6 :

 5556 Figure 5.5: Model of the Producer-Consumer Split-FIFO System Model in BIP

  2 b .α 2 e . . . α n b .α n e and trace(θ D ) = α 1 b .α m1 b .α m1 e .α 1 e .α 2 b .α m2 b .α m2 e .α 2 e . . . α n e Based on the Definition 43, we restrict the trace θ D such that trace D (θ D ) = α 1 b .α 1 e .α 2 b .α 2 e . . . α n b .α n e So, we conclude that trace(θ R ) = trace D (θ D ).

e

  Based on the Definition 43, we restrict the trace θ D such thattrace D (θ D ) = α 1 b .α 1 e .α 2 b .α 2 e . . . α n b .α n eSo, we conclude that trace D (θ D ) = trace(θ R ).

Figure 5 . 7 :

 57 Figure 5.7: Model of the Processor Scheduled System Model in BIP

  .acq, SC.acq}, true, skip), α rel G = ({G.rel, SC.rel}, true, skip), α send d G = ({G.send d, SC.get d}, f, skip), with f : SC.delay = G.delay; α next G = ({G.next, SC.next}, true, skip), α acq F W = ({F W.acq, SC.acq}, true, skip), α rel F W = ({F W.rel, SC.rel}, true, skip), α acq F R = ({F R.acq, SC.acq}, true, skip), α rel F R = ({F R.rel, SC.rel}, true, skip), α tick = ({SC 1 , . . . , SC m }, true, skip)

Figure 6 . 1 :

 61 Figure 6.1: Model of the Processor Scheduled System Model in BIP

Figure 6 . 2 :

 62 Figure 6.2: Traces of Processor Scheduled Producer-Consumer Composition

  α k e -→ q such that θ S belongs in the Split-FIFO Process Network N D . Since we have,trace(θ D ) = α 1 b .α m1 b .α m1 e .α 1 e .α 2 b .α m2 b .α m2 e .α 2 e . . . α mk e .α k e and trace(θ S ) = acq.α 1 b .α m1 b .α m1 e .α 1 e .β 1 .send d.tick 1 . . . tick n .next.α 2 b .α m2 b .α m2 e .α 2 e .β 2 α n b .α n e .rel we conclude, considering the restriction of traces in Definition 48, that trace S (θ S ) = trace(θ D ).

  . The FIFO Buffers are mapped to the shared Memory M of a cluster CL. Thus, we replace the FIFO Buffers with the Memory M . Since the FIFO Routines are mapped on a Processor, we connect them with the Bus Path Components BP of the BU S which connect the Processor P with the Memory M or with the Network Interface N I if the Memory is located in a different cluster.. The set of interactions γ is defined as: γ = γ S ∪ {α m b , α m e |FIFO Routine ∈ N S } ∪ {α µ b , α µ e |BP ∈ BU S} ∪ {tick}, with, α m b = ({F W.mw b , BP.req}, true, skip) or ({F R.mr b , BP.req}, true, skip), α m e = ({BP.ack, F W.mw e , F R.r u }, true, skip) or ({BP.ack, F R.mr e , F W.w u }, true, skip), α µ b = ({BP.op b , M.op b }, true, skip), α µ e = ({BP.op e , M.op e }, true, skip), tick = ({N S .tick, BU S.tick, M.tick}, true, skip).

Figure 6 . 3 :

 63 Figure 6.3: Producer-Consumer System Model on a Shared Memory Cluster in BIP

Figure 6 . 4 :

 64 Figure 6.4: Traces of Processor Scheduled Producer-Consumer Composition on a Shared Memory Cluster

Figure 6 . 5 :

 65 Figure 6.5: Producer-Consumer System Model on a NoC in BIP

Figure 7 . 2

 72 Figure 7.2: Instruction Weight Table ProfilingFlow

Figure 7 . 3 :

 73 Figure 7.3: Execution delay analysis

Figure 7 . 4 :

 74 Figure 7.4: Platform Dependent Code Generation Profiling Flow

Figure 8 . 1 :

 81 Figure 8.1: Timed Composition in BIP with hierarchical connectors.

Figure 8 . 2 :

 82 Figure 8.2: Timed Composition in BIP with hierarchical connector and an Observer Component.

Figure 8 . 3 :

 83 Figure 8.3: Computational Observers in BIP System Model.

Figure 8 . 4 :

 84 Figure 8.4: Observer Component in BIP System Model

Figure 9 . 2 :

 92 Figure 9.2: Fragment of the XML specification of the process network of Figure 9.3 using an iterator.

Figure 10 . 1 :

 101 Figure 10.1: An MPARM architecture with four clusters

2 Figure 10 . 3 :

 2103 Figure 10.3: MPARM Cluster Model in BIP

Figure 10 . 6 :

 106 Figure 10.6: Mpeg-2 Performance Analysis Results

Figure 10 . 7 :Figure 10 . 8 :

 107108 Figure 10.7: Mpeg-2 Processor Performance Analysis Results

Figure 10 . 10 :

 1010 Figure 10.10: Performance Results of Computational Processes in MJPEG Decoder

Figure 10 .

 10 Figure 10.11: FFT application

Figure 10 . 12 :Figure 10 .Figure 10 .

 10121010 Figure 10.12: FFT Mappings on 4-Cluster MPARM Platform

Figure 10 .

 10 Figure 10.15: Demosaicing application

Figure 10 . 16 :

 1016 Figure 10.16: Demosaicing Mappings on 4-Cluster MPARM Platform

Figure 10 .Figure 10 .

 1010 Figure 10.17: Demosaicing Performance Analysis Results per process

Figure 10 . 19 :

 1019 Figure 10.19: Data dependencies for 2 × 2(A), 3 × 3(B) and 4 × 4(C) process decomposition. Identical patterns indicate respectively a similar amount of local computation (processes) or potential for parallel communication (data dependencies).

Figure 10 .

 10 Figure 10.20: Performance Results of Computational Processes in Cholesky(4)

Figure 11 . 1 :

 111 Figure 11.1: P2012 Fabric Template

Figure 11 . 3 :

 113 Figure 11.3: Abstract model of a P2012 Cluster

  Figure 11.3 presents the abstract model of this platform.

Figure 11 . 4 :

 114 Figure 11.4: Platform 2012 Cluster Model in BIP

Figure 11 .

 11 Figure 11.7 presents the model of a 2D-Gabor filter as an atomic component in BIP. This component consists of 6 control locations (START, S1, . . . , S4, DETACH) and two ports, DOL read and DOL write. NDPF state, size and address are local data (variables) of the component. The variables address and size are associated with the ports. The transitions are either internal transitions (internal step) where local computation and updates are made, or port interactions, where the component exchanges data and synchronizes with the other BIP components.We restrict ourselves to the S1 layer of the HMAX models algorithm. The process network in DOL consists of 14 processes and 24 FIFO channels. This DOL model is about 700 lines of XML (defining the process network structure) and 1500 lines of C (defining the process behavior). The software model in BIP is constructed automatically from the DOL model. It consists of 38 atomic components interconnected using 48 connectors. The BIP software model is about 2000 lines of BIP code. The system model obtained by deploying the S1 layer on a single P2012 cluster consists of 125 atomic components interconnected using about 1500 connectors. The total BIP description totalizes about 13000 lines of BIP code. This description is compiled into about 50000 lines of C++ code, used for simulation and performance analysis.The execution time of 2D-Gabor filters on P2012 PEs ranges from 220 • 10 6 to 0.68 • 10 6 cycles, depending on the size of the input image (ranging from 100 × 100 to 15 × 15 pixels). By using these values in the system model, the total execution time of the S1 layer is estimated as 225 • 10 6 cycles. This overall execution time is negatively impacted by the long access time (i.e., about 100 cycles) to the L3 memory (where all FIFOs are mapped) as well as by the bus contention. A slightly better result is obtained if the FIFOs are all mapped into the TCDM memory. In this case, the memory access time is about 1 cycle and there is no more contention. The total execution time reduces to about 220 • 10 6 cycles. However, such a mapping is not feasible due to memory size constraints, that is, FIFOs cannot fit all simultaneously within the TCDM memory.

2

  Example Figure 2.3 shows a graphical representation of a composite component in BIP. It consists of three atomic components, the Sender, the Buffer and the Receiver. The behavior of Sender and Receiver is already introduced in Example 1. The behavior of Buffer has control locations 3 and

4

. It communicates through ports tick, in and out. Ports in, out export the variable y. The Buffer ticks through the tick port to synchronize with the Sender and the Receiver. It communicates through port in which modifies the variable y interacting with Sender via connector io1. Then, the Buffer forwards the same variable to Receiver through port and connector io2. The hierarchical connector tick2 which includes connector tick1, synchronizes all the available components. The tick2 connector has also the least priority among the connectors of the composite component.

  2 , B 3

	Conflict resolution between IP 1 and IP 2
	(i.e. conflict between β and γ)
	IP 2 : interaction γ
	γ : B 4 , B 5
	B 4	B 5

  .3. The NoC offers a high speed, low latency, low power and reliable communication solution Cluster Description based on packet transmission. Each packet contains routing and arbitrating information in order to be transported across the NoC. The packet routing is executed with the use of Routers. A Router contains input and output ports towards each direction (North, South, East, West), as well as towards the Local Cluster, which is connected to it via a Network Interface (NI).

	PE 1	PE 2	PE 8
				PE 1	PE 2	PE 3	PE 4
	M 1	M 2	M 8
					INTERCONNECT
		INTERCONNECT
				M 0	M 1	M 2	M 3
		SM
	Figure 4.1: Cluster Description NI Figure 4.2: Router Router NI Cluster 1 Cluster 2
			Cluster 4	Cluster 3
			NI	NI
		Router	Router

  op e , g ope , skip, 1 ) }.We assume a platform where there are k > 1 processors, one Crossbar Switch Bus and a shared Memory. Bus Scheduler, M the Memory Component. The set of interactions γ is defined as: γ = {α op b , α op e , α acq , α rel |BP ∈ BU S} ∪ {α tick } with, α acq = ({BP.acq, BS.acq}, true, skip), α rel = ({BP.rel, BS.rel}, true, skip), α op b = ({BP.op b , M.op b }, true, skip), α op e = ({M.op e , BP.op e }, true, skip), α tick = ({BS.tick, BP 1 .tick, . . . , BP k .tick, M.tick}, true, skip).

	with,
	f op b : count = 0;,
	g t : [count < mem delay], f t : count + +;,
	g op e : [count == mem delay]

22 Definition (Shared Memory Cluster Compound Component) We define the Shared Memory Cluster Compound Component as M C = πγ(BU S, M ) as the Communication Model of a Cluster, where: BU S = {BP 1 , . . . , BP k , BS}, where k the number of processors, BP the Bus Paths and BS the

  tick, g t 2 , f t 2 , 2 ), τ ope = ( 2 , op e , g ope , skip, 1 ) }

	, with
	f op b : addF irst(buf req, proc id);,
	g t 1 :	[!empty(buf req)],
	f t 1 :	mem conf lict = lastElement(buf req);
		proc id = lastElement(buf req);
		deleteLast(buf req); count = 1;,
	g t 2 :	[count < mem delay + interconnect delay],
	f t 2 :	count + +; incrBuf V alues(buf req);,
	g

ope : [count == mem delay + interconnect delay]

  Figure 4.15: BIP model of a HW platform with four processors and a multi-banked memory Network Interface Model in BIP req (Request), ack (Acknowledgment) are used to interact with the cluster bus. The port send interacts with the local network router and the info port is used to receive packaging information from the Network Interface Incoming Controller.

	req				inf o
	proc_id,dest_id	PE 1	PE 2	PE 3 pack_info	PE 4
					NI-OG
	ni_id	req	1		send
	BI 1 MB 1 ack proc MultiBank TCDM Memory InterConnect count=0; Logarithmic req mem req ack Network Interface BI 2 MB 2 NI-IC tick NI-OG inf o BI 3 MB 3 tick inf o send BI 4 MB 4 rec [count<pack_delay] count=count+1; [count==pack_delay] package=create(pack_info); package 2 4 3 inf o send tick ack Figure 4.16: package=create(proc_id,dest_id); tick send

ack Figure 4.17: Network Interface Outgoing Controller Component in BIP 26 Definition (Network Interface Outgoing Controller Component)

We define the Network Interface Outgoing Controller Component as OG = (L OG , X OG , P OG , T OG ), where:

  = ( 2 , send, g s , skip, 1 ) ,g s : [count == pack delay], τ = ( 1 , inf o, true, skip, 3 ) , τ = ( 3 , ack, true, f ack , 4 ), f ack : package = create(pack inf o);, τ = ( 4 , send, true, skip, 1 ) }.

req, true, f req , 2 ) ,f req : count = 0; package = create(proc id, dest id);, τ = ( 2 , tick, g t , f t , 2 ) ,g t : [count < pack delay], f t : count + +;, τ

  tick, g t , f t , 2 )} , g t : [count < (routing delay + link latency)] , f t : count + +, τ = ( 2 , send, g f , skip, 1 )} , g f : [count == (routing delay + link latency)] }. 32 Definition (Router Compound Component) We define the Router Compound Component as RT = πγ(IR N , IR S , IR E , IR W , IR L , OR N , OR S , OR E , OR W , OR L ), where abbreviations (N, S, E, W, L) stand for (North, South, East, West, Local) respectively. The set of interactions γ s is defined as:

  tick = ({OR N .tick, OR S .tick, OR E .tick, OR W .tick, OR L .tick}, true, skip). For each α ∈ γ, the priority rule π implies that α tick has less priority that any other interaction α ∈ γ. The Router Compound Component exports the ports IR x .rec as rec x , OR x .send as send x

				NI		NI
				IN		IN
	PORT IN	OUT PORT	R T N I O P	NI	CLUSTER 1 CLUSTER 1	NI	CLUSTER 2 CLUSTER 2
			P O O R T U T	OUT		OUT
	PORT OUT		PORT IN	ROUTER	ROUTER
	PORT		PORT
	IN		OUT
				NI		NI
	PORT	PORT		IN		IN
	OUT	IN			CLUSTER 3 CLUSTER 3		CLUSTER 4 CLUSTER 4
				NI		NI
				OUT		OUT
				ROUTER	ROUTER

wd, OR y .rec}, g, skip), with g : [IR x .port id == OR y .port id] and x, y ∈ {N, S, E, W, L}, α

  {R4.send, R1.rec}, α tick = ({CL 1 .tick, . . . , CL 4 .tick, R 1 .tick, . . . , R 4 }, true, skip).

	send, CL.rec},
	α out CL = {CL.send, R.rec}, α in R1 = {R1.rec, R2.send}, α out R1 = {R1.send, R2.rec}, α in R2 = {R2.rec, R3.send}, α out R2 = {R2.send, R3.rec}, α in R3 = {R3.rec, R4.send}, α out R3 = {R3.send, R4.rec}, α in R4 = {R4.rec, R1.send}, α out R4 =

  mw b , g w , skip, 3 ), τ mwe = ( 3 , mw e , true, f wn , 4 ), τ we = ( 4 , w e , true, skip, 1 ), τ acq = ( 5 , acq, g w , skip, 2 ), τ rel = ( 2 , rel, !g w , skip, 5 ),

  Based on the Definition 48, we restrict the trace θ S by removing the send d, tick and next interactions in the first step and by removing the acq, rel interactions in the second step, such that trace S (θ S ) = α 1 .β 1 .α 2 .β 2

β 2 and trace(θ S ) = acq.α 1 .β 1 .send d.tick 1 . . . tick n .next.α 2 .β 2 send d.tick 1 . . . tick n .next.rel

  θ . As we can see in Example 17 the traces of the Processor Scheduled Process Network contain: acq.α 1 .α mw b .α mw e .α w e .β.send d.tick 1 . . . tick n .next . . . rel Interleavings of the above interactions occur due to multiple Processor Schedulers that run in parallel.

  BP i .rel}, true, skip), where i ∈ k, tick bus = ({BP 1 .tick, . . . , BP k .tick}, true, skip). and π bus giving priority on acq bus , rel bus interactions over tick B

	γ bus = {acq bus 1 , rel bus 1 , . . . , acq bus k , rel bus k , tick bus }, with acq bus = ({BS.acq, BP i .acq}, true, skip), i rel bus i = ({BS.rel,

4

, R 1 , . . . , R 4 ) is defined as the Communication Model of the system, where: CL = π CL γ CL (BU S, M, N I) M is the Shared Memory Component and BU S = π bus γ bus (BP 1 , . . . , BP k , BS), where k the number of processors, BP the Bus Paths, BS the Bus Scheduler,

  1 , BP 2 ), with γ bus : BP 2 .acq}, true, skip), rel bus 2 = ({BS.rel, BP 2 .rel}, true, skip), tick bus = ({BP 1 .tick, BP 2 .tick}, true, skip). and γ = γ S ∪ {α rw , α aw , α rr , α ar , α mw S .mw b , BP 1 .req}, true, skip), α mw e = ({F W S .mw e , BP 1 .ack, F R S .r u }, true, skip), α mr b = ({F R S .mr b , BP 2 .req}, true, skip), α mr e = ({F R S .mr e , BP 2 .ack, F W S .w u }, true, skip), α µw b = ({BP 1 .op b , M 1 .op b }, true, skip), α µw e = ({M 1 .op e , BP 1 .op e }, true, skip), α µr b = ({BP 2 .op b , M 1 .op b }, true, skip), α µr e = ({M 1 .op e , BP 2 .op e }, true, skip), tick = ({SC 1 .tick, BU S.tick, M 1 .tick}, true, skip)

	acq bus 1 rel bus 1 = ({BS.rel, BP 1 .rel}, true, skip), = ({BS.acq, BP 1 .acq}, true, skip), acq bus 2 = ({BS.acq, b , α mw e , α mr b , α mr e , tick}: α mw b = ({F W

  .

	. . .
	tick 1
	tick n
	tick 1
	tick n
	. . .
	tick 1	. . .	tick n	tick 1	. . .	tick n	tick 1	. . .	tick n	. . .

  α 1 e . . . rel and trace(θ M ) = acq.α 1 b .α m1 b .tick 1 . . . tick n .acq bus .tick 1 . . . tick l .α BP.β .tick 1 . . . tick j .α µ b . tick 1 . . . tick h .α µ e .rel bus α m1 e .α 1 e . . . rel, where n, l, j, h > 1. Based on the Definition 50, we restrict the trace θ M such that:

  θ . As we can see in Example 18 the traces of the System Model Process Network contain: acq.α w b .α mw b .tick 1 . . . tick n .acq bus .tick 1 . . . tick l .α BP.β .tick 1 . . . tick j .α µw b . tick 1 . . . tick h .α µw e .rel bus α mw e .α w e .

  γ ob with, γ ob = ({γ H .tick, B ob .tick}, α ob , tick) , α ob = ({γ H .tick, B ob .tick}, true, skip) The description in BIP language of the observation connector γ ob used to incorporate the Observer Component to the Timed model is given below. connector type ObserverTick(TickPort tick 1 , TickPort tick 2 ) define tick 1 tick 2 on tick 1 tick 2 export port TickPort tick end

  .3.

	Generator	0000 0000 1111 1111 F0	Square1	0000 0000 1111 1111 F1	Square2	0000 0000 1111 1111 F2	Square3	00000 00000 11111 11111 F3	Consumer
			Figure 9.3: Multiple Square application in DOL

Table 9 . 1

 91 As given in Algorithm 5, we initially load the BIP System Model in the tool. All the blocks of C code of the BIP transitions are instrumented with profiling functions. Then, we configure the HW Platform Cross Compiler and we generate the assembly code. Next, we compile the instrumented BIP model with the profiling library. Finally, we simulate the BIP model and we analyze the target blocks of code based on the low-level instructions of the corresponding assembly code and the pre-defined operation weight table.The tool is implemented both in C language and Perl Scripts. It consists of approximately 22 files and 4000 lines of code, as seen in Table9.1.Algorithm 5 Weight Table Profiling Tool AlgorithmRequire: BIP System Model, HW Platform Cross Compiler, Operation Weight Table,

		#Files #Lines of Code
	C2BIP	7	2892
	DOL2BIP	5	3028
	BIPWeaver	25	8873
	BIP Library	4	7200
	Architecture XML	2	887
	Weight Table Profiler	22	4000
	Code Generator	12	1744

Table 9 . 1 .

 91 Algorithm 6 Platform Dependent Code Generator Tool Algorithm Require: BIP System Model, Virtual Target Platform, Architecture XML, Mapping XML

	Ensure: Calibrated System Model
	load(BIP System Model)
	sys spec = load(Architecture XML, Mapping XML)
	for all process (p) ∈ processList do
	thread = implement as thread(p)
	end for
	for all SW channel (sw) ∈ SW channelList do
	sh q ob = implement as shared queue object(sw)
	end for
	for all threads do
	allocate to cores(thread, sys spec)
	end for
	for all data do
	allocate to memories(data, sys spec)
	end for

  .1.

			ARM 1	ARM 2	ARM 8
	Router	Router
			Bus	Bus	Bus
	Cluster 1	Cluster 2
			L1	L1	L1
	Router	Router		Cross-Bar
	Cluster 4	Cluster 3	NI	L2

Table 10 .

 10

	1: MPARM Cluster Features
		MPARM Cluster Features
	CPU frequency	200MHz
	DRAM Access Delay (conflict free) (L1)	0.5 cycles/byte
	SRAM Access Delay (conflict free) (L2)	5.5 cycles/byte
	AMBA-AHB	1 cycles/access (4 bytes)

Table 10 . 2 :

 102 NoC Features

	NoC Features

Table 10 . 3 :

 103 MPARM Cluster Parameters

	MPARM Cluster Parameters

  4, we illustrate the Router Component in BIP. It is composed using the Router IN and Router OUT Components for each direction: the North, the South, the East, the West and the Local Cluster. The parameters specifying the component are the router delay and the link latency which is incorporated into the Router Components.

				. . .
	acq	rel	req	ack	acq	rel	req	ack
	tick		bus_conflict=0;		tick	bus_conflict=0;
	bus_conflict++;				bus_conflict++;
			count=0;				count=0;
	count++; [count<bus_delay]		. . .	count++; [count<bus_delay]
			[count==bus_delay]				[count==bus_delay]
	mem_conflict++;			mem_conflict++;
	bus_delay : 4 (cycles/access)			[count==mem_delay]
	mem_delay : 22 (cycles/access)
				count=0;	[count<mem_delay]
						count++;

Table 10 . 4 :

 104 NoC Parameters

	NoC Parameters

Table 10 . 7 :

 107 Mapping Description of the processes and the FIFOs

	ARM 1	ARM 2	ARM 3	ARM 4	ARM 5
	1 all
	2 DG, DM , DB, T BCB, CM , CG
	3 DG, DM	DB, T B	CB, CM , CG
	4 DG	DM , DB	T B	CB, CM , CG
	5 DG	DM , DB	T B	CB, CM	CG
	6 DG, DM	DB	T B	CB	CM , CG
	7 DG	DM , DB	T B	CB, CM	CG
	Shared	LM 1	LM 2	LM 3	LM 4	LM 5
	1	all
	2 C4	C1, C2, C3 C5, C6
	3 C2, C4	C1	C3	C5, C6
	4 C1, C3, C4		C2		C5, C6
	5 C1, C3, C4, C6		C2		C5
	6 C2, C3, C4, C5	C1				C5
	7	C1	C2, C3	C4	C5, C6

Table 10 . 8 :

 108 Mapping Description of the processes and the FIFOs

				ARM 1				ARM 2			ARM 3			ARM 4	ARM 5
			1	all
			2	SS, SF , IQ			M F , M S
			3	SS, SF				IQ, M F , M S
			4	SS, SF				IQ				M F , M S
			5	SS, M S				SF				IQ					M F
			6	SS					SF				IQ					M F		M S
			7	SS, SF				IQ				M F , M S
			8	SS					SF				IQ					M F		M S
				Shared				LM 1			LM 2			LM 3	LM 4
			1						all
			2	C6, C7				C1, C2, C3, C4, C5		C8, C9
			3	C3, C4, C5, C6		C1, C2			C7, C8, C9
			4	C3, C4, C5, C6, C7	C1, C2								C8, C9
			5	all
			6	all
			7	C6, C7				C1, C2, C3, C4, C5							C8, C9
			8						C1, C2			C3, C4, C5, C6	C7		C8, C9
	Computation Delay (megacycles)	0	1	2	3	4	5	6	7	8	9	Bus conflict (megacycles)	0 2 4 6 8 10 12	1	2	3		4	5	6	7	8
	Communication Delay (megacycles)	0	1	2	3	4	5	6	7	8	9		0 500 1000 1500 2000 2500 3000 3500 4000 4500	1	2	3	4	5	6	7	8

Table 10 . 9 :

 109 Simulation Comparison in MPARM & BIP System Model (10 6 cycles)

	Cycle Count	MPARM	468.83
		BIP System Model 472.88
		Accuracy	0.87%
	Simulation Time MPARM	50' 48"
		BIP System Model 9' 46"
		Speed-up	5.20

Table 10 .

 10 10: DOL, BIP Models and MPARM Implementation Characteristics

	FFT
		# processes	14
	DOL Process Network	# FIFOs	32
		# lines of code 1616
		# components	168
	BIP System Model	# interactions	706
		# lines of code 9641
	MPARM implementation # lines of code 3986

Table 10 . 11 :

 1011 Execution times for computational routines on FFT processes (in 10 6 cycles)

	FFT
	FFT2 0 0	2.52
	FFT2 0 1	2.51
	FFT2 0 2	2.44
	FFT2 0 3	0.13
	FFT2 1 0	2.33
	FFT2 1 1 32.35
	FFT2 1 2	2.43
	FFT2 1 3 32.32
	FFT2 2 0	2.36
	FFT2 2 1 32.41
	FFT2 2 2 32.32
	FFT2 2 3 34.09

Table 10 .

 10 12: DOL, BIP Models and MPARM Implementation Characteristics

	Demosaicing		M odel(1 × 6)
		# processes	10
	DOL Process Network	# FIFOs	28
		# lines of code	1672
		# components	152
	BIP System Model	# interactions	614
		# lines of code	15366
	MPARM implementation # lines of code	10124

Table 10 .

 10 13: Execution times for computational routines on demosaicing processes (in 10 6 cycles)

	Demosaicing	M odel(1 × 6)
	Demo 1	14.23
	Demo 2	27.03
	Demo 3	26.86
	Demo 4	26.53
	Demo 5	23.87
	Demo 6	14.66

Table 10 .

 10 14: DOL, BIP Models and MPARM Implementation Characteristics

			B = 2	B = 3	B = 4
		# processes	5	8	12
	DOL Process Network	# FIFOs	8	20	40
		# lines of code	864	1400	2171
		# components	40	120	181
	BIP System Model	# interactions	182	445	882
		# lines of code	5207	7491	13648
	MPARM implementation # lines of code	1977	3163	4923

Table 10 .

 10 16: Performance Analysis: MPARM Execution vs BIP System Model Simulation

	B = 2	B = 3	B = 4

Table 11 .

 11 The complete abstract model of the P2012 architecture we considered consists of four clusters, each of them enumerating sixteen processing elements, one 32-banked TCDM memory and one Logarithmic Interconnect, as shown in Table11.2. To concretely model this abstract model in BIP, we need various BIP types and BIP type instances as depicted below inTable 11.3.

	1: P2012 Cluster Parameters
		P2012 Cluster Parameters
	Logarithmic Interconnect Delay (conflict free)	1 cycle/byte
	TCDM Access Delay (conflict free)	1 cycle/byte

Table 11 . 2 :

 112 P2012 architecture

	Hardware Component	Number
	Clusters		4
	Processing Elements/Cluster	16
	Logarithmic Interconnect/Cluster	1
	TCDM/Cluster		1
	Memory Banks/TCDM		32
	Routers		4
	Table 11.3: BIP P2012 Library
	BIP types BIP type instances
	Ports	5	122
	Connectors	7	1094
	Atomic Components	11	69
	Compound Components	3	2

http://www-verimag.imag.fr/BIP-System-Designer.html

http://www.tik.ee.ethz.ch/ shapes/dol.html

http://www.tik.ee.ethz.ch/ shapes/dol.html

Part

System Designer -Chapter 9 -

Tool

In this chapter, we provide the description of the tool-flow and all the individual tools contributing in the System modeling and the performance analysis. The associated toolbox is available in the website 1 of Verimag.

In Figure 9.1 we illustrate the whole tool-flow. The flow mainly contains four different sectors: Input Specification in DOL, System Model Generation, System Model Calibration and Performance Analysis. We developed four different tools which traverse the above sectors and automatize the tool-flow. The tools are given below:

• DOL2BIP, which generates the BIP SW Model.

• BIPWeaver, which constructs the BIP System Model.

• Weight Table Profiler, which provides a technique for System Model Calibration, calculating execution delays of computational blocks of code.

• Code Generator, which generates code to be simulated on a Virtual HW Platform, providing an alternative and more accurate method for calculating execution delays of computational blocks of code.

Except the Weight Table Profiler, which is implemented in C Language and Perl Scripts, all the other tools are implemented in Java. Details concerning the complexity of the tools are given in the next sections.

DOL2BIP Tool

In Algorithm 3, we describe the algorithm we developed to generate a BIP SW Model out of an input specification in DOL. The tool requires as an input the XML specification in DOL of the Process Network and the corresponding source code in C of each process. The Process Network XML file should conform with the process network XML Schema as it is defined in DOL. Further details and information about the DOL input specification is available in the following website 2 . In Figure 3.6 (Chapter 3), a process network example is found. As described in Section 3.3, the process network consists of three XML entities: process, sw channel and connection. Each process has input, output ports and behavior written in C code. Each sw channel has a single input port and a single output port, 10.5, we quote the complexity of the abstract model of MPARM considered. The number of BIP types and BIP type instances needed to model the MPARM platform in BIP are given in Table 10.6. Based on the MPARM Platform model in BIP described in the current section, we generate various mixed hardware/software System models of a series of application case studies. The experimentations conducted are presented in the forthcoming sections.

MPEG-2 Application on MPARM

The MPEG2 decoder application software decodes a set of moving pictures and associated audio information. The corresponding process network is depicted in Figure 10.5. We used a case study where there are seven processes DispatchGops (DG), DispatchMb (DM), DispatchBlocks (DB), TransformBlock (TB), CollectBlocks (CB), CollectMb (CM) and CollectGops (CG) and six software FIFO channels C1, . . . , C6. The behavior of the decoder is described in approximately 7000 lines of C code. The process and the FIFO mappings are illustrated on Table 10 scale input (only one input feature: intensity at pixel level) and the image is then subsampled at several resolutions. For the S1 layer, a battery of three filters is applied to the sub-sampled images (three features) and finally for C1 layer we take the spatial max of computed filters across two successive scales. The process is illustrated in Figure 11. 5.

In this application model, parallelism can be exploited at several levels. First at the layer level, independent features can be computed simultaneously. Second, at the pixel level, the atomic computation of contribution to a feature may be distributed among computing resources. In the scope of this paper, we will consider parallelism at the layer level.