Cezar Junio

D A Ribeiro

Silva

Fernando Magno

Quint Ão Pereira

Mapping Computations in Heterogeneous Multicore Systems with Statistical Regression on Program Inputs

Keywords: CCS Concepts:, So ware and its engineering → Compilers, •Computing methodologies → Parallel programming languages, Machine learning

A hardware con guration is a set of processors and their frequency levels in a multi-core heterogeneous system.

is paper presents a compiler-based technique to match functions with hardware con gurations. Such a technique consists in using multivariate linear regression to associate function arguments with particular hardware con gurations. By showing that this classi cation space tends to be convex in practice, this paper demonstrates that linear regression is not only an e cient tool to map computations to heterogeneous hardware, but also an e ective one. To demonstrate the viability of multivariate linear regression as a way to perform adaptive compilation for heterogeneous architectures, we have implemented our ideas onto the Soot Java bytecode analyzer. Code that we produce can predict the best con guration for a large class of Java and Scala benchmarks running on an Odroid XU4 big.LITTLE board; hence, outperforming prior techniques such as ARM's GTS and CHOAMP, a recently released static program scheduler.

INTRODUCTION

Several modern computer architectures combine, into a single device, fast and slow processing cores able to execute the same set of instructions [START_REF] Kumar | Single-ISA Heterogeneous Multi-Core Architectures for Multithreaded Workload Performance[END_REF][START_REF] Orgerie | A Survey on Techniques for Improving the Energy E ciency of Large-scale Distributed Systems[END_REF]Singh et al. 2020). Fast cores perform computations e ciently, but are power-hungry; Slow cores show the inverse behavior. e ARM big.LITTLE design, ubiquitous in smartphones, is an example of such technology [START_REF] Hähnel | Heterogeneity by the Numbers: A Study of the ODROID XU+E Big. LITTLE Platform[END_REF]. As an illustration, the Apple A14, launched in September of 2020, has two high-performance cores called Firestorm and four energy-e cient cores called Icestorm, all running the ARMv8.4-A instruction set [START_REF] Gurman | Apple Aims to Sell Macs With Its Own Chips Starting in 2021[END_REF]). e combination of heterogeneous processors featuring multiple frequency levels gives programmers many con gurations to choose from when running their applications. However, performing this choice is challenging [START_REF] Waqar Azhar | SaC: Exploiting Execution-Time Slack to Save Energy in Heterogeneous Multicore Systems[END_REF][START_REF] Nejat | Coordinated Management of Processor Con guration and Cache Partitioning to Optimize Energy under QoS Constraints[END_REF][START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF][START_REF] Paul | Adaptive Task Allocation and Scheduling on NoC-Based Multicore Platforms with Multitasking Processors[END_REF][START_REF] Petrucci | Energy-E cient read Assignment Optimization for Heterogeneous Multicore Systems[END_REF].

A recent solution to this problem is CHOAMP, a compilation technique invented by [START_REF] Krishna | CHOAMP: Cost Based Hardware Optimization for Asymmetric Multicore Processors[END_REF]. CHOAMP uses supervised machine learning to map program functions to the con guration that best ts them. Sreelatha et al. capture characteristics of the target architecture's runtime behavior. From this knowledge, they predict the ideal con guration to a program, given its syntactic characteristics. Sreelatha et al.'s approach is fully static: interventions on the program remain con ned into the compiler, and no extra runtime support is required from the hardware. is approach has been made popular by [START_REF] Shelepov | HASS: A Scheduler for Heterogeneous Multicore Systems[END_REF])'s HASS system, a scheduler for same-ISA heterogeneous systems.

We observe that CHOAMP and HASS share a fundamental shortcoming: they do not consider program inputs when performing mapping decisions. As we explain in Section 2, there exist programs for which the best hardware con guration for a given function varies depending on the function's inputs. We make the case that inputs are key to determine good mappings between programs and con gurations supported by the evidence that such mappings do not necessarily converge to a single, ideal con guration, as the size of inputs grows. Our Solution. In this paper, we introduce a compilation approach to map program parts to hardware con gurations. Our technique explicitly takes function inputs into consideration when deciding which hardware con gurations to use. Input-based code optimizations are not a new idea, as we explain in Section 5.3; however, to the best of our knowledge, this paper is the rst to use related techniques to nd optimized hardware con gurations for programs running on big.LITTLE architectures. As we discuss in Section 3, our idea is based on statistical regression on the values of program inputs. Given a function foo, a collection of its inputs {t 1 , t 2 , . . . , t m } available for training, plus a set of hardware con gurations {h 1 , h 2 , . . . , h n }, we run foo(t i ), 1 ≤ i ≤ m, onto a sample of the con guration space {h j | 1 ≤ j ≤ n}. Training gives us the ideal con guration for each input, in terms of a measurable goal, such as runtime or energy consumption. When producing code for foo, we augment its binary representation with this knowledge to predict the best con guration for potentially unseen inputs. Our Results. We have implemented our technique in S [START_REF] Vallée-Rai | Soot -a Java Bytecode Optimization Framework[END_REF]), a bytecode optimizer, and have evaluated it onto an Odroid XU4 big.LITTLE architecture. S lets generate code that, at runtime, changes the hardware con guration per program function, based on training knowledge. We call this code generator the J C compiler, a tool that reads and outputs Java bytecodes. As we explain in Section 4, we have evaluated J C on the Program Based Benchmark Suite [START_REF] Shun | Brief Announcement: e Problem Based Benchmark Suite[END_REF] used by Acar et al [START_REF] Umut | Heartbeat Scheduling: Provable E ciency for Nested Parallelism[END_REF], and on programs from Renaissance [START_REF] Prokopec | Renaissance: Benchmarking Suite for Parallel Applications on the JVM[END_REF]. We have evaluated J C with two objective functions: runtime and energy consumption. We measure energy for the entire board using physical probes, following Bessa et al's methodology [START_REF] Bessa | JetsonLEAP: A framework to measure power on a heterogeneous system-on-a-chip device[END_REF]). Below we summarize the bene ts of our solution in the context of the existing literature:

• Simple: we show that, for typical parallel code, the value of scalar inputs and the size of aggregate inputs yield useful information to feed linear regression models, because the function that maps these values to optimized hardware con gurations form a convex space. • E ective: in most of our benchmarks, ten input sets are already su cient to let us train a predictor to a high level of accuracy. Variety is, of course, important: the more di erent the inputs we have, the more accurate the predictions we perform. • E cient: our approach does not require active runtime monitoring. Inputs must be evaluated upon function invocation, and only then. Evaluation amounts to one vectormatrix multiplication, and is proportional to the number of function arguments (not to their sizes) times the number of valid hardware con gurations. Training is costly, but this cost is paid o ine, before programs run in production mode.

Example 2.2 (Hardware Con guration). e HardKernel Odroid XU4 has four big cores {b 0 , b 1 , b 2 , b 3 } and four LITTLE cores {L 0 , L 1 , L 2 , L 3 }. Big cores have 19 frequency levels {200MHz, 300MHz, . . . , 1.9GHz, 2.0GHz}. LITTLE cores have 14 {200MHz, . . . , 1.5GHz}. is SoC supports any number of active processors; however, big cores must always use the same frequency level. e same is true for LITTLE cores. An example of hardware con guration is {b 0 , b 2 } × 2.0GHz, {L 1 , L 2 , L 3 } × 1.3GHz. e notion of hardware con guration leads to an interesting problem in the eld of adaptive compilation. In the words of Cooper et al [START_REF] Cooper | ACME: Adaptive Compilation Made E cient[END_REF], "an adaptive compiler uses a compileexecute-analyze feedback loop to nd the combination of optimizations and parameters that minimizes [optimizes] some performance goal, such as code size or execution time". In this paper we are interested in solving the adaptive compilation problem introduced by De nition 2.3.

De nition 2.3. I

A S S ISA H A (I ) Input: a function F , its input i, a set of hardware con gurations H = {h 1 , . . . h n }, and a cost function O i F : H → R, which determines the cost of running F with input i on con guration h ∈ H . Examples of cost functions include runtime, energy, energy-delay product, throughput, etc. Output: a con guration h ∈ H that minimizes O i F . As Section 3 explains, we insert code at the entry point of functions to switch the hardware con guration; hence, providing a solution to I . From that region on, the program will run in the chosen con guration, until its execution ow nds the entry point of another function that has also been instrumented. Any function might run at any hardware con guration, for although we target a heterogeneous architecture, big and LITTLE cores run the same instruction set. Notice that moving computations across cores bears a cost: cores do not share L1 caches, and big and LITTLE clusters do not share the L2 cache, although all the cores share the main memory (Weber et al. 2017, Sec.2.2). is cost is embedded in the numbers that we report in Section 4. In other words, the speedups or regressions that we observe experimentally already include the cost of warming up caches due to switching computation between cores.

Program Inputs and Hardware Configuration

Compilers, such as G or C , do not try to capitalize on di erences between cores when producing binary programs: the same executable runs in both cores. Nevertheless, we know of research artifacts that take these di erences into consideration; for example, CHOAMP is a recent technique in this direction [START_REF] Krishna | CHOAMP: Cost Based Hardware Optimization for Asymmetric Multicore Processors[END_REF]. CHOAMP matches program features, such as branches, barriers, reductions and memory access operations with the ideal con guration for each function. CHOAMP has been evaluated on the OpenMP version of the NAS benchmark suite [START_REF] Bailey | NAS Parallel Benchmarks&Mdash;Summary and Preliminary Results[END_REF] with great bene t, producing code that was 65% more energy-e cient than the default Linux scheduler.

