Karol Desnos
email: kdesnos@insa-rennes.fr

Maxime Pelcat
email: mpelcat@insa-rennes.fr

Jean-Franc ¸ois Nezan

Distributed Memory Allocation Technique for Synchronous Dataflow Graphs

This paper introduces a new distributed memory allocation technique for applications modeled with Synchronous Dataflow (SDF) graphs. This technique builds on a State-of-the-Art shared memory allocation technique based on a weighted graph, called Memory Exclusion Graph (MEG). A MEG captures the memory reuse opportunities between memory objects that must be allocated before the execution of an SDF graph. The algorithms detailed in this paper enable a single MEG to be split into separate MEGs, each of which is associated with a memory bank accessible only by one core of the architecture. The proposed technique is implemented within a rapid prototyping framework and is evaluated by deploying real computer vision applications on a Multiprocessor Systemon-Chip (MPSoC). Results show a systematic performance improvement due to better memory usage, with application speedups ranging from 2% up to 380%.

I. INTRODUCTION

In 1995, Wulf and McKee [START_REF] Wulf | Hitting the memory wall: implications of the obvious[END_REF] introduced the "memory wall" problem which identifies the low rate of improvement in memory bandwidth as a major concern for developers of embedded systems. Since then, industrial efforts to keep up with Moore's Law has led to the evolution of architectures that are increasingly more parallel with soon thousands of processing elements embedded into a single chip [START_REF]International Technology Roadmap for Semiconductors (ITRS): System Drivers[END_REF]. As a result of this multi-and manycore trend, distributed memory architecture has been widely adopted by processor manufacturers to avoid hitting the memory wall.

An application specified with a dataflow graph [START_REF] Lee | Dataflow process networks[END_REF] consists of a set of processing entities, named actors, connected by a set of First-In First-Out queues (FIFOs) transmitting data quanta, named datatokens, between actors. An actor starts its preemption-free execution (that is, it fires) when its input FIFOs contain enough data-tokens. When deploying an application specified with a dataflow graph on a multicore architecture, the primary task of memory allocation is to assign an address range of memory to store each data token that transit through the FIFOs of the dataflow graph.

The contribution of this paper is a novel compile-time memory allocation technique for dataflow graphs which supports distributed memory architectures, shared memory architectures, and architecture combining both shared and distributed memory resources. This memory allocation technique builds on memory minimization techniques for shared memory architectures published in [START_REF] Desnos | On memory reuse between inputs and outputs of dataflow actors[END_REF], [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF]. From these shared memory techniques, the new technique inherits memory reuse capabilities at graph level [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF], compatibility with buffer merging for memory reuse between different FIFOs at actor level [START_REF] Desnos | On memory reuse between inputs and outputs of dataflow actors[END_REF], and code generation supporting cache incoherent architectures [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF].

The context of this work is presented in Section II. Section III contains a set of memory reuse techniques used as a basis for the new distributed memory allocation technique, which is then detailed in Section IV. Finally, an experimental comparison of shared and distributed allocation techniques for the deployment of two image processing applications on an Multiprocessor System-on-Chip (MPSoC) is presented in Section V.

II. RELATED WORK

A. Synchronous Dataflow (SDF)

1) The Semantics of the SDF Model of Computation (MoC):

The SDF Model of Computation (MoC) chosen for this study is among the most commonly used dataflow MoCs. The SDF MoC is a specialization of the dataflow MoC where token production and consumption rates of actors set by actor firing rules are fixed scalars and are known at compile-time [START_REF] Lee | Synchronous data flow[END_REF]. This property makes it possible to analyze SDF graphs during their compilation. Static analysis can be used to check consistency and schedulability properties that imply deadlock-free execution and bounded FIFO memory needs. If an SDF graph is consistent and schedulable, a fixed sequence of actor firings, called iteration, can be repeated indefinitely to execute the graph [START_REF] Lee | Dataflow process networks[END_REF].

Formally, an SDF graph G = A, F is a directed graph containing a set of actors A that are interconnected by a set of FIFOs F . prod(f ) and cons(f ) denote the actors in A producing and consuming tokens respectively on a FIFO f . For each FIFO f ∈ F connected to an actor a ∈ A, a data rate is specified by the function rate : A × F → N * .

On the SDF graph presented in Figure 1, expressions displayed adjacent to the data ports are token production and consumption rates on the connected FIFO. Expressions depend on static parameters w and h, the image width and height respectively, and on n, the number of slices into which the image is split to provide parallel processing.

2) Memory Footprint Minimization in the Literature: Minimization of the memory footprint allocated for the deployment of SDF graphs has been the subject of many publications, both for monocore [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF], [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF] and multicore architectures [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF], [START_REF] Lesparre | Compile-time mapping of dataflow applications with buffer minimization[END_REF]. Minimizing the memory footprint of dataflow applications is usually achieved by using FIFO dimensioning techniques [START_REF] Benazouz | A new approach for minimizing buffer capacities with throughput constraint for embedded system design[END_REF], [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF], [START_REF] Parks | Bounded scheduling of process networks[END_REF], [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF]. FIFO dimensioning consist of finding an execution order of the graph actor, called a schedule, that minimizes the memory space allocated to each FIFO of the SDF graph. A disadvantage of these techniques is that memory reuse between FIFOs is not considered [START_REF] Benazouz | A new approach for minimizing buffer capacities with throughput constraint for embedded system design[END_REF], [START_REF] Parks | Bounded scheduling of process networks[END_REF], [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF], or only single-core architectures are considered [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF]. The proposed distributed memory minimization technique is based on a memory allocation model that fosters memory reuse between several FIFOs. Some publications tackle the issue of memory allocation of SDF graphs in a distributed memory context [START_REF] Carpenter | Buffer Sizing for Self-timed Stream Programs on Heterogeneous Distributed Memory Multiprocessors[END_REF], [START_REF] Lee | High-performance buffer mapping to exploit DRAM concurrency in multiprocessor DSP systems[END_REF], [START_REF] Lesparre | Compile-time mapping of dataflow applications with buffer minimization[END_REF]. The technique presented in [START_REF] Lee | High-performance buffer mapping to exploit DRAM concurrency in multiprocessor DSP systems[END_REF] analyzes the scheduling of inter-processor communications in order to allocate buffers of communications which occur simultaneously in different memory banks, thus constituting a shared memory space. Although this technique targets shared memory architectures, its consideration of several memory banks makes it similar to an approach for distributed memory. In [START_REF] Carpenter | Buffer Sizing for Self-timed Stream Programs on Heterogeneous Distributed Memory Multiprocessors[END_REF], a FIFO sizing technique is applied in a distributed memory context with limited memory resources. This allows FIFO sizing to be used as a buffering technique for inter-processor communications. The results published in the study focus on application latency and throughput under Blue and red arrows depict a schedule of the SDF graph on an architecture with two cores. memory constraints. In [START_REF] Lesparre | Compile-time mapping of dataflow applications with buffer minimization[END_REF], authors introduce a mapping technique for SDF actors on a distributed memory architecture with constrained memory resources. The memory-constrained mapping problem is then formulated as an integer linear program of polynomial complexity. The commonality of all these techniques is that none consider memory reuse between different FIFOs. Memory reuse is the rationale behind the proposed study.

III. EXISTING MEMORY REUSE FRAMEWORK

