Kevin J M Martin
email: kevin.martin@univ-ubs.fr

Twenty Years of Automated Methods for Mapping Applications on CGRA

Keywords: CGRA, Mapping, Compilation

Reconfigurable Architectures (CGRAs) emerged about 30 years ago. The very first CGRAs were programmed manually. Fortunately, some compilation approaches appeared rapidly to automate the mapping process. Numerous surveys on these architectures exist. Other surveys also gather the tools and methods, but none of them focuses on the mapping process only. This paper focuses solely on automated methods and techniques for mapping applications on CGRA and covers the last two decades of research. This paper aims at providing the terminology, the problem formulation, and a classification of existing methods. The paper ends with research challenges and trends for the future.

Fig. 1. Architecture comparison proposed in [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF] architectures is simply tremendous and undoubtedly, CGRAs still keep a wide unexplored area. From its reconfigurable features, CGRAs are a key member of the reconfigurable computing family. Figure 1 shows the ideal trade-off between flexibility, performance, and energy efficiency that CGRAs offer compaired with other architectures.

Making an inventory of existing CGRAs is a complex and time consuming task that has been successfully done in the past [START_REF] Hartenstein | A decade of reconfigurable computing: A visionary retrospective[END_REF], [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF], [START_REF] Theodoridis | A Survey of Coarse-Grain Reconfigurable Architectures and Cad Tools[END_REF]- [START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF]. Fortunately, the newcomer in the domain can restrict to reading only few papers to acquire a nice overview. The Hartenstein's paper surveys the first decade of reconfigurable computing [START_REF] Hartenstein | A decade of reconfigurable computing: A visionary retrospective[END_REF]. In 2010, De Sutter et al. published a book chapter detailing the architecture features of a CGRA [START_REF] Sutter | Coarse-Grained Reconfigurable Array Architectures[END_REF]. Wijtvliet et al. review 25 years of CGRAs in 2016 [START_REF] Wijtvliet | Coarse grained reconfigurable architectures in the past 25 years: Overview and classification[END_REF]. The most recent surveys are provided by Liu et al. [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF] and Podebas et al. [START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF]. Liu et al. [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF] suggest another classification, complementary to the ones proposed in the previous surveys. Podebas et al. interestingly gather the published CGRAs from a performance perspective [START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF], and highlights by figures what is commonly accepted: CGRAs are serious competitors to GPGPUs1 . These two last surveys point out the severe limitations that CGRAs meet like the unadapted programming model.

The abovementioned papers focus on the architectures. In order to make use of the abondant number of processing elements available, a CGRA must come along with a compiler. The very early CGRAs were programmed manually, i.e. at assembly level [START_REF] Heysters | Mapping of dsp algorithms on the montium architecture[END_REF]. These first steps were important to understand how to program such an architecture and describe a systematic method that can then be automated. The automated process of programming a CGRA from a high level language falls in the compilation category. The backend part, responsible for defining the use of the hardware resources is called application mapping.

An inventory of existing mapping techniques has also been done in the past [START_REF] Theodoridis | A Survey of Coarse-Grain Reconfigurable Architectures and Cad Tools[END_REF], [START_REF] Choi | Coarse-grained reconfigurable array: Architecture and application mapping[END_REF], [START_REF] Cardoso | Compiling for reconfigurable computing: A survey[END_REF]. Theodoridis et al. present the CAD tools along with the CGRAs up to 2007 [START_REF] Theodoridis | A Survey of Coarse-Grain Reconfigurable Architectures and Cad Tools[END_REF]. In 2011, Choi [START_REF] Choi | Coarse-grained reconfigurable array: Architecture and application mapping[END_REF] wrote a survey that combines both architecture and application mapping. These papers present first the architecture, and their associated mapping flow individually. In [START_REF] Cardoso | Compiling for reconfigurable computing: A survey[END_REF], a survey on compiling for reconfigurable computing architectures covers the broad range of reconfigurable computing, including FPGAs, up to 2010. The common features in the compiler are described, and then some dedicated compilers are presented. This paper focuses on automated methods for mapping on CGRAs only, includes the last decade of research on that topic, and proposes a classification. From the early first papers [START_REF] Bondalapati | Mapping loops onto reconfigurable architectures[END_REF]- [START_REF] Lee | Compilation approach for coarse-grained reconfigurable architectures[END_REF] to the latest publications on the topic [START_REF] Guo | Formulating data-arrival synchronizers in integer linear programming for cgra mapping[END_REF]- [START_REF] Miyasaka | Satbased mapping of data-flow graphs onto coarse-grained reconfigurable arrays[END_REF], this paper paints a picture of two decades of CGRA mapping.

Before presenting what is the mapping problem and the techniques to solve it, this survey proposes a terminology to clearly state the problem, and extracts a general problem formulation. This paper concludes with the research challenges to be taken up.

II. TERMINOLOGY AND METHODOLOGY

This paper starts with definitions and terminology, that might not be so obvious even for experts of the topic. Defining the terms allows for a newcomer to get familiar with the terms.

A. What a CGRA looks like

Even if this paper focuses on the mapping technique, it presents a typical CGRA and describes its main architectural features, which are essential to introduce in order to understand the mapping problem. Figure 2, taken from [START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF], presents a simple CGRA which contains the minimal components of a basic CGRA. A CGRA is a set of processing elements (PEs), also called reconfigurable cells (RCs), or tile, or functional unit (FU). The term cell might be more generic, as in some CGRAs, the cells are heterogeneous, composed of computation unit, or memory units. This set of cells is usually placed as a two dimensions array, where the cells are interconnected through point to point connections, or more complex topologies. The interested reader is invited to read the dedicated papers for more details [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF], [START_REF] Theodoridis | A Survey of Coarse-Grain Reconfigurable Architectures and Cad Tools[END_REF], [START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF], [START_REF] Wijtvliet | Architectural Model[END_REF]. The key element to highlight is that a CGRA exposes both spatial and temporal parallelism.

B. Terminology and definitions

Array or Architecture? A first ambiguity is the 'A' of CGRA. In the literature, it sometimes stands for "Array", sometimes for "Architecture". Both cases make sense. A CGRA is typically organized around an array of cells, but the word architecture encompasses all kind of organisations, not only array-based. Why reconfigurable? A CGRA is a reconfigurable architecture. As such, it relies on configurations. The term context or control are also commonly found in the literature to mean a configuration. Some authors may even use the term instruction. A newcomer might wonder what is the difference between a configuration, a context, and an instruction of a CGRA. The difference lies in the hardware that allows to reconfigure the architecture. Finally, in all CGRAs, the reconfiguration is a matter of signals that drive multiplexers in a data-path. Therefore, a configuration must hold all the values of a set of signals that select the correct input of a multiplexer. A context is such a structure that contains all the raw values. An instruction can be seen as a condensed representation of a context. An instruction needs to go through a decoder whose outputs drive the multiplexers. Deducing that a processor is a reconfigurable architecture is a precocious conclusion that we cannot draw though. But whether it be a context or an instruction, the importance from the compilation point of view is to know what to produce as the format defines the contract between the hardware and the software to reach a valid execution.

Spatial computation vs. temporal computation. One of the crucial hardware feature that the compiler must know is if the CGRA supports spatial computations or temporal computations [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF]. Spatial computation is very similar to FPGAs. Along with spatial computations that all CGRAs support, temporal computations allow to share in time the hardware resources leading to more flexibility, but are often criticized to reduce the energy efficiency [START_REF] Kojima | Genmap: A genetic algorithmic approach for optimizing spatial mapping of coarse-grained reconfigurable architectures[END_REF].

Compilation. Compilation is an automated process that takes an input source code and transforms it into an equivalent binary code, executable by a given architecture. Fig. 3 shows a typical compilation flow for CGRAs. A compiler is conceptually composed of three main steps: (1) the front-end, in charge of parsing the source code and producing an equivalent intermediate representation (IR), (2) the middle-end, where some optimization passes may occur on the IR2 , and (3) the back-end, responsible for producing the binary code from The specific features of the early CGRAs were hardcoded in their own compiler, some techniques being specific to a very particular hardware and hardly reusable. This is why the previous surveys present individually the compilers [START_REF] Theodoridis | A Survey of Coarse-Grain Reconfigurable Architectures and Cad Tools[END_REF], [START_REF] Choi | Coarse-grained reconfigurable array: Architecture and application mapping[END_REF], [START_REF] Cardoso | Compiling for reconfigurable computing: A survey[END_REF], as they are all tailored to a specific target. Designing a retargetable compiler for CGRAs is still an open issue today. DFG, CDFG. The intermediate representation of a compiler is usually in the form of a graph. A Data Flow Graph (DFG) is a graph whose nodes represent operations and whose edges are the data dependencies between the operations. A DFG is embedded in a basic block, such that a basic block has a single entry and single exit. Fig. 3 shows an example of a DFG inside a basic block (BB3). A Control Flow Graph is a graph whose nodes are basic blocks and whose edges are the control dependencies between the basic blocks. The combination of the two forms a CDFG (Control Data Flow Graph). An application specified in a given language can thus be represented in the form of a graph, where the nodes are the operations, and the edges are the dependencies (control or data).