A er CHOAMP trains a regression model, the same core con guration decision applies for a function, regardless of its actual inputs. is shortcoming of purely static approaches has been well-known.

oting Nie and Duan: "since the properties they have collected are based on the given input set, those o ine pro ling approaches are hard to adapt to various input sets and therefore will drastically a ect the program performance" [START_REF] Nie | E cient and Scalable Scheduling for Performance Heterogeneous Multicore Systems[END_REF]. We corroborate this observation and show that it is possible to nd di erent programs for which the ideal hardware con guration varies according to their inputs. Example 2.4 illustrates this nding with an actual experiment.

Example 2.4. Function in Figure 1 inserts into a global map all the values stored in a stream. Values are associated with a key, whose size varies according to the formal parameter S . T has a synchronized block; hence, it can be safely executed by multiple threads. e number of threads is an implicit input. ese three values: size of input stream, size of keys, and number of threads, form a three-dimensional space, which Figure 1 illustrates. e ideal hardware con guration for varies within this space. Figure 2 illustrates this variation for 3 × 25 di erent input sets. e notation XbYL denotes X big cores, and Y LITTLE cores. In this experiment, we have set Freq(b) = 1.8GHz, for any big core b, and Freq(L) = 1.5GHz, for any LITTLE core L.

e construction of a key, at line 5 of Figure 1 is a CPU-heavy, synchronization-free task. e larger the key, the more incentive we have to use the big cores. However, the updating of M at line 9 is a synchronization-heavy task: the more synchronization we have, the heavier is the penalty on the big cores, relative to the LITTLE ones. Indeed, as already observed by [START_REF] Kim | Looking into heterogeneity: when simple is faster[END_REF], context switches are more expensive in the big than in the LITTLE cores. Reasons for this heavier penalty include the larger pipelines used in the big cores. Whereas the ARM A15 (big) core features a pipeline with 15 integer and up to 25 oating point stages, the A7 (LITTLE) core features a pipeline with only 8 stages (Weber et al. 2017, Sec.2.2). Memory accesses are also more expensive (relative to execution cycles) on the faster cores: L2 latency for big cores is 21 cycles while for LITTLE cores it is 10 (Greenhalgh 2011). Furthermore, the larger the input streams, the more o en we access the synchronized region between lines 7 and 10 of Figure 1. We can observe results similar to those seen in Example 2.4 in algorithms like Integer Sort, a benchmark used by [START_REF] Krishna | CHOAMP: Cost Based Hardware Optimization for Asymmetric Multicore Processors[END_REF]), which we re-evaluate in Section 4. 1), for 4, 8 and 16 threads, measured on an Odroid XU4 with the userspace governor. Default configuration is 4b4L. Names in boxes indicate the best configuration(s) for that input. 'X' indicates setups with three or more configurations tied as best. To produce these charts, we followed a methodology to be described in Section 4.4. Even considering 4 threads, there is benefit to enable more than four processors, as the Java virtual machine creates threads for garbage collection and JIT compilation, for instance (Taken from da Silva et al. ( 2020)).

Notice that allowing a program to use more threads does not necessarily mean that this program will draw larger bene t from con gurations with more cores.

is counterintuitive behavior happens because more cores might provoke more thread con icts in synchronization-heavy se ings. Example 2.5 elaborates on this observation.

Example 2.5. Figure 2 shows that when the T function runs with eight threads, the con guration with full resources (4b4L) is o en chosen. However, once 16 threads are employed to generate keys, sometimes not all the cores are used in the fastest con guration. Figure 3 provides numbers to explain this behavior. For small key sizes, collisions between threads happen frequently. In this se ing, 1 0L is the best con guration, regardless of the number of threads considered (even though running times are short, the con dence level of this result is above 99%). Once key size increases, time spent on synchronization becomes less important, and extra cores start to be advantageous. Notice that past certain point (a er keys with 10,000 bits), just-in-time compilation triggers, and the 0.E+00 Fig. 3. Average waiting time and total running time of function T (Figure 1) considering di erent key sizes, and di erent numbers of threads. To perform this experiment, we have modified T to use Java's ReentrantLock class. This new version of T is slower, due to the need to log events; hence, we present total running times to give the reader some perspective on the program's behavior.

average waiting time decreases by approximately 50%. Yet, the total application time still increases, due to the excess of calculations required by the large keys.

Example 2.5 shows that two facts increase the average time that threads spent on critical sections: the total number of working threads that the program uses, and the total number of cores where these threads execute. erefore, adding more resources to thread rich programs can cause them to run more slowly due to extra con icts. Such complex tradeo s make the problem of choosing ideal hardware con gurations a non-trivial endeavor.

Accounting for Energy E iciency

Choosing good hardware con gurations becomes more challenging, once we consider energy as a dimension of e ciency. Low-frequency cores tend to be more power-e cient than high-frequency processors; hence, there is incentive to use them to save energy. However, low-frequency cores tend to take longer to nish tasks; possibly, using more energy to perform a job. is observation is critical in ba ery-powered devices, such as smartphones.

e next example analyzes such power-performance tradeo s. In this experiment, we are measuring the actual power consumed in the entire board, which includes not only its CPUs but also its peripherals, such as memory and cooling. To this end, we use the apparatus described by da [START_REF] Cezar | A Compiler-Centric Infra-Structure for Whole-Board Energy Measurement on Heterogeneous Android Systems[END_REF], which samples power at 20KHz.

Example 2.6. We have used the power measurement apparatus shown in Figure 4(a) to plot runtime and energy consumption for the function earlier seen in Fig. 1, considering two di erent input sets. shows the behavior of for the synchronization-free input. In this case, the size of keys is very large, and the number of insertions in the M is very low, thus con icts seldom happen. On the other hand, if we make the size of keys very small, and the size of the stream very large, then we obtain a rather di erent constellation, which Figure 4(d) outlines. is constellation shows how T performs in a synchronization-heavy environment. Example 2.6 shows how changes in inputs modify the disposition of hardware con gurations in the constellations. e best energy and time con guration in the CPU-heavy se ing, 4b4L, is one of the worst con gurations in the synchronization-heavy se ing. Such dramatic changes make it very di cult for a completely static approach to nd energy-e cient hardware con gurations for program parts. e size and type of program inputs are only known at runtime. To handle the lack of information at compile time, existing prior work [START_REF] David | Continuously Measuring Critical Section Pressure with the Free-lunch Pro ler[END_REF][START_REF] Nishtala | Hipster: Hybrid Task Manager for Latency-Critical Cloud Workloads[END_REF][START_REF] Petrucci | Energy-E cient read Assignment Optimization for Heterogeneous Multicore Systems[END_REF] resorts to online monitoring; however, this may pose a potential overhead on the system as the number of programs and hardware con guration increase.

MULTIVARIATE LINEAR REGRESSION OF PROGRAM INPUTS

We apply statistical regression on the arguments of a function to determine the ideal hardware con gurations for di erent inputs of that function. e pipeline in Figure 5 summarizes how code is modi ed in order to implement this idea. To ease our presentation, we shall be using source code in our examples, as seen in Figure 5. However, our solution works at the Java bytecode level and our interventions happen within the compiler -more precisely in the program's intermediate representation. Our techniques could have been applied directly onto Java sources or even onto a di erent programming language. Nevertheless, working at the bytecode level lets us optimize programs wri en in di erent languages that run on the Java Virtual Machine. In Section 4 we shall validate our techniques using Java and Scala benchmarks.

Multiple Linear Regression

e key ingredient of our work is the application of multivariate regression onto the arguments of functions. Linear regression empowers a prediction model that matches function parameters with resource-e cient hardware con gurations. We extend our regression model to a multivariate system, as the output is a vector (of ideal con gurations). In this model, we de ne a number of dependent variables, grouped into a matrix C, plus a number of independent variables, grouped into a matrix A. e goal of the regression model is to determine a matrix Θ that approximates the product C = σ (AΘ). In this case, σ is the so max function, applied on the rows of the matrix product AΘ. If Z is a 1 × n vector, e.g., a line of AΘ, then σ (Z ) is also an 1 × n vector, whose j th element is de ned as: σ (Z ) j = e Z j / n 1 e Z k . e so max function receives a vector of real numbers, and produces a vector of the same size normalized over a probability distribution. Every σ (Z ) j is a number between 0.0 and 1.0, and the sum of all the elements within σ (Z ) is 1.0.

Example 3.1. Figure 6 presents a formula for regression involving a function f that has three formal parameters. We assume a universe of ve valid con gurations (0 1L , 1 0L, 1 1L, 2 0L and2 1L). e frequency level is immaterial for this example: big and LITTLE cores run at a certain xed frequency, which is not necessarily the same for the two clusters. In this example we have a training set containing four samples, each one representing a di erent invocation of function f , ideally with di erent actual arguments.

Javac/Kotlinc

Pre-process annotations zero, except its i t h index, which is set to one. If C ji = 1, then i is the best con guration for input j.

e next example illustrates these notions with actual data.

Example 3.3. Figure 8 reuses the ten samples seen in Example 3.2 to build the matrix of dependent variables. is matrix has one line per sample, and one column per con guration of interest. is example considers only 10 out of the 4,654 possible con gurations of the Odroid XU4 board.