The distributed memory allocation technique used in this paper consists of the following steps, of which Step 5 (Section IV) constitutes the novelty of this paper:

1) Convert the original SDF graph to single-rate SDF graph. 2) Build a Memory Exclusion Graph (MEG) (Section III-A).

3) Update the MEG with scheduling information [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF]. 4) Apply buffer merging to the MEG. (Section III-B) 5) Create a specific MEG for each memory component. 6) Allocate each specific MEGs to its memory component. 7) Generate code with explicit cache management [START_REF] Cudennec | Generating code and memory buffers to reorganize data on many-core architectures[END_REF], [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF].

A. Memory Exclusion Graph (MEG)

Before allocating an SDF graph in distributed memory, transformations are applied to reveal its parallelism and memory characteristics.

The first step of the proposed technique is the transformation of the original SDF graph into an equivalent single-rate SDF graph where each original FIFO is replaced with one or several single-rate FIFOs whose consumption and production rates are all identical [START_REF] Pino | A hierarchical multiprocessor scheduling framework for synchronous dataflow graphs[END_REF]. Assuming that executions of successive graph iterations never overlap, each single-rate FIFO is thus a buffer of fixed size accessed by two actors. Figure 2 presents the single-rate SDF graph derived from the original SDF graph from Figure 1. Replacing original multirate FIFOs with single-rate buffers yields many advantages [START_REF] Cudennec | Generating code and memory buffers to reorganize data on many-core architectures[END_REF]: FIFO management overhead is removed; actor code does not require push or pop primitives as pointers to single-rate buffers are sufficient; and lifetimes of single-rate buffers span from the start of their producer actor execution, to the completion of their consumer actor.

The second step of the proposed technique consists of building an undirected graph, called Memory Exclusion Graph (MEG), whose weighted vertices are the memory objects that must be allocated in memory to support the execution of the application [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF]. Memory object is a term used variously to designate a single-rate buffer, an initial token, or a working memory used by an actor during its execution. In a MEG, two memory objects are connected with an edge called exclusion if they can not be allocated in overlapping memory ranges. An exclusion is added between two memory objects if they may store valid data simultaneously. An algorithm which constructs a MEG from a single-rate SDF graph can be found in [START_REF] Desnos | Memory analysis and optimized allocation of dataflow applications on shared-memory mpsocs[END_REF].

Formally, a Memory Exclusion Graph (MEG) is an undirected weighted graph denoted by M EG = M, E, w where: M is the set of memory objects. m(f ) ∈ M and m(a) ∈ M are the memory objects associated with the single-rate FIFO f ∈ F , and the working memory of actor a ∈ A, respectively. E is the set of memory exclusions. w : M → N * is a function where w(m) is the size (in bytes) of a memory object m. Figure 3a shows the MEG corresponding to the single-rate buffers contained in the SDF graph of Figure 2. Working memory of actors has been omitted for conciseness. Figure 3b presents a valid memory allocation derived from the MEG of Figure 3a.The horizontal axis represents addresses of shared memory, and vertical axis is used to denote reuse of memory ranges to store several memory objects.

B. Buffer Merging

The memory reuse opportunities modeled in MEGs result from a graph-level analysis of the data dependencies between singlerate buffers. Hence, MEGs are unable to capture memory reuse opportunities between input and output buffers of an actor, resulting from internal data dependencies.

Figure 4a illustrates the internal data dependencies of the Split actor. The purpose of this actor is to copy two overlapping slices from its input buffer to its output buffers. Hence, memory can be saved by merging the output buffers of the actor directly within their corresponding ranges of the input buffer. Figure 4b presents the MEG obtained by merging buffers a, b, and c into a single memory object of weight 730w. To specify that the memory allocated for the new abc buffer can be partially reused to allocate buffers f , h, g, and i, The following notation is used for MEG = M, E, w : M merged ⊂ M is the set of buffers that result from the merging of several memory objects of the original graph. m merged ∈ M merged is a set of the pair { m k , off k }, where m k is a merged memory object from the original MEG on which the buffer merging technique was applied, and off k ∈ N is the start offset in bytes of m k within m merged . f (m) ∈ F is used to denote the single-rate FIFO associated with a memory object m ∈ M , assuming that this memory object is not associated with the working memory of an actor. This is always true for buffers in M merged .

IV. PROPOSED DISTRIBUTED MEMORY ALLOCATION TECHNIQUE

A. Memory Architectures

The three memory architectures depicted in Figure 5 have been chosen to assess the distributed memory allocation technique. With shared memory, all cores of the architecture access a unique memory space that is used to share data among them. With distributed memory, each core of the architecture is associated with a memory component accessible only by this core. With heterogeneous memory, Each core can access both a private memory component accessible only to this core, and a shared memory space. Using MEGs (Section III) to perform memory allocation for shared memory architectures, all memory objects allocated in shared memory will be accessible to all cores. Hence, shared memory is used for both storing buffers accessed by actors mapped on a single core and for storing buffers used for inter-processor communication.

Shared Memory

When deploying an SDF graph on a distributed architecture, special care must be taken to ensure that a memory object allocated in a distributed memory component will be accessible to all cores executing actors accessing this memory object.

M EG i .M ← M EG i .M \ {m(f )} 19 endif 20 else if HETEROGENEOUS MEMORY then 21 if map(prod(f )) = map(cons(f )) = c i then 22 M EG S .M ← M EG S .M \ {m(f )} 23 else 24 M EG i .M ← M EG i .M \ {m(f )}

B. Memory-Specific MEG: No Buffer Merge

To benefit from both the memory reuse opportunities captured by the MEG of an application, and the performance due to distributed memory, it is necessary to identify which memory can be used to allocate each memory object of the MEG. The simplest solution is to use actor mapping information of an application and split its original MEG into several MEGs, each associated with a specific memory component. The algorithm used to split the MEG into memoryspecific MEGs is presented in Algorithm 1. This algorithm is compatible both with distributed and heterogeneous memory organizations.

Algorithm 1 iterates over the cores of the targeted architecture, and verifies whether the memory object m(f ) of each single-rate graph FIFO f is made accessible to the actors using it when m(f ) is allocated in the memory component associated with the current core. Hence, the algorithm outputs as many memory-specific MEGs M EGi as there are memory components in the targeted architecture.

Line 8 of the algorithm initializes each output memory-specific MEG M EGi with a copy of the original MEG: M EG0. The purpose of the final portion of the algorithm is to remove the memory objects that are not allocated in a memory component from the corresponding M EGi. Lines 9 to 13 of the algorithm deal with the working memory of each actor: the corresponding memory object is removed from all M EGi, except if this actor is mapped. The processing of memory objects corresponding to single-rate FIFO depends on the targeted architecture.

The following sections describe MEG splitting methods for distributed memory and heterogeneous memory.

1) Splitting an original MEG for Distributed Memory: The heart of the algorithm for distributed memories (lines 16 to 19) checks if neither prod(f ) nor cons(f ), the producer and consumer actors of a FIFO f , are mapped to the current core ci. Meeting this condition means that m(f ), the memory object associated with single-rate FIFO f , is never accessed by ci and can be removed from M EGi. 6b show the memory-specific MEGs obtained when Algorithm 1 is applied to the MEG from Figure 3a with the mapping from Figure 2, and assuming a distributed memory architecture. A memory object is duplicated in two memory-specific MEGs if its producer and consumer actors are mapped on two different cores. Inter-core communications ensures that coherent data is available in the memory allocated to memory components h and c.