Binding or placing? The word binding holds the idea to tie things together, whereas placing let think a little freedom about the spatial location. Both terms are equally used in the literature for the same meaning. We choose binding for the rest of this paper.

Routing. The routing defines the physical connections between the computing resources. Routing usually builds on placement. In a CGRA, placement and routing of computing resources are already done. In that context, routing does not mean creating a new route with a physical wire, but use an existing link without interfering with already existing communications using this link.

Scheduling. The scheduling is the method that assigns in time, operations to the hardware resource, while guaranteeing the dependencies.

Mapping. The mapping in the main step in the back-end. The word mapping can designate both the process and the output of the process. For a spatial CGRA, the mapping process amounts to solving the binding problem. For temporal CGRA, the mapping process must solve both binding and scheduling problems. When the problem is solved, the output of the process is a valid mapping, i.e. a binding (and scheduling) of operations of the application on the hardware resources while guaranteeing the dependencies. Fig. 3 shows a spatial mapping and a temporal mapping of a simple dot-product input source code. Spatial mapping is also sometimes referred to as straight forward mapping.

Software pipelining and modulo scheduling. Software pipelining is a general technique for overlapping loop iterations. Modulo scheduling is the most commonly used technique for software pipelining, especially in the CGRA domain. In [START_REF] Sutter | Placementand-routing-based register allocation for coarse-grained reconfigurable arrays[END_REF], the authors define clearly the goal: "The objective of modulo-scheduling is to engineer a schedule for one iteration of a loop such that this same schedule can be initiated at regular, as short as possible, intervals, taking into account data dependences and resource constraints. This interval in terms of cycles is termed initiation interval (II)". The quest of the minimum II is the main motivation of many works. Fig. 3 shows an example of modulo scheduling for the dot-product. The II in the example is one, and the figure clearly shows that two different iterations of the loop are being processed at the same time.

CGRA models. The back-end must know the target architecture in order to fully make use of its specific features. The idea of describing to the compiler the CGRA emerged very early [START_REF] Goldstein | Piperench: A reconfigurable architecture and compiler[END_REF]. In 2002, Mei et al. [START_REF] Mei | DRESC: a retargetable compiler for coarse-grained reconfigurable architectures[END_REF] use an architecture abstraction in the famous DRESC. In 2003, Lee et al. propose a generic architecture template called the dynamically reconfigurable ALU array (DRAA) [START_REF] Lee | Compilation approach for coarse-grained reconfigurable architectures[END_REF]. Since then, the great majority of works considers a model of the CGRA as input of the compilation flow. Recent efforts include non-functional constraints [START_REF] Wijtvliet | Architectural Model[END_REF].

C. Problem formulation

This paper focuses on methods to solve the mapping problem, which combines two NP-complete problems: scheduling and binding. This raises CGRA compilation as a unique scientifique problem and main challenge, because mapping might fail [START_REF] Yoon | A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures[END_REF]- [START_REF] Dave | Ureca: Unified register file for cgras[END_REF], which is of course unconceivable from the user point of view. To this end, for instance, HiMap [START_REF] Wijerathne | Himap: Fast and scalable high-quality mapping on cgra via hierarchical abstraction[END_REF] is an iterative algorithm that terminates when a valid mapping is found. Historically, CGRA mapping is the meeting point between VLIW compilation, and FPGA place-and-route. The difference with VLIW compilation is the direct communication possibilities offered by the CGRAs between the different PEs. VLIW processors share data through a register file only. The difference with FPGA place-and-route is the granularity of the processing elements and a usually less flexible interconnect. A single formalisation of the mapping problem is not possible, as it is specific to the architecture model and the execution model considered. The interested reader can refer to other papers where the authors clearly formalized their problem [START_REF] Yoon | A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures[END_REF], [START_REF] Chen | Graph minor approach for application mapping on cgras[END_REF]. The idea is to give an explanation of the problem, understandable by a newcomer.

A nice definition is given in [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF]: "the mapping of a CGRA is actually equivalent to identifying the spatial and temporal coordinates of every node and arc in the control/data flow graph (CDFG). Compilers are responsible for making this arrangement." We may add that the temporal coordinate system is often called the time extended CGRA (TEC) [START_REF] Hamzeh | EPIMap: using epimorphism to map applications on CGRAs[END_REF], or the time-space graph [START_REF] Sutter | Placementand-routing-based register allocation for coarse-grained reconfigurable arrays[END_REF]. The challenge is reminded by Chen et al. [START_REF] Chen | Graph minor approach for application mapping on cgras[END_REF]: to provide high quality solution with fast compilation time. Thus, the mapping problem can be summarized as follows: bind in place and schedule in time operations of the application on the CGRA while guaranteeing the dependencies and in a short time, such that the application executes as fast as possible.

D. Methodology

This paper is solely based on the information found in the publications available online. The authors of the cited papers have not been contacted for more thorough explanation about the techniques (the lack of space when writing papers forces sometimes the authors to simplify or omit some aspects), and the personal knowledge of the authors of this paper is not used.

The papers cited in this survey have been published in high ranked international conferences or journals. As the ranking is an endless debate, and the ranking is subject to change, the international audience targeted preveals. National conferences or journals, even when the proceedings are written in English, are rarely considered for this survey. There are several strong places of CGRAs all around the world. Some groups have a long history and contributed heavily to the increase of knowledge about the CGRAs and corresponding mapping techniques. Only a subset of papers is cited in this survey.

III. A REVIEW OF MAPPING METHODS

This section presents a round-trip of proposed methods to solving the CGRA mapping problem. As the application is composed of data-flow parts, and control-flow parts, some methods have been devised specifically for each part. The section ends with an overview of the scientific production of the last two decades.

A. Data-flow mapping

All the works cited in this paper propose a technique to map the data-flow part of an application. Some methods follow a place-and-route similar to what is done in FPGAs. Some other methods formalized the problem to delegate to a solver. Since the mapping problem is a NP-complete problem, researchers naturally looked after techniques provided by the operational research or graph theory domains. These have been extensively used to solve the data-flow mapping problem.

In [START_REF] Wijerathne | Himap: Fast and scalable high-quality mapping on cgra via hierarchical abstraction[END_REF], Wijerathne et al. suggest to classify the existing CGRA mapping algorithms into three main categories: heuristic-based, graph-based or ILP-based (Integer-Linear Programming). The graph-based approach can be discussed as soon as all applications are modeled by graph, but graph-based approaches use techniques borrowed from the graph theory domain and can deserve an own class. For instance, Hamzeh et al. [START_REF] Hamzeh | REGIMap: registeraware application mapping on coarse-grained reconfigurable architectures (CGRAs)[END_REF] build a compatibility graph, Dave et al. rely on the max clique in RAMP [START_REF] Dave | Ramp: Resourceaware mapping for cgras[END_REF], a graph minor approach is followed in [START_REF] Chen | Graph minor approach for application mapping on cgras[END_REF], and the maximum common subgraph is used in [START_REF] Hamzeh | EPIMap: using epimorphism to map applications on CGRAs[END_REF], [START_REF] Peyret | Efficient application mapping on CGRAs based on backward simultaneous scheduling/binding and dynamic graph transformations[END_REF], [START_REF] Das | An energyefficient integrated programmable array accelerator and compilation flow for near-sensor ultralow power processing[END_REF]. We suggest to follow a more usual way of classifying optimization algorithms between approximate methods and exact methods. The other issue with graphbased approaches, in the general case, is that some of them can be exact and others not. Specifically for the case of CGRA mapping, it appears that all of them are heuristics. We also suggest to further divide the heuristic-based approaches by adding a meta-heuristic category (which is part of the heuristics category but this makes Table I more clear). Finally, we include the ILP into an "exact-based" category, which is also debatable as soon as these techniques do not guarantee an optimal mapping. The main feature of the exact based methods is that they can prove the optimality, whereas heuristics may find the optimal solution, but without the possibility to prove it.

As a second dimension to this classification, we suggest to differentiate spatial and temporal mapping. In the case of temporal mapping, the binding and scheduling steps can be solved together, or can be solved separately (one after the other). In that case, some approaches may use a combination of techniques. Table I gathers all the techniques used to solve the mapping problem, for spatial or temporal architectures. The different techniques used are presented in four main columns: (1) heuristics, (2) meta-heuristics, (3) ILP or Branch and Bound (B&B) methods, (4) Constraint Satisfaction Problems (CSP). The heuristics encompass all the techniques specifically designed for the given problem. The meta-heuristics form a family of optimisation algorithms, and the table further divides it into two families: population-based technics like Genetic Algorithms (GA) or quantum-inspired evolutionary algorithm (QEA), and local search techniques like Simulated Annealing (SA). The exact methods include Integer Linear Programming (ILP) and branch and bound on one side, and techniques that model the mapping problem as a constraint satisfaction problem. This problem is then solved through constraint programming (CP), SAT (Boolean satisfiability), or SMT (Satisfiability Modulo Theories). Please note that all the papers cited do not appear in the table, as some of them rely on already referenced papers. For instance, the approach presented by De Sutter et al. [START_REF] Sutter | Placementand-routing-based register allocation for coarse-grained reconfigurable arrays[END_REF] relies on DRESC compiler [START_REF] Mei | DRESC: a retargetable compiler for coarse-grained reconfigurable architectures[END_REF], which already appears in the table.