is need for bounding the search space might prevent us from discovering good optimization opportunities; however, it ensures that our methodology is practical. Section 4 discusses the criteria used to build the search space of allowed con gurations.

Finding the parameter matrix Θ. e problem of constructing a predictor based on multivariate linear regression consists in nding a matrix Θ that maximizes correct predictions on the training set. e underlying assumption is that if Θ approximates the behavior of the training set, then it is 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 likely to yield good results on the test set. ere exist e cient techniques to nd Θ -gradient descent being the best well-known (Cauchy 1847). Our model is based on multivariate linear regression; thus, searches happen over a linear space. By a linear search space, we mean that, for each element (i, j) in C, we have that:

C i j = Θ 0j + α i1 Θ 1j + . . . + α im Θ mj .
In other words, non-linear expressions such as α ip α iq do not contribute to the value of C i j . Because our model involves only searches over a linear space, gradient descent converges to a global optimum [START_REF] Shi | Convergence of Line Search Methods for Unconstrained Optimization[END_REF]).

Example 3.4. Figure 9 shows a possible matrix Θ that gradient descent nds for the T function, when given the training set seen in Figures 7 and8. Once we apply the so max function onto the product AΘ we obtain a predicted matrix C , which approximates the target matrix C, e.g., C = σ (AΘ). Each line of C adds up to1 1.00. e largest value in each line i of C determines the ideal con guration for the input set A i . e matrix Θ seen in Figure 9 led us into a C that correctly matches the target C in all but two inputs. Some misses are expected. If we resort to more complex regression models, for instance, with non-linear components, then we might nd a Θ that correctly predicts every row of C. However, this matrix, which ts too well the training set, might not yield good predictions on unseen inputs. Using Θ to carry out predictions. e single output of regression is the matrix Θ. Once we nd a suitable Θ, we can use it to predict the ideal con guration for inputs that we have not observed during training. To this e ect, as we shall be er explain in Section 3.3, the constants in Θ are hardcoded into the binary text that we generate for the function f under analysis. If f is invoked with a set of inputs A i , then the expression σ (A i Θ) is computed on-the-y. e result of this evaluation determines the active con guration.

Example 3.5. Figure 10 uses the matrix Θ found in Figure 9 to guess the best con guration for four unseen input sets. ese inputs appear as dark spheres in Figure 10. In this example, Θ correctly predicts the ideal con guration for three out of four samples. In one case, the last input in Figure 10, we wrongly predict the best con guration as 4b2L, whereas empirical evidence suggests that it should be 4b4L.

( × ϴ ) = ( × ϴ ) = ( × ϴ ) = ( × ϴ ) = T"="4"
T"="8"

T"="16"

T"="32"

1.E+00" Unseen inputs Predictions

1.E+01" 1.E+02" 1.E+03" 1.E+04" 1.E+05" 10^1" 10^2" 10^3" 10^3" 10^4" # T h

Engineering the Training Phase

Users of J C specify which methods must be optimized. For each one of these methods, J C singles out its inputs, and instrument them to produce regression data. Are considered inputs: the formal parameters of methods, the global variables used within these methods and the number of active threads. Regression data consists of the size of these inputs. e technique used to obtain these sizes depends on the type of input. Currently, we use the following heuristics: Primitive types: the size of a primitive type is its own value. Wrappers: types such as Integer or Double, which work as wrappers of primitive types, give us a size through their value() methods, e.g., intValue() for Integer. Arrays and Strings: we derive the size of such types via the length property. Collections: we derive the size of collections by invoking their size() method. Other classes: we search within the declaration of the type, or in any of its super-types, for a method called size(); otherwise, we search for a property called length. If such names are not to be found, an error ensues.

Example 3.6. Figure 11 shows two instrumented programs. Pro ling code is inserted in the programs' intermediate representation -source code is used only for readability. Instrumentation is performed by a singleton object Instrumenter, which stores "bundles" of data. Each bundle contains an identi er, a hardware con guration, the independent variables of the adaptive method, and the runtime for those variables. Identi ers map methods to bundles. Multiple invocations of the same method will produce one bundle per call.

Profiling, Logging and

Training. Currently, we use a pro ling infrastructure wri en as a combination of Java code and bash scripts. e part implemented in Java consists of a service that runs the program that we want to optimize in a controlled environment. is driver has two responsibilities: warming up the target program and changing hardware con gurations before every pro ling experiment.

J

C receives an annotated program P, a set of di erent inputs I = {ι 1 , ι 2 , . . . , ι m } of P, and a set of acceptable hardware con gurations H = {h 1 , h 2 , . . . , h n }. It will test the program a predetermined number of times for each pair (h, ι), h ∈ H, ι ∈ I . e best con guration for each input ι is chosen among the most frequent winner. e objective function that determines the winner is con gurable. Currently, we consider time, energy consumption and energy-delay product. In case of ties, we choose the con guration with the least resources. Resources are ordered according to the number of big cores, the number of LITTLE cores, the frequency of the big cores and the frequency of the LITTLE cores, in this sequence. Example 3.7. Figure 12 shows a typical output produced during J C's training phase, considering runtime as the objective function. In this experiment, each pair formed by a hardware con guration and an input is sampled ten times. Vectors at the bo om of Figure 12 are the inputs passed to function T (Fig. 1). ese vectors are the independent variables in the regression model. Vectors at the top of Figure 12 are the best con gurations. ese vectors will give us the dependent variables used in the regression.

Complexity of the Training Phase.

Training involves running the target program in every valid hardware con guration with every available input. erefore, the asymptotic complexity of this phase is determined by the number of valid hardware con gurations, the number of input sets available to run the program and the complexity of the program itself. In other words, the instrumented program P will have to be pro led |H | × |I | times; H being the set of valid hardware con gurations and I the set of available inputs.

e third column of Table 1 (Page 17) reports training times observed when evaluating the benchmarks used in this paper. e longest time was 225 minutes; the shortest 21 minutes. Section 4.1 provides more details about these costs.

Generation of Adaptive Code

e product of training is a matrix Θ of oating-point numbers. Θ is hardcoded into the production code that we want to optimize. Such step happens in the phase labeled "add prediction instrumentation" in Figure 5. e instrumentation that we add into a function f of interest evaluates the expression σ (A i Θ), where A i is a 1 × n vector. e size of A i is one plus the number of inputs of the target function. e expression σ (A i Θ) yields a 1 × k vector of probabilities, whose elements add up to 1.0, where k is the number of hardware con gurations considered as targets. e largest element within σ (A i Θ) determines the next con guration that will be used during the current invocation of f . erefore, the complexity of choosing a hardware con guration is proportional to the number of function arguments (n) times the number of valid hardware con gurations (k). As we shall discuss in Section 4, this time tends to be too short to be of practical consequence.

Example 3.8. Figure 13 shows the production version of our running example, the function T , originally seen in Figure 1. e dashed box outlines the code that we add to T to change the current hardware con guration. We show, on the right of the gure, the key methods used to change and restore the current hardware con guration. e matrix Θ seen in the production version of function T was found a er training, as Example 3.4 explains.

EVALUATION

is section demonstrates the e ectiveness of our technique when optimizing bytecodes that run on top of the Java Virtual Machine. To this end, we shall provide answers to the following research questions: 2.0GHz, and four Cortex A7 cores running at up to 1.5GHz. e board features 2GB of LPDDR3 RAM. To measure the energy consumed exclusively by speci c functions, we send signals to the synchronization circuit seen in Figure 4-a through one of the board's GPIO pin. Code to emit the signal is inserted into Java bytecodes via S , immediately before the invocation of a function of interest, and immediately a er that function returns. We use the energy measurement framework proposed by Bessa et al. [START_REF] Bessa | JetsonLEAP: A framework to measure power on a heterogeneous system-on-a-chip device[END_REF]. Power is measured by a National Instruments DAQ USB 6009 device, at a rate of 12,000 samples per second.

RQ1
e So ware Stack. We use Oracle's OpenJDK/JRE 11 LTS and Soot 3.2.0 to process bytecodes. No modi cations have been made in the Java Virtual Machine -transformations performed by either J C or CHOAMP happen at the bytecode level, and are carried out via Soot. To mitigate the e ect of JIT compilation in the execution time of benchmarks, each application has a warm-up stage before actual execution (details in Table 1). We have used Python 3.4 and Scikit Learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF]) to implement regression. Python was also used, in addition to GNU Bash 4.4.19, to generate the suite of micro-benchmarks used to train CHOAMP. e Operating System in the Odroid XU4 used in our experiments is the GNU/Linux Ubuntu 18.04 LTS with kernel 4.17.

e Benchmark Suite. is paper uses the 18 benchmarks shown in Table 1. Eight of them were taken from Acar et al. [START_REF] Umut | Heartbeat Scheduling: Provable E ciency for Nested Parallelism[END_REF]), who had selected nine programs from Problem Based Benchmark Suite (PBBS) [START_REF] Shun | Brief Announcement: e Problem Based Benchmark Suite[END_REF] to evaluate concurrency models. e version of PBBS used by [START_REF] Umut | Heartbeat Scheduling: Provable E ciency for Nested Parallelism[END_REF]) was implemented in C/C++, so we had to re-implement all the benchmarks in Java. We removed D T from our collection, because we could not ensure that its parallel implementation always produces the same output. e triangulation varies depending on how threads are scheduled; hence, the output of di erent versions of this benchmark might not be equal.

