Ralf Stemmer
email: ralf.stemmer@uol.de

Hai-Dang Vu
email: hai-dang.vu@univ-nantes.fr

Kim Grüttner
email: kim.gruettner@offis.de

Sebastien Le Nours
email: sebastien.le-nours@univ-nantes.fr

Wolfgang Nebel
email: wolfgang.nebel@uol.de

Sebastien Pillement
email: sebastien.pillement@univ-nantes.fr

Towards Probabilistic Timing Analysis for SDFGs on Tile Based Heterogeneous MPSoCs

Keywords: Probabilistic SystemC Model, Multi Processor, Real-Time Analysis

Performance and timing prediction of complex parallel data flow applications on multi-core systems is still a very difficult discipline. The reason for it comes from the complexity of the hardware platforms with difficult or hard to predict timing properties and the rising complexity of the software itself. In this work, we are proposing the combination of timing measurement and statistical simulation models for probabilistic timing and performance prediction of Synchronous Data Flow (SDF) applications on tile-based MPSoCs. We compare our work against mathematical and traditional simulation based performance prediction models.

We have shown that the accuracy and execution time of our simulation can be suitable for design space exploration.

I. INTRODUCTION

Today's and even more future life will be assisted by many small computer systems for sensing and interaction with its environment. The evolution towards the Internet-of-Things era is nowadays challenged by providing high data and sensing quality which will be assisted through machine learning and other AI techniques. Connected with this change is the major challenge of partitioning software between the node (edge, fog) and the cloud. Because of the growing demand in computational efficiency at the edge and fog level, more and more embedded systems are designed on multi-core platforms. In this context, our work addresses the challenge of performance prediction and optimization of complex data processing software running on multi-core edge and fog platforms. On the one hand performance prediction with a high fidelity for one specific data flow mapping and implementation is very important for the validation of extra-functional requirements, such as timing. On the other hand a complete analysis of all possible mappings and implementations of a data flow application have to be quantitatively assessed for choosing the optimal mapping (w.r.t. timing constraints such as application end-to-end latency). In this work we focus on the design space exploration (DSE) aspect of performance analysis.

Performance and timing analysis of parallel software, running on complex multi-core platforms is hard. In the domain of timing analysis of multi-core systems, existing simulationbased approaches and formal mathematical methods are dealing with either scalability problems for a large problem size or provide too pessimistic and thus unusable analysis results. Our work aims at improving scalability of analysis approaches by adopting probabilistic models and simulation techniques. The result is an experimental framework to validate and improve statistical analysis techniques for data flow applications on tilebase multi-core systems. A tile based MPSoC consists of multiple processors with private instruction and data memory. Inter tile communication is realized via dedicated FIFO channels or shared memory. In a previous publication [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF] we have already presented our measurement-based characterization approach and a SystemC based statistical simulation for probabilistic timing and performance analysis.

In this paper, we present the adoption of this approach to different case-studies. We systematically evaluate the benefits and limitations of our statistical simulation for timing analysis of two different data flow applications on tile based multicore systems. For this reason, we have built an experimental setup for the comparison of our probabilistic modeling and analysis against measurements on a hardware prototype, a state-of-the-art static analysis and a simulation based approach. This setup is used for different case-studies and mapping configurations. Configurations are representatives of multicore systems with dedicated FIFO channels, shared buses and shared memories. The evaluation metrics are accuracy of the estimations and analysis time. Moreover, scalability of the analysis approaches is evaluated with respect to different usecase, different platform configurations and different mappings.

The paper is organized as follows: In the next section we are analyzing the state-of-the-art where we are positioning and comparing our approach against other works in the area of timing analysis for multi-core-systems. Sec III presents our approach and provides more details about the creation and structure of our proposed probabilistic simulation model. In Sec IV we present our use-cases, the experimental setup, our comparison results and finally a discussion of these results. The paper closes with a summary and outlook on future work.

II. RELATED WORK

Analysis approaches are commonly classified as simulationbased approaches, which partially test system properties based on a limited set of stimuli, formal approaches, which statically check system properties in an exhaustive way, and hybrid approaches, which combine simulation-based and formal approaches. Simulation-based approaches require extensive architecture analysis under various possible working scenarios but the created architecture models can hardly be exhaustively simulated. Due to insufficient corner case coverage, simulation-based approaches are thus limited to determine guaranteed limits about system properties. Different formal approaches have been proposed to analyze multi-core systems and provide hard real-time and performance bounds. These formal approaches are commonly classified as state-based approaches and analytical approaches. Despite their advantages of being scalable, analytical methods abstract from state-based modus operandi of the system under analysis which leads to pessimistic over-approximated results compared to state-based methods [START_REF] Perathoner | Influence of different abstractions on the performance analysis of distributed hard real-time systems[END_REF]. State-based methods are based on the fact of representing the system under analysis as a transition system and since they reflect the real operation states of the actual system behavior, tighter results can be obtained compared to analytical methods. Many recent approaches for the software timing analysis on many-and multi-core architectures are built on state-based analysis techniques [START_REF] Gustavsson | Towards WCET analysis of multicore architectures using UPPAAL[END_REF]- [START_REF] Fakih | State-based realtime analysis of SDF applications on mpsocs with shared communication resources[END_REF]. However, state-based approaches allow exhaustive analysis of system properties at the expense of time-consuming modeling and analysis effort. The existing state-based approaches are thus dealing with scalability problems and multi-core architectures with complex levels of hierarchy in shared resources can hardly be addressed [START_REF] Fakih | State-based realtime analysis of SDF applications on mpsocs with shared communication resources[END_REF].

Statistical Model Checking (SMC) has been proposed as an alternative to formal approaches to avoid an exhaustive exploration of the state-space model [START_REF] Legay | Statistical model checking: An overview[END_REF]. As classical model checking approach, SMC is based on a formal semantic of systems that allows to reason on behavioral properties. SMC is used to answer qualitative questions 1 and quantitative questions 2 . It simply requires an executable model of the system that can be simulated and checked against statebased properties expressed in temporal logics. The observed executions are processed to decide with some confidence whether the system satisfies a given property. This allows systems that can not be assessed with an exhaustive approach to be approximated. Finally, as a simulation-based approach, it is less memory and time intensive than exhaustive statebased approaches. Various probabilistic model-checkers support statistical model-checking, as for example UPPAAL-SMC [START_REF] David | Statistical model checking for networks of priced timed automata[END_REF], Prism [START_REF] Kwiatkowska | Prism 4.0: Verification of probabilistic real-time systems[END_REF], and Plasma-Lab [START_REF] Jegourel | A platform for high performance statistical model checking -plasma[END_REF]. SMC was adopted in [START_REF] Nouri | Building faithful high-level models and performance evaluation of manycore embedded systems[END_REF] to evaluate a many-core architecture based on a 64-core homogeneous platform. The statistical model checking tool called BIP SMC [START_REF] Nouri | Statistical model checking qos properties of systems with sbip[END_REF] was used to evaluate the probability that timing aspects such as execution time and variability of processing time were bounded. The usage of UPPAAL-SMC to optimize task allocation and scheduling on multi-processor platform has been presented in [START_REF] Chen | Variation-aware evaluation of mpsoc task allocation and scheduling strategies using statistical model checking[END_REF]. Application tasks and processing elements were captured in a Network of Price Timed Automata (NPTA). It was considered that each task execution time follows a Gaussian distribution. In the scope of our work, we especially focus on the preparation process of probabilistic models of execution time. A comparison of formal model checking with SMC has been presented in [START_REF] Stemmer | Probabilistic state-based RT-analysis of SDFGs on MPSoCs with shared memory communication[END_REF]. A multi-processor system was modeled using timed automata and probabilistic timed automata in UPPAAL-SMC. While formal methods use only best and worst case execution times the SMC method allows to model the distribution of execution 1 Is the probability for a model to satisfy a given property greater or equal to a certain threshold?

2 What is the probability for a model to satisfy a given property? Fig. 1. Overview of our workflow. Hardware and Software gets designed following specific models. Then one instance of the system on an FPGA gets characterized. The resulting model can then be analyzed for real time properties (green). For evaluation we also create a static mathematical model shown with dashed red lines. And in dashed orange lines, only observed WCET gets considered.

times between those limits. The possibilities of modeling such a distribution is limited due to UPPAALs modeling language. In contrast to that work, our new SystemC approach allows to not only use a rough model of the distribution but the actual measured execution times. However, SMC methods have rarely been considered to analyze timing properties of applications mapped on multi-processor systems with complex hierarchy of shared resources, especially because the creation of trustful probabilistic SystemC models remains a challenging task. Based on the established framework we attempt to systematically evaluate the benefits of using probabilistic SystemC models to analyze the timing properties of SDF based applications on multi-processor systems, targeting more tightness of estimated bounds and faster analysis times.

The novelty of our presented approach lies in the definition of a measurement-based modeling workflow for the creation of probabilistic SystemC models. SystemC models are calibrated with stochastic execution times that are inferred from measurement done on real prototypes with multi-processor architectures. The efficiency of this workflow to architectures with different levels of complexity is evaluated through different case-studies.

III. APPROACH

Our established workflow is illustrated in Fig. 1. We show our input models for our approach in magenta. The computation model is explained in detail in Sec III-B. The architecture model is explained in Sec III-A These models were used to design our hardware and software system. For later references, we highlighted assumptions with an A.

The system that gets build under the constraints of those models can then be analyzed regarding its timing behavior. Therefore we use a measurement infrastructure described in detail in [START_REF] Schlaak | Power and execution time measurement methodology for sdf applications on fpga-based mpsocs[END_REF]. This measurement method guarantees that there will be no interfering with the main system buses or nonpredictable influence to the code execution on the processor.

