Tomasz Buchert

Lucas Nussbaum

Jens Gustedt

Methods for Emulation of Multi-Core CPU Performance

Keywords: emulation, multi-core, CPU performance, experimental validation

When validating or evaluating real distributed applications, it is useful to be able to test the application in a large range of environments. In that context, emulation of CPU performance enables researchers to investigate how the performance of the application is affected by the performance of the participating CPUs. Using a homogeneous cluster of fast multi-core nodes, it is therefore possible to evaluate how an application would behave on a heterogeneous set of nodes, with varying performance and number of cores.

In this paper, three new methods for the emulation of CPU performance in the multi-core case are proposed: Fracas, CPU-Gov, and CPU-Hogs. Fracas relies on smart configuration of the Linux scheduler to achieve the desired emulation, CPU-Gov leverages the hardware CPU frequency scaling, and CPU-Hogs is a multi-core implementation of a CPU burner. These methods are compared and evaluated together with existing methods, with a set of micro-benchmarks, and show significant improvements over state-of-the-art solutions.

I. INTRODUCTION

The evaluation of algorithms and applications for largescale distributed platforms such as grids, cloud computing infrastructures, or peer-to-peer systems is a very challenging task. Different approaches are in widespread use [START_REF] Gustedt | Experimental validation in large-scale systems: a survey of methodologies[END_REF]: simulation of course (where the target is modeled, and evaluated against a model of the platform), but also insitu experiments (where a real application is tested on a real environment, like PlanetLab or Grid'5000). A third intermediate approach, emulation, consists in executing the real application on a platform that can be altered using special software or hardware, to be able to reproduce desired experimental conditions.

It is often difficult to perform experiments in a real environment that suits the experimenter's needs: the available infrastructure might not be large enough, nor have the required characteristics regarding performance or reliability. Furthermore, modifying the experimental conditions often requires administrative privileges which are rarely given to normal users of experimental platforms. Therefore, insitu experiments are often of relatively limited scope: they tend to lack generalization and provide a single data point restricted to a given platform, and should be repeated on other experimental platforms to provide more insight on the performance of the application.

The use of emulators can alleviate this, by enabling the experimenter to change the performance characteristics of a given platform. Since the same platform can be used for all the experiment, it is easy to conclude on the influence of the parameter that was modified. However, whereas many distributed system emulators (e.g MicroGrid [START_REF] Song | The microgrid: a scientific tool for modeling computational grids[END_REF], Modelnet [START_REF] Vahdat | Scalability and accuracy in a large-scale network emulator[END_REF], Emulab [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF], Wrekavoc [START_REF] Canon | Defining and Controlling the Heterogeneity of a Cluster: the Wrekavoc Tool[END_REF]) have been developed over the years, they mostly focus on network emulation: they provide network links with limited bandwidth or increased latency, complex topologies, etc.

Surprisingly, the question of the emulation of CPU speed and performance is rarely addressed by existing emulators. This question is however crucial when evaluating distributed applications, to know how the application's performance is related to the performance of the CPU (as opposed to the communication network), or how the application would perform when executed on clusters of heterogeneous machines.

This paper explores the emulation of CPU performance characteristics in the context of multi-core systems, and proposes three new methods for CPU emulation. After exposing the related work in Section II, the three methods are described in Section III and evaluated extensively with a set of micro-benchmarks (in Section IV).

II. RELATED WORK

Several technologies and techniques enable the execution of applications under a different perceived or real CPU speed.

Dynamic frequency scaling (known as Intel SpeedStep, AMD PowerNow! on laptops, and AMD Cool'n'Quiet on desktops and servers) is a hardware technique to adjust the frequency of CPUs, mainly for power-saving purposes. The frequency may be changed automatically by the operating system according to the current system load, or set manually by the user. For example, Linux exposes a frequency scaling interface using its sysfs pseudo-filesystem, and provides several governors that react differently to changes of system load. In most CPUs, those technologies only provide a few frequency levels (in the order of 5), but some CPUs provide a lot more (11 levels on Xeon X5570, ranging from 1.6 GHz to 2.93 GHz).

Frequency scaling has the advantage of not causing overhead, since it is done in hardware. It is also completely transparent: applications cannot determine whether they are running under CPU speed degradation unless they read the inria-00535534, version 2 -14 Jul 2011 operating system settings. On the other hand, the main drawback of frequency scaling is the small number of scaling levels available, which might not be sufficient for some experiments. Another drawback is that on most CPUs, it is not possible to change the frequency of each core independently, as exposed by Linux in cpufreq/related_cpus (Figure 1). Finally, dynamic frequency scaling indirectly also affects memory access speed as will be shown in Section IV. CPU-Lim is the CPU limiter implemented in Wrekavoc [START_REF] Canon | Defining and Controlling the Heterogeneity of a Cluster: the Wrekavoc Tool[END_REF]. It is implemented completely in userspace, using a real-time process that monitors the CPU usage of programs executed by a predefined user. If a program has a too big share of CPU time, it is stopped using the SIGSTOP signal. If, after some time, this share falls below the specified threshold, then the process is resumed using the SIGCONT signal. The measure of CPU load of a given process is approximated by: CPU usage = CPU time of the process current timeprocess creation time CPU-Lim has the advantages of being simple and portable to most POSIX systems (the only non-conformance is the reliance on the /proc filesystem). However, it has several drawbacks.

Poor scalability: CPU-Lim polls the /proc filesystem with a high frequency to measure CPU usage and to detect new processes created by the user. This introduces a high overhead in the case of a large number of running processes. The polling interval also needs to be experimentally calibrated, as it influences the results of the experiments.

Not transparent: A malicious program can detect the effects of the CPU degradation and interfere with it by blocking the SIGCONT signal or by sending SIGCONT to other processes.

Incorrect measurement of CPU usage: The CPU usage is computed locally and independently for every process. If four CPU-bound processes in the system consisting of one core are supposed to get only 50% of its nominal CPU speed, then every process will get 25% of the CPU time. Every process has its CPU usage below a specified threshold, yet the total CPU usage is 100%, instead of the expected 50%. Additionally, the method gives sleeping processes an unfair advantage over CPU-bound processes because it does not make any distinction between sleeping time (e.g. waiting for IO operation to finish) and time during which the process was deprived of the CPU.

Multithreading issues: CPU-Lim works at the process level instead of the thread level: it completely ignores cases where multiple threads might be running inside a single process for its CPU usage computation. Therefore, one may expect problems in degrading CPU speed for multithreaded programs.

KRASH [START_REF] Perarnau | Krash: reproducible CPU load generation on many cores machines[END_REF] is a CPU load injection tool. It is capable of recording and generating reproducible system load on computing nodes. It is not a CPU speed degradation method per se, but similar ideas have been used to design one of the methods presented later in this paper, i.e., Fracas.

Using special features and properties of the Linux kernel to manage groups of processes (cpusets, cgroups), a CPUbound process is created on every CPU core and assigned a desired portion of CPU time by setting its available CPU share. The system scheduler (Completely Fair Scheduler) then distributes the CPU time at the cpuset level and later in each cpuset independently, resulting in the desired CPU load being generated for each core.

This method relies on several recent Linux-specific features and interfaces and is not portable to different operating systems. However it has several advantages. First, it is completely transparent, since it works at the kernel level. Processes cannot notice the injected load directly, nor interfere with it. Second, this approach is very scalable with the number of controlled processes: no polling is involved, and there are no parameters to calibrate. There are, however, a few settings of the Linux scheduler that affect the latency of the scheduler, and thus the accuracy of the result, as discussed in [START_REF] Buchert | Accurate emulation of cpu performance[END_REF].

Although there are many virtualization technologies available, due to their focus on performance none of them offer any way to emulate lower CPU speed: they only allow to restrict a virtual machine to a subset of CPU cores, which is not sufficient for our purposes. It is also possible to take an opposite approach, and modify the virtual machine hypervisor to change its perception of time (time dilation), giving it the impression that the underlying hardware runs faster or slower [START_REF] Gupta | Diecast: testing distributed systems with an accurate scale model[END_REF].

Another approach is to emulate the whole computer architecture using the Bochs Emulator, which can be configured to perform a specific number of "emulating instructions per second". However, according to Bochs's documentation, that measure depends on the hosting operating system, the compiler configuration and the processor speed. As Bochs is a fully emulated environment, this approach introduces inria-00535534, version 2 -14 Jul 2011

0 1 2 3 4 5 6 7 VN 1 VN 2 VN 3 Virtual node 4
Figure 2: Multi-core CPU emulation using a 8-core machine decomposed into 4 virtual nodes, using respectively 1, 1, 2 and 4 cores, allocated respectively 75%, 40%, 60% and 25% of the physical cores' performance.

performance impact that is too high for our needs. Therefore, it is not covered in this paper.

III. METHODS FOR MULTI-CORE CPU EMULATION

Several techniques and tools enable the emulation of CPU performance, giving the ability to test an application or an algorithm in an environment with a configurable and reproducible level of heterogeneity of processors. However, the emulation of multi-core (or multi-processor) systems has not been addressed until now. This work targets the emulation of several nodes within one physical node, each possibly with a given number of cores and emulated frequencies. The emulation should also be independent from the number of processes or threads composing the application.

A partial solution to this problem is provided by the Linux cgroups subsystem, which can be used to setup separate scheduling zones with a smaller number of cores. However, while this can be used to restrict a subtree of processes to a subset of CPU cores, the CPU frequency emulation must be carried out by different means.

In this section, three methods for multi-core CPU performance are presented. CPU-Hogs is a multi-core variant of the idea of using spinning CPU-intensive tasks to prevent other applications from using the CPU. Fracas leverages Linux scheduling to allocate the desired CPU share to applications, and CPU-Gov alternates between two hardware CPU frequencies to achieve the desired emulated frequency.

In addition to the ability to emulate CPU speed, these methods can perform it within different scheduling zones, or virtual nodes, with a different CPU speed and a subset of cores. Therefore, it is even possible to emulate a configuration with several virtual nodes, each of them having a different number of core and a different CPU speed (Figure 2).

A. CPU-Hogs

A basic method to degrade the perceived CPU performance is to create a spinning process that will use the CPU for the desired amount of time, before releasing it for the application. This was already implemented in Wrekavoc [START_REF] Canon | Defining and Controlling the Heterogeneity of a Cluster: the Wrekavoc Tool[END_REF]. Figure 3: CPU-Hogs: using CPU burners to degrade CPU performance. Without synchronization between the spinning threads, the user process will migrate between cores and use more CPU time than allocated. This is solved in CPU-Hogs by using a synchronization barrier: there is then no advantage for the user process to migrate between cores.

The CPU-Hogs method generalizes this idea to the multicore case. One CPU burner thread per core is created, and assigned to a specific core using scheduler affinity. They are assigned the maximum realtime priority, so that they are always prioritized over other tasks by the kernel. The CPU burners then alternatively spin and sleep for configurable amounts of time, leaving space for the other applications during the requested time intervals.

However, creating one CPU burner per core is not enough in the multi-core case. If the spinning and sleeping periods are not synchronized between all cores, the user processes will migrate between cores and benefit from more CPU time than expected (Figure 3). This happens in practice due to interrupts or system calls processing that will desynchronize the threads. In CPU-Hogs, the spinning threads are therefore synchronized using a POSIX thread barrier placed at the beginning of each sleeping period.

This method is easily portable to other operating systems (and should be portable without any code change to other POSIX systems). It may have problems scaling to a large number of cores due to the need for frequent synchronization between cores, even though in practice we did not encounter any observable overhead with 8-core systems.

B. Fracas

Whereas CPU-Hogs is responsible for deciding when CPUs will be available for user processes, another solution is to leave that decision to the system scheduler (known as Completely Fair Scheduler since Linux 2.6.23), which is already in charge of scheduling all the applications on and off the CPUs. This is the idea behind Fracas, our scheduler-assisted method for CPU performance emulation root cgroup vn1 vn2 vn3 vn4 all all all all burn0 burn1 burn2 burn3 burn4 burn5 burn6 burn7 process without emulation (system daemons, etc) CPU burner emulated process which shares many ideas with Krash [START_REF] Perarnau | Krash: reproducible CPU load generation on many cores machines[END_REF]. Fracas was already presented in [START_REF] Buchert | Accurate emulation of cpu performance[END_REF], but gained support for emulating several virtual nodes on a physical machine since then. With Fracas, one CPU-intensive process is started on each core. Their scheduling priorities are then carefully defined so that they run for the desired fraction of time. This is implemented using the Linux cgroups subsystem, that provides mechanisms for aggregating or partitioning sets of processes or threads into hierarchical groups. As shown on Figure 4, one cgroup per virtual node is first created. Then, inside each of these cgroups, one cgroup named all is created to contain the emulated user processes for the given virtual node. Finally, cgroups are created around each of the CPU burner processes.

Additionally, within each virtual node priorities of all (pr all ) cgroup and every burn (pr burn ) cgroup must be properly adjusted. The CPU time is distributed proportionally to the priorities of cgroups, thus the values are set so that the following formula holds: pr all pr all + pr burn = µ

where µ is a ratio of the emulated CPU frequency to the maximum CPU frequency. In particular, when the virtual node emulates a CPU half as fast as the physical CPU (µ = 0.5), then both the priorities will have the same value.

Since the system scheduler is responsible for switching between the CPU burner process and the user processes, the frequency of those context switches will influence the quality of the resulting emulation. Two scheduler parameters tunable in /proc/sys/kernel/ have been experimentally verified to influence the scheduling granularity and the quality of emulation: sched_latency_ns and sched_min_granularity_ns. Their default values provide results of acceptable quality as shown in [START_REF] Buchert | Accurate emulation of cpu performance[END_REF], nevertheless they are both configured to their lowest possible values (0.1 ms) for the experiments described in the following sections.

It is worth noting that the implementation of Fracas is strongly related to the Linux kernel's internals: as the scheduling is offloaded to the kernel's scheduler, subtle changes to the system scheduler can severely affect the correctness of Fracas. Results presented in this paper were obtained using Linux 2.6.33.2, but older kernel versions (for example, version 2.6.32.15) exhibited a very different behavior.

C. CPU-Gov

Contrary to the previous methods where the emulation is done purely in software, CPU-Gov is a hardware-assisted approach. It leverages the hardware frequency scaling to provide emulation by switching between the two frequencies that are directly lower (f L ) and higher (f H ) than the requested emulated frequency (f ). The time spent at the lower frequency (t L ) and at the higher frequency (t H ) must satisfy the following formula:

f = f L t L + f H t H t L + t H
For example, if the CPU provides the ability to run at 2.0 GHz and 2.4 GHz, and the desired emulated frequency is 2.1 GHz, CPU-Gov will cause the CPU to run 75% of the time at 2.0 Ghz, and 25% of the time at 2.4 Ghz. The frequency of switching is configurable, but was set to 100 ms during the experiments presented in the following sections.

As described, CPU-Gov can only emulate frequencies which are higher than the lowest provided by hardware: a different solution is required to emulate frequencies that are lower than the ones provided by frequency scaling. For those, a virtual zero frequency is created by stopping all the processes in the virtual node. For this, the Linux cgroup freezer is used, which has the advantage of stopping all tasks in the cgroup with a single operation.

This method has the advantage that, when the frequency is higher than the lowest frequency provided by hardware frequency scaling, the user application is constantly running on the processor. Hence, its CPU time will be correct, which is not the case for the other methods.

However, this method suffers from the limitation mentioned in Section II about frequency scaling: on some CPUs, it is not possible to change the frequency of each core independently: some cores might have to be switched together for the change to take effect, due to the sharing of caches, for example. This is taken into account when allocating virtual nodes on cores, but limits the possible configurations. For example, on 4-core CPUs, it might not be possible to create 4 virtual nodes with different emulated frequencies. To get information about the topology and relations between cores, hwloc library is used.

Another disadvantage is that this method relies on the frequencies advertised by the CPU. On some AMD CPUs, some advertised frequencies were experimentally determined to be rounded values of the real frequency (the performance was not growing linearly with the frequency). It would be possible to work-around this issue by adding a calibration phase where the performance offered by each advertised frequency would be measured.

IV. EVALUATION WITH MICRO-BENCHMARKS

In this section, CPU-Hogs, Fracas and CPU-Gov are evaluated together with the CPU emulator provided in Wrekavoc [START_REF] Canon | Defining and Controlling the Heterogeneity of a Cluster: the Wrekavoc Tool[END_REF], i.e., CPU-Lim, which was already described in Section II.

The original CPU-Lim from Wrekavoc was rewritten for those experiments, as it was not usable under its current form. First, support for controlling virtual nodes was added. Whereas the original CPU-Lim tracks processes of a specific user, the modified version controls processes inside a given cgroup. Moreover, the modified version uses more accurate interfaces to query process timers, improving the quality of emulation. Other modifications were also considered, like the use of the Linux cgroup freezer feature instead of signals to stop and resume tasks, and the use of better interfaces to retrieve the CPU time on a per-thread basis, but it was chosen to avoid diverging from the original design.

All these methods were tested with 6 different microbenchmarks, each representing a different type of workload:

• CPU-intensive -a tight, CPU-intensive loop is performed for 3 seconds. The result is the computation rate.

• IO-intensive -UDP datagrams of size 1 KB are sent to a non-existing IP address for 1 second. The result is the communication rate (number of send loops per second). • Computing and sleeping -a CPU-intensive loop is executed for 1 second, then the process sleeps for 1 second (as if it was waiting for IO operations to finish, or for synchronization with other processes), and finally the CPU-intensive loop is executed for 1 second again. The result is a number of loops performed during the test divided by the time needed to execute them (computation rate). Since the sleeping time is independent from the CPU performance, the result of this benchmark is expected to grow linearly with the CPU performance. • Memory speed -the classic STREAM benchmark is used to measure (in MB/s) the sustainable memory speed. • Multiprocessing -5 processes are created and each of them runs an instance of CPU-intensive benchmark for 1 second. After that, they are all joined (using waitpid call) and the result is a number of loops performed by each of the tasks (which is the same for all of them) divided by the time between the processes' creation and the completion of the final joining. If all the tasks can run simultaneously, the result should be the same as the result of CPU-intensive benchmark. • Multithreading -a modification of the multiprocessing benchmark: instead of processes, POSIX threads are created and managed. All other details remain the same.

In order to ease the reproduction of the experimental results, the source code and scripts used to performed experiments is made available 1 .

A. Experimental Methodology

The tests presented in this section were run on a cluster of 25 identical Sun Fire X2270 machines, equipped with two Intel Xeon X5570 (Nehalem microarchitecture) and 24 GB of RAM each. The Intel Xeon X5570 provides frequency scaling with 11 different levels: 2.93, 2.80, 2.67, 2.53, 2.40, 2.27, 2.13, 2.00, 1.87, 1.73, and 1.60 GHz. Both Intel Turbo Boost and Hyper-Threading were disabled during the experiments.

An unmodified 2.6.33.2 Linux kernel was used on the nodes. To schedule the tests, a test framework written in Python was developed. Only one test was running on each node at a given time. Each individual test was reproduced 40 times and the values presented on the graphs are the average of all samples with the 95% confidence intervals (though most experiments produce very stable results, hence the confidence intervals might not be visible). The same tests were also run on a cluster equipped with AMD Opteron 252 CPUs, and no significant difference was found.

B. Benchmarks on One Core

This section describes the results obtained by the microbenchmarks described in the previous section on a virtual node containing only one core. CPU-Lim, CPU-Hogs, Fracas and CPU-Gov are evaluated, and results obtained using only hardware frequency scaling (later described as CPU-Freq) are also included for comparison.

1) CPU-intensive workload: As can be seen in Figure 5a, all methods perform well when a CPU-intensive application runs inside the emulated environment, i.e., they all scale the speed of the application proportionally to the value of emulated frequency. However, though it cannot be seen on the graphs, the most stable results are produced by Fracas method, and the results with the highest variance are produced by CPU-Lim method.