We chose six programs from the Renaissance benchmark collection, which was recently released by Prokopec et al. [START_REF] Prokopec | Renaissance: Benchmarking Suite for Parallel Applications on the JVM[END_REF]. Renaissance contains 21 benchmarks. All the programs in that collection come with only one set of input values. We chose only six benchmarks because we had to understand and augment each program with more inputs. We have also added veri cation code to these benchmarks to check execution correctness.

e six benchmarks that we chose are implemented in Scala. Our criterion when picking up programs was simplicity: we selected benchmarks that were easy to modify. We have opted for Scala programs to demonstrate that J C can deal well with languages other than Java. In addition to PBBS and Renaissance, J C is distributed with four typical parallel algorithms. C P and N C were taken from public repositories; H S , was adapted from Butcher's book; and

A A was adapted from Zhang et al. (2020)'s Figure 3. Table 1 presents an overview of the benchmarks, as well as basic characteristics of their code.

We recall an observation already made by Prokopec et al., when introducing the Renaissance Benchmark Suite: the source code of the benchmarks is relatively small; however, they cause the invocation of hundreds of di erent methods, potentially millions of times. Many of these methods belong to the Java Standard Library (e.g., java.util.*, java.lang.System, etc). ree of the Renaissance programs: textscAls, C S and D T also rely heavily on Apache's spark engine. e two last columns of Table 1 report the static and dynamic count of methods invoked by each benchmark. To derive these numbers, we use Oracle's VisualVM pro ler on the default inputs of each benchmark. Notice that numbers produced through this pro ling technique cannot be exactly reproduced: small variations are expected due to internal operations of the Java Virtual Machine, concerning, for instance, the activation of the garbage collector or the just-in-time compiler. Example 4.1 clari es this observation for S F . e choice of benchmark in this case is arbitrary, because the other programs that we evaluate show similar behavior.

Example 4.1. e benchmark called S F is part of the Problem Based Benchmark Suite. It computes a series of minimum spanning trees -one per connected component-of undirected graphs. is benchmark's source code contains 410 lines of code, grouped into 31 methods organized in ve java les. We adapt the method called "benchmark", which receives a list of edges and an integer denoting the number of threads that will be created to process these edges. By default, this benchmark receives a graph with 120 nodes and 1,000 edges. With these default inputs, "benchmark" causes the invocation of 1,905 di erent methods. Out of this lot, 1,874 are either part of the Java Standard Library (in classes like java.util.ArrayList or java.util.concurrent.Executors), or are part of the Java Virtual Machine. In a single run of this benchmark with default inputs, these methods were invoked 106,462 times. ese numbers, 1,874 and 106,462, might vary due to internal operations of the JVM. Available Inputs. Each benchmark comes with a default input set. We have augmented every one of them with 13 additional inputs. We tried, as best as our knowledge of the benchmark allowed it, to maximize the diversity of inputs, having data of di erent sizes. Ten of these inputs, randomly chosen, are used for training. When evaluating the model trained for a benchmark, we use four unseen and randomly chosen inputs. Sections 4.2 and 4.3 further discuss the impact of di erent inputs in the execution time and energy consumption of the applications. e separation of inputs into training and evaluation sets is random. Choice of regression target. We optimize one method per benchmark: the routine invoked by the benchmark's main function. is approach is equivalent to doing regression on inputs of the whole program. In other words, in practice, we are tuning the entire program; not a single method of it. As previously mentioned, each of these adapted functions will, during a normal execution of the benchmark, cause the invocation of many methods external to the benchmark's source code. All these activations will run in the hardware con guration determined by the regression model. To give the reader some perspective on this approach, Table 1 contains in the last two columns the number of di erent functions that are a ected by the change in hardware con guration (stCalls), plus the number of times that these functions are dynamically invoked (dyCalls). 1. Benchmarks used for evaluating J C. Column TTime shows time to train each benchmark, which will be further explained in Section 4.1. Lang. contains the source language of benchmarks: J stands for Java and S for Scala. Column W shows the number of warm-up executions performed by each application. StCalls approximates the number of methods invoked by a benchmark running with default inputs; dyCalls approximates the number of times that those functions are invoked. These numbers were produced with Oracle's VisualVM profiler; hence, small variations are to be expected. P finds three points on the same line; S inserts in a concurrent table; N C has several long sequences of branches that are hard to predict; and

A A implements parallel operations on a Database.

On the Choice of Hardware Con gurations. When training J C and CHOAMP, we follow the methodology proposed by Sreelatha et al [START_REF] Krishna | CHOAMP: Cost Based Hardware Optimization for Asymmetric Multicore Processors[END_REF]. us, we consider a universe of six con gurations: 4b4L (4 big and 4 LITTLE cores), 4b0L, 0b4L, 2b2L, 2b0L and 0b2L. LITTLE cores run at maximum frequency: 1.5GHz. Big cores are statically set to run at either 1.6GHz or 1.8GHz (instead of using the maximum 2.0GHz frequency level) due to known thermal issues (da Silva et al. 2019, Sec-4.2). GTS is allowed to choose among any possible hardware con guration involving big and LITTLE cores, and the di erent frequency levels available in the hardware. For the sake of reproducibility and to be er understand the impacts of our technique, we have disabled Dynamic Voltage and Frequency Scaling (DVFS) when using either J C or CHOAMP, but not GTS. Regardless of the methodology used to choose hardware con gurations, thread scheduling uses Linux' default Heterogeneous Multi-Processor (HMP) scheduler [START_REF] Rezki | Doing big.LITTLE right: li le and big obstacles[END_REF], which is integrated into the kernel's Completely Fair Scheduler (CFS). us, threads might switch between big and LITTLE cores. e higher the CPU utilization of a thread, the higher the likelihood that it will run on a big core. On the Implementation of CHOAMP. CHOAMP is a system that, di erent from our approach, relies on the syntax of the program text -and on its implied semantics-to predict ideal hardware con gurations. CHOAMP represents this text of code as a set of characteristics that are useful for training and prediction. Such characteristics, also called prime features by its authors, are split into two di erent groups: language dependent and independent. Language independent features, such as number of branches or memory accesses, are easier to identify and port, as they tend to appear in most languages. On the other hand, features that depend on a speci c programming language need to be adapted when porting the technique to new environments. CHOAMP was initially designed to work with OpenMP applications implemented in C; therefore, some of the prime features used by Sreelatha et al. depend on OpenMP constructs. Our re-implementation of CHOAMP targets Java applications running on Hotspot; thus, some of its features had to be adapted to our needs. Table 2 presents the list of program characteristics originally used by CHOAMP for OpenMP and the new version of them, adapted to the JVM. Most language dependent features nd correspondents in the Java standard library, as is the case of the omp atomic pragma, which we derived from classes in the package java.util.concurrent. atomic. For instance, the occurrence of method incrementAndGet(), from the AtomicInteger class, would add an "Atomic Operation" to the feature vector of the function where incrementAnd Get() is invoked. However, some features like ush operations, proposed by Sreelatha et al. e user adjusts the intensity of each prime feature through command line inputs. We used the originals generator scripts at h ps://bitbucket.org/jkrishnavs/ openmp-eigenbench, adjusting the code to Java. We also used the same range and intensity of features as used in the original work of CHOAMP. Sreelatha et al. have proposed three di erent regression models for CHOAMP. We have experimented with all of them, and end up choosing the linear t, because, in our setup, it yields be er results than the adratic and Gaussian predictors.

is result in on par with the ndings of Sreelatha et al.

RQ1: Training

J C and CHOAMP require training to adjust the parameters of the regression models. While this cost is paid once by CHOAMP, when performing the training over a set of generic micro-benchmarks, J C pays this cost for each application that it optimizes. CHOAMP uses micro-benchmarks for training; J C uses the application itself. e training time of CHOAMP is computed over a set of 285 micro-benchmarks over all the hardware con gurations mentioned in our experimental setup. In our hardware, we took about 780 minutes to train our implementation of CHOAMP.

To train J C, we follow the methodology described in Section 3.2.1. J C's training time depends on the target application's run time, and on the number of available inputs. Table 1 shows the training time of each benchmark. Using ten inputs and ten allowed hardware states (clock speed × hardware con gurations) per benchmark, we took 903 minutes to train the 18 programs used in this section. e longest time, three hours and 45 minutes was spent in Renaissance's HTTP. PBBS's S gave us the fastest training time: 20 minutes and 51 seconds. Once the benchmark is trained, no further pre-processing is required. e product of training, the code earlier seen in Figure 13, is embedded directly into a program's bytecode, and runs in constant time. Training's overhead bears no impact once the optimized code runs. e only overhead that is imposed onto optimized programs comes from the matrix multiplication that happens once a hot function is invoked, as we have discussed in Section 3.3. As we will see in Section 4.2, this runtime overhead is too low to be reliably measured.

RQ2: Speed

Figure 14 summarizes the comparison of the three di erent schedulers, when the objective function that J C and CHOAMP minimize is the execution time of target applications. We have tested each benchmark with four input sets, adopting a signi cance level α = 0.05; i.e., a con dence level of 95%. So, if the results reported by, for instance, J C and CHOAMP cannot be distinguished with a con dence of more than 95%, then we consider them as originating from the same population. us, we use Student's Test to measure the p-value of two populations, and consider signi cant results with a p-value less than 0.05. White boxes with le ers in Figure 14 identify the technique which achieved the best result for a combination of benchmark and input. J stands for J C, C for CHOAMP and G for GTS; X means that the winning systems have produced results statistically similar (p-value greater than 0.05). Above each input set, we show the con guration that J C chose for that input. e grey box, at the right of the name of each benchmark, is the con guration that CHOAMP chooses for that benchmark.