The mapped and scheduled software gets executed on the designed hardware that gets instantiated on an FPGA. This real system is used to characterize the timing behavior of the hardware components as well as the actors of the SDF based application (shown in Fig. 1 analysis focusing on the distribution of the execution times.

We also run a simulation only considering the WCET as comparison (Fig. 1 orange). Furthermore we apply a static mathematical model (Sec III-D), that considers the WCET of the actors and for communication (Fig. 1 red).

A. Model of Architecture

Our hardware platform follows the definition from [START_REF] Stemmer | Probabilistic state-based RT-analysis of SDFGs on MPSoCs with shared memory communication[END_REF] and [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF]. A simple example of such a platform is shown in Fig. 2 (purple). In contrast to the referenced work, we scaled up the system to 7 heterogeneous tiles instead of only 2 tiles.

One processing element with a separate connected private memory is called tile. A1: Executing instructions from this private memory also causes no interference with other tiles. This allows us to design a composable multi processor system. In our system, some tiles are equipped with a floating point unit (FPU) or a hardware multiplier (MUL).

For data exchange between different tiles a shared memory is used, connected via a shared interconnect to the processors and A2: the arbiter uses Round-Robin strategy.

A3: For all memories we use static RAM an do not use any caches. The hardware gets instantiated on an FPGA. A4: All tiles and memories are connected to the same clock.

For comparison we also one experiment on a 4 tile system with peer-to-peer connections. The tiles are connected via exclusive hardware FIFO buffers. This hardware architecture is optimized for the communication structure of the application, so that communication can take part without any interference.

B. Model of Computation (SDF)

We use Synchronous Data Flow (SDF) [START_REF] Lee | Synchronous data flow[END_REF] as computation model (MoC). A simple example of an SDF graph is shown in Fig. 2

(magenta).

This model is used to describe the data flow between actors via communication channels . SDF offers a strict separation of computation (compute) and communication phases (read, write) of actors. During the compute phase, no interference with any other actor can occur. For MPSoCs this separation only works when the instructions are placed on separated memories (Assumption A1), connected with separate interconnects to the processors as presented in Sec III-A. For communication, data get separated into tokens. It is assumed that A5: one token is exact one data word on the interconnect.

Channels are FIFO buffers that can be mapped to any memory that is accessible by the producer (an actor that writes on that channel) and the consumer (an actor that reads from that channel). During the read phase of an actor, tokens get read from the channels buffer. During the write phase, tokens get written into the channel. The amount of tokens a producer writes, or a consumer reads is called token rate. A6: The FIFO access is blocking. An actor can only switch to its compute phase after it read all tokens from all incoming channels. After the compute phase, the actor switches into write phase to write all tokens to the outgoing channels.

A7: The SDF application is self scheduled. After one actor finished writing onto all its outgoing channels, the next actor on the tile starts with its read phase. In case any depending actor (that gets executed on a different tile) did not write its token on the incoming channel of the scheduled actor, it polls on the buffers channel until the data is available.

C. Measurement

For our timing models we need to characterize the compute phase of actor as well as the communication between actors.

For the compute phase we measure the amount of clock cycles a phase needs to be executed. This is done for different input data (input tokens). Since the code of an actor changes on different processors (e.g. with and without FPU), for each processor flavor this characterization needs to be done.

For the communication phases, we use a more sophisticated model that requires some static code analysis as described in [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF]. Therefore the execution of instructions used to access a channel buffer gets considered as well. This allows us to simulate the communication in detail to know when and for how long communication takes place.

For measuring execution times we use a measurement infrastructure based on [START_REF] Schlaak | Power and execution time measurement methodology for sdf applications on fpga-based mpsocs[END_REF]. The infrastructure is split into three components. Two of them are shown in Fig. 2

(green).

The Time Measurement Unit (TMU) is basically a counter with the same cycle rate the processors have. The counter can be started and stopped from any tile individually without interference. When the counter got stopped, it sends its counter value via UART to a host computer. For this method, it is important that all components are clocked with the same frequency (Assumption A4). The management of the individual start/stop signals from the tiles are managed by the Timing Measurement Controller (TMC).

To connect each tile with the TMC a Timing Measurement infrastructure Bridge (TMB) is used to translate a data package from a peripheral bus into the individual control signals (start/stop). A8: We assume that each tile has independent communication features that do not interfere with the system bus (For example General Purpose Input/Output (GPIO) pins or a dedicated peripheral bus). This guarantees that starting or stopping a measurement does not cause any interference on the other bus systems. For our MicroBlaze based system, the AXI Stream Interfaces get used. Since the TMB is only a simple transcoder (if not directly GPIO pins are used), it is not explicitly shown between the tiles and the TMC in Fig. 2.

From the measurements we not only get the BCET and WCET of specific parts of the software like the computation phase of an actor or the access of shared memory. We also get the distribution of execution times for the measured elements which will be used in our probabilistic model. The BCET, WCET and average case execution time gets derived from the measured time values. In the context of our work, Worst-and Best-Case only describes the observed execution times.

D. Static Analytical Model

This subsection presents the static analytical model we use to compare our simulation based approach with (See Fig. 1). For the static approach we need to make further assumptions that only relate to the static analytical model. We mark those assumptions with AS. The model is based on [START_REF] Shabbir | Ca-mpsoc: An automated design flow for predictable multi-processor architectures for multiple applications[END_REF] and [START_REF] Hoes | Predictable dynamic behaviour in noc-based multiprocessor system-on-chip[END_REF].

As mentioned in Sec III-B, the execution of an actor is split into three phases: read, compute, write. Those phases are also represented in the equation 1 for calculating the execution time of an actor. For the compute phase t compute , the measured computation time of an actor gets used. The delay of reading t read (r) (Equ. 2) and writing t write (Equ. 3) is a function of the token rate R(c) of a channel c. All incoming channels C in and outgoing channels C out need to be considered.

t exec = c∈Cin t read (r(c))+t compute + c∈Cout t write (r(c)) (1)
The equations for reading (Equ. 2) and writing (Equ. 3) need to consider the bus access time for reading (t r ) and writing (t w ) onto the bus. For our system, one token is one word on the bus (Assumption A5). Some computational overhead needs to be considered via t cr for the reading procedure and t cw for the writing procedure. Bus arbitration time t a is determined by Equ. 4. Those three delay parts (t r/w , t a , t c ) occur for each token r including further data r meta for managing the FIFO buffer of a channel.

t read (r) = (r meta + r) • (t a + t r + t cr ) (2)
t write (r) = (r meta + r)

• (t a + t w + t cw ) (3)
The arbitration delay t a (Equ. 4) is calculated under the assumption of having a Round-Robin bus arbiter (Assumption A2). Furthermore we assume for our static model that AS9: each other tile of all tiles (n tiles ) of the system gets bus access before and that AS10: each of those tiles holds the bus access for the longest possible amount of time. For a single beat bus protocol this is ether reading or writing a word onto the bus.

t a = (n tiles -1) • max (t r , t w ) (4)
The data for the computation time of an actor (t compute ) comes from our measurement infrastructure (Sec III-C). The delay for t r/w as well. The computational overhead t c r/w is based on static code analysis as presented in [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF].

To calculate the time a complete iteration of executing the SDF application takes, the execution times t exec for all actors that get executed in serial needs to be summed up. For actors that get executed in parallel, the longest execution time will be considered. Furthermore it is assumed that AS11: an actor gets only executed, when all its preceding depending actors are completely executed, which may take longer than waiting until all tokens on the channel are available. For the peer-to-peer connected platform (Fig. 5, left) we can simplify some equations. The meta-tokens in Equ. 3 and Equ. 2 for managing the FIFO buffer are not needed because the FIFO behavior is implemented in hardware. Furthermore there is no arbitration. This leads to the following simplification: r meta = 0, t a = 0. The value of t r/w as well t c r/w must be adapted to the different implementation and bus interface.

E. SystemC Model

The SystemC model is a representation of the whole system. It models the mapped and scheduled SDF application on a specific hardware platform. Fig. 3 shows in the top half the SystemC model for a 3 tile platform. In blue the parts of the SystemC model are shown, in green everything related to the measured timings (Sec III-C). The bottom half of the figure shows, how the simulated system gets transformed into the actual system. In purple hardware related parts are described, in magenta all software related parts.

The SystemC model consists of three major parts: 1) the Tile modules for simulating the actors' execution on a tile, 2) the Interconnect module that simulates the bus behavior and 3) the Shared memory module for the read and write access to shared memory.

Tiles represent the actual tiles of the modeled platform as well as the execution of the SDF actors mapped on this tile. The timing behavior of the actors is simulated in an SC THREAD of the tile module. The computation phase of an actor is a wait statement using the actors' computation time t compute ∈ T actor . Furthermore the Tiles-Module provides a model of the function used for communicating over channels. The timing behavior was analyzed and modeled in detail via static code analysis on instruction level we describe in [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF].

The Interconnect module manages the structural integrity by connecting all tiles to shared memories.

The Shared Memory module simply distinguishes read t r and write access t w . Depending on the access type, it proceeds the simulation time by the related time.

In our simulation we use two representations of computation time. For WCET simulation the computation time of an actor is represented by its observed worst case computation time. For considering the distribution of execution times of an actor, we use all observed execution times. In each simulated iteration of the system, a new execution time of an actor gets selected from a list of observed delays (see Fig. 3). This is realized by reading a text file that provides the raw measured computation time of this actor. We randomly select (using std::random_shuffle) data from the list of delays, taking care that no element of this list gets selected twice. We refer to this random selection of recorded execution times as injected data or injected distribution in the following experiments. Depending on the experiments it is possible to switch between Injected, Uniform or Gaussian distribution as well as only the WCET. For Uniform and Gaussian distribution we use the GNU Scientific Library (GSL) [START_REF] Galassi | The gnu scientific library reference manual[END_REF]. The parameters for these distributions are derived from the measured delays.