2) Splitting an original MEG for Heterogeneous Memory: The heterogeneous memory portion of the algorithm (lines 20 to 25) checks if both prod(f ) and cons(f ), the producer and consumer actors of FIFO f , are mapped to core ci. Meeting this condition means that m(f ), the memory object associated with single-rate FIFO f , is only accessed by core ci and can be removed from M EGS, i.e. the memory-specific MEG associated with shared memory. Otherwise, m(f ) is removed from M EGi as it is accessed by other core(s) and should be allocated either in shared memory or in the memory associated with a core distinct from the current core ci. 3a with the mapping from Figure 2, and assuming a heterogeneous memory architecture. Memory objects accessed by several cores are not duplicated as they are allocated in the shared memory supporting inter-core communication.

C. Memory-Specific MEG: With Buffer Merging

Since a memory object resulting from the merge of several buffers does not have a unique producer and consumer actor, it is necessary to include the call for Algorithm 2 in Line 14. Algorithm 2 processes each buffer resulting from a buffer merge. The behavior of Algorithm 2 differs depending on the targeted memory organization, as described in following sections. 4b with the mapping from Figure 2, and assuming a distributed memory architecture. All three merged buffers, a, b, and c, from the original MEG are accessed by core 1. Consequently, buffer abc is completely copied in the memory-specific MEG associated with core 1 (Figure 8a), thus decreasing the allocated memory footprint to 1102w bytes.

c i 4 M accessed ← ∅ 5 for each m k ∈ m merged do 6 if map(prod(f (m k ))) = c i or map(cons(f (m k ))) = c i then 7 M accessed ← M accessed ∪ {m k } 8 R ← R ∪ [off k , off k + w(m k )[
2) Merged Buffers and Heterogeneous Memory: When targeting heterogeneous memory, Lines 19 to 25 of Algorithm 2 are used to check whether a buffer m merged resulting from a merging operation should be allocated in a distributed memory component or in shared memory. A buffer m merged resulting from a merging operation will be allocated in the private memory component of a core ci if all actors accessing merged buffers m k ∈ m merged are mapped on ci.

This strategy was adopted to favor memory reuse opportunities offered by buffer merging over allocation of memory objects in distributed memory components. Indeed, buffer merging removes many memory copy operations (memcpy() in C language) between merged buffers, which improves performance more than allocating mergeable memory objects in distributed memory components [START_REF] Desnos | On memory reuse between inputs and outputs of dataflow actors[END_REF]. Figure 9 shows memory-specific MEGs and allocations obtained when applying Algorithms 1 and 2 to the MEG from Figure 4b with the mapping from Figure 2 assuming heterogeneous memory. In this example, one of the merged buffers, buffer c, is accessed by more than one core, resulting in the allocation in shared memory of the whole buffer produced by the merge of buffers a, b, and c (Figures 9c).

V. EXPERIMENTS

The distributed memory allocation technique proposed in this paper is implemented within the open-source rapid prototyping framework PREESM [START_REF] Pelcat | PREESM: A Dataflow-Based Rapid Prototyping Framework for Simplifying Multicore DSP Programming[END_REF]. This implementation is used to assess the behavior and impact of the proposed technique on real applications, both theoretically and practically, by generating code for an MPSoC.

A. Experimental context 1) Applications: Two applications are used to assess the proposed memory allocation technique: Sobel, an image processing application and Stereo, a computer vision application. The properties of these applications are presented in Table I The Sobel application is the original SDF graph presented in Figure 1 with parameters h = 720, w = 1280, and n = 8. The purpose of this application is to apply several commonly used 2D image filters in order to detect the edges of the processed image. The Stereo-matching application is a State-of-the-Art computer vision algorithm whose purpose is to extract 3D information from a pair of 2D images [START_REF] Mercat | Implementation of a Stereo Matching Algorithm Onto a Manycore Embedded System[END_REF]. The large number of actors, FIFOs and exclusions of this application make it an interesting test case for the proposed allocation technique. These two applications are chosen from an open-source repository of PREESM applications (https://github.com/ preesm/preesm-apps), to allow these experiments to be reproduced.

2) Target Architecture: : The TMS320C6678 is an MPSoC manufactured by Texas Instruments. This MPSoC contains eight C66x Digital Signal Processors (DSPs). In these experiments, a heterogeneous memory organization is used on the C6678 with 512 Mbytes of external shared memory, and 512 kBytes of L2 private memory for each core. The TMS320C6678 has no hardware cache coherence mechanism between the private L1 32 kBytes caches of the 8 cores.

B. Memory Footprint Study

Using the technique introduced in Section IV, memory allocation of applications presented in Table I is performed for each memory organization presented in Figure 5. Memory footprints resulting from the allocation of the two applications are plotted in Figures 10 and11 In Figures 10 and11, for all memory organizations, a green rectangle represents the footprint allocated in shared memory, and red rectangles represent the total footprint allocated in the private memory component of all the cores. In Figure 11, an enlarged view of the 0-7MB portion of the plot is presented below the overall graph, clarifying details between the Shared and Heterogeneous scenarios.

As shown in these results, memory footprints allocated for distributed and heterogeneous memory organizations are larger than for shared memory organization. This increase of footprint has two causes. First, splitting the original MEG of an application into memory-specific MEGs removes memory reuse opportunities between memory objects allocated in separate memory components. Second, when generating memory-specific MEGs for distributed memory organization, memory objects accessed by two cores are duplicated in their respective MEGs.

In these experiments, the heuristic algorithm responsible for mapping and scheduling SDF actors on cores of the targeted architecture does not consider memory. Instead, latency-oriented optimizations may result in application mappings where most memory objects are accessed by several cores, and which may undermine the efficiency of the proposed memory distribution technique [START_REF] Pelcat | PREESM: A Dataflow-Based Rapid Prototyping Framework for Simplifying Multicore DSP Programming[END_REF].

In the heterogeneous scenario, approximately 2/3 of the memory objects of Sobel, representing 44% of the memory footprint, and 1/3 of the memory objects of Stereo, representing 28% of the memory footprint, can be allocated in private memory components. Memory footprints allocated in the heterogeneous scenario are only slightly larger than memory footprints allocated in the shared scenario; footprints are only 15% larger for Sobel, and 23% larger for Stereo.

In the distributed scenario, memory footprints are 51% larger for Sobel and 606% larger for Stereo when compared with those of the shared scenario. The large memory footprint of the Stereo application is caused by the duplication of large memory objects corresponding to the pair of input images processed by the application, and accessed by actors mapped on all cores. A finer modeling of the Stereo application, where the input image is sliced instead of being duplicated, would decrease the memory footprint in the distributed scenario.

The results using heterogeneous memory show the efficiency of the proposed allocation technique. To further increase the efficiency of the proposed method, a memory-aware mapping technique such as that proposed in [START_REF] Lesparre | Compile-time mapping of dataflow applications with buffer minimization[END_REF] will be considered in future work.

C. Performance Study