We notice that in 26 cases, out of 72 combinations of [benchmarks × inputs], J C achieved be er results when compared to the other techniques. In other 42 cases, J C was at least as fast as GTS or CHOAMP. CHOAMP, in turn, accounted for 3 best results, and GTS for only one, in S 's I 4. ese numbers show that J C usually outperforms the two other techniques considered in this paper; however, J C's performance still depends on a good choice of inputs for training. Example 4.2 highlights this fact. Further discussion about the importance of nding good training sets shall appear in Example 4.6 (Page 27).

Example 4.2. J C performed rather poorly in P , due to an unfortunate choice of training inputs. Indeed, the 10 training inputs chosen when optimizing P nd in 4 4L their best con guration. However, coincidentally, three of the test inputs ask for 4 0L. It su ces to switch one of the test and training inputs to put J C on pair with the other schedulers.

is experiment shows that con gurations impact in non-trivial ways the behavior of applications. All the winning con gurations, regardless of the technique, converged to the frequency of 1.8GHz whenever at least one big core was present. e most recurring con gurations were 4b4L (16x for CHOAMP and 37x for J C), 0b4L (2x/11x), 4b0L (17x for J C only), 2b0L (4x for J C only), and 0b2L (2x for J C only). Example 4.3 further emphasizes the importance of the hardware con guration in the behavior of a program.

Example 4.3. Considering S 's last input ( = 2, SIZE = 1, 023, 464), J C prediction of the con guration 4b0L led to a mean run time of 8.18 seconds, while CHOAMP decision led to 8.47 and GTS to 9.00. For its second input ( = 4, SIZE = 2, 250, 467), we observed J C prediction (4b0L) leading to mean run time of 17.00 seconds, CHOAMP to 18.70 and GTS to 17.76. In every case, p-values comparing these populations were less than 0.008. 1. Y -axis shows time in seconds. X -axis shows di erent experiments; each experiment uses di erent inputs. Boxplots are ordered by J C, CHOAMP and GTS.

• • • • • • • 2 3 4 5 In1 In2 In3 In4 collinearPoints • • • • • • • • • • • • • 0 2 4 6 8 In1 In2 In3 In4 randomNumComp • • 0 1 2 3 4 5 In1 In2 In3 In4 hashSync • • • • • 0 10 20 30 40 In1 In2 In3 In4 bfs • • • • • • • 0.050 0.075 0.100 0.125 0.150 In1 In2 In3 In4 spaningForest • • • • 0 10 20 30 In1 In2 In3 In4 insertAndAdd • • • • • • 1 2 In1 In2 In3 In4 nearestNeighbors • • • • • • • • • 0.4 0.8 1.2 1.6 In1 In2 In3 In4 convexHull • • 1.5 2.0 2.5 3.0 In1 In2 In3 In4 removeDuplicates • • • • • • • 1 2 In1 In2 In3 In4 suffixArray • • • • • • • • • • • 0 5 10 15 In1 In2 In3 In4 sampleSort • • • • • 0.2 0.4 0.6 In1 In2 In3 In4 radixSort • • • • 10
J J J J X X 4b0L 4b0L 4b0L 4b4L 4b4L X X 4b4L 4b4L 4b4L 4b4L 4b4L 0b4L 0b2L 0b2L 0b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b0L 4b4L 4b0L 4b4L 4b4L 0b4L 0b4L 0b4L 0b4L 4b4L 4b4L X X X X X X J X X X J X X X X X G J J J J C X 4b4L 4b0L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 0b4L 4b4L 4b4L 4b4L 4b0L 4b0L 4b0L 4b0L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b4L 4b0L 4b4L 4b4L 4b4L 4b4L 2b0L 4b0L 2b0L 4b0L 4b4L 4b4L 4b4L 4b4L 4b4L 0b4L 4b0L 4b0L 4b0L 4b0L 4b4L 4b0L 0b4L 0b4L 0b4L 4b4L 2b0L 2b0L 0b4L 0b4L X X X X J J J J X X X C X X X X J J J J J J J X J X X X J J C X J X X X 4b4L 4b4L 4b4L J X X X X

RQ3: Energy

Figure 16 compares CHOAMP, GTS and J C regarding energy consumption. e clock speed of 1.6GHz was the most common among all the schedulers, except for one input set of S , when CHOAMP chose to use 1.8GHz. GTS can choose any possible frequency levels from 200MHz to 1.8GHz in the big cluster and from 200MHz to 1.5GHz in the li le one. is exibility may lead to performance degradation because GTS increases frequency gradually, even in computationintensive programs. Even with several warm-up rounds, GTS might take an excessively long time to achieve maximum frequency levels for some applications. us, J C outperforms GTS mostly due to its ability to choose high-performance hardware con gurations, such as 4b4L at 1.6GHz, immediately. GTS, in turn, needs a warm-up period to arrive at them.

Figure 16 shows that J C achieved the best results in 20 experiments (out of 72); GTS won in 2, and CHOAMP in 6. In 44 experiments there was no clear winner. is di culty to pinpoint a best technique is due to the fact that we measure energy for the entire board. erefore, peripherals like the fan and the memory bus increase the variance of results. is decision was no accident: we believe that measuring energy for the entire boards provides a more realistic assessment of the behavior of our techniques if adopted in production. CHOAMP has chosen the 0b4L con guration at 1.6GHz for almost all the samples in this evaluation.

is behavior is due to some features, such as branching and memory operations, dominating the others in most of the functions that constitute a benchmark. It is possible to improve this behavior by scaling the relative importance of the features; however, this optimization is out of the scope of this work.

On the In uence of Execution History. Execution history impacts the energy consumed by di erent programs. Take as an example the entry corresponding to S in Figure 16. Although J C and CHOAMP predicted the same con guration for the second input set (In2), the former consumed marginally more energy. is behavior is even more surprising once we consider that J C's and CHOAMP's code run within about the same time, as Figure 14 reveals. e culprit of this counter-intuitive result is the board state at the time measurement started. e warm-up phase, in this case, is responsible for giving J C's and CHOAMP's code di erent starting states. In the discussion that follows, we shall separate the execution of a benchmark into two parts: warm-up, when the target routine is called a number of times to stabilize the Java Virtual Machine; and measurement, when the behavior of the benchmark is actually gauged. Hysteresis. Figure 15 shows the power pro le of S , including warm-up and measurement phases. Invocations in the warm-up stage use di erent inputs than in the measurement stage. As a result, our technique predicted the con guration 4b4L for the last warm-up invocation, which is di erent than 0b4L, the con guration predicted at measurement. e use of big cores during warm-up increased the amount of energy consumed by the board in the measurement step, due to a well-known phenomenon: the hysteresis of power dissipation.

e mean power dissipated by J C's version of S in Figure 15(a) was 4.68W. CHOAMP's was 4.09W, as seen in Figure 15(b). J C's program consumes more energy (9.47J vs 8.22J). However, if we x the hardware con guration in the warm-up phase of J C's code, then the average dissipation goes down to 3.95W. Figure 15(c) reports the power pro le of this setup.

e only di erence between the executions of J C in Figures 15 (a) and (c) is the con guration used in the warm-up stage. ere is no statistically signi cant di erence between the amount of energy consumed by CHOAMP and J C when both warm-up with the same hardware con guration. is behavior caused by di erences between con gurations chosen at warm-up and measurement phases only a ects J C. CHOAMP always chooses the same hardware con guration per function, and GTS increases frequency gradually. e only further impact that this di erence had in J C's behavior was observed in T and P . In both cases, only for the last input set (In4), and only when measuring running time (Fig. 14). e need to change con guration when moving from warm-up to measurement has cost J C's code some time. Nevertheless, when

2b0L 2b0L 0b4L 0b4L X X X X C X X X C C X X X X X J X 4b4L 4b4L 4b4L C X J G X J J J J X X X X G X J J J J J J C X X X X X J J X X X X J J X X X X X X X
Fig. 16. Energy consumed by the benchmarks in Table 1. Y -axis shows energy in Joules. X -axis shows di erent experiments. Boxplots are sorted as in Figure 14.

region covered by the same optimal con guration is continuous. In other words, while varying this single input monotonically, we will not leave a region r where a certain con guration h is the best, a new region r governed by a di erent con guration h , only to nd h again later, an omnibus test -it analyzes the data as a whole; hence, we performed a post-hoc test to nd out where the di erences among the groups were.

e post-hoc test consists of a series of T-tests between each pair of con gurations. e signi cance level is adjusted to avoid spurious positives. To that end, we used the Bonferroni correction [START_REF] Emilio | Teoria statistica delle classi e calcolo delle probabilità[END_REF][START_REF] Jean Dunn | Estimation of the Means for Dependent Variables[END_REF]. Each individual hypothesis is tested with a threshold of α/n, where α is the signi cance level for the entire set of comparisons, e.g., 0.05, and n is the number of statistical tests performed. us, analogously to the ANOVA test, if the resulting P-value is lower than the signi cance level given by the Bonferroni correction, then the null hypothesis can be rejected. Rejection of the null hypothesis is equivalent to assume that the two groups of con gurations present a statistically signi cant di erence. Monotonicity and Convexity. As Example 4.4 shows, Convexity is a tendency, not a rule. Nevertheless, we believe that convexity is common because the asymptotic behavior of most , 2b0L, 4b0L, 4b4L 0b2L, 0b4L, 2b0L, 4b0L, 4b4L Fig. 18. Best hardware configuration, considering running time as the objective function. I A D receives four inputs. We fixed the "initial capacity" in 5,000 and the "change threshold" in 500. R D receives three inputs. We fixed the "size of the keys" in 16 bytes. This choice of values is arbitrary, and was necessary to give us 2D figures.