B. Control-flow mapping

Mapping the control-flow graph raises another difficulty. A solution adopted in many cases is to let the control flow managed by a host processor. But this reduces greatly the pos- Spatial mapping [START_REF] Yoon | A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures[END_REF], [START_REF] Hatanaka | A modulo scheduling algorithm for a coarse-grain reconfigurable array template[END_REF], [START_REF] Li | Chordmap: Automated mapping of streaming applications onto cgra[END_REF] GA [START_REF] Kojima | Genmap: A genetic algorithmic approach for optimizing spatial mapping of coarse-grained reconfigurable architectures[END_REF] SA [START_REF] Weng | Dsagen: Synthesizing programmable spatial accelerators[END_REF], [START_REF] Gobieski | Snafu: An ultra-low-power, energy-minimal cgra-generation framework and architecture[END_REF] ILP [START_REF] Yoon | A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures[END_REF], [START_REF] Chin | An architecture-agnostic integer linear programming approach to cgra mapping[END_REF], [START_REF] Nowatzki | A general constraint-centric scheduling framework for spatial architectures[END_REF] Temporal mapping [START_REF] Bondalapati | Mapping loops onto reconfigurable architectures[END_REF], [START_REF] Lee | Ultra-fast cgra scheduling to enable run time, programmable cgras[END_REF], [START_REF] Wijerathne | Himap: Fast and scalable high-quality mapping on cgra via hierarchical abstraction[END_REF], [START_REF] Zhao | Towards higher performance and robust compilation for cgra modulo scheduling[END_REF]- [START_REF] Canesche | Traversal: A fast and adaptive graph-based placement and routing for cgras[END_REF] SA [START_REF] Mei | DRESC: a retargetable compiler for coarse-grained reconfigurable architectures[END_REF] ILP [START_REF] Brenner | Optimal Simultaneous Scheduling, Binding and Routing for Processor-Like Reconfigurable Architectures[END_REF] B&B [START_REF] Karunaratne | Dnestmap: Mapping deeply-nested loops on ultra-low power cgras[END_REF] CP [START_REF] Raffin | Scheduling, binding and routing system for a run-time reconfigurable operator based multimedia architecture[END_REF] SAT [START_REF] Miyasaka | Satbased mapping of data-flow graphs onto coarse-grained reconfigurable arrays[END_REF] SMT [START_REF] Donovick | Agile smtbased mapping for cgras with restricted routing networks[END_REF] Binding [START_REF] Lee | Compilation approach for coarse-grained reconfigurable architectures[END_REF], [START_REF] Das | A scalable design approach to efficiently map applications on cgras[END_REF], [START_REF] Hamzeh | EPIMap: using epimorphism to map applications on CGRAs[END_REF], [START_REF] Yin | Joint affine transformation and loop pipelining for mapping nested loop on CGRAs[END_REF]- [START_REF] Peyret | Efficient application mapping on CGRAs based on backward simultaneous scheduling/binding and dynamic graph transformations[END_REF] QEA [START_REF] Lee | Mapping Multi-Domain Applications Onto Coarse-Grained Reconfigurable Architectures[END_REF] SA [START_REF] Hatanaka | A modulo scheduling algorithm for a coarse-grain reconfigurable array template[END_REF], [START_REF] Friedman | SPR: An Architecture-adaptive CGRA Mapping Tool[END_REF], [START_REF] Schulz | Rotated parallel mapping: A novel approach for mapping data parallel applications on cgras[END_REF] ILP [START_REF] Guo | Formulating data-arrival synchronizers in integer linear programming for cgra mapping[END_REF], [48] Scheduling [START_REF] Das | A scalable design approach to efficiently map applications on cgras[END_REF], [START_REF] Hamzeh | EPIMap: using epimorphism to map applications on CGRAs[END_REF], [START_REF] Zhao | Towards higher performance and robust compilation for cgra modulo scheduling[END_REF], [START_REF] Hamzeh | REGIMap: registeraware application mapping on coarse-grained reconfigurable architectures (CGRAs)[END_REF], [START_REF] Lee | Mapping Multi-Domain Applications Onto Coarse-Grained Reconfigurable Architectures[END_REF], [START_REF] Schulz | Rotated parallel mapping: A novel approach for mapping data parallel applications on cgras[END_REF]- [START_REF] Balasubramanian | Crimson: Compute-intensive loop acceleration by randomized iterative modulo scheduling and optimized mapping on cgras[END_REF] ILP [START_REF] Guo | Formulating data-arrival synchronizers in integer linear programming for cgra mapping[END_REF], [START_REF] Mu | Routability-enhanced scheduling for application mapping on cgras[END_REF] sibilities to use the CGRA and increases the communication overhead, loosing sometimes the benefit of the acceleration provided by the CGRA. Another approach is to provide the CGRA with extra hardware features to support the control flow. Two structures are distinguished: Conditional and alternative structures, and iterative structures. 1) Conditional and alternative structures: Conditional and alternative structures are if-then-else (ITE) constructs. As clearly presented in [START_REF] Yuan | Dynamicii pipeline: Compiling loops with irregular branches on static-scheduling cgra[END_REF], there are four basic methods to map applications with ITE onto CGRAs: (1) Full predication [START_REF] Anido | Improving the operation autonomy of simd processing elements by using guarded instructions and pseudo branches[END_REF], (2) Partial predication [START_REF] Chang | Mapping control intensive kernels onto coarsegrained reconfigurable array architecture[END_REF], (3) Dual-issue single execution [START_REF] Yuan | Dynamicii pipeline: Compiling loops with irregular branches on static-scheduling cgra[END_REF], [START_REF] Hamzeh | Branch-aware loop mapping on cgras[END_REF], [START_REF] Karunaratne | 4d-cgra: Introducing branch dimension to spatio-temporal application mapping on cgras[END_REF], (4) Direct CDFG mapping [START_REF] Das | Efficient mapping of CDFG onto coarse-grained reconfigurable array architectures[END_REF]. Supporting ITE constructs efficiently is still a hot topic, as witnessed by recent publications [START_REF] Yuan | Dynamicii pipeline: Compiling loops with irregular branches on static-scheduling cgra[END_REF], [START_REF] Karunaratne | 4d-cgra: Introducing branch dimension to spatio-temporal application mapping on cgras[END_REF].

2) Iterative structures: Iterative structures are defined by an initialisation phase, an iteration condition, and an iteration step. Most of the works focus on for loops. Loops have been the primary care since the early days of CGRAs [START_REF] Bondalapati | Mapping loops onto reconfigurable architectures[END_REF]. Since loops concentrate the most important computing part of the application, researches naturally focused on this specific case, and the topic has been intensively studied during the last two decades. Most of the works consider the loop body, letting the control flow managed by a host processor. When the loop body contains conditional or alternative structures, the techniques presented in III-B1 can be used. Mapping loops on CGRA is so intensively studied that it would certainly deserve a survey on its own. Modulo scheduling. Modulo scheduling is the most widely used technique to map loops on the CGRA [START_REF] Sutter | Placementand-routing-based register allocation for coarse-grained reconfigurable arrays[END_REF], [START_REF] Hatanaka | A modulo scheduling algorithm for a coarse-grain reconfigurable array template[END_REF], [START_REF] Balasubramanian | Crimson: Compute-intensive loop acceleration by randomized iterative modulo scheduling and optimized mapping on cgras[END_REF], [START_REF] Mei | Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling[END_REF]. It can rely on a modulo routing resource graph (MRRG) [START_REF] Karunaratne | 4d-cgra: Introducing branch dimension to spatio-temporal application mapping on cgras[END_REF], [START_REF] Mei | Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling[END_REF]. It can also be solved through graph-based approaches [START_REF] Park | Edge-centric Modulo Scheduling for Coarse-grained Reconfigurable Architectures[END_REF], [START_REF] Dave | Ramp: Resourceaware mapping for cgras[END_REF].

Hardware loops. Hardware loops consist of extra logic inside the CGRA to manage the iterations of the loop in order to reduce the overhead of loop control by the processor [START_REF] Balasubramanian | Laser: A hardware/software approach to accelerate complicated loops on cgras[END_REF]- [START_REF] Vadivel | Loop overhead reduction techniques for coarse grained reconfigurable architectures[END_REF].

C. Data mapping