Using PREESM, code was generated for the C6678 architecture for the two applications. Because the current code generation only supports shared memory-based communications, no code was generated for the distributed memory organization. The performance of the Sobel application with deactivated caches is increased by 380% for the heterogeneous scenario compared to the shared scenario. The better result is due to the performance gap between memory accesses in shared L3 memory, and in private L2 memory components. This example shows that application performance can be dramatically increased with only 44% of the memory allocated in the private memory of the cores. The performance of the Sobel application when L1 caches are activated is only 2% higher for the heterogeneous scenario than for the shared scenario. The near equivalence of performance between the two scenarios is due to the efficiency of the caching mechanism thus masking the majority of differences in access times between shared and private memory components.

The performance of the Stereo application for the heterogeneous scenario is 35% better than for the shared scenario, when the caches are deactivated. When L1 caches are activated, the performance in the heterogeneous scenario remains 19% higher than for the shared scenario. In the Stereo application, large memory objects are accessed by the application, thus decreasing the efficiency of the caching mechanism while preserving the benefits of the distributed memory allocation technique. These results show that the memory distribution technique proposed in this paper has a positive impact on the performance of applications executed on a real off-the-shelf MPSoC.

VI. CONCLUSION

This paper introduced a new memory allocation technique for the deployment of applications modeled with dataflow graphs on multicore architectures with distributed memory components. The proposed technique builds on a State-of-the-Art memory allocation technique for shared memory architectures. While providing allocation of dataflow applications in distributed memory components, the proposed technique preserves memory reuse opportunities between the application buffers, including memory reuse specified using a State-of-the-Art buffer merging technique. Experiments show that using the proposed technique when deploying a real image processing application on an off-the-shelf MPSoC leads to better application performance. Future work on this topic includes predicting time performances related to memory allocation and combining the proposed memory allocation technique with a memory-aware mapping and scheduling algorithm.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Synchronous Dataflow (SDF) graph of the Sobel application

Fig. 3 .

 3 Fig.3. MEG derived from the SDF graph of Figure2

Fig. 4 .

 4 Fig. 4. Buffer merging opportunity for Split actor

Fig. 5 .

 5 Fig. 5. Memory architectures

ALGORITHM 1 : 2 M 5 M 8 M 11 M 14 Call

 12581114 Split MEG into memory-specific MEGs Input: G = A, F a single-rate SDF graph M EG 0 = M, E, w the original MEG derived from G C = {c i , i = 1..n} the set of cores of an architecture map : A → C the mapping actors A on cores C Output: {M EG i , i = 1..n} the memory-specific MEGs associated to c i ∈ C M EG S the MEG associated to shared memory 1 if HETEROGENEOUS MEMORY then EG S ← M EG 0 3 for each a ∈ A do M EG S .M ← M EG S .M \ m(a) endfor 4 else EG S ← ∅ 6 endif 7 for eachc i ∈ C do EG i ← M EG 0 9 for each a ∈ A do 10 if map(a) = c i then EG i .M ← M EG i .M \ m(a)Algorithm 2 for c i , M EG i , and M EG S 15 for each f ∈ F with m(f ) / ∈ M merged do 16 if DISTRIBUTED MEMORY then 17 if map(prod(f )) = c i and map(cons(f )) = c i then 18

Fig. 6 .

 6 Fig. 6. Memory-specific MEGs: Distributed scenario

Fig. 7 .

 7 Fig. 7. Memory-specific MEGs: Heterogeneous scenario

ALGORITHM