The Tile, Interconnect and Shared Memory SystemC modules can be directly transferred to the real hardware. (Fig. 3) The target platform can be designed on an FPGA if the simulation not already represents existing hardware. The main loop of the SystemC threads represent the main loops of the firmware executed on the actual tiles. Instead of the waitstatement, the actual function of the actor must be called. Furthermore the ReadTokens and WriteTokens function now expect an address of a local buffer for the actual token.

To analyze different type of tiles with different processing elements, only the timing characteristics of the actors must be updated by measuring their computation time distribution on such a processing element. For different memories, the regarding access times, or the memory model needs to be updated. For different interconnects the ReadTokens and WriteTokens model as well as the interconnect module needs to be updated.

IV. EXPERIMENTS

This section describes our experiments. We first characterize all actors of our use-cases. Then we simulate different possible mappings to get the worst case and average case execution time, as well as a distribution of possible execution times of an iteration of the executed software. We then execute those experiments on the real platform and measure the actual execution times of each iteration to compare the real system's behavior with our analysis.

We present our use-cases in Sec IV-A and our hardware platform in Sec IV-B. In Sec IV-C we describe the mapping of the use-cases on our platform. The characterization is shown in Sec IV-D At the end of this section we present and discuss the results of our experiments.

We provide git repositories3 for our use-cases, measurement infrastructure and models.

A. Use cases

In our experiments we want to analyze the execution time of an iteration of an SDF base application (Sec III-B). Therefore we apply our models to 2 different software applications:

Sobel-Filter (Fig. 4 left). In this use-case, the communication part of the software takes most of the execution time. The computation part should be highly predictable when executed on tiles with an hardware multiplier, because there are only a few possible execution paths except of GetPixel actor. The results of analyzing this application could benefit from a detailed communication model as we use it in our simulation.

JPEG Decoder (Fig. 4 right). This use-case has a huge computation part with an unmanageable amount of execution paths for most of the actors. Except for the inverse quantization (IQ-Actors) which is only a matrix multiplication and has only one execution path when a hardware multiplier is available. The results of analyzing this application would benefits from considering the distribution of possible execution times instead of just considering BCET and WCET.

B. Platform

For most of our experiments we use a heterogeneous multiprocessor system with 7 tiles (Fig. 5 right). The individual tiles use a MicroBlaze soft core that is equipped with private memory. The tiles T1, T2, T3 are extended by a hardware multiplication unit (MUL). Tiles T4, T5, T6 are extended with a floating point unit (FPU). Furthermore there exists a shared memory that is used for communication between the tiles.

Since the Sobel-Filter use case has a high communication part compared relative to its computation part, we also built an experiment with a hardware platform that is ideal for this application (Fig. 5 left). It comes with 4 tiles that have a peer-to-peer connection to avoid any bus contention. These connections are realized by hardware FIFO buffers so that also the computational overhead for communication is reduced to a minimum to make analysis as simple as possible.

C. Experiment setup

This subsection describes the experiments we did with our use-cases. We label our experiments for later reference in the results section. Furthermore we highlight and enumerate the hypotheses we want to check with an H.

For the Sobel-Filter we run 3 experiments: Sobel1, So-belP2P and Sobel4. For the JPEG decoder we also run 3 experiments: JPEG1, JPEG3 and JPEG7.

For all experiments the instructions and local data of an actor is mapped on the private memory of a tile. The mapping of the actors of our application for the individual experiments is shown in Tab. I. With exception of the peer-to-peer experiment, all communication channels of our application are mapped on the shared memory of our platform (Fig. 5).

Sobel1 In our 1 st experiment, we execute all actors of the Sobel-Filter on a single tile that comes with a hardware multiplication unit. H1: This should be the most easy setup since the amount of possible execution paths are minimized and there is no contention possible on the interconnect. SobelP2P In the 2 nd experiment we run the Sobel-Filter on a 4 tile platform with peer-to-peer connection (Fig. 5 left). The mapping corresponds to the 4 tile mapping in Tab. I. H2: This setup shall avoid any bus contention, simplify the communication model by using hardware FIFOs and provide hardware multiplier to get a predictable multiprocessor system.

Sobel4 The 3 rd Sobel-Filter experiment uses the same mapping as in the SobelP2P experiment, but now on the 7-Tile hardware platform (Fig. 5 right). Again, the mapping considers the usage of hardware multiplication.

These three Sobel-Filter experiments are used to evaluate the communication model of our simulation and static analysis model. Compared to the Sobel-Filter, the JPEG decoder is much more compute intensive and uses algorithms that come with much more execution paths.

JPEG1 In the 1 st JPEG experiment we run all actors of the decoder on tile 0, that does not provide any hardware accelerators for multiplications and floating point operations. So these operations are done in software (via libgcc 8.2.0) which introduces further execution paths. H3: This mapping should lead to highly unpredictable execution times and challenge our probabilistic approach.

JPEG3 The 2 nd JPEG experiment uses 3 tiles. H4: This experiment should the execution paths since the actors benefit from the hardware accelerators they need. JPEG7 In the last experiment all 7 tiles are used for mapping the actors to focus on highest possible parallelisation. The actors are mapped on tiles that provide the hardware accelerators they can make use of. H5: This should lead to better predictable execution times for the computational part, but lead to much communication on the bus. This experiments challenges the communication model of our simulation and the static analytical model.

For the simulation using injected data we do 1 000 000 simulation runs, so that we make use of all observed timings. This is not an exhaustive simulation since this covers not all possible combination of execution times. For the WCET simulation we do only 10 000 runs, because the variety of input data is much less (one delay per actor).

D. Characterization

To estimate the execution time of an iteration of the executed application, the timing behavior for each actor needs to be characterized once.

In our heterogeneous platform (Fig. 5) we have 3 different kinds of tile-based architectures. A simple MicroBlaze architecture without any extension, an FPU extended MicroBlaze and a MicroBlaze with a hardware multiplication unit (MUL).

Our two applications (Fig. 4) are compiled for all three architectures to make use of the additional instructions. The compilation process is only done once per architecture to make sure that the timing behavior of an actor never changes after it got characterized. The compiled actors then get only linked into the firmware of each processing element.

For measurement, a start and a stop instruction for the measurement infrastructure get placed into a test application. The position of the measurement instructions are around the call of the actors function, after the read-phase and before the write-phase. So only the compute-phase gets measured.

Then the actor gets executed with representative stimuli data. For our experiments, we used a 48 px × 48 px grayscale white-noise image for our Sobel-Filter application. For the JPEG decoder a 128 px × 128 px landscape photo with a quality of 95 % is used. Each actors compute phase, compiled for each architecture got measured 1 000 000 times.

For our probabilistic simulation we use all measured samples to have a realistic execution time distribution. The simplified Worst-Case-Simulation only uses the observed worst-case execution time for each actors samples.

For our static analytical model we use the observed worstcase execution time for t compute for the worst-cases analysis. The average case analysis is done by using the average execution time of all actor's samples for t compute .

For the evaluation of our experiments, we also need to measure the execution time of whole iterations of the application. This requires instrumentation of the actual application without changing its timing behavior. Starting and stopping a measurement takes exact 2 clock cycles. To avoid changing the temporal behavior of the measured software this needs to be considered. At any point access to the measurement infrastructure is required, No-Operation instructions must be placed that take the exact same amount of time. For our usecases it is before the first actor and after the last actor of our applications are called.

E. Results

The results of our experiments are presented in Tab. II. We compare the observed execution times of an iteration of our use-cases with the results of the static analytical model and our simulation. We also shows the error of our models compared to the observed behavior. In the first column (Experiment), the experiments from Sec IV-C are listed. The top half of the table shows the observed worst case execution times, the bottom half the average case. After the experiments names, the measured iteration duration of our SDF applications are presented (Measured). For the worst case analysis, the highest observed delay is shown, for the average case the average of all observed delays is shown. The next three columns (Anal. Model, WC Simulation and Prob. Simulation) present the results of our analysis. The input data (actor execution time) varies between the analysis approaches. For the static analytical model, the measured WCET of the actors are used for the worst case analysis, and the average execution time for the average case analysis. The worst case simulation (WC Simulation) uses only the WCET of an actor and only returns the worst case iteration time. For the probabilistic simulation (Prob. Simulation) the distribution of execution time is used as input These simulations also return a distribution of possible iteration delays (Shown in Fig. 6). For the worst case analysis, the highest returned iteration duration got selected. For the average case the average value of all returned iteration delays got calculated. The static analytical model tends to over-approximation, especially for applications that actors get executed in parallel. The simplified and more predictable communication for the SobelP2P experiment reduced the over estimation. For the Sobel-Filter executed on 4 Tiles (Experiment Sobel4) the analysis has the highest error of 89.40 %.

Our simulation based approached has higher error for single processor applications with an error of up to 7.22 % for the Sobel1 experiment. Also for the peer-to-peer connection based platform for experiment SobelP2P the error is high with 7.35 %. Tab. II also shows, that for mappings with high communication (more tiles) the simulation under-approximates with up to -5.17 % for average case simulation of the Sobel-Filter application (Sobel4).

In general the analytical model has higher errors than the simulation compared to the measured execution times. Because we focus on DSE and not on WCET analysis, under-approximation is not considered worse than over- In Fig. 6, the measured (blue) and the simulated (green) distribution of the execution time of an iteration are presented. The dotted line marks the average execution time, the solid line the observed worst case. For the Sobel-Filter experiments the relative high error of up to 7.22 % (Sobel1, WCET) and -5.17 % (Sobel4, Average case) is visible. For the JPEG decoder the figure shows a better fitting of the simulated execution times with the observed ones. Fig. 6 also demonstrates the advantages of considering the distribution of execution times. The distribution of the analyzed execution times come close to the distribution of the observed execution times.