The interaction between the CGRA and the memory is also of utmost importance as it defines the efficiency of the whole execution of the application. Various parameters of the memory can be considered for an efficient mapping: number of banks, communication bandwidth, and memory size [START_REF] Schulz | Rotated parallel mapping: A novel approach for mapping data parallel applications on cgras[END_REF], [START_REF] Li | Combining memory partitioning and subtask generation for parallel data access on cgras[END_REF]- [START_REF] Yin | Conflict-free loop mapping for coarse-grained reconfigurable architecture with multibank memory[END_REF].

The internal memory resources of the CGRA should also be used efficiently. Register allocation is presented in [START_REF] Sutter | Placementand-routing-based register allocation for coarse-grained reconfigurable arrays[END_REF], [START_REF] Hamzeh | REGIMap: registeraware application mapping on coarse-grained reconfigurable architectures (CGRAs)[END_REF], for a rotating register file [START_REF] Sutter | Placementand-routing-based register allocation for coarse-grained reconfigurable arrays[END_REF], or for a unified register file [START_REF] Dave | Ureca: Unified register file for cgras[END_REF].

D. Timeline

Fig. 4 presents the evolution of scientific production around CGRA mapping the last two decades. The number of publications per year is not accurate, as it considers the papers focusing on CGRA mapping only, and a subset of selected papers, but still it shows that the community has intensified the efforts in the last decade, with a clear increase in 2021. The figure also shows that modulo scheduling was considered since the beginning of the studies, that supporting branches started in the early 2000s, and that memory-aware methods gained interest around 2010.

IV. THE FUTURE

The first wave of CGRA was fueled by signal processing applications, especially multimedia applications like image, audio, and video, for embedded systems, constrained by stringent power and energy budget. The Samsung Reconfigurable Processor (SRP) [START_REF] Jin | Low-power reconfigurable audio processor for mobile devices[END_REF], an ADRES-like CGRA, integrated in the past in the Exynos SoC, is an example of a commercial use of CGRAs. The choice of Samsung to discontinue the use of SRP in favor of more conventional processors is the sign of a mitigated success [START_REF] Frumusanu | The Samsung Exynos 7420 Deep Dive -Inside A Modern 14nm SoC[END_REF].

A. Trends

CGRAs experience a new momentum as they get carried away by artificial intelligence (AI) applications. The massive need of high-performance computing, coupled with the slowdown of Moore's law and end of Dennard scaling, and the mismatch between AI workloads and conventional Von Neumann architectures, drives the efforts towards a multitude of AI-accelerators, which fall in the category of CGRAs. The diversity of names in the literature also shows that the domain is buzzing: Xilinx AI-engine [START_REF]Architecture apocalypse dream architecture for deep learning inference and compute-versal ai core[END_REF], Reconfigurable Dataflow Architecture [START_REF] Sambanova | Accelerated Computing with a Reconfigurable Dataflow Architecture[END_REF], Reconfigurable Dataflow Accelerator [START_REF] Zhang | Sara: Scaling a reconfigurable dataflow accelerator[END_REF]. These "modern" CGRAs differ from the legacy ones in the number of cells that are available, which causes a serious scalability issue that is discussed in the challenge section. Another difference is the coupling with a host CPU. Modern CGRAs tend to be standalone, similarly to a GPU, and they require a full system integration. CGRAs are the relevant (if not the only credible) solution to take up the challenge of energy-efficient AI applications. The second wave of CGRAs might eventually be the one that meets an industrial success.

2 0 0 0 2 0 0 1 2 0 0 2 2 0 0 3 2 0 0 4 2 0 0 5 2 0 0 6 2 0 0 7 2 0 0 8 2 0 0 9 2 0 1 0 2 0 1 1 2 0 1 2 2 0 1 3 2 0 1 4 2 0 1 5 2 0 1 6 2 0 1 7 2 0 1 8 2 0 1 9 2 0 2 The mapping problem is complex, and needs sophisticated algorithms that are time consuming to understand, and to formalize. The methods based on artificial intelligence and machine learning are clearly interesting trails [START_REF] Liu | Data-flow graph mapping optimization for cgra with deep reinforcement learning[END_REF]. AI-based methods help in concentrating within a single model some functional but also non functional contraints, that are hard to formalize through traditional methods. AI for electronic design automation in general is at its early beginnings, and AI for CGRA specifically will be part of this global trend.

From the architectural point of view, some evolutions will obviously impact the compilation. The CGRA coupling can also be further explored: near the memory, or directly integrated within the memory array in a processing-in-memory manner [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF]. The emerging memory technologies will also be game changers.

Finally, some open-source frameworks recently appeared [START_REF] Weng | Dsagen: Synthesizing programmable spatial accelerators[END_REF], [START_REF] Anderson | Cgra-me: An open-source framework for cgra architecture and cad research[END_REF]- [START_REF] Podobas | A template-based framework for exploring coarse-grained reconfigurable architectures[END_REF] to share the technical efforts and provide a ready for use tool to democratize the CGRAs and make them widely adopted for energy-efficient or high-performance computing. These frameworks are also part of a wider trend about open source hardware.

B. Challenges a) Programming model:

The unadapted programming model used up to now for CGRAs is the main limitation identified in two recent surveys [START_REF] Liu | A survey of coarse-grained reconfigurable architecture and design: Taxonomy, challenges, and applications[END_REF], [START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF]. Other programming models needs to be considered, more adapted to CGRAs, able to specify the data-level parallelism, like OpenMP, SYCL, CUDA or OpenCL. The dataflow model of computation could also be interesting to look at. This kind of streaming model can fit with CGRAs [START_REF] Li | Chordmap: Automated mapping of streaming applications onto cgra[END_REF], [START_REF] Nicol | A coarse grain reconfigurable array (cgra) for statically scheduled data flow computing[END_REF].

b) Scalability: Scalability is clearly one of the biggest challenge to be taken up. Some techniques are already proposed do deal with scalability. In [START_REF] Wijerathne | Himap: Fast and scalable high-quality mapping on cgra via hierarchical abstraction[END_REF], the repetitive patterns of loops are detected and are mapped in a hierarchical way. In [START_REF] Das | A scalable design approach to efficiently map applications on cgras[END_REF], the partial solutions are stochastically pruned to keep under control their number. But while legacy CGRAs are composed of tens of cells, with a use rate quite low limited by the intruction level parallelism available in the applications, the more recent and modern CGRAs, the most capable of crunching AI workloads, contains hundreds to thousands of cells. The issue is to effectively make use of the massive number of cells. The standalone feature of modern CGRAs is another game changer for mapping methods. The mapping problem is intractable, scalability further raises the challenge, and the number of cells involved takes it in yet another dimension. The application should be considered as a whole, not with intensive kernels to be offload to the CGRA and letting the host processor interact with the system. A holistic approach is thus needed to first analyse the input application, and then relevantly partition it for finally an efficient complete mapping. SARA [START_REF] Zhang | Sara: Scaling a reconfigurable dataflow accelerator[END_REF] is such a recent approach. It relies on a hierarchical pipelining to further extract parallelism. For instance, at loop level, two sibling loops might be executed in parallel. When there are data dependencies across the loops, the memory consistency is managed by the compiler, and the instructions are ordered to guarantee the correct execution. SARA makes use of spatial parallelism and temporal parallelism. The iterations of the loops are overlapped at all levels as an advanced implementation of software pipelining (not only modulo scheduling). In other words, the new generation of compilers for CGRAs must be able to make use of all levels of parallelism : instruction level, data level, and loop level.

V. CONCLUSION

This paper presents twenty years of methods for mapping application on CGRA. It provides the terminology and basic knowledge for the newcomer. The paper focuses on offline methods from imperative language, presents a classification of the methods and shows a timeline of the last two decades. The paper ends with current trends, calls for open-source frameworks for a democratization of the CGRA technology, and discusses the challenges for the near future of modern CGRAs. Among the upcoming challenges, the use of other programming models, and scalability for modern CGRAs running AI workloads, are specifically identified.

Fig. 2 .

 2 Fig.2. Illustration of a simple CGRA taken from[START_REF] Podobas | A survey on coarse-grained reconfigurable architectures from a performance perspective[END_REF], showing the mesh topology (a), the internal architecture of the Reconfigurable Cell, RC (b), and an example of the configuration register (c).

Fig. 3 .

 3 Fig. 3. Classical compilation flow for CGRAs

Fig. 4 .

 4 Fig.[START_REF] Voitsechov | Inter-thread communication in multithreaded, reconfigurable coarse-grain arrays[END_REF]. Number of publications related to CGRA mapping over the last two decades. Note that this timeline does not include papers about CGRA architectures, and is not comprehensive.

TABLE I A

 I REVIEW OF BINDING AND SCHEDULING TECHNIQUES FOR AUTOMATED SPATIAL AND TEMPORAL MAPPING OF APPLICATIONS ON CGRAS.

	Approximate methods			Exact methods
	Heuristics	Meta-heuristics	ILP/B&B	CSP
	Population-based	local search