11 M 17 M 24 M 1 )

 1117241 EG i .M ← M EG i .M \ m merged 12 for each range r ∈ R do 13 mnew ← new memory object of size r.length 14 for each m k ∈ M accessed with [off k , off k + w(m k )[∩r = ∅ do 15 Merge m k within mnew with offset (off k -r.start) 16 endfor EG i .M ← M EG i .M ∪ {mnew} 18 endfor 19 else if HETEROGENEOUS MEMORY then 20if ∀m k ∈ m merged , 21 map(prod(f (m k ))) = map(cons(f (m k ))) = c i then 22 M EG S .M ← M EG S .M \ {m merged } 23 else EG i .M ← M EG i .M \ {m merged } MergedBuffers and Distributed Memory: When targeting distributed memory, Lines 3 to 10 of Algorithm 2 are used to identify which ranges of bytes R of the current buffer m merged ∈ M merged are accessed by actors mapped on core ci. At the end of this loop, R may contain zero, one or several non-contiguous ranges of bytes of m merged accessed by ci, and M accessed contains the set of buffers merged within m merged that are accessed by ci.Lines 12 to 18 of Algorithm 2 create a new memory object mnew for each non-contiguous range of bytes r ∈ R accessed by core ci. All buffers in M accessed whose offset off k in m merged overlaps with the current range of bytes r are merged within the new memory object at Line 22. Only new memory objects mnew are kept in M EGi, the processed buffer m merged is removed from M EGi at Line 11.

Fig. 8 .

 8 Fig. 8. Merged buffers: Distributed scenario

Fig. 9 .

 9 Fig. 9. Merged buffers: Heterogeneous scenario

  .

Fig. 11 .

 11 Fig. 10. Sobel application memory footprints

2 :

 2 Preprocess merged buffers Input: c i a core of the architecture M EG i the MEG associated with c i M EG S the MEG associated with shared memory Output: Updated M EG i and M EG S 1 for each m merged ∈ M EG i .M merged do // byte ranges of m merged accessed by

	2	if DISTRIBUTED MEMORY then
	3	R ← ∅

  . For each application, the number of actors |A| and FIFOs |F | of the original and single-rate SDF graphs are presented as well as the number of memory objects |M | and the number of exclusions |E| of the original MEG.

		SDF graph Single-rate	MEG
	Application |A| |F | |A| |F | = |M |	|E|
	Sobel	6	7	29	36	524
	Stereo	28	42 320	1067 310230
			TABLE I
		PROPERTIES OF THE TEST GRAPHS

  Table II shows the resulting performance of the Sobel and Stereo applications. In this table, performance is expressed as the number of frames per second (fps) processed by the applications. Columns No cache and L1 cache give the performance of applications when the private L1 caches are deactivated and activated, respectively.

			Performance
	Application Archi.	Caches off Caches on
	Sobel	Shared	1.08 fps	12.39 fps
		Hetero	5.18 fps	12.66 fps
	Stereo	Shared	0.40 fps	2.50 fps
		Hetero	0.54 fps	2.97 fps
		TABLE II
		APPLICATION PERFORMANCE


Maxime Pelcat

Karol Desnos

Luca Maggiani

Yanzhou Liu

Julien Heulot

Jean-Franc ¸ois Nezan

Shuvra S Bhattacharyya

Models of Architecture: Reproducible Efficiency Evaluation for Signal Processing Systems

The current trend in high performance and embedded signal processing consists of designing increasingly complex heterogeneous hardware architectures with non-uniform communication resources. In order to take hardware and software design decisions, early evaluations of the system non-functional properties are needed. These evaluations of system efficiency require high-level information on both the algorithms and the architecture. In this paper, we define the notion of Model of Architecture (MoA) and study the combination of a Model of Computation (MoC) and an MoA to provide a design space exploration environment for the study of the algorithmic and architectural choices. A cost is computed from the mapping of an application, represented by a model conforming a MoC onto an architecture represented by a model conforming an MoA. The cost is composed of a processing-related part and a communicationrelated part. It is an abstract scalar value to be minimized and can represent any non-functional requirement of a system such as memory, energy, throughput or latency.

I. INTRODUCTION

In the 1990s, models of parallel computation such as the ones surveyed by Maggs et al. in [START_REF] Maggs | Models of parallel computation: A survey and synthesis[END_REF] were designed to represent a system including hardware and software-related features. Since the early 2000s, rapid prototyping initiatives such as the Algorithm-Architecture Matching (AAA) methodology [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF] have fostered the separation of algorithm and architecture models in order to automate design space exploration.

Models of Computation (MoCs) and especially dataflow MoCs are currently gaining popularity for the design of stream processing systems [START_REF] Bhattacharyya | Handbook of signal processing systems[END_REF]. Their popularity comes from their capacity to model a parallel application and to guarantee (under certain conditions) functional properties such as deadlock-freeness and memory boundedness while ignoring hardware concerns (instruction set, number of processing elements, etc.).

Modern hardware processing systems are a combination of nonequivalent processing and communication resources, referred to as heterogeneous Multiprocessor Systems-on-Chips (MPSoCs) [START_REF] Mazo | Programming Heterogeneous MP-SoCs[END_REF]. The design and programming costs of heterogeneous MPSoCs are constantly rising, because the improvement of programming efficiency is slower than the increase of system complexity. This phenomenon is known as software and hardware productivity gaps [START_REF] Mazo | Programming Heterogeneous MP-SoCs[END_REF]. In MPSoCs, different sources of heterogeneity arise such as different types of processing units, Non Uniform Memory Access (NUMA) and different types of interprocessor communication (IPC). A unique MoC model is thus unable to represent the properties of an application and the resources of the hardware platform.

In this paper, the notion of Model of Architecture (MoA) is introduced. The main goal of an MoA is to offer standard, reproducible ways to evaluate the efficiency of design decisions. Reproducibility signifies that the model alone, without an associated implementation, is sufficient to reproduce the cost computation. One may note a difference between system performance and system efficiency. In computer science, and considering an application alone, performance is often a synonym of throughput [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF] [START_REF] Bambha | Intermediate representations for design automation of multiprocessor DSP systems[END_REF]. However, signal processing system design requires decisions based on many non-functional costs such as memory, energy, throughput, latency, or area. These costs can be seen as the different modalities of a system's efficiency. In order to evaluate these non-functional costs, an MoA models the internal behavior of an architecture at a high level of abstraction.

Modern streaming applications such as telecommunication, video processing, or deep learning, require a great amount of computation. An early evaluation of the system efficiency is a valuable tool for system designers, as shown by company products such as Poly-Platform from PolyCore Software, Inc., SLX Explorer from Silexica or Pareon from Vector Fabrics whose objectives include providing early performance numbers to the designers. These tools have internal performance models but no standard approach is shared between them. MoAs complement the work on MoCs in providing precise semantics for the second input of the Y-chart [START_REF] Kienhuis | An approach for quantitative analysis of application-specific dataflow architectures[END_REF]. The Y-chart separates the description of an application from the one of an architecture, as illustrated in Figure 1 where algorithm descriptions, conforming to a precise MoC are combined with architecture descriptions conforming to an MoA. The paper is organized as follows: Section II presents state of the art MoCs for parallel computation. Section III introduces the notion of MoA and Section IV proposes a new MoA named Linear System-Level Architecture Model (LSLA). Section VI demonstrates systematic, reproducible cost computation from algorithm and architecture models.

II. STATE OF THE ART OF MOCS

The objective of this paper is to sketch the contours of MoAs as the architectural counterparts of MoCs, thereby helping to bridge the increasing gap between MoC-based application design, and platformbased hardware/software implementation. This section introduces a few representative MoCs that are relevant to signal processing system design. These MoCs will be used in Section VI to demonstrate the proposed LSLA MoA.

Many MoCs have been designed to represent the behavior of a system. The Ptolemy II project [START_REF] Eker | Taming heterogeneity-the ptolemy approach[END_REF] has had a considerable influence in promoting MoCs with precise semantics and different forms. Different families of MoCs exist such as finite state machines, process networks, Petri nets, synchronous MoCs and functional MoCs. This paper leverages on both dataflow MoCs and the Bulk Synchronous Parallel (BSP) MoC for their capacity to represent parallel computations, and their relevance to signal processing system design. Section II-A presents static and dynamic dataflow models while Section II-B introduces the BSP MoC.

A. Dataflow MoCs

A dataflow MoC represents a streaming application with a graph where vertices, named actors, represent computation and exchange data through First In, First Out data queues (FIFOs). The unitary exchanged data is called a data token. Computation is triggered when the data present on the input FIFOs of an actor respect its firing rules. Dozens of different dataflow MoCs have been explored [START_REF] Yviquel | From dataflow-based video coding tools to dedicated embedded multi-core platforms[END_REF] and this diversity of MoCs demonstrates the benefit of precise semantics and reduced model complexity.

1) The Synchronous Dataflow (SDF) MoC: Synchronous Dataflow (SDF) [START_REF] Lee | Synchronous data flow[END_REF] is the most commonly used dataflow MoC [START_REF] Lee | Dataflow process networks[END_REF]. SDF has a limited expressivity and an extended analyzability. Production and consumption token rates set by firing rules are fixed scalars in an SDF graph and for that reason, SDF is commonly called a static dataflow MoC.

Static analysis can be applied on an SDF graph to determine whether or not fundamental consistency and schedulability properties hold. Such properties, when they are satisfied, ensure that an SDF graph can be implemented with deadlock-free execution and FIFO memory boundedness.

An SDF graph (Figure 2) is defined as G = A, F where A is the set of actors, and F is the set of FIFOs. For an SDF actor, a fixed integer-valued data rate is set for each port by the function rate : P in data ∪ P out data → N * where P in data is the set of input ports, P out data is the set of output ports for an actor and N * is the set of strictly positive integers. A delay d : F → N is set for each FIFO f ∈ F , corresponding to a number of tokens initially present in the FIFO F . N refers to the set of non negative integers. If an SDF graph is consistent and schedulable, a fixed sequence of actor firings, called a graph iteration, can be repeated indefinitely to execute the graph, and there is a well defined concept of a minimal sequence for achieving an indefinite execution with bounded memory.

The notion of graph iteration will be used to compute the cost of mapping an SDF algorithm model on an LSLA architecture model in Section VI-A.

2) The Enable-Invoke Dataflow (EIDF) and Core Functional Dataflow (CFDF) MoCs: EIDF is a highly expressive form of dataflow MoC that is useful as a common basis for implementing and analyzing a wide variety of specialized dataflow MoCs [START_REF] Plishker | Heterogeneous design in functional DIF[END_REF]. While specialized models such as SDF are useful for exploiting specific characteristics of targeted application domains, the more flexibly-oriented MoC EIDF is useful for interfacing different forms of dataflow and providing tool support that spans heterogeneous systems.

In EIDF, the behavior of an actor is decomposed into a set of actor modes such that each actor firing operates according to a given mode. At the end of each actor firing, the actor determines a next mode set, which specifies the set of possible modes according to which the next actor firing can execute. The dataflow behavior (production or consumption rate) for each actor port is constant for a given actor mode. However, the dataflow behavior for the same port can differ for different modes of the same actor, which allows for specification of dynamic dataflow behavior. An EIDF graph is defined as G = A, F and notations used to denotes actors, FIFOs, and data ports are identical to these defined in SDF.