In Tab. III the execution time to run the simulations is shown. We simulated with 1 000 000 computation time samples for each actor. Each simulated experiment represents our 7 Tile platform with exception of the SobelP2P experiment.

The left column of Tab. III shows the simulation time considering the distribution of execution times. We simulated 1 000 000 iterations. For efficiency we split our simulation into 20 processes (each on a dedicated processor), each simulating 50 000 iterations.

The middle column shows the worst case simulation considering only the worst observed computation time for each actor. Since there is no variance in the computation time we simulated only 10 000 iterations. During these simulations we observed the worst case execution time (Tab. II, WC Simulation) at minimum of 715 times for the Sobel4 experiment.

The right column shows for comparison the time it took to measure the actual execution time on the real platform. Again, 1 000 000 samples were measured.

The simulation time varies from a few seconds up to one hour for the JPEG7 experiment.

F. Discussion

In preliminary work [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF], [START_REF] Stemmer | Probabilistic state-based RT-analysis of SDFGs on MPSoCs with shared memory communication[END_REF], [START_REF] Stemmer | Feasibility Study of Probabilistic Timing Analysis Methods for SDF Applications on Multi-Core Processors[END_REF] we compared different delay distribution of the simulated actors of our model regarding the error of the results. We repeated this experiment for the JPEG1 experiment because it is more compute intensive (Hypothesis H3) than the Sobel-Filter of our previous work. The results are presented in Fig. 7. Beside the distributions (Uniform (magenta), Gaussian (blue), Injected (teal)) we also varied the amount of simulation runs (Fig. 7 ordinate). We compared the results of the simulation with the observed behavior regarding average execution tile (filled data points) and WCET (outlined data points). The error is depicted on the abscissa of Fig. 7. The uniform distribution of delays between the observed BCET and WCET are suitable for quick WCET estimations but have a high error for the average case, independent how many simulation runs are performed. The reason is that the average case of our applications is not in the center between their BCET and WCET. For our worst-case estimation (Tab. II, WC Simulation) we did 10 000 simulation runs using only one static delay. The Gaussian distribution is good for a quick average case estimation because the center point of the distribution is based on the mean value of our observed actor delays. The width of the Gaussian distribution leads to a very high over estimation of the WCET. The injected distribution, provides good average case and good worst case estimation. A downside is the need of many simulation runs to reduce the error. For our simulation using the injected distribution (Tab. II, Prob. Simulation) we did 1 000 000 simulation runs.

The static analytical model shows good results for application with high computational parts (Experiments JPEG1, JPEG3 and JPEG7), because it benefits from our measurement based analysis of the execution times of each actor. The static analysis of the Sobel-Filter executed on 4 Tiles (Experiment Sobel4) has an error of 89.40 %. This is due to the fact, that the static model does not considers interleaving of execution phases of depending actors executed in parallel (Assumption A11). For the Sobel4 experiment, the actor GX could already start its read phase while GetPixel is still in its write phase, writing data on the channel to GY. For applications with short computation phases and long communication phases, this situation has a huge impact to the analyzed execution time.

Our simulation results are closer to the actual system because of the detailed communication model. Anyway, there is still a high error for the Sobel1 and Sobel4 experiments. The negative error of the Sobel4 and JPEG7 simulation may be due to an over optimistic communication model, because for the Sobel-Filter as well as for the highly parallel JPEG decoder a good communication model is crucial.

The different worst case estimations of the WC Simulation and Prob. Simulation are due to the different inputs of the simulation. While the WC Simulation only uses one static delay for each actor (the worst observed delay), the probabilistic simulation uses the whole distribution of all observed execution times. In case of the JPEG1 experiment, this allows more than 1.17 × 10 21 different combinations of actor delays which is not covered by our simulation. Therefore the combination of all worst actor delays may be not included in the 1 000 000 simulation runs. The Sobel4 experiment shows that considering only the worst case actor delays may not reveal the worst case iteration delay. Using the whole range of possible delays lead to a situation where the impact of the communication between actors caused a longer iteration time.

The error of the SobelP2P experiment is because of limitations of our communication model. While our hypothesis H2 is valid regarding the simplicity of the communication hardware, the software to access the hardware FIFOs is hard to model because the processor architecture uses different instructions to access individual FIFOs. This leads to code with high branching behavior that is hard to represent in our communication model for the simulation [START_REF] Stemmer | Experimental evaluation of probabilistic execution-time modeling and analysis methods for SDF applications on MPSoCs[END_REF] as well as the model used for our static analysis Sec III-D.

The results of our analysis also show, that the distance between the worst case and the average execution time of an iteration is low. For the Sobel-Filter, the reason is the small interval of the actual execution time (Sobel 1: 21802 . . . 22052, Sobel 4: 17887 . . . 18128). For the JPEG Decoder, in average the execution time is closer to the worst case than to the best case execution time as it can be seen in Fig. 6.

Fig. 6 also shows that our simulation comes close to the observed distributions, despite some offsets for the Sobel-Filter. The knowledge of the distribution of execution times can be used estimate how close the average case or the median is to the worst case. This can be useful for soft-real-time applications since it allows to estimate how often a certain deadline can be missed.

The JPEG experiments demonstrate the benefit of our approach for design space exploration. While increasing the number of tiles from 1 to 3 tiles with different accelerators, the execution time of an iteration decreased by the factor of 2.3 in average (Based on the Prob. simulation results in Tab. II). By further increasing the number of tiles to 7, so that each color channel of the JPEG image can be decoded in parallel, the average execution time only decreased by the factor of 1.01 compared to the 3 tile mapping. The JPEG decoder benefits from a heterogeneous 3 tile system compared to only 1 tile. Further tile have only little influence in the performance of the decoder and can be avoided to lower the hardware cost.

The fast simulation time (Tab. III) allows exploring different hardware configurations an mappings in short time. The comparison with the measurement time shows the benefit of our simulation. Beside the fact that the simulation makes the existing of the actual system needless, it is also faster than measuring each possible mapping. The reason for the long measurement time for the JPEG Decoder is the circumstance that the execution time of the decoder itself is very high For the JPEG1 experiment, an iteration takes up to 2 746 197 cycles for the worst case. At a tile frequency of 100 MHz this is approximately 27 ms per iteration. For 1 000 000 samples the execution time can be up to 19 h. This is why the measurement time in Tab. III correlates with the execution times in Tab. II.

Tab. III shows the simulation time for our experiments in hours. The low simulation times for the Sobel-Filter experiments and the JPEG-Decoder that got mapped on one Tile comes from the efficient communication between the actors. As long as no other actor is polling on data, the simulation can proceed the simulated time by the execution time of an actor. When there is an actor polling on data in parallel, then the simulation can only proceed by the time steps of the communication model. In our model, polling takes about 20 Cycles. If an actor polls on data of a preceding actor with an execution time of about 66 000 Cycles (GetMCU of the JPEG application) that gets executed in parallel, then the simulation gets slowed down by the factor of 3300. So the less polling is necessary for the simulated application, the faster the simulation is. An improvement of the simulated model (using events) and improving the communication model (more abstraction) can improve the simulation speed tremendously. This will remain future work.

V. CONCLUSION

In this paper we presented the benefits and limitations of our simulation based real-time analysis method. In comparison with a static mathematical model, the error of our model is smaller. Furthermore does our method provide an approximation of the distribution of execution times for the analyzed system. The increasing simulation time for system with large application (long computation time) and many cores is currently limiting our approach to small systems.

Our approach is limited to tile-based multiprocessor systems. To apply measurements to actors on this platform it furthermore must provide the necessary individual independent outputs. In our experiments we synthesized such a system on an FPGA. But there are also commercial off-the-shelf platforms available that fulfill these requirements [START_REF] Inc | Parallax propeller[END_REF].

The advantage of our approach is that our analysis not only estimates a WCET, but also provides an approximation of the distribution of possible execution times. Furthermore we use actual observed actor execution times as input which reduces the error of the analysis, because approximated function can lead to execution times that are outside the observed BCET/WCET boundaries (Gaussian distribution) or represent an unrealistic average execution time (Uniform distribution). This allows us using a single tile (e.g. on a cheep evaluation board) for characterizing all actors of an application, and later decide, based on our simulations, how many tile in combination of different mappings and features are suitable for a specific application.

With our experiments we confirmed that our model is consistent and matches the reality with an error of less than 7.4 % for WCET estimation and 6.8 % for the average case. Our model needs some improvements to avoid negative errors for WCET analysis. For the average case, the negative errors are less critical. The accuracy in combination with the distribution of possible execution times and fast analysis time our approach is very suitable for design space exploration.

VI. FUTURE WORK

In future work we plan to improve simulation quality as well as simulation speed by creating a more abstract communication model and considering data dependencies to reduce the amount of simulation runs as well as lowering the error for some application. Our current communication model represents communication in detail. A more abstract probabilistic model as used for the computation can increase simulation speed. We also did not consider any data dependency in our model. By considering data dependency, our model can not only be used for functional testing but also provides the possibilities to reduce simulation runs by avoiding redundancy and having a metric for determine the coverage of data paths.

One further step would be reduce the required number of simulation runs with SMC methods. SMC methods, such as the Monte Carlo method, allow the number of simulation runs to be controlled with given level of confidence. By controlling the number of simulation runs, a trade-off between high confidence and fast analysis time is possible. The instrumentation and monitoring of SystemC models to carry out statistical analysis were presented in [START_REF] Ngo | Statistical model checking for systemc models[END_REF]. This approach could thus be adopted to quantitatively evaluate from the created models properties like the probability to miss a deadline.