provided that we do not consider GPGPUs as part of the big CGRA family

in real life there are multiple IRs according to the optimisation to perform


Kevin J M Martin
email: kevin.martin@univ-ubs.fr

ManyGUI: A Graphical Tool to Accelerate Many-core Debugging Through Communication, Memory, and Energy Profiling

Keywords: CCS CONCEPTS, Hardware → Simulation and emulation;, Computer systems organization → Multicore architectures Many-core, Validation, Graphical, Energy, Memory, Network-on-Chip

The debugging and validation of the many-core design is a complex task due to numerous events happening in the system simultaneously. Current state-of-the-art many-cores are strongly based on waveforms and log files to validate their behavior during simulation. Our hypothesis is that, as happened with ASIC development, a Graphical User Interface (GUI) can significantly accelerate the many-core development. To sustain that, we propose an open-source GUI tool called ManyGUI for many-core debugging. ManyGUI is organized in a framework that collects and classifies high-level events during simulation related to computation (executed CPU instructions), memory, and communication (NoC packets). Such events are shown graphically to the developer through a set of intuitive and practical frames. We evaluate ManyGUI in a silicon-proven state-of-the-art open-source manycore called OpenPiton, which uses RISC-V 64-bits CPU, 3 NoCs, and a distributed/shared cache memory organization. Results show that ManyGUI allows the developer to rapidly obtain a comprehensive view of the many-core behavior in terms of communication statistics (packets paths, link utilization), memory statistics (memory access, miss rate), and energy (CPU, memory, and NoC).

INTRODUCTION

Many-cores are systems-on-chip that reach outstanding processing power by assuming tiles implemented as a processor, memory, or a specific accelerator [START_REF] Davidson | The Celerity Open-Source 511-Core RISC-V Tiered Accelerator Fabric: Fast Architectures and Design Methodologies for Fast Chips[END_REF]. The tiles are connected through a scalable on-chip technology called Network-on-Chips (NoCs) [START_REF] Monemi | ProNoC: A low latency network-on-chip based many-core system-on-chip prototyping platform[END_REF]. Many-cores quickly evolve from research prototypes to mature designs used in industry today 1 . The next generation of manycore, powered by the advances in semiconductor technologies and novel power management techniques, is expected to reach hundreds either thousands of tiles. While NoCs facilitate the placement of new tiles on the chip, the complexity of such systems due to the abundance of components, events, protocols, among others, pose significant challenges to debugging them during the design phase. Specifically, there is an important lack of tools that allow the designer to rapidly understand what is happening in the system regarding communication events (packet level), memory statistics, and energy consumption.

A study of the state-of-the-art of current many-core platforms leads to the observation that they are heavily based on log files and waveforms. We see that such methods can be significantly extended by using Graphical User Interfaces (GUI). The introduction of GUI in the ASIC design allowed a rapid and intuitive chip development. As happened on ASIC design, we support that GUI advantages can also be exploited to accelerate many-core functional development, assuming a higher level observation strategy that aims to reduce the time lost analyzing big waveforms and understanding large log files. Figure 1 position our idea. It shows functional development steps of many-cores typically found in the literature [START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF][START_REF] Monemi | ProNoC: A low latency network-on-chip based many-core system-on-chip prototyping platform[END_REF][START_REF] Qureshi | Gem5-X: A Many-Core Heterogeneous Simulation Platform for Architectural Exploration and Optimization[END_REF][START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF]. The figure can be observed from the bottom to the top. At first, the developers work in designing the hardware model, for instance, using RLT-based languages like VHDL and Verilog. The software design comprises the Operating System (OS) and application development.

After having the software and hardware design, the developers team usually creates scripts that automatically resize the model before compilation according to design-time features, such as the number of cores, memory sizes, and NoC flit width. The scripts generate essential software and hardware files, as "include files," which will drive the automatic generation of hardware and predefined pragmas in software. Once the final design was generated, the flow advances to the simulation phases, using commercial or open-source simulator tools, which compile the hardware in a given description level and simulate its behavior based on the software. The next step is the debugging and validation, where the developer will analyze if everything is working as expected at a logical level 2 . Traditionally, simulators provide waveforms, which allow a very detailed (gate-level) representation of the system. The design can also print some values at important checkpoints, which are displayed in log files. If the hardware is not modeled at the RTL level (as in the Gem5 simulator [START_REF] Qureshi | Gem5-X: A Many-Core Heterogeneous Simulation Platform for Architectural Exploration and Optimization[END_REF]), the simulator can only output log files. The motivation for this work is that current debugging methods based on waveform and log files are slow and prone to interpretation errors due to the fatigue passed to the developer to follow the massive information volume that many-core generates while simulating. The goal of this work is to go one step higher in the debugging and validation process by proposing a GUI tool called ManyGUI that, based on high-level events collected at computation, memory, and communication level, can depict the communication flow, memory statistics, and energy consumption. ManyGUI allows a rapid and comprehensive understanding of the many-core behavior and, consequently, the application running on it. This work has the following contributions:

(1) An overview of recent many-cores platforms and how they implement the debugging during simulations; (2) A framework to collect and classify events of computation (executed CPU instructions), memory, and communication (NoC packets) during the many-core simulation, assuming a generic interface which can be easily adapted to different many-core designs; (3) A set of graphical frames which show, during the simulation, communication statistics (packets paths, link utilization), memory statistics (memory access, miss rate), and energy (CPU, memory, and NoC); (4) A case study of ManyGUI in a state-of-the-art open-source many-core called OpenPiton [START_REF] Balkind | OpenPiton+ Ariane: The First Open-Source, SMP Linux-booting RISC-V System Scaling From One to Many Cores[END_REF].

OVERVIEW OF MANY-CORE PLATFORMS AND DEBUGGING

This section presents contribution [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF]. Table 1 addresses the main characteristics of the state-of-the-art many-core design platforms in literature. The 1 st column shows the name of the platform, its reference work, and the year. Focusing on an updated classification, we consider only recent works, dating not more than 5 years ago (from 2017 on). Older platforms classifications can be found in [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF][START_REF] Kamaleldin | Towards a Modular RISC-V Based Many-Core Architecture for FPGA Accelerators[END_REF][START_REF] Ruaro | Memphis: a framework for heterogeneous many-core SoCs generation and validation[END_REF]. The 2 nd column addresses the language used to model the platforms. It is possible to see that most of the listed platforms use Verilog or System-Verilog (SV) while very few rely on VHDL and System-C. One of the advantages of using Verilog and SV is its C-like style and its easy integration with open-source simulators as Verilator3 , which promises to speed-up the simulation by converting the model to multithreaded C++. The 3 rd column classifies works by detailing how the computation is implemented. Noticeably, RISC-V was received considerable attention from research, resulting in the majority of the works, which either adopt RISC-V cores exclusively [START_REF] Balkind | OpenPiton+ Ariane: The First Open-Source, SMP Linux-booting RISC-V System Scaling From One to Many Cores[END_REF][START_REF] Elmohr | RVNoC: A Framework for Generating RISC-V NoC-Based MPSoC[END_REF][START_REF] Kamaleldin | Towards a Modular RISC-V Based Many-Core Architecture for FPGA Accelerators[END_REF] or use it in an on-chip heterogeneous fashion [START_REF] Davidson | The Celerity Open-Source 511-Core RISC-V Tiered Accelerator Fabric: Fast Architectures and Design Methodologies for Fast Chips[END_REF][START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF][START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF]. Another observed aspect is that many-cores are increasingly adopting accelerators to reach energy efficiency in complex applications, specifically to support machine learning [START_REF] Davidson | The Celerity Open-Source 511-Core RISC-V Tiered Accelerator Fabric: Fast Architectures and Design Methodologies for Fast Chips[END_REF][START_REF] Petrisko | BlackParrot: An Agile Open-Source RISC-V Multicore for Accelerator SoCs[END_REF][START_REF] Qureshi | Gem5-X: A Many-Core Heterogeneous Simulation Platform for Architectural Exploration and Optimization[END_REF][START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF]. The 4 th column classifies works by their memory organization. Few architectures adopt purely distributed system [START_REF] Elmohr | RVNoC: A Framework for Generating RISC-V NoC-Based MPSoC[END_REF][START_REF] Monemi | ProNoC: A low latency network-on-chip based many-core system-on-chip prototyping platform[END_REF][START_REF] Ruaro | Memphis: a framework for heterogeneous many-core SoCs generation and validation[END_REF]. Most systems use a hybrid shared memory system, which includes a private memory (L1 or scratchpad) with a logically shared but physically distributed last level shared memory [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF][START_REF] Balkind | OpenPiton+ Ariane: The First Open-Source, SMP Linux-booting RISC-V System Scaling From One to Many Cores[END_REF][START_REF] Kamaleldin | Towards a Modular RISC-V Based Many-Core Architecture for FPGA Accelerators[END_REF][START_REF] Petrisko | BlackParrot: An Agile Open-Source RISC-V Multicore for Accelerator SoCs[END_REF][START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF]. Such hybrid systems are suitable to many-core since a centralized shared memory is not scalable for a high number of tiles [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF]. Some works adopt cache coherence protocols, as the distributed directory-based protocol [START_REF] Balkind | OpenPiton+ Ariane: The First Open-Source, SMP Linux-booting RISC-V System Scaling From One to Many Cores[END_REF][START_REF] Petrisko | BlackParrot: An Agile Open-Source RISC-V Multicore for Accelerator SoCs[END_REF]. Other works [START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF][START_REF] Kurth | An Open-Source Platform for High-Performance Non-Coherent On-Chip Communication[END_REF][START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF], argue that cache coherence protocols are not scalable for many-cores due to their high cost in terms of synchronization overhead and energy consumption observed, specifically, for streaming data-flow applications [START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF]. Instead, the alternative is to rely upon software-managed scratchpad memory close to each CPU, with the communication among CPUs initialized by software [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF][START_REF] Kamaleldin | Towards a Modular RISC-V Based Many-Core Architecture for FPGA Accelerators[END_REF][START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF][START_REF] Ruaro | Memphis: a framework for heterogeneous many-core SoCs generation and validation[END_REF][START_REF] Savas | A framework to generate domain-specific manycore architectures from dataflow programs[END_REF]. Some designs cluster the cores and assign a shared memory for each cluster [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF][START_REF] Kamaleldin | Towards a Modular RISC-V Based Many-Core Architecture for FPGA Accelerators[END_REF][START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF][START_REF] Qureshi | Gem5-X: A Many-Core Heterogeneous Simulation Platform for Architectural Exploration and Optimization[END_REF]. Such an approach has benefits since it preserves data locality inside the cluster, speeding intra-cluster communication. The side effect is the heterogeneous latency (jitter) caused to access off-cluster data and the task mapping complexity for applications that do not fit in one cluster.