In this paper, we focus on a restricted form of EIDF called core functional dataflow (CFDF) (Figure 3a). CFDF requires the next mode set that emerges from any firing to contain exactly one element [START_REF] Plishker | Functional DIF for rapid prototyping[END_REF], ensuring model determinacy. The unique actor mode within the next mode set of a CFDF actor firing is referred to as the next mode associated with the firing. Dataflow attributes of a CFDF actor are characterized by a dataflow table (Figures 3b and3c). The rows of the table correspond to the different actor modes, and the columns correspond to the actor ports. Given a CFDF actor A, we denote the dataflow table for A by TA. If m is a mode of A and p is an input port of A, then TA[m][p] = -κ(m, p), where κ(m, p) is the number of tokens consumed from p in mode m. Similarly, if q is an output port of A, then TA[m][q] = ρ(m, q), where ρ(m, q) is the number of tokens produced onto q in mode m. Mode transition for a CFDF actor is represented by a mode transition graph (Figures 3d and3e). Given a CFDF actor A, the mode transition graph for A, denoted MTG(A) is a directed graph in which the vertices corrspond to the modes of A. The edge set of MTG(A) can be expressed as {(x, y) ∈ VA × VA | y ∈ µA(x)}, where VA represents the set of vertices in MTG(A), and µA(x) is the set of possible next modes for actor x. While production and consumption rates for CFDF actor modes cannot be data-dependent, the next mode can be datadependent, and thus, µA(x) can have any number of elements up to the number of modes in A.

X Y

Port:p 1 Port:p 2 A Actor FIFO (a) Example of a CFDF graph. Mode p1 1 2 1 2 (b) Dataflow table for X. Mode p 2 -1 -4 1 2 (c) Dataflow table for Y. M(X,1) M(X,2) M(X,1) M(X,2) (d) Mode transition graph for X. M(Y,1) M(Y,2)
(e) Mode transition graph for Y. The combination of the CFDF MoC and the LSLA MoA to compute an efficiency cost will be discussed in Section VI-B.

B. The Bulk Synchronous Parallel MoC

Another example of a MoC for parallel computation is the Bulk Synchronous Parallel (BSP) [START_REF] Valiant | A bridging model for parallel computation[END_REF] MoC. BSP analyzes an application into several phases called supersteps. A BSP computation is composed of a set of components A called agents in this paper to distinguish them from the Processing Elements (PEs) in an MoA. Each agent α ∈ A has its own memory. An agent α can access the memory of another agent β through a remote access (message) r(α, β) via a so-called router. Application execution happens in a series of supersteps indexed by σ ∈ N and consisting of processing efforts, remote accesses and a global synchronization s(σ) (Figure 4).

α Agent α β γ δ ε

Memory

Router time

Remote access

Superstep A lower bound for the time of a superstep is computed by:

α 1 β 1 γ 1 δ 1 ε 1 α 2 β 2 γ 2 δ 2 ε 2 α 3 β 3 γ 3 δ 3 α 1 Firing of A in superstep 1 Synchronization ε 3
Tσ = max 0≤α<card(A) w(ασ) + hσ × g + s (1)
where card(A) is the number of agents, g is the time to execute one atomic remote transfer, and s is a fixed synchronization time.

A superstep has a discrete length n × L with n ∈ N and L the minimal period of synchronization. Smaller values of L in general lead to superstep times that are closer to the corresponding lower bounds. The BSP execution cost computation is limited to latency and assumes that communication costs for an agent are additive. The combination of the BSP MoC and the LSLA MoA to compute an efficiency cost will be explained in Section VI-C. Each one of the previous MoCs is characterized by a specific set of properties such as their expressiveness, dynamicity, analyzability, or their decidability. Depending on the complexity and constraints of the modeled application, a simple SDF representation or a more complex CFDF or BSP representation may be chosen. MoCs, by nature, do not carry hardware related information such as resource limitations and hardware efficiency. In this paper, we propose the concept of MoA to complement MoCs in the process of design space exploration.

III. DEFINITION OF MODELS OF ARCHITECTURE (MOAS)

Definition 1. A Model of Architecture (MoA) is an abstract efficiency model of a system architecture that provides a unique, reproducible cost computation, unequivocally assessing a hardware efficiency cost when processing an application described with a specified MoC.

An MoA does not need to reflect the real hardware architecture of the system. It only aims to represent its efficiency at a coarse grain. As an example, a complete cluster of processors in a manycore architecture may be represented by a single Processing Element (PE) in its MoA representation, hiding the internal structure of this PE. MoAs are intended to be used at a high level of abstraction where hardware, operating system and middleware may be abstracted together. MoAs can be used at all stages of the system design process, from early steps (e.g. to define how many hardware coprocessors are necessary) to late steps (e.g. to optimize runtime scheduling). In addition to classical information such as processor frequency, number of cores or memory architecture, an MoA can give information on physical properties such as energy consumption and temperature dissipation.

In the next section, a new MoA is proposed and named LSLA. This model is providing simple semantics for computing an abstract cost from the mapping of an application described with a precise MoC.

IV. THE LINEAR SYSTEM-LEVEL ARCHITECTURE MODEL (LSLA) MOA

A. Definitions

As an MoA, LSLA provides reproducible cost computation when the activity A of an application is mapped on the architecture. Three application-related notions are required prior to the definition of LSLA: application activity, quanta and tokens. These notions are necessary because they make LSLA independent from the chosen MoC.

Definition 2. The application activity A represents the amount of processing and communication necessary for accomplishing the requirements of the application. Definition 3. A quantum q is the smallest unit of application activity. There are two types of quanta: processing quantum qP and communication quantum qC .

Two distinct instances of processing quanta are equivalent in the sense that they represent the same amount of computational activity. Processing and communication quanta do not share the same unit of measurement. As an example, in a system with a unique clock and Byte addressable memory, 1 cycle of processing can be chosen as the processing quantum and 1 Byte as the communication quantum. Definition 4. A token τ ∈ TP ∪ TC is a non-divisible unit of application activity, composed of a number of quanta. The function size : TP ∪ TC → N associates to each token the number of quanta composing the token. There are two types of tokens: processing tokens τP ∈ TP and communication tokens τC ∈ TC .

The activity A of an application is defined by the set:

A = {TP , TC } (2)
where TP = {τ 1 P , τ 2 P , τ 3 P ...} is the set of tokens composing the application processing and TC = {τ 1 C , τ 2 C , τ 3 C ...} is the set of tokens composing the application communication.

An example of a processing token can be a run-to-completion task. It is composed of N processing quanta (for instance, N cycles). An example of a communication token is a message in a message passing system. It is composed of M communication quanta (for instance M Bytes). Using the two levels of granularity of a token and a quantum, the LSLA MoA can reflect the cost of managing a quantum and the overhead of managing a token composed of several quanta. Definition 5 formally defines the LSLA model, illustrated in Figure 5. Definition 5. The Linear System-Level Architecture Model (LSLA) is a Model of Architecture (MoA) that consists of a four-tuple M = (G, L, cost, λ). Here, G = (P, C) is an undirected graph where P is the set of abstract architecture Processing Elements (PEs) and C is the set of architecture Communication Nodes (CNs). A processing token τP must be mapped to a PE p ∈ P to be executed. A communication token τC must be mapped to a CN c ∈ C to be transferred. L = (ni, nj), ni ∈ C, nj ∈ C ∪ P is a set of undirected links connecting either two CNs or one CN and one PE. A link models the capacity of a CN to communicate tokens to/from a PE or to/from another CN.