In the context of WCET analysis, authors in [START_REF] Cazorla | Proartis: Probabilistically analyzable real-time systems[END_REF], [START_REF] Cazorla | Proxima: Improving measurement-based timing analysis through randomisation and probabilistic analysis[END_REF] proposed a measurement-based approach in combination with hardware and/or software randomization techniques to conduct a probabilistic worst-case execution time (pWCET) through the application of Extreme Value Theory (EVT). In future work we are going to analyze under which conditions (assumptions on the measurement and model calibration) we can apply EVT on our analytical execution time distributions to provide an analytic pWCET.

Fig. 3 .

 3 Fig.3. Overview of our SystemC model with 3 tiles and how it is related to the later implementation of the simulated system. Tile 0 is presented in detail, with one actor (IDCT Y ) mapped on it.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Applications we use in our experiments represented as SDFG.

Fig. 6 .

 6 Fig.6. Distribution of the measured data (blue) compared to the results of the probabilistic simulation (green) for all experiments. The dashed lines show the median of the distribution, the solid lines the observed worst case.

Fig. 7 .

 7 Fig. 7. Detailed analysis of the JPEG1 experiment. We compare Simulation runs to the error of the analysis results compared to the observed average and worst-case behavior for different distributions.

TABLE I MAPPING

 I OF THE SOBEL-FILTER AND JPEG EXPERIMENTS ON THE TILES OF THE HARDWARE PLATFORM.

	Experiment→ JPEG JPEG JPEG Exp. → Sobel Sobel
	Actor ↓	1 Tile 3 Tile 7 Tile Actor ↓ 1 Tile 4 Tile
	Get MCU	0	0	0	GetPixel	1	1
	IQ Y IQ Cr IQ Cb IDCT Y	0 0 0 0	1 1 1 4	1 2 3 4	GX GY ABS	1 1 1	2 3 0
	IDCT Cr	0	4	5
	IDCT Cb	0	4	6
	YCrCb RGB	0	0	0

TABLE II COMPARISON

 II OF THE STATIC MODEL AND THE SIMULATION RESULTS WITH THE ACTUAL OBSERVED BEHAVIOR. THE TOP HALF COMPARES THE WCET (IN CYCLES), THE SECOND HALF THE AVERAGE CASE. THE ERROR TO THE OBSERVED BEHAVIOR IS SHOWN NEXT TO THE RESULTS.

		Experiment Measured	Anal. Model	WC Simulation	Prob. Simulation
	Worst Case	Sobel, 1 Tile Sobel, P2P Sobel, 4 Tile JPEG, 1 Tile 2 746 197 22 052 14 342 18 128 JPEG, 3 Tile 1 185 223 JPEG, 7 Tile 1 185 483	27 650 17 305 34 277 2 848 154 1 262 589 1 258 751	25.39 % 20.66 % 89.08 % 3.71 % 2 792 946 23 654 15 396 17 318 6.53 % 1 190 392 6.18 % 1 175 734	7.26 % 7.35 % -4.47 % 1.70 % 2 768 023 23 645 15 396 17 326 0.44 % 1 190 287 -0.82 % 1 175 713	7.22 % 7.35 % -4.42 % 0.79 % 0.43 % -0.82 %
	Average Case	Sobel, 1 Tile Sobel, P2P Sobel, 4 Tile JPEG, 1 Tile 2 385 860 21 878 14 191 17 946 JPEG, 3 Tile 940 836 JPEG, 7 Tile 059	27 362 17 017 33 989 2 445 913 1 013 566 1 009 812	25.07 % 19.91 % 89.40 % 2.52 % 7.73 % 7.31 %			23 366 15 108 17 019 2 390 002 941 352 926 771	6.80 % 6.46 % -5.17 % 0.17 % 0.05 % -1.52 %

TABLE III SIMULATION

 III TIME IN HOURS WITH INJECTED DATA FOR 1 000 000 ITERATIONS. AND WCET SIMULATION WITH 10 000 ITERATIONS.

	Experiment	Distribution	WCET	Measurement
		[HH:MM:SS]	[HH:MM:SS]	[HH:MM:SS]
	Sobel, P2P	0:00:06	0:00:03	0:09:28
	Sobel, 1 Tile 0:00:14	0:00:04	0:14:36
	Sobel, 4 Tile 0:00:39	0:00:05	0:11:59
	JPEG, 1 Tile 0:00:35	0:00:06	13:14:31
	JPEG, 3 Tile 0:38:30	0:00:34	5:12:58
	JPEG, 7 Tile 1:46:30	0:01:25	5:13:02

Intel® Xeon® CPU E5-2630 v4 (2.20 GHz) at https://ccipl.univ-nantes.fr Simulation split into 20 processes, each on a dedicated processor approximation.

Repository: https://gitlab.uni-oldenburg.de/stemmer/erts20

ACKNOWLEDGMENT

This work has been partially sponsored by the DAAD (PETA-MC project under grant agreement 57445418) with funds from the German Federal Ministry of Education and Research (BMBF). This work has also been partially sponsored by Campus France (PETA-MC project under grant agreement 42521PK) with funds from the French ministry of Europe and Foreign Affairs (MEAE) and by the French ministry for Higher Education, Research and Innovation (MESRI).


Marcelo Novaes
email: marcelonovaes@dcc.ufmg.br

Vinicius Petrucci
email: vinicius.petrucci@dcc.ufba.br

Abdoulaye Gamatié
email: abdoulaye.gamatie@lirmm.fr

Fernando Magno
email: fernando@dcc.ufmg.br

Quintão Pereira

Vinícius Petrucci

Fernando Quintão

Vinícius Petrucci

Compiler-assisted adaptive program scheduling in big.LITTLE systems

Keywords: big.LITTLE architecture, Adaptation, Compiler 1

Introduction

Contemporary hardware found in mobile phones and data centers sport multiple ways to reduce energy consumption. Two of these techniques are the combination of low and high power cores (the so called big.LITTLE architectures) [START_REF] Chung | Heterogeneous Multi-Processing Solution of Exynos 5 Octa with ARM big[END_REF], and the ability to adjust power and speed dynamically (DVFS) [START_REF] Le | Dynamic Voltage and Frequency Scaling: The Laws of Diminishing Returns[END_REF]. This design gives us the possibility to allocate to each parallel application the hardware configuration that best suits it. A hardware configuration consists of a number of cores, , .

their type and their frequency level. We say that a configuration H 1 suits a program better than another configuration H 2 if H 1 runs said program more efficiently than H 2 , according to some metric such as runtime or energy consumption. Nevertheless, even though we have today the possibility of choosing among several configurations, the one that better fits the needs of a certain program, we still have no clear technique to perform this choice seamlessly.

We call the task of allocating parts of a parallel program to processors the code placement problem. State-of-the-art approaches solve this problem dynamically or statically. Dynamic solutions [START_REF] Margiolas | Portable and Transparent Software Managed Scheduling on Accelerators for Fair Resource Sharing[END_REF][START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF][START_REF] Petrucci | Octopus-man: QoSdriven task management for heterogeneous multicores in warehousescale computers[END_REF] are implemented at the runtime level, at the operating system, or via a middleware. Static approaches [START_REF] Grewe | A static task partitioning approach for heterogeneous systems using OpenCL[END_REF][START_REF] Mendonça | DawnCC: Automatic Annotation for Data Parallelism and Offloading[END_REF][START_REF] Nugteren | Bones: An Automatic Skeleton-Based C-to-CUDA Compiler for GPUs[END_REF][START_REF] Verdoolaege | Polyhedral Parallel Code Generation for CUDA[END_REF] are implemented at the compiler level. The main advantage of the dynamic approach is the fact that it can use runtime information to weight the choices it makes. Static techniques, in turn, provide reduced runtime cost and better leverage of program characteristics. In this paper, we claim that it is possible to join these two approaches, achieving a synergy that, otherwise, could not be attained by each technique individually.

To fundament this claim, we start from a technique that has been proven effective to schedule computations in big. LITTLE architectures: Reinforcement learning. Nishtala et al. [START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF] showed that reinforcement learning helps to find good hardware configurations to applications subject to varying dynamic conditions. The beauty of this approach is adaptability: it provides the means to explore a vast universe of states, formed by different hardware setups and runtime data changing over time. Given enough time, well-tuned heuristics find a set of scheduling decisions that suits the underlying hardware. Yet, "enough time" can be too long. The universe of runtime states is unbounded, and program behavior is hard to predict without looking into its source code. To speedup convergence, we resort to the compiler.

The compiler gives us two benefits. First, it lets us mine program features, which we can use to train the learning

Empirical Observations

This section motivates our work through three empirical observations. First, different hardware configurations yield very different tradeoffs between power consumption and runtime speed for a program (Figure 1). Second, this behavior happens because programs have power phases: depending on the operations that they perform, they might consume more or less power per time unit (Figure 2). Third, the best hardware configuration for a program might not suit the needs of a different application (Figure 4). Central to the discussion in this section is the notion of a hardware configuration: Definition 2.1 (Hardware Configuration). A heterogeneous architecture is formed by a set P = {p 1 , p 2 , . . . , p n } of n processors. A hardware configuration is a function H : P → Boolean. If H (p i ) = True, then processor p i is said to be active in H , otherwise it is said to be inactive. is measured in terms of processing time and energy consumption. Figure 1 shows how two benchmarks from the PARSEC suite -Freqmine and Streamcluster -fare on an Odroid XU4 board featuring 4 Cortex-A15 2.0Ghz cores and 4 Cortex-A7 1.4Ghz cores. Following a nomenclature adopted by ARM, we shall call the A15 cores bigs, and the A7 cores LITTLEs. By switching on and off the different cores, we have 24 different hardware configurations 1Each dot in the figure represents the average of 10 executions on the same configuration, using the smallest 2 input available in PARSEC. Variance is almost negligible, staying under 1% in every sample, for the two benchmarks. The X-axis shows the sum of the execution times of processors active in a particular configuration; hence, it is not clock time. Energy is measured with the Odroid XU3 on-board power measurement circuit and refers to work performed within the processors only; thus, peripherals are not considered.