The 5 th column classifies works by communication implementation. NoCs are interesting solutions to build scalable and high throughput interconnections [1, 2, 4, 6-8, 11, 12, 14, 15]. Some platforms adopt hybrid approaches (bus + NoC), specifically, those that adopt clustering [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF][START_REF] Kamaleldin | Towards a Modular RISC-V Based Many-Core Architecture for FPGA Accelerators[END_REF][START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF]. Thus, a bus implements the communication intra-cluster, while a NoC implements the communication inter-cluster. The 6 th column details if the work is open-source. Finally, the last column details if works adopt some GUI-based method. As can be observed, GUI-based debugging is the main gap found in the state-of-the-art. In [START_REF] Monemi | ProNoC: A low latency network-on-chip based many-core system-on-chip prototyping platform[END_REF], the authors use a GUI to generate the many-core according to some properties and also to collect NoC-centered statistics during simulation. In [START_REF] Ruaro | Memphis: a framework for heterogeneous many-core SoCs generation and validation[END_REF], the authors use a GUI to assist platform debugging during simulation. They focus on CPU scheduling and, as in [START_REF] Monemi | ProNoC: A low latency network-on-chip based many-core system-on-chip prototyping platform[END_REF], mostly into communication statistics. This work advances the state-of-the-art of GUI debugging for many-core by addressing not only communication but memory statistics and energy consumption. As could be observed from previous columns, systems are increasingly complex, and memory is a key player in driving the chip's performance and energy efficiency. Therefore, easily understanding the memory statistics and the energy consumption is fundamental in the design of next-generation many-cores.

MANY-CORE GUI DEBUGGING

This section presents the contributions ( 2) and (3). Figure 2 presents an overview of ManyGUI debugging framework. It includes the steps of event extraction, classification, and representation. The event extraction is built inside the hardware by monitoring instruction events from the CPU, memory events from the memory subsystem, and NoC events from the NoC router. These events are inserted into a database during the simulation. In parallel, the ManyGUI desktop application (implemented in Java), read from this database, classifies, and displays the event graphically. ManyGUI desktop application is composed of two parts: (1) a back-end part, implemented by an event classification engine (ECE); (2) a frontend part, implemented by the Event Graphical Interface (EGI). The back-end part reads from the database and creates a logical structure of the events in the memory of the ManyGUI program. The front-end part displays graphically and intuitively the events to the developer in a set of frames. The following subsection will enter in details of each part. the memory, the MEM extracts memory events. Memory events vary according to the many-core memory organization. Cache memories are currently common implementations, and one of the ManyGUI goals is to be suitable to caches. Therefore, memory events types include L1 access, L1 miss, L2 access, L2 miss, and DRAM accesses.

Event Monitoring

Each MEM event has a timestamp and an ID representing the class. Classes that store all the events read from the database.

Finally, inside the NoC routers, the PCM extracts communication events. The PCM generates one new event each time a packet enters in a router by a given input port. The PCM comprises a timestamp, packet size, current router address, destination router address, input port, and packet service.

An important functional property of the monitors is that they register the events in three respective databases shown in Figure 2. Such a database can be implemented as a structured database (as Structured Query Language (SQL)) or simply by using text files on the host OS directory structure.

Event Classification Engine (ECE)

The Event Classification Engine (ECE) aims to read the events from the database and compute statistics at runtime. It was designed to provide a simplified set of data structures that the ManyGUI front-end can easily access. We use object-oriented implementation to classify the data. Figure 3 shows two main class diagrams implemented by ECE. For clarity, we omit the functions of these classes and keep only the attributes and UML relationships among them.

Figure 3(a) shows the class diagram of the basic classes to represent events. It consists of 3 classes (MemEvent, CPUEvent, NoCEvent) which store one single event from database. These 3 classes inherit from the Event abstract class, which has the attribute time. The MemEvent class has one attribute that stores the type of memory event (e.g.: L1 miss, L1 access, L2 miss). The CPUEvent class stores the additional attributes of instruction type (e.g.: add, sub, jal), and instruction class (e.g.: ALU, branch, multiplications). Finally, the NoCEvent class stores all attributes required to one packet (size, current router address, target router address, input port, and service). Figure 3(b) shows the class diagram that stores all events from the database. At runtime, the ECE pools the database during a fixed interval of time (200 milliseconds), gets all new incoming events within this time, and classifies them by storing in a high-level class structure. To implement such a structure, we design a class named EventInfo. It is the top-level class that stores all events of the system. It is composed of 3 other classes: MemEventInfo, CPUEventInfo, and NoCEventInfo. Those 3 classes implement a similar behavior which can be explained as a single one. Each one has a hash table, where keys represent the tile IDs and values represent a list of events for that tile. This hash table allows to speed up the access to events by the EGI since it rapidly extracts event associated to a given tile due to its average access time complexity of O(1) [START_REF] Thomas | Introduction to Algorithms[END_REF]. These 3 classes also implement functions to collect statistics from the events, which include: cache miss rate, NoC links throughput, CPU energy, memory energy, and NoC energy.

The cache miss rate is calculated by dividing the number of cache misses by the cache access. The NoC link throughput is calculated by dividing the total time the router was busy handling packets by the total simulated time. The energy estimation is performed by assuming a previous hardware characterization of the manycore (out of the scope of this work). In this work we adopted the characterization provided in [START_REF] Mckeown | Power and Energy Characterization of an Open Source 25-Core Manycore Processor[END_REF] for memory and NoC, and in [START_REF] Zaruba | The Cost of Application-Class Processing: Energy and Performance Analysis of a Linux-Ready 1.7-GHz 64-Bit RISC-V Core in 22-Nm FDSOI Technology[END_REF] for CPU. Based on such energy characterization, the developer can extract the following information: (1) energy at computation level: the energy per CPU instruction class; (2) energy at memory level: the energy per memory miss and hit, and (3) energy at communication level: the energy to transmit one-hop flit into the NoC. These energy values are informed to the tool using a configuration file which is loaded when ManyGUI is initialized (section 3.4).

In summary, the goal of ECE is to provide a structured event classification to compute statistics about the events. This structure is clustered in the class EnergyInfo, which is the input of the frontend EGI.

Event Graphical Interface (EGI)

The Event Graphical Interface (EGI) is composed of a set of frames that brings information about the system's communication, memory, and energy. Figure 4 shows the principal frames of ManyGUI . The next subsections explain the functional properties of the frames. The explanation of the data content is left to section 4.

Communication.