2) IO-intensive workload: How the emulation of CPU frequency should influence the performance of the network, or of any other IO operation, is unclear. One could assume that their respective performance should be completely independent. However, IO operations require CPU time to prepare packets, compute checksums, etc. The methods exhibit very different behaviors, as shown in Figure 5b, though which one should be considered the best is not clear. CPU-Lim, Fracas and CPU-Gov only scale IO performance up to a certain point, which could be consistent with the fact that IO operations require a certain amount of CPU performance to perform normally, but that adding more CPU performance would not improve the situation further. On the other hand, CPU-Hogs scales IO performance linearly with the emulated frequency.

3) CPU and sleeping workload: All the methods, with a sole exception of CPU-Lim, perform very well in that benchmark, as presented in Figure 5c. This is expected, because CPU-Lim does not take the sleeping time of a process into the account, and wrongly gains an advantage after a period of sleep.

Amongst the well-behaving methods, the most stable results are produced by CPU-Gov.

4) Memory speed: How the memory speed should be affected by the CPU speed emulation is not clear, since both parameters are closely related. The speed of the memory directly controls the speed of instruction fetching and of memory accesses, and consequently the speed of execution. On the other hand, a slower CPU will execute instructions accessing the memory slower, so will indirectly degrade the memory speed, at least from the user perspective. Therefore, which method provides the best results is not obvious in Figure 5d. It may be only noted that the most predictable and easy to understand behavior is that of CPU-Hogs and Fracas, since they are stable and almost linear with the respect to the emulated frequency. This can neither be said about CPU-Lim method, whose results fluctuate greatly, nor about CPU-Gov method which gives predictable results, but without any obvious relation to the value of emulated frequency.