Energy (joules) 0L1B 0 L 3 B 4L0B 1L0B 1L1B 2L1B xLxB 1L2B 2 L 2 B 1 L 3 B 2 L 3 B 1 L 4 B 3 L 2 B 2 L 4 B 4L1B 3L1B 3L3B 4L4B 4L3B 4L2B
Figure 1 lets us conclude that the energy and runtime footprint of applications vary greatly across different hardware configurations. For instance, the most time efficient configuration for Freqmine is 0L4B, i.e., four bigs and no LITTLEs (2.90secs, 10.43J). However, the most energy efficient configuration is 4L0B (4.01secs, and 8.65J). Results are not the same for Streamcluster. The best energy configuration is 0L1B (0.48secs, 0.69J). This is also the most time efficient configuration. Freqmine shows more parallelism than Streamcluster; therefore, it benefits more from a larger number of cores. This diversity of scenarios happen because programs have phases. Energy and runtime behavior are similar within the same phase, and potentially different across different phases. Second Observation. The instantaneous power consumed by a program is not always constant. In other words, a program has power phases. Figure 2 (a) shows a program which we have crafted to emphasize the different phases that a program undergoes during its execution. This program performs the following actions: (i) read two matrices from text files; (ii) multiply them and (iv) prints all the matrices in the standard output. In between each of these actions we have interposed commands to read data from the standard input.

Figure 3 shows the power profile of this program. This chart has been produced with JetsonLeap [START_REF] Bessa | JetsonLeap: A Framework to Measure Energy-Aware Code Optimizations in Embedded and Heterogeneous Systems[END_REF], an apparatus that let us measure the energy consumed by programs running on the Nvidia TK1 Jetson board 3 . JetsonLeap is formed by three components: the target Nvidia board (Figure 2 (b)), a data acquisition device, which reads the instantaneous power consumed by the board (Figure 2 (c)), and a synchronization circuit, which lets us communicate to the power meter which program event is running at each instant (Figure 2 (c)).

Distinct phases exist within the same program because it might use the hardware resources differently, depending on which part of it is running. By reading performance counters, we know that during matrix multiplication, CPU is at is maximum usage. During the input/output operations, this utilization drops slightly, and other components of the hardware, such as its serial port, are more exercised instead. This fall is steep once the program is waiting for user inputs. The CPU is not the only hardware component that accounts for power dissipation. The JetsonLeap apparatus measure energy for the entire hardware. Thus, the under utilization of the CPU does not mean that overall power consumption will decrease. Nevertheless, variations in the CPU usage are likely to cause variations in the power profile of the program.

Discovering such program phases by means of purely dynamic techniques is possible, yet difficult. As we shall demonstrate in Section 4, we can use profiling techniques, à la Hipster [START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF], to identify variations in program behavior. However, this approach has two shortcomings. First, distinct program parts, with very different resource demands 3 In this section we use two different experimental setups: Odroid XU4 and Tegra TK1. The former gives us the richness of configurations seen in Figure 1. This diversity is absent on the latter, that has only one LITTLE core. However, the TK1 board gives us access to JetsonLeap, and, consequently, the ability to measure energy per programming events. in terms of memory, CPU, disk and such, can display similar dynamic characteristics. For instance, we could imagine a scenario in which function read_user_data, in Figure 2 is implemented via busy waiting. In this case, instead of the valleys observed in Figure 3, we would encounter a power line similar to that produced by CPU-intensive functions like mulMatrix. Second, profiling-based techniques face a tradeoff between precision and overhead. Fast detection asks for high sampling rates; thus burdening the application which originally we intended to optimize. On the other hand, purely However, when operating on matrices that are too small, the cost of changing the hardware configuration might already overshadow the possible gains available through more parsimonious usage of the architecture's resources. Third Observation. The best architecture configuration, in terms of runtime or energy consumption, differs among programs. Figure 4 shows the best configurations that we have found on the Odroid XU4 setup, for six PARSEC applications.

We define the best configuration as the one that spends less energy, given a certain slowdown compared to the fastest configuration. Clearly, there is not a single winner. Configurations vary among programs, and even within the same program, given different acceptable slowdowns.

In the rest of this paper, we shall describe a general methodology, henceforth called the Astro system, which mixes static and dynamic analyses, to find good hardware configurations for the functions invoked during the execution of a program. In this section, we have highlighted key motivation behind our design: (i) a modern heterogeneous hardware exposes a number of different configurations that is too large to be evaluated manually; (ii) a program presents power phases, which can be more easily detected by methods that are aware of structural properties of the code. Thus, we claim that effective adaptation demands knowledge of program characteristics. Such information is readily available to the compiler; however, it is hard to be precisely acquired by techniques unaware of the program's structure.

The Astro System

This section describes the design and implementation of our approach to solve the problem of finding good hardware configurations for programs. We state this problem as follows: Definition 3.1. Scheduling of Programs in Heterogeneous Architectures (SPha) Input: a program P, its input I , hardware configurations H 1 , . . . H n , energy threshold E, and performance threshold S. Output: P ′ , a new version of P, which switches between configurations, and process I using E% less energy, with a slowdown of no more than S%.

In this paper, we solve SPha using an assortment of techniques, which give us the means to generate code that is well adapted to different architectures and workloads. , brief introduction to Q-Learning, the flavour of reinforcement learning that we have adopted.

Q-Learning. Q-learning is a reinforcement learning algorithm [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF]. Given some notion of state (Definition 3.2) and reward (Definition 3.7), it finds an optimized policy to perform the best action (Definition 3.9). Q-learning is attractive because there is no need to know in advance the precise results of the actions before we perform them; that is, we learn about the environment as we perform actions on it. A Markov Decision Process (MDP) drives Q-learning. A MDP is given by a set of states S, a set of possible actions A, a reward function R : S × A → R, and a state transition mapping T : S × A → S that describes the effects of taking each action in each state of the environment. The Markov property says that the results of an action depends only on the state where the action was taken, regardless of any other prior states. In this paper, we mine (e.g., collect) features from the intermediate program representation that the compiler manipulates before producing executable code. We have implemented a Phase-Extractor using the LLVM compiler. The result of mining program features is a map that assigns phases to program regions. This map depends on the choice of program region. Many different granularities of regions are possible, such as instruction, basic block, loop, Single-Entry-Single-Exit block [START_REF] Ferrante | The program dependence graph and its use in optimization[END_REF], etc. We have chosen to work mostly at the granularity of functions. The "mostly" in this case, refers to the fact that we also change phases before and after library calls that cause the program to block waiting for some event (see the Barrier phase, in the discussion that follows). Pragmatically, this amounts to say that the instrumented program adds logic to change phases at the entry point of functions, and around certain library calls.

Example 3.5. Figure 6 shows the five functions in Figure 2, classified according to features seen in Example 3.4. We are assigning these functions hypothetical values. Because we have three features, we can map them into a three-dimensional space. Each phase corresponds to a cube in this space. Figure 6 shows the sub-space that corresponds to the phase: Arith.Density ∈ [0, 0.25), I/O Weight ∈ [0, 1) and NestingFactor ∈ [0, 1). Function main, in our example, fits in this phase.

Our Choice of Program Phases. In our implementation, we combine four code features to determine program phases. These features are all "densities", i.e., they represent a certain quantity of instructions normalized by the total of instructions in the target function. We use the following features:

• IO-Dens: proportion of library calls that perform I/O operations;

• Mem-Dens: proportion of instructions that access memory (loads and stores); • Int-Dens: proportion of arithmetic and logic instructions that operate on integer types. • FP-Dens: proportion of arithmetic and logic instructions that operate on floating point types. • Locks-Dens: proportion of lock instructions.

• Barrier: true when the program invokes a multi-thread barrier that forces it to wait for some blocking event.

• Net: true when the program invokes a library call that forces it to wait for some network-related event.

• Sleep: true when the program invokes a sleep library call that forces it to wait unconditionally. We have defined four program phases, which appear as combinations of the features above. This choice is arbitrary. We have opted for a simple partitioning, involving only a handful of features for convenience, as this choice already lets us support the main thesis of this paper: that static features greatly enhance the dynamic scheduling of computations in heterogeneous hardware. The program phases that we shall consider in Section 4 are:

• Blocked: Barrier = true or Net = true or Sleep = true or Locks-Dens > 0.5; • I/O Bound: IO-Dens + Mem-Dens > 0.5 and not (Blocked) and Locks-Dens = 0; • CPU Bound: Int-Dens + FP-Dens > 0.5 and not(Blocked); • Other: in case none of the previous relations hold.

Hardware Phases

While the program phases seen in Section 3.1.1 depend only on syntactic program characteristics, hardware phases depend on the dynamic state of the hardware: Definition 3.6 (Hardware Phase). A Performance Counter is any monitor that collects dynamic information about the hardware state, such as CPU performance and cache miss rate. The domain over which the performance counter ranges can be partitioned into phases. Given a collection of performance counters {C 1 , C 2 , . . . , C n }, where each C i is partitioned into R i phases, then a hardware phase is any combination within the product

R 1 × R 2 × . . . × R n .
The monitoring of hardware phases does not require program instrumentation. Instead, an actuator reads the state of hardware performance counters periodically. Modern architectures already provide an array of performance counters that can be queried. In this paper, we consider four kinds of counters to define hardware phases:

• IPC: instructions per cycle in the ranges [0, .5), [. • CPU: utilization of the CPU, in the ranges [0, 20%), [20%, 50%), [50%, +∞). Each counter is partitioned in three buckets. Therefore, we consider a total of 3 × 3 × 3 × 3 = 81 hardware phases.

(H i-1 , S i-1 , D i-1 , H i , r i ) backprop. (H i , D i , S i ) (A 1 , R 1 ) ... (A n , R n ) H' = best(A x , R x ) 1 x n H i+1 = chg(H', H i ) Next Config H' feedforward i i+1 i > 0 M O N I T O R L E A R N A D A P T OS (H i , p i ) PowMon e i