The communication is the initial frame of the tool and is called when ManyGUI is opened. Figure 4(a) shows an example for a many-core with 9 tiles (3x3 dimension). This frame aims to show the interconnection among cores, the packets traversing the NoC in a given time (red arrows), and the link utilization of each router input port. The frame contains several configuration panels at bottom. In the panel detailed by marker (1), the user can control the displaying of the packet events (start, stop, show next packet). When a new NoC event is read by the tool, it colors in red the arrow between the current router and the previous router. By keeping the arrows colored until the packet reaches the destination router, it is possible to show the full path of the packet, as zoomed by marker [START_REF] Desnos | Distributed Memory Allocation Technique for Synchronous Dataflow Graphs[END_REF], which shows a packet generated by tile 0x0 and that arrived at tile 0x2, crossing the router of tile 0x1. Marker [START_REF] Balkind | OpenPiton+ Ariane: The First Open-Source, SMP Linux-booting RISC-V System Scaling From One to Many Cores[END_REF] shows the speed control panel, in which the velocity of displaying the NoC event can be controlled. Marker (3) allows backing the packet displaying to a specific period in the simulation time. Finally, marker (4) allows for seeing the packet service, which carries the meaning of that packet. In this example, the packet is a DATA_ACK, representing an acknowledgment message from a high-level cache to a low-level cache. The debug possibilities of this frame include the validation of the routing algorithms, communication load distribution, link utilization, and packet content. Additionally, we observe that this frame is helpful when the simulation hangs due to a software error inside a given tile. Using the tool, the developer can quickly identify the tile responsible for this bug by observing that it stopped consuming packets, which leads to a cascade effect in the NoC. This awareness is more difficult (in terms of time) to be reached just using log files or waveform since the developer needs to trace log by log (or signal by signal) along the time to find the actual source of the hang.

Energy.

From the communication frame, the user can open the energy frame depicted in Figure 4(b). The goal of this frame is to detail the energy consumption for each tile. The energy is shown in the form of a plot for each tile in a 2D-mesh layout. The energy measurement is broken in monitoring windows, so each tile bar at the x-axis represents the energy accumulated on one monitoring window. The y-axis of each tile represents the energy in nJ. The frame contains some configuration panels at the bottom. In the panel detailed by marker (1), the user can enable or disable the update of new events during simulation. In the panel of marker ( 2), the user can configure the size of the window. In this example, it was configured to the default size, which is 1 Kcycles. The panel of marker (3) allows the user to choose if the displayed values inside each tile must be normalized to the worst value among all tiles or according to a specified value. This option is helpful to allow a quick and fair comparison among the energy consumed by all tiles. However, sometimes one tile can consume much more energy than the other ones, which will hide the energy bars of the low-energy tiles. In such a case, the user can specify an absolute value, which will be used as a reference to set the maximum value of the y-axis for all plots. Finally, the panel of marker (4) shows the current time of the simulation in clock cycles. Another debug property of this frame is to show the tile energy in a detailed frame (by clicking over the tile), shown in Figure 5(a). There, the developer can observe 4 plots related to energy: the total accumulated energy (top-left) and its normalized version (top-right), and the energy per window (bottomleft) and its normalized version (bottom-right). Each energy bar of those plots is broken in the energy of CPU, memory, and NoC, allowing the user to profile quickly which many-core subsystem is spending more energy at a given time.

The debug possibilities of the energy frame include: achieving a comprehensive view of energy for all tiles, detecting tiles that are energy-hungry, observing the total energy and energy per window over time, comparing the energy consumption among different many-core subsystems (CPU, NoC, memory).

Memory. Figure 4(c)

shows the memory frame. Its layout is similar to the energy frame, especially regarding the configuration panels at the bottom. This frame includes an upper panel highlighted by marker [START_REF] Ax | CoreVA-MPSoC: A Many-Core Architecture with Tightly Coupled Shared and Local Data Memories[END_REF], which selects which memory statistics must be displayed, e.g., L1-D access, L1-D miss, L2 access. Thus, the user can rapidly see the statistics of different memory properties. The y-axis of each tile represents the number of events (e.g., number of L1-D miss), and the x-axis represents the monitoring window. Similar to the energy frame, this frame allows to click over the tile to achieve a detailed memory statistic frame. This action generates the frame depicted in Figure 5(b). There, the developer can observe 4 plots: at the top, one big plot shows the memory event scheduling. This plot is proper to compare different memory events and see how they can influence each other and impact tile's energy consumption. At the bottom, there are 3 plots showing the miss rate for L1-D (left), L1-I (center), and L2 (right). Each of these plots also brings the total miss rate achieved at that given simulation time (represented by the horizontal dashed line).

The debug possibilities of the memory frame include: achieving a comprehensive view of memory behavior for all tiles, detecting undesired memory behavior in a given tile, crossing different memory parameters with the energy frame, observing the memory event scheduling and the miss rate of different cache levels.

Plot

Generator. An additional frame shown in Figure 6 consists of a plot generator, which, based on a set of filters, allows the developer to generate in a vector format any specific plots shown in the energy and memory frames. To implement this, we integrate the tool with Matplotlib 4 (python-based script to generate plots). To generate a new plot, the developer must filter which parameters must be considered (e.g., L1-D access of tile 1x0, the energy of tile 0x0). Once the generate command is pressed, the vector version of the plot will be shown in a separated frame. This plot can be saved (e.g., in PDF) for future use in presentations or reports.

Configuration file

At initialization, ManyGUI demands a configuration file as input. Table 2 describes the parameters of the configuration file. From left to right, the columns detail the name, the unit, the numeral format, and the description. This file allows the developer to configure important parameters, such as the XY dimension, the router that implements off-chip connection, frequency, flit width, NoC number, the monitoring window used by energy and memory frames, and the energy for events of instructions, memory, and NoC.

CASE STUDY: OPENPITON MANY-CORE

OpenPiton is a state-of-the-art silicon-proven many-core developed by Princeton University [START_REF] Balkind | OpenPiton+ Ariane: The First Open-Source, SMP Linux-booting RISC-V System Scaling From One to Many Cores[END_REF][START_REF] Mckeown | Power and Energy Characterization of an Open Source 25-Core Manycore Processor[END_REF]. Figure 7 presents an overview of OpenPiton. Tiles are organized in a 2D-mesh topology, with routers of tile 0x0 connected to off-chip peripherals. Each tile has a CPU (with L1 D and I caches), one L1.5 cache (a replica of L1 cache), and a slice of L2 cache, modeled as a distributed/shared memory. The

Experimental Setup

Intending to address an easy-to-follow debugging experiment, we build the OpenPiton many-core with 9 tiles (3x3 dimension) and run on this system a synthetic application shown in Figure 8(a). The application consists of 3 classes of tasks. A single Split task receives input data and splits it among several parallel tasks, called Proc, which process the data slice in parallel. A Join task receives the processed data gathering them to compose the final result. This parallel application pattern is commonly found in image and video processing applications [START_REF] Desnos | Distributed Memory Allocation Technique for Synchronous Dataflow Graphs[END_REF]. The application runs during 3 iterations. The size of the input data is 26.25 KB, meaning that each Proc task handles 3.75 KB at each iteration. The Proc cost function has a complexity of O(n), where n is equal to 960 (3.75 KB / 32 bits).

Figure 8(b) shows the task mapping of the application in Open-Piton. Each task runs in one tile in a bare-metal fashion (without OS). The application communicates using semaphore operations of up() and down() to produce and consume data, respectively. Due to the absence of OS, the semaphore implementation spins the lock until it is released by the communicating task pair, then it advances to modify the semaphore counter. This behavior is important since it will stress the cache memory, as will be evaluated in the next subsection.

Split

Results

The goal of the results is not to enter in the merit of the application performance but evaluate the capabilities of ManyGUI to provide a rapid understanding of the many-core in terms of communication, memory usage, and energy consumption. For the sake of space, we reuse the frames of Figure 4.

The first basic information that can be achieved, is the simulation time, shown in all frames. It can be observed that the application took 72,974 cycles to finish its execution (marker (4) of Figure 4(b)).

Communication.

In communication frame, each tile was graphically modeled to represent the inputs and outputs of each NoC router. As OpenPiton has 3 NoCs, each tile has 3 sets of inputs and outputs that represent packets entering and exiting it. The inner draw of the tile represents the local interface between the memory with routers (which can be better understood jointly to the Figure 4). A descend arrow means a connection from a given memory module (L1.5 or L2) to the router. The ascendant arrow means the opposite, the connection from the router to the memory module.

The zoomed panel shown in marker [START_REF] Desnos | Distributed Memory Allocation Technique for Synchronous Dataflow Graphs[END_REF] of Figure 4(a) points that L2 of tile 0x0 is sending a packet by NoC2 to the L1.5 of tile 0x2 at time 15,864 (marker 2). Another interesting behavior is link utilization. Observing the marker (5) it is possible to see that the left-most NoC input link (NoC1) of tile 0x0 is saturated, with 93% of utilization. This behavior is expected because the application fits entirely inside the L2 cache of tile 0x0, which stores the data and semaphores locks used for synchronization among all tasks. This makes all the cores communicate with L2 of tile 0x0. As the communication on NoC uses XY algorithm, the south input port receives most of the packets since 6 in 9 (66%) tiles use this port to communicate with tile 0x0. Looking to the east input port of tile 0x0, we can see a link utilization of 40%. This usage is lower since only 2 tiles (22%) use this link to communicate.

Memory