algorithms is described by monotonic -therefore convex-functions. e running time of algorithms tend to be governed by convex functions ranging on their inputs. is observation can also be projected onto parallel algorithms, once we consider the number of threads as an input. In other words, variations in the running time of a parallel algorithm tend to be described by (typically decreasing) monotonic functions ranging on the number of available threads [START_REF] Keller | Practical Pram Programming[END_REF]. As an example, Figure 18 shows the best hardware con guration for two of our benchmarks, considering running time as the objective function. In this case, we are varying, in addition to some input, the number of available threads. It is possible to observe the convex shape of the space delimited by the best hardware con gurations for these benchmarks. 4.4.2 Separability. In the context of classi cation problems, the main bene t of convexity is separability. e Hyperplane Separation eorem (Boyd and Vandenberghe 2004, Ch.4) states that two disjoint convex sets are linearly separable. In other words, if C 1 and C 2 are closed convex sets such that C 1 ∩ C 2 = ∅, then there exists a linear function (x) = w T x + w 0 such that (x) > 0 for every x ∈ C 1 and (x) < 0 for every x in C 2 . Function is called a linear discriminant, because it can distinguish points from C 1 and C 2 [START_REF] Chan | Linear Separability[END_REF].

In this paper, we use multivariate linear regression to build linear discriminants. As already mentioned in Section 2.1, these functions range on the space formed by program inputs. Completely chartering this space would involve applying the methodology discussed in Section 3.2 to every possible combination of inputs that a program might use. is task is impractical-if at all possible; thus, in Section 4.4.1 we have evaluated a handful of inputs for a few benchmarks. is evaluation indicates that, at least for these benchmarks, the regions in the search space covered by similar hardware con gurations tend to be convex.

Figure 17 shows that the regions in which speci c hardware con guration excel are not disjoint. In other words, the same set of function arguments could be mapped to di erent hardware con gurations with similarly good e ects. Nevertheless, the linear discriminants that we build are disjoints, for, in case of ties, we choose the con guration with less resources as explained in Section 3.2.1. is said, the accurate classi cation of regions into the right hardware con gurations still depends on a good assortment of inputs. Example 4.6 illustrates this fact.

Example 4.6. Figure 19 (a) shows an idealized representation of the search space for a hypothetical program2 . is space is formed by three convex sets mapping inputs to con gurations 4 0L, 0 4L and 4 4L. A perfect classi cation model would nd the three lines that separate these regions. In practice, classi cation approximates these lines by maximizing the distance between the known inputs. In this example, we have three of them. e white regions in each gure show points for which classi cation would give wrong answer. e more inputs are used in training, the smaller these regions tend to be, as the comparison between Figures 19 (b

RELATED WORK

Our work explores a type of machine learning technique -multivariate linear regression-to solve an instance of program scheduling in heterogeneous architectures. ere exists vast literature about uses of machine learning in compilers (Wang and[START_REF] Wang | Machine Learning in Compiler Optimization[END_REF][START_REF] Amir | A Survey on Compiler Autotuning Using Machine Learning[END_REF]. Equally abundant is the material about scheduling in heterogeneous multi-core systems. For a comprehensive overview on this topic, we recommend the survey recently carried out by Singh et al. (2020). In the rest of this section, we discuss some of this research, focusing on scheduling, with the intention to explain how our work stands within the contemporary literature.

A General Overview on Program Scheduling in Heterogeneous Systems

e general problem of scheduling computations in heterogeneous architectures has a racted much a ention, as Mi al and Ve er have discussed (Mi al and Ve er 2015). Table 3 provides a taxonomy of previous solutions to this problem. We group them according to the level at which they are implemented, and to the way they answer each of the following four questions:

• Architecture: do they apply to Single or Multi-ISA systems? et al. 2014;[START_REF] Zhang | Maximizing Performance Under a Power Cap: A Comparison of Hardware, So ware, and Hybrid Techniques[END_REF]. By leveraging runtime information, the system can use environment information, unknown at compilation time. Examples of such information include varying input sizes and resource demands. However, there may be some overhead on accurately collecting and processing runtime data. Besides, because scheduling decisions are taken on-they, usually the scheduler cannot spend much time weighing choices. us, even though these algorithms use runtime information, they might still take suboptimal decisions, due to their inability to spend much time solving hard scheduling problems. Hybrid Solutions. Approaches that mix static and dynamic techniques are called hybrid. Examples of hybrid solutions to scheduling include works from [START_REF] Piccoli | Compiler Support for Selective Page Migration in NUMA Architectures[END_REF], [START_REF] Cong | Energy-e cient Scheduling on Heterogeneous Multi-core Architectures[END_REF], and [START_REF] Tang | ReQoS: Reactive Static/Dynamic Compilation for QoS in Warehouse Scale Computers[END_REF]. Piccoli et al [START_REF] Piccoli | Compiler Support for Selective Page Migration in NUMA Architectures[END_REF]) have used a compiler to instrument a program with guards that determine, based on input sizes, where each loop should run. Cong and Yuan [START_REF] Cong | Energy-e cient Scheduling on Heterogeneous Multi-core Architectures[END_REF], in turn, use the compiler to partition a program in regions of similar behavior, and rely on runtime information to schedule computation so as to minimize the energy consumed by each region. Finally, Tang et al. [START_REF] Tang | ReQoS: Reactive Static/Dynamic Compilation for QoS in Warehouse Scale Computers[END_REF]) use a compiler to populate a program code with markers, so that low-priority applications can manage their own contentiousness to ensure the QoS of high-priority co-runners. None of these previous work use any form of learning technique to tune the behavior of the scheduler, as Table 3 indicates in the column Learn. Guards, once created, behave always on the same way.

Scheduling in Single-ISA Heterogeneous Systems

Much a ention has been dedicated to the problem of nding good placements of computation on heterogeneous multicore systems, as Mi al et al. (Mi al 2016) has summarized. However, we emphasize that a large part of this literature concerns the design of scheduling heuristics implemented at the level of the hardware or the operating system [START_REF] Cai | Montgol er: Latencyaware power management system for heterogeneous servers[END_REF][START_REF] Garcia-Garcia | Contention-Aware Fair Scheduling for Asymmetric Single-ISA Multicore Systems[END_REF][START_REF] Agostino Masci I | An Adaptive, Utilization-Based Approach to Schedule Real-Time Tasks for ARM Big[END_REF][START_REF] Sparsh | A Survey of Techniques for Architecting and Managing Asymmetric Multicore Processors[END_REF][START_REF] Leal | ULOOF: A User Level Online O oading Framework for Mobile Edge Computing[END_REF][START_REF] Park | RPPC: A Holistic Runtime System for Maximizing Performance Under Power Capping[END_REF]Van Craeynest et al. 2012b). is section describes works that, like J C, can be auto-tuned to characteristics of the runtime environment, and that have been speci cally designed for big.LITTLE architectures. By characteristics of the runtime environment we mean the nature of the inputs or the behavior of the hardware. We leave out of this comparison scheduling algorithms that rely on worst-case execution estimates of tasks, such as Masci i et al. (2020)'s or [START_REF] Roeder | Energy-aware Scheduling of Multi-version Tasks onHeterogeneous Real-time Systems[END_REF]. In other words, no assumptions are made on the time or energy budget of a given task.

Table 4 categorizes these techniques along the following lines:

• Granularity: what is the data used for training? Most of the techniques use runtime information (R) -available via performance counters. CHOAMP relies on features mined from the program's syntax (S). We use the program's inputs to perform predictions (I). We have compared J C with CHOAMP extensively in this paper. SIAM, in turn, is a system that targets speci cally graph algorithms parallelized via OpenMP. It consists of a prediction model that, given a particular shape of a graph, determines the best data-structure format and hardware con guration for that shape. We could, in principle, adapt it to implement some of our benchmarks, such as F and BFS -graph-based algorithms. However, this implementation would involve providing each algorithm with di erent graph representations -a task to be paid at a non-negligible programming cost.

Input-Aware Program Autotuning

Our work is centered around the idea that characteristics of the input can be used to determine the behavior of a program. Autotuning techniques that take decisions based on inputs are well-known. Even relatively old libraries such as FFTW [START_REF] Frigo | The Design and Implementation of FFTW3[END_REF] provide code that is optimized for di erent input sizes [START_REF] Guarrasi | Auto-tuning of the FFTW Library for Massively Parallel Supercomputers[END_REF]. And more recent work [START_REF] Esper | A Comparative Evaluation of Latency-Aware Energy Optimization Approaches in Many-Core Systems[END_REF][START_REF] Teich | Run-Time Enforcement of Non-functional Program Properties on MPSoCs[END_REF]) has demonstrated that input-awareness can be used to keep programs running in multi-core systems within the limits of predetermined energy or time requirements. Along these lines, a direction of research that has been much explored concerns the matching of inputs with data-structures [START_REF] Costa | CollectionSwitch: A Framework for E cient and Dynamic Collection Selection[END_REF][START_REF] Jung | Brainy: E ective Selection of Data Structures[END_REF][START_REF] Schiller | Compile-and run-time approaches for the selection of e cient data structures for dynamic graph analysis[END_REF]. We emphasize that none of these previous techniques embed regression code into the compiled program, in order to bestow on said program the ability to choose hardware con gurations based on input value.