Actuation

The heart of the Astro system is the Actuation Algorithm outlined in Figure 7. Actuation consists of phase monitoring, learning and adapting. These three steps happens at regular intervals, called check points, which, in Figure 7, we denote by i and i+1. The rest of this section describes these events.

Monitoring

To collect information that will be later used to solve SPha, Astro reads four kinds of data. Figure 7 highlights this data:

• From the Operating System (OS): current hardware configuration H and instructions p executed since last check point. • From the Program (Log): the current program phase S.

• From the device's performance counters (PerfMon):

the current hardware phase D. • From the power monitor (PowMon [START_REF] Walker | Accurate and Stable Run-Time Power Modeling for Mobile and Embedded CPUs[END_REF]): the energy e consumed since the last checkpoint. The monitor collects this data at periodic intervals, whose granularity is configurable. Currently, it is 500 milliseconds. The recording of the program phase is aperiodic, following from instrumentation inserted in the program by the compiler. As discussed in Section 3.1.1, information is logged at the entry point of functions, and around library calls that might cause the program to enter a dormant state. The hardware configuration is updated whenever it changes. The metrics e and p lets us define the notion of reward as follows: Definition 3.7 (Reward). The reward is the set of observable events that determine how well the learning algorithm is adapting to the environment. The reward is computed from a pair (e, p), formed by the Energy Consumption Level e, measured in Joules per second (Watt), and the CPU Performance Level p, measured in number of instructions executed per second.

The metric used in the reward is given by a weighted form of performance per watt, namely MIPS γ /W att, where γ is a design parameter that gives a boosting performance effect in the system. This is usually a trade-off between the performance and energy consumption. To optimize for energy, we let γ = 1.0. A value of γ = 2.0 emphasizes performance gains: the reward function optimizes (in fact, maximizes the inverse of) the energy delay product per instruction, given by W att/IPS 2 ; letting IPS = I /S we have (W att × S × S)/I 2 = (Enerдy × Delay)/I 2 . This aims to minimize both the energy and the amount of time required to execute thread instructions [START_REF] Brooks | Power-Aware Microarchitecture: Design and Modeling Challenges for Next-Generation Microprocessors[END_REF].

Example 3.8. Continuing with Example 3.5, Figure 8 (a) shows the instrumentation of function main (Figure 2) to log program phases.

Learning

The learning phase uses the Q-learning algorithm. As illustrated in Figure 7, a key component in this process is a multi-layer Neural Network (NN) that receives inputs collected by the Monitor. The NN outputs the actions and their respective rewards to the Actuator so that a new system adaptation can be carried out. Following common methodology, learning happens in two phases: back-propagation and feed-forwarding. During back-propagation we update the NN using the experience data given by the Actuator (Figure 7). Experience data is a triple: the current state, the action performed and the reward thus obtained. The state consists of a hardware configuration (H i-1 ), static features (S i-1 ) and dynamic features (D i-1 ) at check points i-1. The action performed at check point i-1 makes the system move from hardware configuration H i-1 to H i . The reward is given by r i , received after the action is taken. The NN consists of a number of layers including computational nodes, i.e., neurons. The input layer uses one neuron to characterize each triple (state, action, reward). The output layer has one neuron per action/configuration available in the system. During the feed-forward phase, we perform predictions using the trained NN. Each node of the NN is responsible to accumulate the product of its associated weights and inputs. Given as input a state (H i , D i , S i ) at check point i, the result of the feed-forward step is an array of pairs A × R, where A is an action, and R is its reward, estimated by NN. Actions determine configuration changes; rewards determine the expected performance gain, in terms of energy and time, that we expect to obtain with the change. We use the method of gradient descent to minimize a loss function given by the difference between the reward predicted by the NN, and the actual value found via hardware performance counters.

Adaptating

At this phase, Astro takes an action. Together with states and rewards, actions are one of the three core notions in Q-learning, which we define below: Definition 3.9 (Action). Action is the act of choosing the next hardware configuration H to be adopted at a given checkpoint.

An action may change the current hardware configuration; hence, adapting the program according to the knowledge inferred by the Neural Network. Following Figure 7, we start this step by choosing, among the pairs {(A 1 , R 1 ), . . . , (A n , R n )}, the action A x associated with the maximal reward R x . A x determines, uniquely, a hardware configuration H ′ . Once H ′ is chosen, we proceed to adopt it. However, the adoption of a configuration is contingent on said configuration being available. Cores might not be available because they are running higher privilege jobs, for instance. If the Next Configuration is accessible, Astro enables it; otherwise, the whole system remains in the configuration H i active at check point i. Such choice is represented, in Figure 7, by the function

H i+1 = chg(H ′ , H i ).
Regardless of this outcome, we move on to the next check point, and to a new actuation round.

Code Scheduling

After we have trained a program to a given architecture, we imprint this knowledge directly in that program's code. In Figure 5, this step is named Final Code Generation. Code generation consists in inserting instrumentation into the target program. Instrumentation is inserted in the same regions modified to mark program phases (see Section 3.1.1): at the entry point of functions, and around particular library calls. Example 3.10 illustrates this instrumentation.

Example 3.10. Figure 8 shows the final actuation code for the program in Figure 2. Function determine_active_configuration tries to move the program to the configuration that has produced the largest rewards for that program phase. We consider two versions of instrumentation: static, as in Figure 8(b), and hybrid, as in Figure 8 (c). The latter can read hardware status to improve the decision making process.

The static scheduling discussed in Example 3.10 always maps the same program region to the same hardware configuration. Hybrid scheduling might change decisions, given enough runtime information. As we show in Section 4, the static scheduling yields lower runtime overhead than Astro's hybrid scheduling. However, this modus operandi is unable to adapt the program to its workload; and cannot recover from bad decisions. A striking example is the benchmark ParticleFilter (see Fig. 10 in Section 4.2). In this case, even with the runtime overhead, the flexibility of hybrid instrumentation paid off in terms of energy and speed.

Evaluation

This section presents an experimental evaluation of the Astro system over several parallel benchmarks running on a big.LITTLE system. In the process of evaluating Astro, we shall provide answers to the following research questions:

• RQ1: How close can Astro be from an optimal oracle? • RQ2: How does Astro compare against fixed and immutable best configuration choices? • RQ3: How does Astro compare against state-of-the-art schedulers? • RQ4: How does Astro behave on an actual device? • RQ5: How much does Astro increase code size? Experimental Setup. We use two experimental setups: program traces, henceforth called simulation; and an actual device, the Odroid XU4. Experiments in Section 4.1 use simulation because they involve testing exhaustively every hardware configuration. Experiments in Section 4.2 run on an actual device: the Odroid XU4 development board with a big.LITTLE ARM processor (Samsung Exynos 5422) featuring 4 big cores (Cortex-A15 2.0 Ghz) and 4 LITTLE cores (Cortex-A7 1.4 Ghz), running on Linux odroid 3.10.63, using the "performance" frequency governor, with cores at maximum speed. This device was also used to produce the simulation traces. We report CPU power consumption via PowMon [START_REF] Walker | Accurate and Stable Run-Time Power Modeling for Mobile and Embedded CPUs[END_REF]. Astro is implemented on LLVM 3.8. Benchmarks. The simulation traces used in Section 4.1 were produced on Parsec's FluidAnimate [START_REF] Bienia | The PARSEC Benchmark Suite: Characterization and Architectural Implications[END_REF]. Experiments on Section 4.2 use eight benchmarks from Rodinia and Parsec. These are the only programs that we can currently instrument, as our LLVM module does not recognize mangled C++ routines yet (to discover program phases such as I/O density -Sec. 3.1.1). We used FluidAnimate to obtain the initial learning parameters; hence, we do not use it for validation.

Results in the Simulated Environment

In this section we report results that are hard to obtain on an actual device, because they involve exhaustive search on the universe of valid hardware configurations. We have approximated the exhaustive execution of configurations by generating traces for every hardware configuration. These traces lets us simulate different behaviors, by choosing, at each checkpoint, the reward offered by one of them. Different policies can guide this choice: optimal, best fixed and random for instance. Producing such traces is time consuming, thus, we have produced them only for fluidanimate. We took between 410 seconds to up to 7,000 seconds to produce each trace, depending on the hardware configuration. RQ1: how close is Astro to an optimal oracle? The data collected for every possible configurations lets us know, for each part of the program, which configuration consumes less energy and has the best performance. We then combine these 24 traces into a single trace, choosing, at each check point, a particular configuration. This "optimal" trace is what we call the Oracle. Our oracle is not an optimal global solution to SPha. Rather, it is a greedy approximation: given that at check-point i we are at configuration H i , what is the configuration that gives us the best reward at check-point i + 1. Figure 9 shows two oracles: (E) and (T). The former yields optimal energy consumption; the latter yields optimal execution time. Astro's reward function prioritizes time over energy; hence, it leads to execution times close to T. 10 shows the runtime (5 samples) of three different solutions to SPha: Astro (purely static or hybrid), and Global Task Scheduling (GTS). GTS is a scheduling algorithm developed by ARM. This scheduler is aware of the different compute capabilities of big and LITTLE cores in the system. It uses historical data of the running tasks and active cores to determine where each individual thread will run. By tracking the load information at runtime, GTS migrates tasks that are compute-intensive to big cores and those that are less intensive to little cores. Load balancing heuristics are periodically executed to minimize concentrating compute-intensive threads excessively on big cores and letting little cores underutilized. Numbers reported for Astro include all the overhead of monitoring and adapting the target application. Astro, in its static or hybrid flavours, yields faster code than GTS in six benchmarks, and more energy efficient code in five. We show two p-values next to each plot: S and H. The former is the probability that the static and purely dynamic (GTS) samples come from the same distribution. The latter relates the hybrid and purely dynamic distributions. The closer to zero, the more statistically significant are our results. We emphasize that GTS is a state-of-the-art approach, widely used in operating systems running on ARM hardware, and the fact that Astro can consistently outperform it testifies in favour of the benefits of syntax awareness when taking scheduling decisions. There is no clear winner between the hybrid and static versions of Astro. We observer that the former tends to be better in more regular (kernel-like) applications, such as CFD and sradv2. We also observe strong correlation between runtime and energy consumption, except for Swaptions. In that case, the Static version of Astro tends to avoid using the high-frequency cores, a fact that leads to slower runtime, but also to less power dissipation. In ParticleFilter the static version was penalized for a wrong scheduling decision: it stays in 1b2L, and the lack of runtime information prevents it from fixing this choice. RQ5: How much does Astro increase code size? There are three different versions of instrumented programs: those used during Astro's learning phase; the programs that use static instrumentation; and the programs that use hybrid instrumentation. The binary size of the last two is the almost the same: it consists of code that collects data, plus the Astro library. The only different between static and dynamic instrumentation is the code used to collect dynamic data in the latter version. This different is too small; hence, in Figure 11 we include both types of binaries in the same bar: Instrumented. As the figure shows, most of the size overhead imposed by Astro is due to its dynamic library. This increase is constant across benchmarks. The amount of instrumentation in binaries grows linearly with the program size. This growth tends to be very small. As evidence to this small growth, in the Learning phase, binaries do not use any dynamically linked library; thus, code size expansion is due to instrumentation only, and it is small, as seen in Figure 11.