5) Multiprocessing:

With multiple tasks, either processes or tasks, it is expected to linearly and independently degrade the speed of each CPU-intensive task. Most methods provide good results as seen in Figure 5e, with the exception of CPU-Lim. As CPU-Lim computes the CPU usage independently for each process, but does not sum it to compute the virtual node's CPU usage, it appears that the CPU-Lim method does not emulate anything, as the CPU usage of each independent process stays under the limit.

6) Multithreading:

The expected behavior in the benchmark presented in Figure 5f is exactly the same, as in the previous benchmark. This time even the CPU-Lim method performs very well, because the CPU time of the emulated threads is accumulated for the whole process. Again, there is no clear winner in terms of the stability of the results, i.e., all methods give satisfactory results in that sense.

C. Benchmarks on 2, 4 and 8 Cores

Contrary to the previous set of tests, the microbenchmarks were run in an environment emulating more than one core. In each case, five user processes or threads are executed. All single-task benchmarks gave the same results as before, so they are not included.

1) CPU-Hogs and CPU-Gov: The results (Figure 6) clearly show the superiority of CPU-Hogs and CPU-Gov methods, as the result of the benchmarks is proportional to the emulated frequency only in their case (and for the CPU-Freq method, but it's not able to emulate continuous range of frequencies, and therefore is not considered as a fully functional method). Additionally, CPU-Hogs is superior to CPU-Gov in terms of stability of results, providing results with a slightly smaller variation.

2) CPU-Lim: The CPU-Lim method is able to properly emulate multiprocessing type of work, however only when each process can run on an independent core. This can be seen in Figure 6e -all processes cannot saturate available cores and CPU-Lim works as required. Nevertheless, we can see that the result is too high most of the time for benchmarks with a lower number of tasks, due to CPU-Lim's problem with computing CPU time (Section II). As the benchmark consists of 5 processes, each of them will get approximately 2•100% 5 = 40% and 4•100% 5 = 80% of the CPU time, for cases in Figure 6a and Figure 6c, respectively. As can be seen, this is precisely a fraction of maximum CPU frequency where the graph suddenly drops. Therefore, in general, CPU-Lim will not properly emulate a group of processes in multi-core configuration.