. By observing the L1-D miss plots of Figure 4(c), it is possible to identify (after a warm-up period) 3 increasing patterns in the miss along the time. A similar pattern is found when selecting the L1-D access (not shown in the figure). These memory peaks occur because at each new application iteration (3 in total), the Split task overwrites new data in the shared buffers used by the Proc task to access the data. This invalidates the current data, increasing the L1-D misses. This behavior is endorsed by observing the detailed memory frame of Figure 5(b), specifically, the bottom-left plot, which shows the L1-D miss rate at tile 0x0. Clearly, 3 peaks can be observed in the miss rate, representing the 3 iterations of the application. In this same frame, it is also possible to observe that the L1-I miss rate (bottom-center plot) is higher during the warm-up period (up to 16 Kcycles) when the task's code is loaded inside the L1-I cache.

By using the plot generator frame, it is possible to look at the statistics closer. Additionally, it is possible to collect system-level metrics. As an example, Figure 9(a) and (b) shows the system miss rate for L1-D and L1-I, respectively. As expected, the L1-D miss rate (after warm-up) shows the same 3 patterns already explained. The horizontal line represents the average miss rate, which reached 6.7% in this case. In the L1-I miss rate, a peak occurs only during the warm-up, with the miss rate remaining below 0.1% after that. The average LI-D miss rate is 0.51%. The normalized total energy of the tile (top-right plot) shows that the NoC has a low influence on the total energy after the warm-up period, representing on average less than 4% of the tile's energy. This observation is in accordance with what was observed in the characterization of OpenPiton in silicon [START_REF] Mckeown | Power and Energy Characterization of an Open Source 25-Core Manycore Processor[END_REF], which pointed out the low impact of NoC in the chip's energy consumption. Additionally, the most important player in energy consumption is the memory (> 88% after warm-up), which in this case is highly used since the semaphores implement busy-wait spinlock.

Looking into the all tiles energy plots in Figure 4(b), we can see that the 3 peaks observed in the memory frame are correlated with the energy consumption of all tiles, except for tile 0x0, which presents the largest energy consumption among all. This energy consumption is directly impacted due to the high L2 usage of tile 0x0 previously explained. As the energy of miss and hit increases according to the highest cache level [START_REF] Mckeown | Power and Energy Characterization of an Open Source 25-Core Manycore Processor[END_REF], the L2 energy dominates the energy consumption of tile 0x0. To perform a detailed analysis, we use the plot generator frame to extract the accumulated energy of tile 0x0 in Figure 10

CONCLUSION

This work has investigated that state-of-the-art open-source platforms have an important gap in debugability of high-level events, leading the developer to meticulous tasks of debugging and correlating log files and waveform to understand what is happening during the simulation. We proposed ManyGUI , a graphical tool to debug many-cores, composed of a data extraction and classification framework connected to a set of graphical frames that allows to represent the many-core behavior during simulation in an intuitive way. The choice to focus in high-level events (instructions, memory, and NoC packets), allows to build a comprehensive profile of many-core in terms of communication events, memory events and energy consumption. We implemented the support of ManyGUI to state-of-theart silicon-proven many-core called OpenPiton. The experimental results show that ManyGUI can profile correctly NoC, cache memory, and energy consumption, presenting values already endorsed in silicon energy analysis.

ManyGUI is an open-source tool accessible to download in github.com/Nooman-LabSTICC/manyGUI. Since OpenPiton is also a open-source tool, we believe that the combination of both will contribute to accelerate many-core research. Future works include to add thermal estimation and collect events at the software level, allowing to correlate a given software region with the statistics of memory and energy. In such a way, the developer could improve the software design accordingly to the presented statistics.

Figure 1 :

 1 Figure 1: Overview of many-core functional design steps. This work proposes a high-level GUI-based debugging step, extending waveforms and log files.

Figure 2 Figure 2 :

 22 Figure2shows an example of a many-core with 4 tiles. To support event monitoring, we implemented inside each tile three types of event monitors: Instruction Counter Monitor (ICM), Memory Event Monitor (MEM), and Packet Counter Monitor (PCM). The role of these monitors is to extract events from the hardware model during the simulation and insert them into a database structure.The monitors implementation consists of non-synthesizable code inside key hardware points, which are generic to any modern manycore: CPU (ICM), memory (MEM), and NoC router (PCM). Inside CPU, the ICM extracts computation events by monitoring the executed instruction. Each ICM event consists of a timestamp in clock cycles, an instruction ID, and a class ID representing its instruction class (e.g., branch, ALU, multiplication, and floating-point). Inside

Figure 3 :

 3 Figure 3: Class diagram of the Event Classification Engine (ECE). (a) Classes that model the 3 collected events. (b)Classes that store all the events read from the database.

Figure 4 :

 4 Figure 4: ManyGUI main frames.(d) Energy detail frame (e) Memory detail frame

Figure 5 :

 5 Figure 5: ManyGUI detailed frames.

Figure 6 :

 6 Figure 6: Plot generator frame.

  4 www.matplotlib.org

Figure 7 :

 7 Figure 7: Hardware overview of OpenPiton many-core.

Figure 8 :

 8 Figure 8: Synthetic application.

Figure 9 :

 9 Figure 9: System statistics.

  (a) and the L2 miss rate in Figure10(b) (the red rectangles where manually inserted). It is possible to see in Figure10(b) that there are 3 periods where the energy remains practically constant. Such points correlate precisely with the 3 L2 miss rate plateaus of Figure10(a), caused due to the computing period of the Proc tasks. Such computation moments are outside of the critical region, and therefore do not push the L2 cache to keep the lock synchronized among tiles. As a last observation, Figure10(a) also allows for achieving the total energy consumption of tile 0x0, which was 218,648 nJ (maximum value of y-axis).

Figure 10 :

 10 Figure 10: Tile 0x0 statistics.

Table 1 :

 1 State-of-the-art (from 2017) many-core platforms.

	Name, Work, Year	Language	Computation	Memory	Communication	Open GUI Debug
	ProNoC, [11], 2017	SV	Generic (not the focus)	Distributed/core	Parameterizable VC-based NoC (inter-core) ✓	To generation (NoC-centered)
	CoreVA-MPSoC, [1], 2017 N.A.
							-
	RVNoC, [6], 2018	Verilog	RISC-V	Distributed/core	Parameterizable VC-based NoC	✓	-
	Celerity, [4], 2018	Verilog	RISC-V + NN Accelerator L1 cache/core	1x NoC	✓	-
	OpenPiton, [2], 2019	Verilog, SV	RISC-V	L1,L1.5/core + L2 slice/core	3x NoCs	✓	-
	Memphis, [14], 2019	VHDL, System-C	MIPS-I	Distributed/core	1x NoC	✓	NoC + CPU scheduling
	Kamaleldin et al., [7], 2020 N.A.	RISC-V	L1/core + L2/cluster	Bus (intra-cluster) + NoC (inter-cluster)	-	-
	BlackParrot, [12], 2020	SV	BlackParrot Core + Heterogeneous tiles	L1/core + L2 slice/core	1x NoC	✓	-
	Savas, [15], 2020	Verilog + Chisel RISC-V + Accelerator	L1/core + Shared L2 slice/core	1x NoC	✓	-
	Gem5-X, [13], 2021	C++	ARMv8 + Accelerators	L1/core + L2/Cluster + L3/System Bus	✓	-

CoreVA L1/core + L2 slice/Cluster Bus (intra-cluster) + 1x NoC (inter-cluster) --HERO,

[START_REF] Kurth | HERO: An Open-Source Research Platform for HW/SW Exploration of Heterogeneous Manycore Systems[END_REF]

, 2018 SV RISC-V + ARM L1/Cluster + L2/System Bus (intra-cluster) + 1x NoC (inter-cluster) ✓

Table 2 :

 2 Configuration file description.

	Name	Unit	Form. Description
	X Dimension	Number of tiles N	Horizontal length of many-core
	Y Dimension	Number of tiles N	Vertical length of many-core
	Offchip XY addr	NoC XY address NxN	Address of the router connected to the offchip interface
	NoC number	NoC	N	Amount of NoC or sub-NoCs
	Flit size	Bits	N	Size of one NoC flit
	Frequency	MHz	R>0	Many-core running frequency
	Monitor Window	Clock cycles	N	Size of one monitor window
	EnergyInstru<ALU>	pJ	R>0	Energy per ALU instruction
	EnergyInstru<Mult>	pJ	R>0	Energy per Branch instructions
	EnergyInstru<...>	pJ	R>0	...
	EnergyMem<L1 miss> pJ	R>0	Energy per l1 miss
	EnergyMem<L1 hit>	pJ	R>0	Energy per l1 hit
	EnergyMem <...>	pJ	R>0	...
	EnergyNoC <Flit>	pJ	R>0	Energy per flit hop

www.kalrayinc.com/products/mppa-technology

www.veripool.org/verilator/

ACKNOWLEDGMENTS

This work is supported by the Agence Nationale de la Recherche under Grant No.: ANR-17-CE24-0018.