{'fraction_non_alphanumeric': 0.026367689933116105, 'fraction_numerical': 0.011726119019036186, 'mean_word_length': 5.068557304540133, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ALEA: Fine-grain Energy Profiling with Basic Block Sampling

Energy efficiency is an essential requirement for all contemporary computing systems. We thus need tools to measure the energy consumption of computing systems and to understand how workloads affect it. Significant recent research effort has targeted direct power measurements on production computing systems using on-board sensors or external instruments. These direct methods have in turn guided studies of software techniques to reduce energy consumption via workload allocation and scaling. Unfortunately, direct energy measurements are hampered by the low power sampling frequency of power sensors. The coarse granularity of power sensing limits our understanding of how power is allocated in systems and our ability to optimize energy efficiency via workload allocation. We present ALEA, a tool to measure power and energy consumption at the granularity of basic blocks, using a probabilistic approach. ALEA provides fine-grained energy profiling via statistical sampling, which overcomes the limitations of power sensing instruments. Compared to state-of-the-art energy measurement tools, ALEA provides finer granularity without sacrificing accuracy. ALEA achieves low overhead energy measurements with mean error rates between 1.4% and 3.5% in 14 sequential and parallel benchmarks tested on both Intel and ARM platforms. The sampling method caps execution time overhead at approximately 1%. ALEA is thus suitable for online energy monitoring and optimization. Finally, ALEA is a user-space tool with a portable, machine-independent sampling method. We demonstrate two use cases of ALEA, where we reduce the energy consumption of a k-means computational kernel by 37% and an ocean modelling code by 33%, compared to high-performance execution baselines, by varying the power optimization strategy between basic blocks.


Introduction
Association of energy use with specific software abstractions and components enables the energy-efficient use of computing systems. Numerous energy profiling tools target platforms ranging from sensors, to smartphones, embedded systems, and high-end computing systems. These tools guide softwarecontrolled energy optimization techniques such as dynamic voltage and frequency scaling, thread packing, and concurrency throttling. Emerging algorithmic energy models and metrics [1,2] for high-level computation and communication abstractions make accurate energy accounting between software abstractions even more pressing.
Prior energy accounting tools can be broadly classified into two categories: Tools that measure energy by taking direct power measurements using on-board sensors or external instruments [3,4,5,6,7,8]; and tools that model energy based on activity vectors derived from hardware performance counters, kernel event counters, finite state machines, or instruction counters in microbenchmarks [9,10,11,12,13,14,15,16,17,18,19]. All of these tools can associate energy measurements with software contexts via manual instrumentation, context tracing, or profiling.
Energy accounting tools based on direct power measurement can accurately measure both componentlevel and system-wide energy consumption, before and after the system's power supply units. However, the time granularity of the sensors fundamentally limits these tools. State-of-the-art external instruments such as the Monsoon power meter have sampling rates of at most 5 kHz [20]. Some direct energy measurement and profiling tools use instruments with sampling rates as low as 1 Hz [5,4]. Internal energy and power sensors such as Intel's RAPL [21] or the sensors commonly found on ARM-based boards [22] have sampling frequencies between 1 and 3 kHz. The coarse granularity of direct power measurements limits their ability to account for the energy consumption of specific instructions or many software components as basic blocks and most function instances, which typically execute for periods far shorter than the instrument sampling period.
Tools that model energy consumption from activity vectors can break the granularity barrier of direct energy measurements but suffer from several other shortcomings. Their accuracy may be limited and highly dependent on architectural variations between platforms and workload patterns [13,11,12,18,19]. The tools require extensive training and benchmarking processes that must be repeated per platform and workload, to calibrate platform parameters.
This paper presents a new method that directly measures power consumption in computing systems and accounts for energy consumption of fine-grain code blocks, including basic blocks with execution duration shorter than the minimum power consumption sampling period. We use the term coarse-grain for basic blocks of longer duration. Our energy accounting tool combines the accuracy of direct power measurements with the fine granularity of energy accounting between basic blocks. Our Abstraction-Level Energy Accounting (ALEA) tool uses the systematic sampling of physical power measurements and a probabilistic model to distribute energy between basic blocks of any granularity, while capturing the dynamic execution context of these blocks. ALEA achieves portability through a machine-independent sampling method that abstracts the details of the underlying architecture and power measurement instruments. We demonstrate its accuracy, efficiency and portability on two multicore platforms based on the Xeon Sandy Bridge and Samsung Exynos processors. We validate ALEA with 14 sequential and parallel applications. ALEA's mean error for coarse-grain basic blocks, as well as for the whole program, is 1.4% on the Sandy Bridge server and 1.9% on the Exynos SoC. ALEA's mean error for fine-grain basic blocks is 1.6% on the Sandy Bridge server and 3.5% on the Exynos SoC. We use ALEA to demonstrate the correlation between power consumption and cache accesses at the basic block level across our benchmark suite. Finally, we demonstrate two use cases of ALEA, where we reduce the energy consumption of a k-means computational kernel by 37% and an ocean modeling code by 33%, compared to high-performance execution baselines, by varying the power optimization strategy between basic blocks.
The rest of this paper is structured as follows. Section 2 presents related work. Section 3 describes our platforms and their direct energy measurement sensors. Section 4 details our energy sampling and profiling models and the key aspects of their implementation. Section 5 validates ALEA's mechanisms for our fourteen benchmarks. Section 6 demonstrates memory instruction experiments. Section 7 presents use cases of ALEA for fine-grain energy optimization in parallel codes. Section 8 summarizes our findings.

Related Work
Statistical sampling of the execution context of a running program is an established method for performance profiling [23,24,25,26]. Sampling is also a state-of-the-art method for profiling large-scale data centers [27]. ALEA is the first tool to deploy basic block sampling and power sampling for fine-grain energy profiling based on a probabilistic approach.
Several tools for energy profiling use manual instrumentation to collect samples of hardware event rates from hardware performance monitors (HPMs) [13,9,12,28,11]. These tools empirically model power consumption as a function of one or more activity rates. These rates attempt to capture the utilization and dynamic power consumption of specific hardware components. HPM-based tools and their models have guided several power-aware optimizations. However, they often estimate power with low accuracy. Further, they rely on architecture-specific training and calibration.
PowerScope [4,29], an early energy profiling mechanism, profiles mobile systems through direct hardware instrumentation. It samples power consumption, which it attributes to processes and procedures through post-processing. In contrast, ALEA profiles at a finer granularity (basic blocks instead of functions).
Eprof [19,18] models hardware components as finite state machines with discrete power states and emulates their transitions to attribute energy use to system call executions. JouleUnit [17] correlates workload profiles with external power measurement to derive energy profiles across method calls. JouleMeter [6] uses post-execution event tracing to map measured energy consumption to threads or processes. These tools perform energy accounting at the granularity of functions or system calls, a limitation that ALEA overcomes. Fine-grained energy profiling enables more compile and run time opportunities for power-aware code optimization.
PowerPack [5] uses manual code instrumentation and platform-specific hardware instrumentation for component-level power measurement to associate power samples with functions. NITOS [7] measures energy consumption of mobile device components with a custom instrumentation device. Similarly, LEAP [8] measures energy consumption of code running on networked sensors with custom instrumentation hardware. These tools profile power at the hardware component level, thus capturing the contributions of non-CPU components, such as memories, interconnects, storage and networking devices. ALEA is complementary to these efforts. ALEA's sampling method can account for energy consumed by any hardware component between basic blocks, while the statistical approach followed in ALEA overcomes the limitations of coarse and variable power sampling frequency in system components.
Other energy profiling tools use build instruction-level power models bottom-up from gate-level models, or models extracted at design time to provide power profiles to simulators and hardware prototyping environments [16,15]. These inherently static models fail to capture the variability in instructionlevel power consumption due to the context in which instructions execute in real programs. Similarly, using microbenchmarks [14] to estimate the energy per instruction (EPI) or per code blocks based on their instruction mix does not capture the impact of the execution context.

Platforms and Energy Measurement
The ALEA energy profiler builds on platform-specific substrates to measure or model power. ALEA operates under the sampling rate constraints of the underlying power or energy sensors. In this paper we use two distinct platforms for power measurement, one based on Intel's Running Average Power Limit (RAPL) apparatus on a Xeon Sandy Bridge server and a second based on integrated power sensors on an ARM Exynos board.
On the Sandy Bridge server, we directly measure energy consumption through on-chip energy counters, which we access through the RAPL interface [21]. RAPL allows us to account for the energy consumption of the following four components: PKG, which measures the energy consumed by the processor package, including the multicore processor; PP0, which measures the energy consumed by the power plane that powers the cores and the on-chip caches (L1/L2/L3); PP1, which measures the energy consumed by the on-chip graphics processor (for client platforms); and DRAM, which measures the energy consumed by memory DIMMs. Client platforms can only access the PKG, PP0 and PP1 counters, while server platforms can access the PKG, PP0 and DRAM counters. Our Sandy Bridge server includes two Intel Xeon E5-2650 processors with eight cores per processor, 32KB/32KB I/D-Cache per core, 2MB shared L2 cache per 8 cores, and 20MB shared L3 cache per package. The system runs CentOS (release 6.5). The frequency of the system is up to 2 GHz. We disable Turbo Boost and Hyperthreading in our experiments.
Our other platform, an ODROID-XU+E board [30], has a single Exynos 5 Octa processor. The processor's ARM Big.LITTLE architecture has four Cortex-A15 cores and four Cortex-A7 cores, 32KB/32KB I/D-Cache per core, NEONv2 floating point support per core, VFPv4 support per core, one PowerVR SGX 544 MP3 GPU, and 2 GBytes of LPDDR3 DRAM. A 2 MByte L2 cache is shared between all Cortex-A15 cores and a 512 KByte L2 cache is shared between all Cortex-A7 cores. The ODROID board also includes power meters on each voltage plane to measure consumption for the following four sets of components: Cortex-A7 cores, including their shared L2 cache; Cortex-A15 cores, including their shared L2 cache; GPU; and DRAM. The system runs Ubuntu 14.04 LTS. In our experiments, we use the Cortex-A15 cores only at their maximum frequency of 1.6 GHz.

Profiling
Execution time profiling can use sampling or instrumentation [24,27]. Compiler or binary instrumentation inserts profiling instructions that track dynamic execution counts and the execution time of code paths, as well as software and hardware-provided events. Sampling-based profilers suspend binary execution to sample the execution state (the current program counter and possibly register contents or a stack traceback) and to correlate the sample with software or hardware events or metrics.
We use statistical sampling for fine-grained energy profiling and demonstrate that we can probabilistically estimate energy consumption at fine and coarse granularities. Our profiling approach simultaneously samples the currently executing basic block and takes power measurements, which it assigns to the basic block ( Figure 1). We perform a one-pass sampling of power measurements during a single program execution. Our tool processes the profiling results off-line, using a probabilistic model to estimate the execution times and the mean power consumption for each basic block.

Execution time profiling model
ALEA estimates execution time and energy consumption of basic blocks with a probabilistic model. It repeatedly samples the execution at a predefined rate and extracts the basic block that encloses the program counter at each sample. To motivate the model, Figure 2 shows the iterative execution of a basic block that is executed k times. The model makes the simplifying assumption that the processor executes instructions from one basic block (bbm) in each clock cycle. The latency of each basic block (latency j bbm ) may vary between iterations. For example, a basic block may execute the same load instruction with different latencies between iterations, depending on the level of the memory hierarchy that provides the requested data.
If we sample the program counter once during the execution of a program at a random clock cycle, we define the random variable X bbm as: In our probabilistic model, CPU clock cycles (ticks) correspond to the units of the finite population (U ) and an implementation of the random variable X bbm during a clock cycle is a characteristic associated with this clock cycle [31]. Then, the probability that bbm is sampled is: where t bbm is the total execution time of instances of bbm, t exec is the total execution time of the program, and C 1 S is a 1-combination of a set S. We measure time in ticks and represent it in seconds by dividing it by the CPU frequency. Equation 2 captures the observation that the probability of sampling a basic block at a random clock cycle is equal to the ratio of its execution time to the program's total execution time. If the probability p bbm and the total execution time are known then the execution time of bbm (t bbm ) is: We assume that X bbm follows a Bernoulli distribution because it is binary, random, and p bbm is a constant in our model. By applying random sampling (see Figure 3), we can estimate the probability as the maximum likelihood estimator of parameter p bbm in the Bernoulli distribution for X bbm = 1 [32,33]: In Equation 4, n bbm is the number of samples of some instruction from bbm, and n is the total number of samples.
Thus, we estimate the execution time of any basic block as:

Energy profiling model
We apply the same probabilistic approach to profile power and energy. Similar to the execution time profiling model, we consider power consumption as a random variable (pow, Figure 3) and an implementation of this variable at a clock cycle as a characteristic associated with this clock cycle. We simultaneously take samples of the program counter and power consumption, which we assign to the sampled basic block even though that power consumption likely includes power that instructions outside that basic block consume.
Assuming n bbm samples of block bbm, we estimate its mean power consumption as [33]: In Equation 6, pow i bbm is the power consumption associated with the i − th sample of block bbm. We estimate the energy consumption of bbm as: e bbm =pow bbm ·t bbm (7)

Bounds and Confidence
If p bbm is not too close to 0 or 1 and n is relatively large (np bbm > 5, n(1 − p bbm ) > 5) [33], then we can construct the confidence interval with upper and lower bounds on p bbm : In Equations 8 9, 10, z α is the 1 − α/2 percentile of the standard normal distribution, and 1 − α is a confidence level. The interval in Equation 10 includes the true value of p with probability 1 − α. According to Equation 5, by multiplying the lower and upper bounds of p with the total execution time t exec , we obtain an interval in which the true execution time t bbm of bbm lies: We can similarly build a confidence interval for power [33]: pow l bbm ≤ pow bbm ≤pow u bbm (15) where s is the corrected sample standard deviation. Using confidence intervals for execution time and power, we can derive a confidence interval for energy consumption: If we increase the total number of samples, then the length of the confidence intervals is reduced as it is inversely proportional to the square root of the number of samples (time:∼ const √ n ,power:∼ const √ n bbm ). Thus, the accuracy of the energy estimates should increase with increasing total number of samples (n) and the given basic block samples (n bbm ). Because n bbm is strongly correlated with n, the accuracy of the energy estimates is primarily affected by the total number of samples (n).

Profiling of parallel applications
We employ the same execution time and energy profiling models for multithreaded applications, with the essential difference being that each sample is a vector of program counters simultaneously sampled across all executing threads. Thus, we distribute the execution time and energy across combinations of basic blocks, which are executed on different threads: where comb corresponds to a combination of basic blocks that were sampled on different threads (l threads). We consider all threads of an application running on the same processor package collectively during sampling, because they share resources and because resource sharing contributes additional energy consumption due to contention between threads. Shared resources include caches, buses and network links, all of which can significantly increase power consumption under contention. We could apportion power between threads based on dynamic activity vectors that measure the occupancy of shared hardware resources per thread [10]. However, these vectors are difficult to collect on real hardware, as current hardware monitoring infrastructures cannot distinguish between the activity of different threads on shared resources. As such, per-thread energy apportioning cannot be accurately validated on real hardware.
We can still correlate power consumption with basic blocks with this approach. For example, we can investigate how the energy profile of a basic block changes between stand-alone execution and execution with different co-runners, to capture contention for shared resources. Further, our methodology helps us understand how synchronization can decrease power consumption, which in turn reveals opportunities for reducing energy consumption in the runtime system by applying dynamic concurrency throttling [28].

Power measurements
We measure processor power consumption on our Sandy Bridge server for a given sample (pow i bbm ) by dividing the energy consumed since the last sample by the length of the sampling period. We used a 10 ms sampling period following rigorous analysis of sampling overhead and accuracy, which we present in the following sections. This approach conforms to RAPL, which provides running energy but not power measurements.
Our Exynos platform includes TI INA231 power meters [34], which directly sample power consumption for the System-On-Chip averaged over a user-defined period. We used the minimum feasible period on the Exynos, which is 280 microseconds.
Our sampling method estimates the energy consumption of basic blocks of any duration, including ones that run for less than the sampling period, under a probabilistic model of the fraction of program execution time that each given basic block consumes and the average power consumption due to execution of that basic block.

Implications of systematic sampling
Systematic sampling, which approximates random sampling, selects units from an ordered population with the same sampling period. It selects the first unit of a sample randomly from the bounded interval [1, length of sampling period]. We use systematic sampling for time and energy profiling, in which units correspond to CPU clock cycles and the user sets the sampling period [31].
Systematic sampling tends to be inefficient with populations that exhibit a periodic variation and the period of the variation is an integral multiple of the sampling period. For example, if the same basic block is executed with a period equal to the sampling period then theoretically, we will only sample that basic block. In practice, the precise size of a sampling period in CPU clock cycles varies randomly between samples due to the inaccuracy of the timer and variance in the execution length of the sampling code itself. We find that on the Sandy Bridge and Exynos platforms, the variation in the delay between samples may be up to hundreds of microseconds. This random variation obviates the need to add deliberate randomization during the sampling process.

Sampling period
The accuracy of our sampling estimates theoretically improves with an increasing number of samples. However, sampling incurs overhead, which biases execution time and energy estimates. This overhead increases linearly or superlinearly with the number of samples, since the program must be interrupted for each sample. Thus, the estimation error is composed of random error, which is introduced by sampling, and systematic error, which is introduced by profiling overhead. If we increase the number of samples, then the random error decreases but the systematic error increases.
We use our benchmark suite to capture basic blocks with diverse execution times and power consumption to find the best sampling period in terms of energy estimation accuracy and execution time overhead. As an example, the streamcluster benchmark from the Rodinia suite includes basic blocks with latency varying between 1 and 30 ms on the Sandy Bridge platform. Figures 4 and 5 show the trade off between the length of the sampling period, overhead and accuracy of energy estimates for the Sandy Bridge and Exynos platforms, using both sequential and parallel executions of the benchmark. We observe similar results in all benchmarks, pointing to a sampling period of 10 ms as a good compromise between energy estimation error and runtime overhead. Selecting a fixed sampling period helps deployment of ALEA as a continuous, online application energy profiler with capped overhead. However, we note that selecting an application-specific sampling frequency is also feasible and indeed exposing the sampling interval as a user-defined parameter is a feature of the tool.

Implementation
ALEA uses a separate control process to obtain the current instruction pointer of the profiled application and to take power measurements. We use the ptrace interface, which allows one process to retrieve the contents of registers in another process or thread. Thus, the profiled program does not execute any additional code, unlike sampling schemes based on signals [23]. Instead, the control process captures context information and energy/power measurements. This approach reduces system overhead because system call interfaces are offloaded from the profiled program's critical path to the control process. However, this approach still incurs performance and energy overhead because processes or threads of the profiled program are suspended while the control process reads the registers via the ptrace interface. ALEA currently executes on a dedicated core that is not used by the profiled application.

Validation
We use 14 benchmarks (sequential and parallel) from four different suites (SPEC 2000, Parsec, Rodinia, SPEC OMP) to validate the accuracy of ALEA's execution time and energy consumption estimates. We use a wide range of benchmark suites to provide good coverage of basic block features in terms of execution time, including fine-grain and coarse-grain blocks, and energy consumption, including blocks with distinct power profiles and/or power variations between their samples. We use native input data for benchmarks from PARSEC and standard input for benchmarks from other suites.
We measure whole program execution time and energy. We also measure the execution time and energy of those basic blocks with latency that exceeds the sampling period (10 ms) in isolation. Further, in isolation, we measure the execution time and energy of fine-grain basic blocks that have shorter latency than the sampling period, but that are enclosed in innermost loops such that the overall loop latency exceeds this period. Overall, direct per-basic block measurements cover 81% of the execution time of each benchmark on average. We compare ALEA's execution time and energy consumption estimates to these per-basic block direct measurements. For basic blocks that are not captured by direct measurements, we compare whole program measurements to the sum of execution time and energy consumption estimates for all basic block sampled by ALEA at least once during program execution.
We execute each benchmark at least six times. The first run directly measures energy and time. The next five or more runs use ALEA to estimate the execution time and energy consumption of each basic block. We use at least five runs and as many more as needed (we needed up to 20 runs) to keep the 95% confidence interval of the time, power and energy measurements within 5% of the mean. We compile all benchmarks using gcc with -O1 and -ffast-math, which inlines mathematical and other functions when possible. For validation, we use the -O1 optimization level instead of -O3 to increase latencies of some basic blocks, which should be sufficient to take direct measurements. For example, the energy counter on the Sandy Bridge platform is updated only once per 1 ms.
The ALEA profiler executes on a core that is not in use by the profiled application, to minimize interference. Specifically, ALEA runs on a separate Sandy Bridge socket but on the same Exynos fourcore Cortex A15 cluster since our Odroid board does not allow co-execution on both of the A15 and A7 clusters. A more recent release of the board will allow us to run the profiler on a separate four-core cluster of the ARM Big.LITTLE processor. We present results from experiments using up to eight threads on one socket of the Sandy Bridge platform and up to two threads of the A15 cluster on the Exynos platform for the execution of parallel benchmarks. Running the profiler on a separate core keeps the overhead under 1% on both platforms. We also experimented with running the profiler on the same core as one of the threads of each profiled program and observed the overhead to increase to up to 10% (not shown). This overhead can be mitigated by reducing the sampling frequency (Figure 4, 5). Halving the sampling frequency halves the overhead and keeps the ALEA average energy estimation error at a manageable 5% (Exynos) to 6% (Sandy Bridge). Figure 6 presents the average error of ALEA's execution time and energy consumption estimates for basic blocks in each benchmark on the Sandy Bridge platform. The average error is 1.3% for the execution time estimates and 1.4% for the energy consumption estimates. 99% of the execution time and energy measurements lie within 95% confidence intervals. For those fine-grain basic block sets enclosed in loops that allow us to measure time and energy directly, the average error in ALEA's energy estimate is 1.6% (1.3% for execution time). For coarse-grain basic blocks, the ALEA profiling error is 1.4% for both execution time and energy consumption. The average errors of the ALEA execution time and energy estimates for parallel benchmarks ( Figure 6) are 3.1% and 2.6%. Our average whole program absolute error across all benchmarks is 1.1% for execution time and 1.4% for energy.

Exynos results
While RAPL allows us to take direct energy measurements on the Sandy Bridge platform, we can only directly measure power on the Exynos platform. We thus follow a different approach to validate energy profiling between basic blocks on it. We again instrument the benchmarks to perform execution time profiling. However, in each instrumented basic block, we sample the power consumption using the system timer and corresponding signal handler. We set the Exynos TI power meters to compute average power over the minimum feasible period of 280 microseconds. This instrumentation has higher overhead than direct energy measurements on the Sandy Bridge platform due to the interrupt per sample. This higher overhead introduce a bias in energy measurements, which leads to higher estimates of ALEA's average error for energy estimates. Thus, these results provide upper bounds on ALEA's error.
The average error in ALEA's energy estimates (not shown due to space limitations) is 2.6% (also 2.6% in execution time estimates) for sequential benchmarks and 3.6% (2.8% in execution time estimates) for parallel benchmarks. 99% of all time and energy measurements again lie within 95% confidence intervals. The average error in ALEA's energy estimate for fine-grain basic blocks is 3.5% (3.7% for execution time) and 1.9% (1.8% for execution time) for coarse-grain basic blocks. The average error across the benchmarks of the total execution time estimates is 1.4% while that of the total energy estimates is 1.9%.

Sequential benchmarks
We can optimize a program's energy consumption by reducing its execution time or power consumption. However, reducing execution time often increases power consumption significantly. We use ALEA to investigate the causes of increased power consumption in optimized programs. Our experiments indicate that the power consumption may vary considerably between basic blocks. Figure 7 shows a basic block from art (BBA) and a basic block from heartwall (BBB). On the Sandy Bridge platform. BBA consumes 10.10W (98.39J in total), while BBB consumes 8.80W (278.63J in total). Our experimental study shows that the power consumption of a basic block is primarily affected by the cache access intensity and does not vary considerably with the type of executed instructions. In our example, BBA accesses approximately 7 MB of data during its execution (which fits in the L3 cache), while BBB accesses only 36KB of data (which fits in the L1 cache). The Exynos platform exhibits similar behaviour.   To confirm the effect of cache accesses, we develop a series of microbenchmarks based on BBA. We create a basic block with the same set of instructions and context for both processors. We divide its instructions into two groups: memory access instructions and arithmetic/logic instructions. We use these two groups to implement different versions of BBA (Table 1). We then add a basic block with a single nop instruction, which does not use any floating point unit (FPU). On the Exynos platform, we limit the size of the accessed data to 2 MB so that the data fits in the L2 cache. Figure 8 shows the power and execution time measurements for our experimental set of basic blocks on the Sandy Bridge platform. The Nop and NoMem blocks consume almost the same power even though the second block occupies the FPU. In contrast, the difference in power consumption between the Mem and NoMem blocks is more than 1.5W. Similarly to the Sandy Bridge platform, the Nop and NoMem basic blocks show the same power consumption on the Exynos platfrom, while the Mem (L2) block consumes more power than does the NoMem block ( Figure 9). Thus, the increase in power consumption on both platforms is primarily due to data cache accesses and not the type of instructions executed.
Pipelining effect: Even though the NoMem block merely omits the memory access instructions of BBA, these blocks have nearly the same execution time on both platforms because pipelining hides the data access latencies of BBA. Thus, its execution time does not increase despite the energy used for the data accesses.
Pipelining can lead to significant errors in energy consumption estimates based on EPI [14], which ALEA mitigates. For example, BBA is a union of instructions from Mem and NoMem blocks. On the Sandy Bridge, according to an EPI model, BBA, which consumes 1,474J, should consume the sum of the energy consumed by Mem (955J) and NoMem (1,245J) blocks, which is 2,200J or over 1.5× more. On the Exynos platform, the energy consumption of BBA is 1.29× smaller than the sum of that of the NoMem and Mem blocks.

Parallel benchmarks
Our experiments show that the power consumption of basic blocks executed in parallel applications depends on the form of activity in each thread. For example, the ammp (SPEC OMP) benchmark contains a basic block with 564 instructions that correspond to a loop body in the mm fv update nonbon procedure (rectmm.c, line 1210). This basic block includes regular accesses to caches. When four threads execute this block in parallel, the Sandy Bridge processor consumes approximately 19.07 W (1153J). However, if only one thread executes this basic block while the other three threads wait in synchronization, power consumption drops to 13.19W (513J). We observe similar results on the Exynos platform. When two threads execute the same mm fv update nonbon block, the Exynos processor consumes 2.70W (37.70J). If only one thread executes this block while the second waits in synchronization, then the Exynos processor consumes 1.88W (22.50J). Similarly to sequential benchmarks, the difference in power consumption arises because of cache access intensity.
We parallelize our microbenchmarks (Table 1) with OpenMP to explore the impact of concurrency on power consumption further. We observe that power consumption linearly increases with increasing thread count. Compared to the sequential versions, we observe similar trends in power consumption when introducing cache accesses, but we also observe that the relative increase in power consumption due to cache accesses on the Sandy Bridge platform is higher for multithreaded execution (growing from ≈ 25W to ≈45W) compared to sequential execution (growing from ≈8.5W to ≈11W), thereby indicating affects of cache contention.

Use cases
We present two use cases of how basic block level energy profiling can be used in energy-aware program optimization. Our first use case uses hot spot analysis and uncovers opportunities for energy optimizations in a single dominant basic block, based on techniques that adapt the degree of parallelism in the program such as concurrency throttling, thread packing or using sleep states on a subset of cores [35,36,37,38,39]. Our second use case explores fine-grain optimization and power capping opportunities across multiple basic blocks in an HPC application [40], showcasing that the entire space of parameters for dynamic voltage and frequency scaling, concurrency throttling and compiler optimizations must be searched to yield optimally energy-efficient execution.

Hotspot energy optimization
Our first use case uses ALEA to apply hotspot energy optimization to k-means benchmark from the Rodinia suite using one socket on our Sandy Bridge platform. ALEA runs on one core of the other socket. We used the standard input set scaled up six times to model realistic uses of the benchmark, which is an important clustering algorithm that is widely used in search engines, data mining and data analytics. Our analysis of the benchmark's sequential version shows that 56% of the total execution time is spent on the basic block that corresponds to the loop that calculates the multidimensional spatial Euclidean distance square (euclid dist 2 function). We use the -O3 compilation flag as a default option. However unroll and auto-vectorization optimizations are, surprisingly, not applied to the basic block. We use compiler hints (C-extensions: parameter and function attributes) to force the compiler to apply unrolling. We also use parameter attributes to align and restrict pointers so the compiler recognizes the proper context for auto-vectorization. Finally, the -ffast-math -mavx flag enables floating-point arithmetic transformations and the use of AVX-256 instructions. We summarily refer to these optimizations as hints. Table 2 reports execution time, power, energy, energy-delay and energy-delay 2 estimates for the k-means key basic block optimized with -O3 and the same block optimized with -O3 + hints. Additionally, we measure the entire k-means program, also presented in Table 2. Our optimizations reduce execution time of the dominant basic block by up to 8× when running with one or two threads but the  impact of these optimizations on performance is less pronounced with further increases in the number of threads, possibly due to memory contention that limits scalability. The speedup of the full benchmark when running with more cores is limited by the significant percentage of sequential execution time spent on I/O operations (up to 55% after optimizations). The optimization hints that significantly accelerate the dominant basic block actually reduce the speedup from using more cores. The impact on energy consumption is considerably different from that on execution time. Power consumption increases disproportionally when optimizations and additional concurrency are applied to the benchmark. Energy consumption is not minimized with the set of optimizations or the degree of concurrency that minimize execution time. A combination of unrolling, vectorization and maximal concurrency (eight threads) achieve peak performance for the benchmark (18.51 seconds), while energy consumption is minimized with optimizations turned on but using only two cores, at a 20% performance loss. Overall, optimizing the dominant basic block for energy consumption yields 37% energy savings for the entire program, compared to the high-performance execution baseline (eight cores, -O3 + hints).
The kmeans example exhibits clear trade-offs between performance and energy consumption. Optimization criteria that place heavier emphasis on performance (execution time, energy-delay 2 ), when applied to the dominant basic block, indicate preference for the highest concurrency and manual code optimization via hints. Optimization criteria that place heavier emphasis on power and energy opt for lower concurrency. Furthermore, a different optimization strategy needs to be considered for the whole of the program, compared to the strategy followed for the dominant basic block ( Table 2, configurations highlighted in bold). This result motivates fine-grain energy accounting.
We also observe a 4× power gap between different degrees of concurrency and optimization in the dominant basic block, becoming a 2× gap for the entire program. The average power consumption of the critical basic block in k-means is almost twice as high as the average power consumption of the benchmark as a whole, due to the memory access intensity of the optimized basic block, but also due to low-power execution of the sequential part of the benchmark, which is dominated by I/O operations. The results suggest that if k-means executed in a power-constrained environment [41,42], any code  Table 3: Time and energy impact of fine-grain, basic-block level optimization for ocean cp benchmark on Exynos, using a baseline with four threads running at maximum frequency adaptation to meet a power cap should focus on the dominant basic block and use its available range of degrees of concurrency, frequencies and optimizations.

Fine-grain power optimization across basic blocks
We use the ocean cp benchmark from PARSEC suite to explore whether ALEA exposes different energy optimization strategies for different basic blocks in the same code, in order to achieve better wholeprogram energy-efficiency. Such an optimization strategy would motivate ALEA's fine-grain profiling. We use the native input data set and modify the time between relaxations to increase the overall execution time of the benchmark in order to achieve stable and repeatable results. Time profiling of ocean cp indicates that more than 50% of the total execution time is spent executing six basic blocks (Table 3), to which we refer as bb1 through bb6. We initially compile this benchmark for highest performance using the following flags:-O3, -mfpu=neon-vfpv4, -mtune=cortex-a15, -ffast -math, -funroll-loops, -ftree -vectorize,-fprefetch-loop-arrays. Motivated by our experimental analysis of the power implications of memory instructions (Section 6), we disable optimizations that could increase the rate of cache accesses to reduce power. The disabled optimizations are prefetching, for bb3, and the combination of unroll and vectorization, for bb1 and bb2. By disabling these optimizations for the said basic blocks, we reduce power consumption by up to 14% for bb2, 10% for bb1, and 4% for bb3. Further code inspection of bb4,bb5 and bb6 reveals that the compiler inserted additional stack access instructions before each of these basic blocks, due to the predictive commoning optimization, which has no affect on performance, but increases power consumption. By disabling this optimization we reduce power consumption for these three basic blocks by between 3% to 10%. Table 3 shows selected results from an experimental campaign to understand how to minimize the energy consumption of the six dominant basic blocks in ocean cp. The baseline for this campaign is execution of the code using the maximum number of cores on an Exynos cluster (four) and the maximum frequency (1600 MHz). Besides execution time and energy of the baseline case, we show execution time and energy of the energy-optimal configuration, as well as details of the program and system configurations that achieve energy minimization, including clock frequency, number of threads and use or no use of the three manual power optimizations considered: unrolling, vectorization and predictive commoning.
The table reveals several findings that motivate the ALEA approach to fine-grain profiling. First, finegrain energy optimization at the basic block level yields substantial energy savings, ranging from 10% for bb4 to 41% for bb6; and 33% for the program as a whole compared to the baseline. Second, the factor that catalyzes energy minimization varies between basic blocks: most basic blocks are more energy-efficient when running at slightly lower than the maximum frequency (1500 vs. 1600 MHz); most basic blocks run most efficiently with one or two, not all four, cores on the chip, suggesting that system bottlenecks such as memory contention dominate energy consumption; and at least one basic block (bb2) requires manual optimization to achieve maximum energy-efficiency. Third, fine-grain power optimization implies the ability to perform fine-grain power capping and more efficient power-constrained exuection beyond what is afforded by voltage and frequency scaling which is the only option considered by the state of the art [40]. For example a 10% reduction of the power cap in Exynos can be met with reducing frequency by one step but also through concurrency throttling and manual or compiler-driven code optimization, with the latter two options showing better energy savings potential with a power cap.

Conclusion
This paper presented a probabilistic approach for fine-grained energy profiling, implemented in ALEA, an energy profiling tool for sequential and parallel applications based on statistical sampling. Sampling is an established technique for fine-grain execution time profiling and apportioning to source and binary code. This paper shows that sampling is a viable option for detailed energy accounting, where this is needed to understand the power implications of microarchitectural and memory structures, and perform code-level energy-aware optimization. Importantly, we demonstrate an energy accounting method that is portable and overcomes the fundamental limitation of power measurement frequency, which is common across computing platforms. The tool operates entirely in user space and is portable across architectures.
We validated the ALEA probabilistic model and energy profiling tool using 14 instrumented benchmarks from the SPEC2000, SPEC OMP, PARSEC and Rodinia suites on Sandy Bridge and Exynos platforms. We demonstrated high profiling accuracy with low profiling overhead on both platforms. ALEA thus achieved both functional and performance portability. We conducted experiments that provide understanding of the power implications of memory access rates. We found strong correlation between power consumption and cache access rates on both Intel and ARM processors, as well as a clear impact of shared cache contention on power consumption. We presented use cases of ALEA where we conducted energy optimizations of individual basic blocks, using different strategies, and achieved whole-program enery savings of up to 37%. These use cases motivated fine-grain energy accounting and uncovered the complex interplay between code optimization, multicore execution and energy consumption.
We will pursue three directions for future work in ALEA. The first direction will evolve ALEA into a production-strength energy accounting tool that maps energy consumption to source code and language abstractions, along the lines of Intel's Vtune and HPC Toolkit. The second and complementary direction is to extend ALEA's capabilities to provide binary-level energy accounting of legacy programs running on virtualized software stacks. The third direction is to use ALEA to guide construction of a library of optimizations that programs can use to run efficiently in power-or energy-constrained environments.