Link

PE Processing Element

The element of G denoted as "cost" is a function associating a cost to different elements. The cost related to the management of a token τ by a PE or a CN is defined by:

cost : TP ∪ TC × P ∪ C → R τ, n → αn.size(τ ) + βn, αn ∈ R, βn ∈ R (3)
where αn is the fixed cost of a quantum when executed on n and βn is the fixed overhead of a token when executed on n. A token communicated between two PEs connected with a chain of CNs Γ = {x, y, z...} is reproduced card(Γ) times and each occurrence of the token is mapped to 1 element of Γ. This procedure is explained on different exemples in Section VI. A token not communicated between two PEs, i.e. internal to one PE, does not cause any cost.

The cost of the execution of application activity A on an LSLA model M is defined as:

cost(A, M ) = τ ∈T P cost(τ, map(τ )) + λ τ ∈T C cost(τ, map(τ )) (4)
where map : TP ∪ TC → P ∪ C is a surjective function returning the architecture elements where a token is mapped.

λ ∈ R is a lagrangian coefficient setting the Computation to Communication Cost Ratio (CCCR), i.e. the cost of a single communication quantum relative to the cost of a single processing quantum. The concept of MoA is evoked in [START_REF] Kienhuis | A methodology to design programmable embedded systems[END_REF] where it is defined as "a formal representation of the operational semantics of networks of functional blocks describing architectures". This definition is very broad, and allows the concepts of MoC and MoA to overlap. As an example, an SDF graph representing a fully specialized system may be considered as a MoC because it formalizes the application. It may also be considered as an MoA because it fully complies with the definition from [START_REF] Kienhuis | A methodology to design programmable embedded systems[END_REF]. This is in contrast to the orthogonalization between MoC and MoA representations that is supported in our proposed modeling framework. Moreover, contrary to the definition from [START_REF] Kienhuis | A methodology to design programmable embedded systems[END_REF], our proposed definition of MoA does not compel the MoA to match the internal structure of the hardware architecture, as long as the generated cost is of interest.

V. RELATED WORK ON MOAS

Table I references architecture models of abstract heterogeneous parallel architectures. An evaluation of the level of abstraction of each model is given, as well as some properties.

UML Marte [START_REF]A UML Profile for MARTE: Modeling and Analysis of Real-Time Embedded Systems[END_REF] is a system modeling standard offering a holistic approach encompassing all aspects of real-time embedded systems. The standard consists of Unified Modeling Language (UML) classes and stereotypes. As a specification language, UML Marte does not standardize how a cost should be derived from the specified hardware resources and non-functional properties. In contrast, an MoA focuses on reproducible cost computation.

The Architecture Analysis and Design Language (AADL) language [START_REF] Feiler | The architecture analysis & design language (AADL): An introduction[END_REF] defines a syntax and semantics to describe both software and hardware components. The language constructs match logical and physical features such as threads and processes for software and bus and memory for hardware. In contrast, MoAs offer abstract features for describing hardware architectures and delegate responsibility for modeling algorithms to MoCs.

Castrillón and Leupers define in [START_REF] Mazo | Programming Heterogeneous MP-SoCs[END_REF] a quasi-MoA that divides an architecture into PEs. Each PE has a specific Processor Type (PT) associated to multiple costs and attributes such as context switch time and resource limitations. A graph G of PEs is defined where each edge interconnecting a pair of PEs is associated to a Communication Primitive (CP), i.e. a software application programming interface that is used to communicate among tasks. A CP refers to a refers to a Communication Resource (CR) and has its own cost model associating different costs to communication volumes taking into account the number of channels and, the amount of available memory in the module, etc. This model is refered to as a quasi-MoA because it does not specify the cost computation procedure from the data provided in the model.

In [START_REF] Kianzad | CHARMED: A multi-objective cosynthesis framework for multi-mode embedded systems[END_REF], Kianzad and Bhattacharyya present the CHARMED framework that aims at optimizing multiple system parameters represented in pareto fronts. CHARMED uses an MoA composed of a set of PEs and Communication Resources (CR). Each PE has an attribute vector including processor area, processor price, data memory size, instruction memory size, and power consumption. Each CR also has a vector of attributes including power consumption and transmission speed. This model constitutes, to our knowledge, the only existing MoA as stated by Definition 1. Compared to LSLA, the model in [START_REF] Kianzad | CHARMED: A multi-objective cosynthesis framework for multi-mode embedded systems[END_REF] is more complex and does not abstract the computed cost, limiting the model to the defined metrics.

In [START_REF] Grandpierre | Un nouveau modèle générique d'architecture hétérogène pour la méthodologie AAA[END_REF], Grandpierre and Sorel define a graph-based quasi-MoA for message passing and shared memory data transfer simulations of heterogeneous platforms. Memory sizes and bandwidths are taken into account in the model. This model can also be considered as a quasi-MoA because the cost computation procedure is not specified.

In [START_REF] Raffin | Scheduling, binding and routing system for a run-time reconfigurable operator based multimedia architecture[END_REF], Raffin et. al, describe a quasi-MoA for evaluating the performance of a Coarse Grain Reconfigurable Architectures (CGRAs). The model is customized for a processor type named ROMA and based on a graph representing PEs, memories, a network connecting PEs to memories, and a network interconnecting PEs. The model contains memory sizes, network topologies and data transfer latencies. The objective of the model is to provide early estimations of the necessary resources to execute a dataflow application. Contrary to [START_REF] Raffin | Scheduling, binding and routing system for a run-time reconfigurable operator based multimedia architecture[END_REF], LSLA abstracts the computed cost and provides a reproducible cost computation procedure.

The System-Level Architecture Model (S-LAM) [START_REF] Pelcat | A system-level architecture model for rapid prototyping of heterogeneous multicore embedded systems[END_REF] quasi-MoA focuses on timing properties of a distributed system and defines communication enablers such as Random Access Memory (RAM) and Direct Memory Access (DMA). S-LAM is focused on time modeling and does not provide reproducible cost computation.

Compared to all models except [START_REF] Kianzad | CHARMED: A multi-objective cosynthesis framework for multi-mode embedded systems[END_REF], LSLA is the only model that abstracts the type of the computed implementation cost. By its flexibility and low complexity, LSLA is intended to be used both (a) early in the system design process, when high modeling accuracy is not needed, and (b) post-deployment for runtime management decisions, when the decision processing budget is limited. The next sections illustrate the cost computation provided by LSLA when combined with SDF, CFDF, and BSP MoCs (Section II).

VI. COMPUTING THE COST OF AN APPLICATION EXECUTION ON

AN LSLA ARCHITECTURE A. Computing the cost of an SDF application execution on an LSLA architecture 4). The cost unit depends on the type of cost represented by the model.

The cost computation mechanism of the LSLA MoA is illustrated by an example in Figure 6 combining an SDF application model and an LSLA architecture model. The scope chosen for the cost computation of a couple (SDF, LSLA), provided that the SDF graph is consistent, is one SDF graph iteration (Section II-A1). Each actor firing is transformed into one processing token and each dataflow token is transformed into one communication token. A token is embedding several quanta (Section IV), allowing a designer to describe heterogeneous tokens to represent firings and data of different weights. In Figure 6, each firing of actor A1 is associated with a cost of 3 quanta and each firing of actor A2 is associated to a cost of 4 quanta. Communication tokens represent 2 quanta each.