In this regard, recent work by [START_REF] Oliveira | Improving energy-e ciency by recommending Java collections[END_REF] have shown that the implementation of data structures bear much impact upon the energy consumption of mobile applications. From their observations, Oliveira et al. provide developers with a number of recommendations to code energy e cient so ware, following a methodology previously proposed by [START_REF] Couto | Energy Refactorings for Android in the Large and in the Wild[END_REF]. is line of work aims at building tools that work like code linters: tools that point out potential power ine ciencies to programmers. is modus operandi is made clear by [START_REF] Melfe | Helping developers write energy e cient Haskell through a data-structure evaluation[END_REF]. is paper, in contrast, describes an automatic optimization: our code transformation works at the compiler level, and does not require intervention from users.

CONCLUSION

is paper presented an end-to-end code generation technique that matches programs to hardware con gurations in heterogeneous multicore systems. is paper is centered around the thesis that the values of a function's arguments provide enough information to predict the best hardware con guration for that function. Our technique is able to outperform, be it in energy consumption, be it in execution time, the default Linux scheduler for ARM (the Global Task Scheduler), and CHOAMP, a recently released tool that predicts the best hardware con guration to a parallel program based on its syntax.

Limitations and Future Work. As any pro ler-based technique, J C has limitations. Its e ectiveness depends on having adequate training inputs for each program that it optimizes. However, the more inputs are used, the longer the training time, as observed in Section 3.2. We speculate that it might be possible to remove the need of training per application if we use static-pro ling techniques [START_REF] Ball | Branch Prediction for Free[END_REF][START_REF] Wu | Static Branch Frequency and Program Pro le Analysis[END_REF] to infer, at compilation time, how the inputs of a program might in uence that program's behavior. In terms of engineering, we believe that the techniques that we advocate in this paper could be ported to programming environments other than the JDK's ecosystem. For instance, to port our technique to C/OpenMP, J C could be reimplemented in LLVM [START_REF] La | LLVM: a compilation framework for lifelong program analysis transformation[END_REF]. In this regard, LLVM would ll in that se ing the role that Soot has lled in this paper. Notice that our techniques do not depend on static program features, so feature engineering would not be necessary for portability. We leave the investigation of such possibilities as future work.

So ware. J

C is available at h ps://github.com/lac-dcc/JINN-C under the GPL-3.0 License. Details about this project can be found at h ps://homepages.dcc.ufmg.br/ ∼ juniocezar/intelligentDVFS