A different problem can be seen in the case of the multithreading benchmark. Now, the CPU-Lim method gives values lower than the expected ones. This is because it controls processes (or groups of threads), not threads. The CPU time of a process is a sum of CPU-times of all its threads, and as such, it may go up faster than the realtime clock. Moreover, when CPU-Lim sends a signal to stop the process, all its threads will be stopped. Put together, this explains why the results in Figure 6b, Figure 6d, and Figure 6f are precisely 2, 4, and 8 times lower than those for CPU-Hogs or CPU-Gov.

A very strange phenomenon can be observed in Figure 6c -the benchmark gives higher results in the environment emulated with CPU-Lim than in the unmodified one. This counterintuitive behavior is due to the kernel which, when the processes are run normally, will put every process on one of 4 cores and, as there are 5 processes in total, one core will execute two processes simultaneously. They will run twice as slow as the remaining ones and, consequently, will degrade the overall result of the benchmark (it is possible to mitigate the problem by extending the time of the benchmark). With CPU-Lim method, the processes are stopped periodically, forcing the scheduler to migrate them between unused cores and giving them fairer amount of CPU time. It seems that the Linux scheduler, as much as advanced it is, is by no means perfect. But even knowing that, the conclusion must be drawn that CPU-Lim behaves improperly, as we aim to emulate the exact behavior of the unmodified kernel.