Each processing token is mapped to one PE (A, B, C or D). Communication tokens are "routed" to the CNs connecting their producer and consumer PEs. For instance, the second communication token in Figure 6 is generating 3 tokens mapped to CNs x, y, and z because the data is carried from PE C to PE B. Since a multiplication by λ = 0.3 brings the cost of communication tokens to the processing domain, the total cost for communication would be 0.3 × (2 + 2 + 20 + 2) = 7.8. The resulting cost from Equation 4 is 66.8. This cost is reproducible and abstract, making LSLA an MoA.

B. Computing the efficiency of a CFDF application execution on an LSLA architecture

Using dynamic dataflow models such as CFDF, a simulation-based integration is a natural way to apply MoA-driven cost computation since there is in general no standard, abstract notion of an application iteration -i.e., no notion that plays a similar role as the periodic schedules of consistent SDF graphs. Figure 7 illustrates an example of execution of a CFDF dataflow graph on an LSLA architecture. We define the cost of execution of actor X in mode M (X, 1) to be 3 quanta and the cost of execution of actor X in mode M (X, 2) to also be 3 quanta. Similarly, the cost of execution of actor Y in mode M (Y, 1) is 2 quanta and the cost of execution of actor Y in mode M (Y, 2) is 4 quanta. These choices represent additional information associated with the CFDF MoC. The cost of communication tokens on the FIFO is set to 2 quanta. We can then compute a cost for every PE and CN. There are 2 actor tokens mapped to PE A. Each of them has 3 quanta. The cost for PE A is 2 × (3 × 10 + 1) = 62. There are 2 actor tokens mapped to PE B representing 2 and 4 quanta respectively. The cost for PE B is 1 × (2 × 5 + 1) + 1 × (4 × 5 + 1) = 32. There is 1 actor token mapped to PE C representing 3 quanta. The cost for PE C is 1 × (3 × 2 + 1) = 7. There are 5 communication tokens mapped to CN x. Each of them has 2 quanta. Therefore, the cost for CN x is 5×(2×1) = 10. Similarly, the cost of y is 1×(2×10) = 20 and the cost of z is 1 × (2 × 1) = 2. The obtained cost is the summation of all PEs' costs and CNs' costs multiplied by λ, which in this example sums up to 62 + 32 + 9.6 + 7 = 110.6.

C. Computing the efficiency of a BSP application execution on an

LSLA architecture α β γ δ ε α 1 β 1 γ 1 δ 1 ε 1 α 2 β 2 γ 2 δ 2 ε 2 α→γ β→ε δ→α ε→δ ε→β β→γ α→β ε→γ ε→δ α 1 β 1 γ 1 δ 1 ε 1 α 2 β 2 γ 2 δ 2 ε 2 time σ=1 processing σ=1 communication σ=2 communication σ=2 processing
Fig. 8: Extracting the activity of a BSP model.

Figures 8 and9 illustrate the cost computation of the execution of a BSP algorithm on an LSLA architecture. Figure 8 displays the extraction of the activity from the BSP description, where each processing effort ασ is transformed into one processing token consisting of w(ασ) quanta (Section II-B) and each (atomic) remote access is transformed into one communication token of one quantum. Figure 9 shows the mapping and pooling of tokens, consisting of associating tokens to PEs and CNs and replicating communication tokens to route the communications. Agents α and β are mapped on core B, agent γ is mapped on core A, agent is mapped on core C and agent δ is mapped on core D. The global cost is computed as the sum of the cost of each token on its PE or CN. The communication token α → β is ignored because it is communicating a token between two agents mapped on the same PE and such a communication has no cost in LSLA, because there is no remote access. The abstract cost of 144.6 is obtained for this couple (BSP, LSLA) and, as for SDF and CFDF MoCs, this cost is reproducible as long as the activity extraction from the BSP model follows the same conventions. When compared to using BSP alone, combining BSP and LSLA helps in studying the cost of mapping multiple agents on a single PE -for example, to understand the potential to exploit slack and balance activity between PEs.

D. Discussion on LSLA cost computation

In previous sections, the cost computation mechanisms of LSLA have been demonstrated on static SDF dataflow, dynamic CFDF dataflow and BSP MoCs. The generic and reproducible cost computation of LSLA make LSLA an MoA. While CNs with high cost (such as y in Figure 9) represent bottlenecks in the architecture, i.e. communication media with low data rates, PEs with high cost (such as A in Figure 9) represent processing facilities with limited processing efficiency. Each PE can indifferently model a General Purpose (GPP), a Graphics Processing Unit (GPU), or a Digital Signal Processor (DSP) core executing software as well as a hardware component implemented on a Field-Programmable Gate Array (FPGA) or an Application-Specific Integrated Circuit (ASIC).

VII. CONCLUSION

High performance and embedded signal processing systems require increasingly heterogeneous architectures. Reproducible models are necessary in order to model reliably system-level efficiency. In this paper, the notion of Model of Architecture (MoA) has been defined.

An MoA models the behavior of an architecture at a high level of abstraction. When combined to an application model conforming to a given MoC, an architecture model conforming to an MoA provides reproducible cost computation mechanisms for evaluating non-functional system properties such as memory, energy, throughput, etc.

An MoA called Linear System-Level Architecture Model (LSLA) has been introduced and compared to the state of the art of architecture models. LSLA represents hardware efficiency with a linear model, summing the influences of processing and communication on system efficiency.

In future publications, we intend to demonstrate the capabilities of different MoAs to feed efficiency evaluations of systems, optimizing various non-functional properties.

Fig. 1 :

 1 Fig. 1: MoC and MoA in the Y-chart [7].

Fig. 2 :

 2 Fig. 2: Example of an SDF Graph.

Fig. 3 :

 3 Fig. 3: Dataflow attributes of an example CFDF graph.

Fig. 4 :

 4 Fig. 4: Example of a BSP Representation. Each agent α executes in the superstep σ the processing effort ασ, requiring a time w(ασ) ∈ N. During the superstep σ, an agent sends or receives at most hσ remote accesses, each access transferring one atomic data from one agent to another. A barrier synchronization follows each superstep, ensuring global temporal coherency before starting the superstep σ + 1.A lower bound for the time of a superstep is computed by:

10x+1

  Per token cost (x=# of quanta)

Fig. 5 :

 5 Fig. 5: LSLA MoA semantics elements.

Fig. 6 :

 6 Fig. 6: Computing the cost of executing an SDF graph on an LSLA architecture. The obtained cost for 1 iteration is 31 + 21 + 0.3 (2 + 2 + 20 + 2) + 7 = 66.8 (Equation4). The cost unit depends on the type of cost represented by the model.

Fig. 7 :

 7 Fig. 7: Computing the cost of executing a CFDF graph on an LSLA architecture. The obtained abstract cost for the chosen simulation scope is 62 + 32 + 0.3 (10 + 20 + 2) + 7 = 110.6.

Fig. 9 :

 9 Fig. 9: Computing the cost of executing the BSP model in Figure 8 on an LSLA architecture. The obtained abstract cost is 31 + 31 + 11 + 11 + 11 + 6 + 0.3 (6 + 40 + 6) + 7 + 5 + 11 + 5 = 144.6 (Equation4).

TABLE I :

 I Properties of different state of the art architecture models.