Related Work

The problem of scheduling computations in heterogeneous architectures (Definition 3.1) has attracted much attention in recent years. Table 1 provides a taxonomy of previous solutions to this problem. We group them according to how they answer each of the following four questions:

• Source: is the program's code modified?

• Auto: is user intervention required?

• Runtime: is runtime information exploited?

• Learn: is there any adaptation to runtime conditions? Perhaps the most important difference among the several strategies proposed to solve SPha concerns the moment when they are used: at compilation time, at runtime, or both.

Purely static approaches work at compilation time. They might be applied by the compiler, either automatically, i.e., without user intervention [START_REF] Cong | Energy-efficient Scheduling on Heterogeneous Multi-core Architectures[END_REF][START_REF] Jain | Continuous shape shifting: Enabling loop co-optimization via near-free dynamic code rewriting[END_REF][START_REF] Luk | Qilin: Exploiting Parallelism on Heterogeneous Multiprocessors with Adaptive Mapping[END_REF][START_REF] Poesia | Static Placement of Computation on Heterogeneous Devices[END_REF][START_REF] Rossbach | Dandelion: A Compiler and Runtime for Heterogeneous Systems[END_REF][START_REF] Tang | ReQoS: Reactive Static/Dynamic Compilation for QoS in Warehouse Scale Computers[END_REF], or not. In the latter case, developers can use annotations [START_REF] Mendonça | DawnCC: Automatic Annotation for Data Parallelism and Offloading[END_REF], domain specific programming languages [START_REF] Luk | Qilin: Exploiting Parallelism on Heterogeneous Multiprocessors with Adaptive Mapping[END_REF][START_REF] Rossbach | Dandelion: A Compiler and Runtime for Heterogeneous Systems[END_REF] or library calls [START_REF] Augonnet | StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] to indicate where each program part should run. In Table 1, techniques implemented at either the compiler or library levels are purely static. Purely dynamic approaches take into account runtime information. They can be implemented at the architecture level [START_REF] Joao | Bottleneck Identification and Scheduling in Multithreaded Applications[END_REF][START_REF] Lukefahr | Exploring Fine-Grained Heterogeneity with Composite Cores[END_REF][START_REF] Rangan | Thread Motion: Fine-grained Power Management for Multi-core Systems[END_REF][START_REF] Van Craeynest | Scheduling Heterogeneous Multi-cores Through Performance Impact Estimation (PIE)[END_REF][START_REF] Yazdanbakhsh | Neural acceleration for GPU throughput processors[END_REF], or at the virtual 1 indicates in the column Learn. Once guards are created, they always behave on the same way. That is the main difference between these previous approaches and the Astro method.

Conclusion

This paper has presented Astro, a program scheduler for big.LITTLE architectures. Astro uses machine learning to adapt a program to runtime conditions. However, it departs from previous approaches, also based on machine learning, because it takes program characteristics into consideration. Astro relies on the compiler to identify program regions that contain similar syntactical features. We classify these features in sets called program phases, and track, at runtime, which program phase is currently valid. When combined with dynamic data, this information lets a neural network train the program, so to maximize some metric of efficiency, such as energy or runtime. By combining static and dynamic information, we are, effectively, building architecture-aware code optimizations for parallel programs.

First

  Observation. The same application might benefit differently from different hardware configurations. This benefit

Figure 2 .Figure 3 .

 23 Figure 2. (a) Simple matrix multiplication implemented in C. (b) The Nvidia TK1 board. (c) NI 6009 Data Acquisition Device. (d) Synchronization circuit.

Figure 4 .

 4 Figure 4. Best configurations for seven PARSEC applications, if we accept an slowdown of 1% or 5% to save more energy.

Figure 5 .

 5 Figure 5. The Astro System.

3. 1

 1 Phase Partitioning A running program might cause the hardware to go over an infinite number of different states. Because this universe is unbounded, Definition 3.2 discretizes the notion of a State. In that definition, S is a Program Phase and D is a Hardware Phase. Program phases are discussed in Section 3.1.1, and hardware phases are discussed in Section 3.1.2. Definition 3.2 (State). A state is a triple ⟨H, S, D⟩ representing a hardware configuration H , a program phase S and a hardware phase D.

3. 1 . 1 Figure 6 .

 116 Figure 6. Mapping the functions in Figure 2 (a) to program phases.

Figure 7 .

 7 Figure 7. The Actuation Algorithm.

}Figure 8 .

 8 Figure 8. (a) Instrumentation to mine features. (b) Final instrumentation, inserted in production code.

Figure 9 .

 9 Figure 9. Comparison between Astro and a system that chooses the next configuration randomly.

,

  None of these previous work use any form of learning technique to adapt the program to runtime conditions, as Table

  If we schedule Fluidanimate with Astro, its final runtime is only 10% slower than T. However, it is more energy hungry: it uses 8% more energy than T, and 15% more energy than E. RQ2: How does Astro compare against immutable best configuration choices? If we fix the hardware configuration, then 4b4L (4 bit, 4 LITTLE cores) gives us the best runtime and the best energy consumption for the simulation of Fluidanimate. This configuration is 45% slower than Astro, yet it is 4% more energy efficient. The fact that Astro, and the energy oracle, could beat 4b4L is surprising. We have found out that 4b4L tends to slowdown programs at critical sections, due to an excess of conflicts between threads. Astro eventually learns to use configurations with less cores at these program phases; hence, speeding up execution. Figure 9 also shows the configuration that yields the slowest and more power hungry execution: 1b0L. It is almost 15 times slower than Astro, and spends 3.6x more energy. RQ3: How does Astro perform when compared with state-of-the-art program schedulers? We tried to implement, on the simulator, two well-known schedulers for big. LITTLE architectures: Hipster[START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF] and Octopus-Man[START_REF] Petrucci | Octopus-man: QoSdriven task management for heterogeneous multicores in warehousescale computers[END_REF]. The implementation of Hipster used in Figure9differs slightly from the original description of Nishtala et al, although we have reused much of their code base. Hipster was originally conceived to deal with cloud workloads; hence, we had to customize its state and reward function for multithreaded programs. In this experiment, both, Hipster and Astro use the same reward function. Octopus-Man is the profiling mechanism used in Hipster; hence, it does not use the notion of reward. Astro produces code that runs 17% faster than Hipster, and 15% faster than Octopus-Man. However, Astro uses 6% more energy than the former, and 4% more than the latter.

	4.2 Results in an Actual Device
	RQ4: How does Astro behave on an actual device? Fig-
	ure

We have

= 5 × 5 -1 configurations, because we do not count the setup in which all cores are off.[START_REF] Barik | A Black-box Approach to Energy-aware Scheduling on Integrated CPU-GPU Systems[END_REF] This experiment would take 12 days using the largest inputs.

machine (VM)/OS level [START_REF] Barik | A Black-box Approach to Energy-aware Scheduling on Integrated CPU-GPU Systems[END_REF][START_REF] Gaspar | A Framework for Application-Guided Task Management on Heterogeneous Embedded Systems[END_REF][START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF][START_REF] Petrucci | Octopus-man: QoSdriven task management for heterogeneous multicores in warehousescale computers[END_REF][START_REF] Somu Muthukaruppan | Price Theory Based Power Management for Heterogeneous Multi-cores[END_REF][START_REF] Zhang | Maximizing Performance Under a Power Cap: A Comparison of Hardware, Software, and Hybrid Techniques[END_REF]. By leveraging runtime information, the system can use environment information, unknown at compilation time, to solve SPha. However, there may be some overhead on accurately collecting and processing runtime data. Besides, because scheduling decisions are taken on-the-fly, usually the scheduler cannot spend much time weighting choices. Thus, even though these algorithms use runtime information, they might still take suboptimal decisions. Approaches that mix static and dynamic techniques are called hybrid. Astro is a hybrid method.

Other hybrid approaches to this problem exist [START_REF] Cong | Energy-efficient Scheduling on Heterogeneous Multi-core Architectures[END_REF][START_REF] Piccoli | Compiler Support for Selective Page Migration in NUMA Architectures[END_REF][START_REF] Tang | ReQoS: Reactive Static/Dynamic Compilation for QoS in Warehouse Scale Computers[END_REF].