3) Fracas: The results for Fracas method show, as was already observed in [START_REF] Buchert | Accurate emulation of cpu performance[END_REF], that the method does not work well for multitasking type of work. The results of the benchmarks are much lower than expected. For example, it can be seen in Figure 6b, Figure 6d and Figure 6f that the results are 2, 4, and 8 times lower, respectively. This is because the priority of cgroup consisting of the emulated tasks is constant (as defined by a formula in Section III-B). Even if the emulated tasks are running on different cores, the total allowed CPU time of them will be bounded by this priority. The priority of the cgroup can be adjusted so that it will work for a particular number of processes inside the emulated environment, but, unfortunately, there is no a generic value that will work for every possible number of tasks.

Also, one can see a significant discrepancy between pairs of figures: Figure 6a and Figure 6b, Figure 6c and Figure 6d. This does not happen in the last pair: Figure 6e andFigure 6f. Again the reason is the scheduler and was observed in CPU-Lim case before -when there are more tasks than cores in the system, some arbitrary decisions made by the system make the parallel execution suboptimal. Evidently, this is much more expressed in the case of multiple number of threads, not processes, but was also manually triggered in the latter case. This could have been expected, but the difference in the execution time is startling. More confusingly, the behavior of the scheduler can change quite dramatically with every version of the Linux kernel. That was in fact so, and other anomalies were observed with different releases of Linux kernel.

The results clearly show that reliance on the system scheduler may be deceiving and, as a result, the Fracas method should not be used to emulate an environment with multiple tasks (unless the number of cores is greater than their number).

V. CONCLUSIONS