/

  / The number of threads is a hidden input void task(Stream<Value> s, long keySize) { while (!s.empty()) { // Get a key of the proper size: BigInteger key = getNextKey(keySize); // Use key to update globalMap synchronized(globalMap) { Value value = s.next(); globalMap.put(key, value)

Fig. 1 .

 1 Fig. 1. (Le ) A program whose behavior can be computation-heavy or synchronization-heavy, depending on its inputs. (Right) The search space formed by the program's inputs. (Taken from da Silva et al. (2020)).

Fig. 2 .

 2 Fig.2. Ideal configuration for di erent parameters of the function (Fig.1), for 4, 8 and 16 threads, measured on an Odroid XU4 with the userspace governor. Default configuration is 4b4L. Names in boxes indicate the best configuration(s) for that input. 'X' indicates setups with three or more configurations tied as best. To produce these charts, we followed a methodology to be described in Section 4.4. Even considering 4 threads, there is benefit to enable more than four processors, as the Java virtual machine creates threads for garbage collection and JIT compilation, for instance (Taken from da Silva et al. (2020)).

  Figure 4(b) shows the power pro le of T for a synchronization-free set of inputs (top) and for a synchronization heavy set (bo om). Following Silva et al. (da Silva et al. 2018), we call the chart relating runtime and energy a constellation. e constellation in Figure 4(c)

  function is still multi-threaded void syncFreeTask(Stream<Value> s, long keySize, Map<BigInteger, Value> privateMap) { while (!s.empty()) { // Get a key of the proper size: BigInteger key = getNextKey(keySize); // Use key to update the map (private per thread) Value value = s.next(); privateMap.put(key, value)

Fig. 4 .

 4 Fig. 4. (a) The energy measurement apparatus adopted in this paper. (b) Power charts for configuration 4b4L with synchronization-free inputs (top) and synchronization-heavy inputs (bo om). (c) Time vs energy constellation for the synchronization-free input set. (d) The constellation for the synchronization-heavy input set. Big cores run at 2.0GHz and LITTLE cores run at 1.5GHz. (Taken from da Silva et al. (2020))

  e matrix A of independent variables. As Example 3.1 illustrates, the matrix A encodes known values of function arguments. ese values are called the training set of our regression. If we are analyzing a function with n arguments, and our training set contains m function calls, then A is a matrix with m rows and n + 1 columns. e extra column is the all-ones vector 1 m , which represents intercepts -constants that allow us to handle a scenario in which the training set contains only null values. is all-ones column is the rst column of matrix A in Figure 6. Example 3.2.Figure 7 shows how ten di erent samples of function T , from Fig. 1, are organized into a matrix A of independent variables. e matrix C of dependent variables. C represents the ideal hardware con guration for each input in the training set. If we admit k valid con gurations, and our training set has m samples, then C is an m × k matrix. Each line of C is a unitary vector e i , which has all the components set to void task(Stream<Value> s, long keySize) { Bundle b

Fig. 5 .

 5 Fig. 5. The execution pipeline of J C, as shown in our previous work (da Silva et al. 2020).

Fig. 6 .

 6 Fig.6. Formula to train a 3-ary function f (α 0 , α 1 , α 2 ). The goal of multivariate linear regression is to find the coe icients Θ that approximate the product C = σ (AΘ). Training set contains four samples.

Fig. 7 .

 7 Fig. 7. Training set for the T method (Fig. 1). The table on the right is matrix A of independent variables (taken from da Silva et al. (2020)).

Fig. 8 .

 8 Fig. 8. Matrix of independent variables built for ten di erent invocations of function T in Figure 1 (taken from da Silva et al. (2020)).

Fig. 9 .

 9 Fig. 9. The result of multivariate linear regression produced by the training set seen in Examples 3.2 and 3.3 (taken from da Silva et al. (2020)).

  r e a d s s.s iz e( )

Fig. 10 .

 10 Fig. 10. The matrix Θ (see Figure 9) used to predict ideal configurations for unseen inputs. Light-grey points form the training set. Inputs in the test set are dark-grey. (taken from da Silva et al. (2020))

Fig. 11 .

 11 Fig. 11. Instrumented version of two programs. Grey code is from the original method. (Le ) Breadth-first search. (Right) Sorting application. (taken from da Silva et al. (2020))

Fig. 12 .

 12 Fig. 12. Training output produced by the driver on a few inputs seen in Figure7. Y-axis is runtime.

  Fig. 13. The production version of function T , first seen in Figure 1.

  [START_REF] Krishna | CHOAMP: Cost Based Hardware Optimization for Asymmetric Multicore Processors[END_REF], were not reused in our implementation, due to a lack of correspondents. Training and Tuning Following Sreelatha et al., we have trained the probabilistic model of CHOAMP by running it on a set of generic micro-benchmarks. As the original training set was wri en in C and OpenMP, we had to create a new training set that suits Java. e micro-benchmarks we used were directly based on the scripts made public by Sreelatha et al. ese scripts generate hundreds of micro-benchmarks.

Fig. 14 .

 14 Fig. 14. Execution time of benchmarks from Table 1. Y -axis shows time in seconds. X -axis shows di erent experiments; each experiment uses di erent inputs. Boxplots are ordered by J C, CHOAMP and GTS.

Fig. 17 .

 17 Fig. 17. Best configurations for 4 benchmarks used in our evaluation. The charts exemplify the convex space over benchmarks inputs. HashSync and FutureGenetic receive 3 inputs each, but for this experiment we fixed the number of workers in HashSync to 16 and the number of generations in FutureGenetic to 5000.

  Fig. 19. (a) An ideal representation of the space of best hardware configurations, with three convex sets. (b) Approximation of this space a er training with three inputs covering two convex sets. (c) Approximation of this space a er training with inputs that cover all the convex sets. White regions are misclassified zones.

  ) and (c) illustrates. For a concrete discussion about the impact of training inputs on the quality of the classi cation model, we refer the reader to Example 4.2 (Page 19).

  [START_REF] Fisher | e Correlation Between Relatives on the Supposition of Mendelian Inheritance[END_REF]

	0b1L	1b0L	1b1L	2b0L	2b1L	function arguments 1 01 02 03 1 11 12 13 1 21 22 23 1 31 32 33	training inputs	×

= Best(f( 01 , 02 , 03 )): 1b0L Best(f( 11 , 12 , 13 )): 0b1L Best(f( 21 , 22 , 23 )): 2b1L Best(f( 31 , 32 , 33 )): 2b1L C A ϴ

Table 2 .

 2 Prime features and their correspondent Java VM implementation.

	Prime Feature Lang.Dep.	OpenMP	Java VM
	Branch operations	No	-	-
	Memory operations	No	-	-
	Atomic operations	Yes	omp atomic	atomic
	Barriers	Yes	omp barrier CyclicBarrier, Phaser
	Critical Sections	Yes	omp critical	Synchronized
	False Sharing	No	-	-
	Flush operations	Yes	omp ush	not used

Table 4 .

 4 • Training: when does learning occur? O -line (o ) systems calibrate prediction before the target program runs; on-line (on) systems do it while the program executes. • Data: what is the source of training data? OS-based o -line systems usually rely on microbenchmarks (µ-benchs) to perform calibration. CHOAMP uses features of the program, which it extracts from its syntax. Techniques used in servers can rely on the target program itself as the source of training data, for said program is bound to run for a long time. • Target: in which scenario is the technique meant to be used? Most of the papers that deal with I (De nition 2.3), ours included, present solutions for embedded devices and smartphones (clients). S , S C, O M and H guarantee QoS in servers. • Level: the di erent adaptive techniques that we list in Table 4 either run on the operating system (OS), or are implemented at the compiler's level (CP). Recent solutions to I . Granularity (Gran.) uses R for runtime, S for syntax and I for input. Training (Tr.) uses on for on-line and o for o -line. Level uses OS for operating system and CP for compiler. Two systems that solve I (De nition 2.3) in big.LITTLE architectures at the compiler level are Sreelatha et al. (Sreelatha et al. 2018)'s CHOAMP, and Krishna et al. (Krishna and Nasre 2018)'s SIAM.

			Approach Gran.	Tr.	Data	Target Level
	O M (Petrucci et al. 2015)	R	on	self	server	OS
			S C (Azhar et al. 2019)	R	on	self	server.	OS
		S	(Azhar et al. 2017) R/S	on	self	server OS/CP
	S	(Donyanavard et al. 2016)	R	o	µ-bench	client	OS
		D PO (Gupta et al. 2017)	R	o	µ-bench	client	OS
	Tzilis et al (Tzilis et al. 2019)	R	o -line	µ-bench	client	OS
	H		(Nishtala et al. 2017)	R	o /on µ-bench+self server	OS
	CHOAMP (Sreelatha et al. 2018)	S	o	µ-bench	client	CP
	SIAM (Krishna and Nasre 2018) S+I	o	self	client	CP
			J	C	I	o	self	client	CP

ACM Transactions on Embedded Computing Systems, Vol. 1, No. 1, Article 1. Publication date: January 2021.

We are using only two decimal digits; hence, rounding errors prevent us from obtaining 1.00 in every line.ACM Transactions on Embedded Computing Systems, Vol. 1, No. 1, Article 1. Publication date: January

We say "idealized" because, in practice, we would not be able to determine the best hardware con gurations for every input set, due to imprecisions in the measurement apparatus. Imprecisions are especially present when considering small inputs, which tend to cause short running times.ACM Transactions on Embedded Computing Systems, Vol. 1, No. 1, Article 1. Publication date: January 2021.

ACKNOWLEDGMENTS

is work has been made possible by the support of the following agencies: ANR (the CONTINUUM project: grant ANR-15-CE25-0007-01); CNPq (Grants PDE-202896/2017-0 and 406377/2018-9); FAPEMIG (Grant PPM-00333-18) and CAPES (Edital CAPES P I ). While working on this project, Junio Cezar was the recipient of a scholarship generously donated by Google LLC (Research Awards for Latin America-LARA).

reporting the results in this paper, we have opted to let the hardware con guration uctuate during warm-up, as this is the expected behavior of J C, once it is deployed in production.

RQ4: Convexity

A convex space is a region within a Euclidean Space whose intersection with any line results in a continuous line segment. If the convex space can be described by a function, then said function is also called convex. Convex functions are very important in classi cation problems. Firstly, because exploration methods based on derivatives, like gradient descent, converge to the optimal solution when applied on them [START_REF] Boyd | Convex Optimization[END_REF]. Secondly, as we discuss in Section 4.4.2, disjoint convex sets are linearly separable. us, linear techniques, like the one employed in this paper, tend to yield good results when used to classify such sets.

In our se ing, the search space is a function that maps program inputs to hardware con gurations. is function is discrete, because its image is a nite set of hardware con gurations. As a consequence of convexity, if we x all the program inputs and vary one of them, then every once we cross the boundary between r and a third region r . Notice that convexity is a tendency, not a principle: it is possible to implement programs whose space of optimal con gurations is not convex, as Example 4.4 demonstrates. Example 4.4. e space formed by ideal hardware con gurations associated with i in unlikely, below, is non-convex:

e unlikely routine receives one input, namely, the integer i. If i is less than 10 or greater than 100, it invokes a computationally intensive procedure; otherwise, it invokes a synchronization intensive one. e optimal con gurations for these two pieces of code di er. e space occupied by the optimal hardware con guration for comp intensive, i.e., [-∞, 10[∪], 100, +∞], is noncontinuous; hence, concave.

Space

Exploration. e program discussed in Example 4.4 is unlikely to exist in the realworld. To support this statement, Figure 17 provides a glimpse of the best hardware con gurations for di erent inputs of four benchmarks in our collection. Each matrix in Figure 17 associates a pair of inputs with the hardware con gurations that yielded the shortest execution times for those inputs. In this experiment, we chose the two benchmarks from our collection that contain two inputs. We have augmented this set with S and G , to t the gure into a 2 × 2 matrix (for aesthetic reasons). However, to avoid having to draw a 3D-gure, we have xed one input each benchmark: number of Generations for G , and number of workers, for S . e computational time involved in the production of each gure follows: S : 1 hour and 37 minutes; P : 2 hours and 24 minutes; G : 55 hours and 53 minutes; and S : 58 hours and 12 minutes. e four tables in Figure 17 show convex spaces: any sequence of rows or columns traverses a continuous region, as Example 4.5 illustrates:

Example 4.5. Consider S in Figure 17(c). If we x the value for keySize in 10 6 , and vary s.size() in the set {10, 10 2 , 10 3 , 10 4 , 10 5 }, we observe that each one of the continuous intervals [10, 10], [10 2 , 10 2 ] and [10 3 , 10 5 ] is governed by the same set of optimal hardware con gurations.

Dealing with variance: To arrive at this result, we had to account for small time variations. To generate the data in every table seen in Figure 17, we considered 5 × 5 combinations of inputs, and the hardware con gurations used in the previous sections. We run each pair of inputs with every con guration of interest 20 times. To reduce variance, we removed the four fastest and the four slowest samples; hence, considering 12 executions per input per con guration. Nevertheless, this expedient only would not be enough to mitigate the problem of high variance, mostly when considering input se ings with small runtimes.

To mitigate variance for small inputs, we consider not the best, but the set of best hardware con gurations per input. For each input, we ed our linear regression model using the least squares method to estimate the model parameters. We analyze the di erences among group means with standard analysis of variance (ANOVA) [START_REF] Fisher | e Correlation Between Relatives on the Supposition of Mendelian Inheritance[END_REF]; hence, generalizing the T-test beyond two means. In the context of this work, we consider groups of hardware con guration; and the null hypothesis states that samples from di erent hardware con gurations came from the same probability distribution. us, the null hypothesis means that there is no statistical di erence between the execution time of di erent hardware con gurations. We checked if the data were statistically signi cant considering a con dence of 95%, i.e., a P-value less than 0.05. ANOVA is • Source: is the program's code modi ed?

• Input: is the approach input-aware?

• Auto: is user intervention required to choose con guration?

• Runtime: is runtime information exploited?

• Learn: is there any adaptation to runtime conditions? Perhaps the most important di erence among the several strategies proposed to nd ideal hardware con gurations concerns the moment at which said strategy is used. In the rest of this section, we consider the following three possible choices: at compilation time, at runtime, or both. Static Solutions. Purely static approaches work at compilation time. ey might be applied by the compiler, either automatically, i.e., without user intervention [START_REF] Cong | Energy-e cient Scheduling on Heterogeneous Multi-core Architectures[END_REF][START_REF] Jain | Continuous shape shi ing: 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] Krishna | CHOAMP: Cost Based Hardware Optimization for Asymmetric Multicore Processors[END_REF][START_REF] Tang | ReQoS: Reactive Static/Dynamic Compilation for QoS in Warehouse Scale Computers[END_REF], or not. In the la er case, users can use annotations (Mendonc ¸a et al. 2017), domain speci c 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 Uni ed Platform for Task Scheduling on Heterogeneous Multicore Architectures[END_REF] to indicate where each program part should run. e main bene t of static techniques is low runtime overhead: because every scheduling decision is taken before the program runs, no dynamic checks are necessary to schedule computations. However, these techniques tend to be in exible: they are unable to take runtime information into consideration; hence, the same program phase is always scheduled in the same way. In Table 3, techniques implemented at either the compiler or library levels are purely static. Dynamic Solutions. Purely dynamic approaches take into account runtime information. ey can be implemented at the architecture level [START_REF] Joao | Bo leneck Identi cation and Scheduling in Multithreaded Applications[END_REF][START_REF] Lukefahr | Exploring Fine-Grained Heterogeneity with Composite Cores[END_REF][START_REF] Rangan | read Motion: Fine-grained Power Management for Multi-core Systems[END_REF]Van Craeynest et al. 2012a;[START_REF] Yazdanbakhsh | Neural acceleration for GPU throughput processors[END_REF], or at the virtual 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 | Energy-E cient read Assignment Optimization for Heterogeneous Multicore Systems[END_REF][START_REF] Annirmalai Somu Muthukaruppan | Price eory Based Power Management for Heterogeneous Multi-cores[END_REF]