Emulation of CPU performance is an important asset in the context of the evaluation of applications targeted at heterogeneous systems. In this work we propose three new methods for the emulation of CPU performance: Fracas (based on a preexisting idea from the Krash workload After a detailed description of those three methods, we compare them with the current CPU emulator in Wrekavoc, i.e. CPU-Lim, by running a carefully designed set of microbenchmarks. Results show that both CPU-Gov and CPU-Hogs generate the desired experimental conditions, with some variations in some benchmarks where the expected behavior is not completely clear. In contrast, CPU-Lim and Fracas exhibit severe limitations, especially when used to execute applications consisting of several processes or threads in a multi-core environment.

In the future, we will continue to evaluate those CPU emulators by running experiments with real applications. We also plan to experiment with memory performance emulation, as memory speed has become a very important parameter for understanding the performance of applications.

Figure 1 :

 1 Figure 1: Architecture of a dual Intel L5420 machine, as shown by hwloc [6]. Cores sharing their L2 cache cannot change speed independently.

Figure 4 :

 4 Figure 4: Structure of cgroups in Fracas for the example from Figure 2.

Figure 5 :

 5 Figure 5: Results for micro-benchmarks running on one core (Section IV-B)

Figure 6 :

 6 Figure 6: Results for micro-benchmarks running on 2, 4 and 8 cores (Section IV-C)

http://www.loria.fr/ ∼ lnussbau/files/cpuemul-exp.tgz


Philippe Angot

Jean-Paul Caltagirone

Pierre Fabrie

A new fast method to compute saddle-points in constrained optimization and applications

come

A new fast method to compute saddle-points in constrained optimization and applications


Keywords: emulation, processor, scheduler émulation, processeur, ordonnnanceur

This paper addresses the question of CPU performance emulation, which allows experimenters to evaluate applications under a wide range of reproducible experimental conditions. Specifically, we propose Fracas, a CPU emulator that leverages the Linux Completely Fair Scheduler to achieve performance emulation of homogeneous or heterogeneous multi-core systems. Several benchmarks reproducing different types of workload (CPU-bound, IO-bound) are then used to thoroughly compare Fracas with another CPU emulator and hardware frequency scaling. We show that the design of Fracas results in a more accurate and a less intrusive CPU emulation solution.

Introduction

The evaluation of algorithms and applications for large-scale heterogeneous platforms is a very challenging task. Different approaches are in widespread use [START_REF] Gustedt | Experimental Validation in Large-Scale Systems: a Survey of Methodologies[END_REF]: simulation of course, but also in-situ experiments (where a real application is tested on a real environment), and emulation (where a real application is tested on a simulated environment).

It is often difficult to perform experiments in a real environment that suits the experimenter's needs: the available infrastructure might not be large enough or have the required characteristics. Moreover, controlling experimental conditions in heterogeneous and distributed systems, like grids or the Internet, makes the experimental validation error-prone. Therefore, in-situ experiments are often not feasible, and the use of an emulated or simulated environment is often preferred. Many distributed system emulators (e.g. MicroGrid [START_REF] Song | The microgrid: a scientific tool for modeling computational grids[END_REF], Modelnet [START_REF] Vahdat | Scalability and accuracy in a large-scale network emulator[END_REF], Emulab [START_REF] White | An integrated experimental environment for distributed systems and networks[END_REF], Wrekavoc [START_REF] Canon | Defining and Controlling the Heterogeneity of a Cluster: the Wrekavoc Tool[END_REF]) have been developed over the years, but most of them focus on network emulation.

Surprisingly, the question of the emulation of CPU speed and performance is rarely addressed by them. However, it is crucial to evaluate applications under a set of different experimental conditions: to know how application's performance is related to the performance of the CPU (as opposed to the communication network), or how an application would perform when executed on clusters of heterogeneous machines, with different CPUs.

This paper explores the emulation of CPU performance characteristics, and proposes a new implementation of a CPU emulator: Fracas. After exposing the related works in Section 2, the problem is clarified and formalized in Section 3. Fracas is then described in Section 4, and evaluated extensively in Section 5.

Related Work

Several technologies and techniques enable the execution of applications under a different perceived CPU speed.

Dynamic frequency scaling (known as Intel SpeedStep, AMD PowerNow! on laptops and AMD Cool'n'Quiet on desktops and servers) is a hardware technique to adjust the frequency of CPUs, mainly for power-saving purposes. The frequency may be changed automatically by the operating system according to the current system load, or set manually by the user. In most CPUs, those technologies only provide few frequency levels (around 5), but some CPUs provide a lot more (11 levels on Xeon X5570, ranging from 1.6 GHz to 2.93 GHz).

Frequency scaling has the advantage of not causing overhead, since it is done in hardware. It is also completely transparent: applications cannot determine whether they are running under CPU speed degradation unless they read the operating system settings. On the other hand, the main drawback of frequency scaling is the small number of scaling levels available, which might not be sufficient for some experiments. It should also be noted that it is usually not possible to change the frequency of the processor cores independently, and that dynamic frequency scaling indirectly affects memory access speed as will be shown in Section 5.

RR n°7308

inria-00490108, version 3 -26 Oct 2010 CPU-Lim is the CPU limiter implemented in Wrekavoc [START_REF] Canon | Defining and Controlling the Heterogeneity of a Cluster: the Wrekavoc Tool[END_REF]. It is implemented completely in user-space, using a real-time process that monitors the CPU usage of programs executed by a predefined user. If a program has a too big share of CPU time, it is stopped using the SIGSTOP signal. If, after some time, this share falls below the specified threshold, then the process is resumed using the SIGCONT signal. The measure of CPU load of a given process is approximated by: CPU usage = CPU time of the process current time -process creation time CPU-Lim has the advantages of being simple and portable to most POSIX systems (the only non-conformance is the reliance on the /proc filesystem). However, it has several drawbacks.

Poor scalability: CPU-Lim polls the /proc filesystem with a high frequency to measure CPU usage and to detect new processes created by the user. This introduces a high overhead in the case of a large number of running processes. The polling interval also needs to be experimentally calibrated, as it influences the results of the experiments.

Not transparent: A malicious program can detect the effects of the CPU degradation and interfere with it by blocking the SIGCONT signal or by sending SIGCONT to other processes.

Incorrect measurement of CPU usage: The CPU usage is computed locally and independently for every process. If four CPU-bound processes in the system consisting of one core are supposed to get only 50% of its nominal CPU speed, then every process will get 25% of the CPU time. Every process has its CPU usage below a specified threshold, yet the total CPU usage is 100%, instead of the expected 50%. Additionally, the method gives sleeping processes an unfair advantage over CPU-bound processes because it does not make any distinction between sleeping time (e.g. waiting for IO operation to finish) and time during which the process was deprived of the CPU.

Multithreading issues: CPU-Lim works at the process level instead of the thread level: it completely ignores cases where multiple threads might be running inside a single process for its CPU usage computation. Therefore, one may expect problems in degrading CPU speed for multithreaded programs.

KRASH [START_REF] Perarnau | Krash: reproducible CPU load generation on many cores machines[END_REF] is a CPU load injection tool. It is capable of recording and generating reproducible system load on computing nodes. While it is not a CPU speed degradation method per se, similar ideas have been used to design Fracas, which is presented later in this paper.

Using special features and properties of the Linux kernel to manage groups of processes (cpusets, cgroups), a CPU-bound process is created on every CPU core and assigned a desired portion of CPU time by setting its available CPU share. The system scheduler (Completely Fair Scheduler) then distributes the CPU time at the cpuset level and later in each cpuset independently, resulting in the desired CPU load being generated for each core.

Although this method relies on several recent Linux-specific features and interfaces and is not portable to different operating systems, however it has several advantages. First, it is completely transparent, since it works at the kernel level. Processes cannot notice the injected load directly nor interfere with it. Second, this approach is very scalable with the number of controlled processes: no polling is involved, and there are no parameters to calibrate. There are, however, a few settings of the Linux scheduler that affect the accuracy of the result, as discussed later (see Section 4).

While there are many virtualization technologies available, due to their focus on performance none of them offer any way to emulate lower CPU speed: they only allow to restrict a virtual machine to a subset of CPU cores, which is not sufficient for our purposes. It is also possible to take an opposite approach, and modify the virtual machine hypervisor to change its perception of time, giving it the impression that the underlying hardware runs faster or slower [START_REF] Gupta | Diecast: testing distributed systems with an accurate scale model[END_REF].

Another approach is to emulate the whole computer architecture using the Bochs Emulator [START_REF]Bochs documentation[END_REF], which can be configured to perform a specific number of "emulating instructions per second". However, according to Bochs's documentation, that measure depends on the hosting operating system, the compiler configuration and the processor speed. As Bochs is a fully emulated environment, this approach introduces performance impact that is too high for our needs. Therefore, it is not covered in this paper.

Problem Statement

In this section core is the smallest processing unit that can execute the code of the program independently on a processor. It is equivalent to a core of a physical processor. Consequently, processor is a set of cores and is equivalent to a physical processor. Additionally, a distinction is made between real processor/core (the one existing as a hardware implementation) and emulated processor/core (the one being emulated).

Let's assume that a computer system consists of N cores with speeds α 1 ≤ α 2 ≤ α 3 ≤ . . . ≤ α N . The goal is to emulate M processors, using this physical processor. The m-th emulated processor, denoted C m occupies a subset of real cores: C m ⊂ {1, 2, . . . , N }. None of the physical cores will be occupied by more than two emulated ones so

C i ∩ C j = ∅ for 1 ≤ i < j ≤ M .
Finally, for each emulated processor

C m (1 ≤ m ≤ M ), a core k ∈ C m has the emulated speed β k . If k ∈ C m for every 1 ≤ m ≤ M then by definition β k = 0.
It is also reasonable to assume that α i ≥ β i for i ∈ {1, . . . , N }, so that each emulated core can be mapped to a physical one. Also, in most real-life scenarios it is true that α 1 = α 2 = α 3 = . . . = α N . If not stated differently, this is always assumed in the following sections.

An example of the problem instance is presented in Figure 1.

The following special cases of this problem are of particular interest and are considered in this paper:

(A) M = 1 and C 1 has one element -a single core processor is emulated.

(B) M = 1 and C 1 has exactly N elements -the only emulated processor spans all physical cores. This is a hardly a complete formalization of the general problem. In a more general setting one may relax some previous assumptions or take other properties of the computer systems into account: speed of the random access memory, the CPU cache size and properties, Simultaneous Multi Threading (SMT)

N = 4, α 1 = α 2 = α 3 = α 4 = 10, M = 2, C 1 = {1, 2}, C 2 = {3}, β 1 = β 2 = 5, β 3 = 7, β 4 = 0 .
(e.g. Intel Hyper-Threading technology) or Non-Uniform Memory Architectures (NUMA).

Proposed Solution

Fracas is using an approach similar to KRASH. On every processor core a CPUintensive process is created. It burns a required amount of CPU cycles on its core. All other tasks in the system are moved to another group which spans all cores. CPU time is distributed to groups proportionally to their weights so, by adjusting them properly, the latter group will acquire the desired amount of the CPU time. Figure 2 presents the idea graphically. This method uses Completely Fair Scheduler (CFS) by Ingo Molnar which is a default scheduler in the current Linux release (2.6.34). It was merged into kernel mainline in version 2.6.23. Cpusets, which also play an important role, were introduced in version 2.6.12 of the Linux kernel. The O(1) scheduler (also by Ingo Molnar) used back then does not possess the features as required by Fracas [START_REF] Perarnau | Krash: reproducible CPU load generation on many cores machines[END_REF].

The following CFS parameters [START_REF] Jones | Inside the Linux 2.6 Completely Fair Scheduler: Providing fair access to CPUs since 2[END_REF] have been experimentally verified to have impact on the work of Fracas: latency (default kernel value: 5ms) -targeted preemption latency for CPU-bound tasks, and min granularity (default kernel value: 1ms) -minimal preemption granularity for CPU-bound tasks. The first one defines the time which is a maximum period of a task being in a preempted state and the latter is a smallest quantum of CPU time given to the task by the scheduler.

Ignoring rounding, the kernel formula for computing the period in which every running task should be ran once is (n r -a number of running tasks) max (n r • min granularity, latency).

Therefore, setting latency and min granularity to the lowest possible values (which is 0.1ms for both of them) will force the scheduler to compute the smallest possible preemption periods and, as a result, the highest possible activity of the scheduler. This substantially improves the accuracy of Fracas (see Figure 3). In this figure each plot presents the result for Linpack benchmark (see Section 5.2) under different scheduler latency. As can be seen, the lower the latency, the more the results converge to the perfect behavior.

Evaluation

In the following sections three different methods are evaluated which can be used to emulate the CPU speed: dynamic frequency scaling (abbreviated to CPU-Freq), CPU-Lim and Fracas.

There are many pitfalls related to the experiments involving processors. Contemporary processors have a very complex architecture -due to cache, branch prediction, simultaneous multithreading technology, code alignment in the memory and other factors, the behavior of programs may vary significantly in similar conditions. Another problem is posed by external factors that may change the execution conditions on the fly. For instance, dynamic frequency scaling is used to conserve power or to generate less heat than during a normal operation. Preferably this feature should be turned off during all the experiments. Nevertheless, even if turned off, most CPUs may also throttle their frequency down in the case of dangerous overheat, leading to an unexpected performance loss. To make things even worse, the newest Intel processors in the Nehalem family (used in our experiments) may introduce an "unexpected" performance gain: Turbo Mode technology allows a processor core to overclock itself when the other cores are idle. In the following experiments this technology was knowingly turned off as well as Intel Hyper-Threading.

The experimental scientist must be aware of these problems to perform the experiments reliably.

Experimental Setup

All experiments were performed on the Grid'5000 experimental testbed [START_REF]The Grid'5000 experimental testbed[END_REF]. Specifically, the following clusters were used:

The Parapide cluster located in Rennes, France. All nodes in the cluster have two quad-core Intel processors (Intel Xeon X5570). Each core has 11 different levels of dynamic frequency scaling available.

The Chti cluster located in Lille, France. All nodes in the cluster have a pair of single-core AMD processors (AMD Opteron 252). Finally, this CPU model offers 6 levels of dynamic frequency scaling.

RR n°7308

inria-00490108, version 3 -26 Oct 2010

All nodes from a given cluster offer exactly the same configuration so it was possible to perform experiments in parallel. To achieve this, a client-server application was created to distribute the tests automatically. The order in which tests are distributed is randomized. Nodes involved in the experiments were deployed with the same instance of Linux operating system (kernel version: 2.6.33.2).

The experimental framework as well as instructions to reproduce the results are available at http://www.loria.fr/ ~lnussbau/files/fracas.html.

Benchmarks

The following benchmarks, testing important aspects of the CPU emulation, were used: Linpack (GFLOP/s) -a well known benchmark used to measure floating point computing power. The version used is a slightly modified version included in the HPCC Benchmark suite (version 1.4.0, released 2010-03-26) [START_REF]HPC Challenge Benchmark[END_REF].

Sleep (Loops/s) -a test performing CPU-intensive work, sleeping for the amount of time that was required to perform the work, and finally running the same computation once again. The result is the number of the computation cycles performed divided by the the time of the whole computation.

UDP (Sends/s) -a program that measures the time required to send many UDP packets to the network. The result is a number of sendto() invocations divided by the time required to perform them.

Threads (Loops/s) -a benchmark that creates a few threads (5 threads for the Parapide cluster and 2 threads for the Chti cluster). After a simple integer computation all threads are joined (using pthread join) and the result is the number of computation cycles performed by each thread divided by the time required to join all of them.

Processes (Loops/s) -a modification of Threads benchmark. Instead of the threads, processes are created. They are joined using waitpid syscall. STREAM (GB/s) -a synthetic benchmark that measures sustainable memory bandwidth. It is available at [START_REF]avenue de l'Europe -38334 Montbonnot Saint-Ismier Centre de recherche INRIA Lille -Nord Europe : Parc Scientifique de la Haute Borne -40, avenue Halley -59650 Villeneuve d'Ascq Centre de recherche INRIA Paris -Rocquencourt : Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay[END_REF].

Each benchmark performs a small calibration loop at the beginning to assure that the computation time is big enough as to yield meaningful results (i.e. it's not affected by the granularity of system clock). Please also note that the results from different benchmarks, even though sometimes measured in the same units, are not comparable in any sensible way.

Results and Discussion

All tests were performed ten times each and the final plot value is the average of all results. The whiskers describe the 95% confidence intervals of this value. The results from the Chti cluster are attached only if they significantly differ from the results obtained on the Parapide cluster. The majority of the results is identical and differences can be easily explained. This further convinces us that the results are independent and general. Most of the time the results obtained by CPU-Freq method are used as a reference, as a model we want to emulate using other methods.

For every emulated frequency f , let's define µ = f fmax as a scaling ratio (where f max is the maximum processor speed).

For a CPU intensive work the execution speed should be proportional to the ratio µ. In Figure 4 one can see that all three methods behave similarly for a CPU intensive work. Nevertheless CPU-Lim gives less predictable results and the slope of a plot with Fracas results is different than the one obtained from CPU-Freq. The observed difference between Fracas and CPU-Freq while emulating processor at 1.6 GHz speed is around 2.5%. This shows that dynamic frequency scaling on Intel processors affects the performance by a different factor than just the ratio µ.

The time when processes sleep, either voluntarily or waiting for IO operation to finish, should not influence the behavior after the process is woken up. However, from Figure 5 it is evident that CPU-Lim has problems with controlling processes which perform this type of work. Both Fracas and CPU-Freq behave as expected.

Generally, IO operations should not be affected by the CPU scaling because they depend on the hardware traits (like network card speed). Results from the Parapide cluster show that the time required to perform intensive access to the hardware does not scale with emulated CPU speed on the tested Intel processor. However, the results from the Chti cluster show (see Figure 9) that it scales by a factor of 16% when emulating the lowest possible frequency using CPU-Freq. It is because the AMD Opteron 252 processor has a wider range of available frequencies than Intel Xeon X5570 (but a smaller set of possible values). If scaled to 1.0 GHz, the time required to prepare UDP packet is becoming a significant factor. This is a proper behavior of all methods.

The CPU time is a resource shared by all the tasks running in the system. All the methods should scale down the total CPU usage and not only the one perceived by every process. Multiple tasks doing the same work simultaneously on different cores should finish at the same time and the total time should be roughly the same as the CPU time consumed by one task. In Figure 6 and Figure 7 the results for this kind of work are presented. A strange behavior of Fracas was observed -the time required to finish the work is much longer than the expected time. This odd behavior is of course a wrong one. CPU-Lim performs much better but its results are very unstable. Additionally, a significant overhead of CPU-Lim method can be observed when used to control even just 5 processes -the results of CPU-Lim method oscillate in the range 77% ÷ 89% of the respective CPU-Freq result (excluding the case of emulating the highest possible frequency when CPU-Lim processes are not started at all). The only significant difference between Figure 7 and Figure 6 is the behavior of CPU-Lim. The observed phenomenon was described in Section 2 as Incorrect measurement of CPU usage -the whole process (consisting of 5 threads) is controlled and the CPU usage is an accumulated value from all the threads. Therefore, CPU-Lim stops the process too often. As predicted, each result of CPU-Lim equals almost exactly 20% percent of CPU-Freq's one.

Generally, the memory speed is expected to not change at all while scaling CPU speed down. The conclusion from the data from Figure 8 is that memory speed is indeed affected by every presented method and by each method in its own way. Interestingly dynamic frequency scaling does not change memory speed linearly (as opposed to the pure computation speed, as can be seen in Figure 4).

All the above observations are summarized in a less formal way in Table 1.

Conclusions

Unfortunately, the obtained results show that none of the presented methods is perfect. Dynamic frequency scaling provides the best results, but its appli- cability is very limited due to its coarse granularity of CPU speed emulation, preventing the emulation of arbitrary speeds. Similarly, Fracas is a very good solution for the single thread/process case, and provides notable improvements compared to CPU-Lim, especially regarding accuracy and intrusiveness, but exhibits some problems in the multi-thread/process case.

In our future work, we plan to make further improvements to Fracas. First, we will try to solve the problems shown in the multi-thread/process case. Second, we will try to incorporate the emulation of other CPU characteristics, like memory bandwidth, as it becomes a crucial characteristic of modern CPUs. We would also like to emulate common features such as simultaneous multithreading. The ultimate goal is to create a reliable, fine-grained solution to cover all important aspects of CPU emulation.

In order to provide an easy way to run experiments with Fracas, we will integrate it into the Wrekavoc emulator, enabling experimenters to combine CPU emulation with Fracas, and network emulation on large clusters.

2 Figure 1 :

 21 Figure 1: An example of a CPU emulation problem. Here:N = 4, α 1 = α 2 = α 3 = α 4 = 10, M = 2, C 1 = {1, 2}, C 2 = {3}, β 1 = β 2 = 5, β 3 = 7, β 4 = 0 .

3 Figure 2 :Figure 3 :

 323 Figure 2: The idea behind Fracas

Figure 4

 4 Figure 4: Linpack benchmark

Figure 5 :

 5 Figure 5: Sleep benchmark

Figure 7

 7 Figure 7: Threads benchmark

Figure 8

 8 Figure 8: STREAM benchmark

Figure 9 :

 9 Figure 9: UDP benchmark (on Chti cluster)

Table 1 :

 1 Summary of the presented emulation methods CPU-Freq CPU-Lim Fracas

	Granularity of emulation	Coarse	Very good	Very good
	Accuracy of results	Excellent	Mediocre Depends on work
	Stability of emulation	Excellent	Mediocre	Very good
	Scalability (with no. of tasks) Unlimited Very bad	Very good
	Intrusiveness	None	Very high	Almost none

RR n°7308

http://www.inria.fr ISSN 0249-6399 inria-00490108, version 3 -26 Oct 2010