Erven Rohou

Tiptop: Hardware Performance Counters for the Masses

Keywords: performance, hardware counters, analysis tool

Hardware performance monitoring counters have recently received a lot of attention. They have been used by diverse communities to understand and improve the quality of computing systems: for example, architects use them to extract application characteristics and propose new hardware mechanisms; compiler writers study how generated code behaves on particular hardware; software developers identify critical regions of their applications and evaluate design choices to select the best performing implementation.

In this paper, we propose that counters be used by all categories of users, in particular non-experts, and we advocate that a few simple metrics derived from these counters are relevant and useful. For example, a low IPC (number of executed instructions per cycle) indicates that the hardware is not performing at its best; a high cache miss ratio can suggest several causes, such as conflicts between processes in a multicore environment. We also introduce a new simple and flexible user-level tool that collects these data on Linux platforms, and we illustrate its practical benefits through several use cases.

Tiptop: compteurs de performance matériels pour les masses Résumé : Les compteurs de performance matériels ont récemment rec ¸u un surcroît d'intérêt. Ils ont été utilisés par diverses communautés pour analyser et améliorer la qualité des systèmes informatiques: par exemple, les architectes les utilisent pour extraire des caractéristiques applicatives et proposer de nouveaux mécanismes matériels; les concepteurs de compilateurs étudient comment le code produit se comporte sur un matériel particulier; les développeurs logiciel identifient les régions critiques de leurs applications et comparent différentes approches pour sélectionner la meilleure implémentation.

Dans ce document, nous proposons de mettre les compteurs de performance à la disposition de tous les utilisateurs, en particuliers les non-experts, et nous préconisons quelques métriques simples, dérivées de ces compteurs, qui sont pertinentes et utiles. Par exemple, un IPC faible (nombre d'instructions exécutées par cycle) indique que le matériel n'est pas utilisé au maximum de ses possibilités; un taux de défauts de cache élevé suggère plusieurs raisons, comme des conflits entre processus dans un environnement multicoeurs.

Nous proposons un nouvel outil, simple et flexible, qui collecte ces informations dans une plate-forme Linux, et nous illustrons son utilité par plusieurs études de cas.

Mots-clés : performance, compteurs matériels, outil d'analyse

Introduction

The complexity of computing system increases at a fast pace, and this trend is likely to continue in the foreseeable future. Several roadmaps [START_REF] Asanović | The Landscape of Parallel Computing Research: A View from Berkeley[END_REF][START_REF]Computing Systems Consultation Meeting. Research Challenges for Computing Systems -ICT Workprogramme 2009-2010[END_REF][START_REF] De Bosschere | High-Performance Embedded Architecture and Compilation Roadmap[END_REF] predict thousands of cores on a chip by the end of this decade, which also implies complex memory hierarchies, interconnects, etc. The increasing variability of the lithographic process will also directly impact the diversity of platforms available in the computing ecosystem in the near future.

Moore's law drives the complexity of processor micro-architectures, which impacts all other layers: hypervisors, operating systems, compilers and applications follow similar trends. While a small category of experts is able to comprehend (parts of) the behavior of the system, the vast majority of users are only exposed to -and interested in -the bottom line: how fast their applications are running.

UNIX users typically rely on commands such as ps or top and look at the column %CPU for their processes. When this number is significantly below 100 %, they can investigate the reasons: resource conflicts (e.g. more processes than hardware threads), slow I/O, virtual memory effects, etc. When the CPU usage is close to 100 %, users can only conclude that there is no visible reason to be concerned.

CPU usage, however, only tells the user one part of the story: how often their processes are scheduled for execution by the operating system. It does not say anything about the way execution proceeds. In Section 3.1, we describe an extreme case, derived from real-life experiments: a simple floating point computation on the x86 architecture can perform up to 87× worse than expected for pathological parameters, because of micro-code assistance, and still show 100 % CPU usage.

In this work, we propose to take advantage of hardware performance counters to expose some details of the execution of applications that are currently not easily available to the average user. We propose tiptop, a new tool that is as easy to use as the top UNIX utility, and requires neither special privilege, nor application source code, nor expert knowledge what so ever. Simple metrics can let users feel how fast their applications are actually running. Advanced users, such as compiler developers or HPC (high-performance computing) experts, can also use our tool to compute more sophisticated ratios and get deeper insights, while still using the same simple tool. The contribution of this paper is three-fold:

• we advocate that performance monitoring counters should be easily available to the rest of us, as easily as one launches the top utility, to quickly obtain a simple, and high-level view of what is going on in the machine. Users should not require complex setups, root access, or even application source code. They should not need to restart an application (that may have been running for hours or days, and is not acceptable in a commercial environment) to monitor its behavior;

• we advocate that simple and easy to understand metrics, such as IPC (instructions per cycle) or cache miss ratio, are meaningful and useful to non-expert users, and we illustrate our claim with several use cases;

• we present a simple utility called tiptop, very similar to the top utility present in UNIX environment, that practically achieves our goals.

The rest of this paper is structured as follows: Section 2 describes the tool we propose, with its features and characteristics. In Section 3, we present several use cases that show the practical and theoretical usefulness of such a tool and the information it can provide. We review related work in Section 4 and we conclude in Section 5.

Tiptop

Tiptop is a command-line tool for the Linux environment, purposely very similar to the popular top utility. Figure 1 illustrates its output at a glance. It is a snapshot of the activity of a node in our data center: three users and eleven processes share a node of an Intel bi-Xeon E5640 quad-core with hyper-threading (16 logical cores). Beyond the familiar PID, USER, COMMAND and %CPU, the tool reports the number of execution cycles and executed instructions (both in millions) since last refresh, the current IPC (the ratio of the previous columns), and the number of last-level cache misses per hundred instructions.

Description

Various means to access hardware performance counters have been proposed. We review several of them in Section 4. Tiptop is built on top of the perf_event system call recently added in Linux 2.6.31 [START_REF] Eranian | Linux new monitoring interface: Performance counter for Linux[END_REF], which is available on many architectures, including x86, PowerPC, Sparc or ARM. This system call lets tiptop register new counters for processes running on the machine, and subsequently read the values of the counters. The tiptop process monitors the behavior of other processes, and periodically displays the values of some ratios of interest (IPC, miss ratio, branch misprediction, etc.) Tiptop has two running modes. The live mode periodically refreshes the screen with new values of the monitored events (similar to top) and lets users interactively inspect processes. The batch mode produces the same information, but as a streaming text output, similar to top -b, convenient for further processing. Tiptop has no graphics capability, our focus is only the collection of the raw data, in the spirit of UNIX filters such as sed, awk, etc. We plan to make tiptop publicly available (as soon as the anonymous review process is over).

Features

Our goal is to make the collection of performance and bottleneck data as simple as possible. Extremely simple installation and usage are a basic requirement. In particular, we stress the following points.

• Installation is only a matter of compiling the source code. No patching the Linux kernel is needed, and no special-purpose module needs to be loaded.

Inria i n t p e r f e v e n t o p e n ( s t r u c t p e r f e v e n t a t t r * hw , p i d t p i d , i n t cpu , i n t grp , i n t f l a g s ) • The usage is similar to top. There is no need for the source code of the applications of interest, making it possible to monitor proprietary applications or libraries. And since there is no probe to insert in the application, understanding of the structure and implementation of complex algorithms and code bases is not required.

• Applications do not need to be restarted, and monitoring can start at any time (obviously, only events that occur after the start of tiptop are observed).

• Events can be counted per thread, or per process.

The collected events and displayed ratios are fully customizable. The Linux header files provide a few generic events (total cycles, instructions, cache misses, branch mispredictions) that make it easy to compute portable metrics, such as IPC or last-level cache miss ratio, as shown in Figure 1. The default configuration collects these generic and portable events. But the tool is very flexible and lets users monitor any targetspecific event supported by the underlying architecture.

Our focus is not the detection of very fine-grain events, that would help analyze the performance of a small function, or study the cost of a particular lock, for example as in the work of Demme and Sethumadhavan [START_REF] Demme | Rapid identification of architectural bottlenecks via precise event counting[END_REF]. On the contrary, we provide a coarser-grain view of the behavior, and we typically take samples every few seconds.

Implementation

Tiptop is basically an infinite loop that displays how many times the requested events have happened for each task (process or thread), and then goes idle until some timeout expires or the user pressed a key.

Performance counters are accessed thanks to the perf_event system call, available since Linux 2.6.31 [START_REF] Eranian | Linux new monitoring interface: Performance counter for Linux[END_REF]. Its prototype is shown in Figure 2. pid is the task ID to monitor. We set cpu to -1 to monitor events per task (as opposed to CPU). grp and flags are unused. The hw struct is defined in /usr/include/linux/perf_event.h. It specifies which event is to be tracked. Generic target-independent events are defined in the same header file. Target specific events must be looked up in the vendor's architecture manuals (such as [START_REF]Intel. Intel64 and IA-32 Architectures Software Developer's Manual -System Programming Guide[END_REF]). The system call returns a file descriptor from which we read the values of the counters using a regular read.

Additional information such as %CPU, processor on which a task is running, etc. is retrieved from the /proc filesystem.

For the live-mode, we rely on the widespread ncurses library to refresh the screen and pretty-print information. In case the library is not available, tiptop can still be built, but only batch-mode is functional.

E. Rohou

Validation

We validated our tool in two ways. Note that our goal is not validate the hardware counters themselves, but to confirm that our tool correctly reads the values proposed by the counters.

First, we manually crafted micro-kernels for which we can analytically estimate the number of instructions (by inspecting the assembly file of a single basic-block loop), the number of cache misses or the misprediction ratio (random or periodic indirect jumps to well known locations). Tiptop reports numbers in line with predictions. We describe another such micro-benchmark in Section 3.1.

Second, we measured the total number of executed instructions of all SPEC 2006 benchmarks, with reference input, and compared with the numbers produced by Pin [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF]. We used the unmodified inscount2 example provided by the Pin distribution version 2.8. The number of instructions we obtain is on average within 0.06 % (i.e. 6 × 10 -4 ) of Pin's count.

Perturbation

There are two main methods to collect data from performance monitoring counters: counting and sampling. Counting is often referred to as an exact count, while sampling is statistical in nature. We currently use counting (see Section 4 for more discussion on sampling vs. counting).

Measurement introduces perturbation. In performance monitoring, the bias typically comes with the additional code introduced in the application to setup and read the counters. Recent work [START_REF] Demme | Rapid identification of architectural bottlenecks via precise event counting[END_REF] focused on reducing this overhead to a few instructions by directly reading the Intel x86 registers, instead of invoking a system call, and dealing with occasional overflows when they occur. While this approach clearly reduces the number of instructions and the time needed to read data from a probe, it also (slightly) modifies the code of the application. Unfortunately, it has been shown that the performance of modern architectures is very unstable, and a single nop instruction can impact the performance [START_REF] Hundt | MAO -an extensible micro-architectural optimizer[END_REF]. Mytkowicz et al. [START_REF] Mytkowicz | We have it easy, but do we have it right[END_REF] also describe the so-called observer effect: they show that the mere fact of inserting probes impacts the layout of the code, which interferes with branch predictors, instruction caches, etc. The same authors previously studied how changing the linking order of object file, or even adding a totally unrelated variable to the UNIX environment of the process can change performance in unpredictable ways, simply because the start address of process' stack changes, and cache effects differ [START_REF] Mytkowicz | Producing wrong data without doing anything obviously wrong! In 14th International Conference on Architectural Support for Programming Languages and Operating Systems[END_REF]. Other prior work [START_REF] Weaver | Can hardware performance counters be trusted?[END_REF] report on the impact of instrumentation on the result of floating point computation, and on the interaction with the virtual memory layout.

Our approach avoids these pitfalls altogether by leaving the application code untouched. No change is required in the UNIX environment either. The impact is limited to the cost of saving a few counters at context switches of the monitored tasks, and the system calls of the monitoring task (one per monitored process and per event of interest) every few seconds. The memory footprint is small: the executable for a Nehalem workstation is 40 KB (.text section is 21 KB) with support of the ncurses library, and 32 KB (.text is 16 KB) without ncurses. The tiptop process is idle most of the time between refreshes. We measured that the CPU activity of tiptop itself is below 0.06 % when refreshing every five seconds. Note that in a multicore environment, the Linux scheduler will also likely place tiptop on the least loaded core in order to further reduce interference.

Inria

We ran the entire SPEC 2006 suite, reference input, on an Intel Xeon W3550, 3.07 GHz with Linux 2.6.31 (three runs, median value reported, as per SPEC). Having tiptop run concurrently with the benchmarks resulted in a 0.7 % degradation of the score. As a comparison, we ran the entire suite ten times (three runs each, median reported) on the same idle machine and we measured that the variability across runs is 1.4 % on average. The impact of tiptop is definitely within the order of magnitude of the noise. The suite run with inscount2, as described in the previous subsection, is 1.7× slower.

Metrics and Methodology

We can compute any metrics that can be derived from performance monitoring counters available on the target hardware. The only practical limit is the number of available concurrent counters. Older machines used to have only a few counters, however newer processors have ample room for event counting. Our Intel Xeon W3550, for example, supports up to sixteen simultaneous events.

Complex metrics might be useful for advanced users, such as HPC experts or compiler writers. But we claim that, in most situations, a few simple metrics can characterize the behavior of an application. We also focus on coarse-grain samples, typically every few seconds.

The simplest metrics is probably IPC. Many pitfalls are related to IPC. In many cases, it is not a direct proxy for performance. For example, a compiler cannot be evaluated (only) by the IPC of the generated code 2 . But, from the point of view of a user given a program executable, the number of instructions (I) to execute to completion is fixed 3 . The higher the IPC, the lower the number of cycles (C), the better.

As noted by Diamond et al. [START_REF] Diamond | Making sense of performance counter measurements on supercomputing applications[END_REF], advertised peak performance is rarely attainable, and IPC is only useful when compared to a known reasonable value. A good IPC does not necessarily mean that nothing can be improved, however a low IPC is a symptom that something is wrong. Users may or may not improve it, depending on their skills, the cause for under-performance, and the steps they can take (such as recompile, migrate the process, modify the source...), but we show in Section 3 that the information is useful in many contexts.

Once we identify a performance bottleneck, several other metrics help pinpoint its cause. Our purpose in this paper is not to provide an exhaustive list of metrics, but to illustrate a methodology with a few use cases (see next section). Diamond et al. [START_REF] Diamond | Evaluation and optimization of multicore performance bottlenecks in supercomputing applications[END_REF] propose to consider two metrics: FPC (flops per cycle) and LPC (loads per cycle) to characterize respectively the CPU subsystem and the memory subsystem. Intel provides a list of "drill-down techniques for performance analysis" in §B.5 of [START_REF]Intel. Intel64 and IA-32 Architectures Optimization Reference Manual[END_REF], as well as an extensive list of event ratios of interest ( §B.6). Most of them target advanced users, but a few of them are general enough to give a high-level view of how the architecture performs. Coarse grain characteristics of the application (regardless of its behavior) can be obtained with related metrics: FPI (flops per instruction), LPI (loads per instruction), or BPI (branches per instruction). The reported instruction mix is useful in selecting the most appropriate processor in a family of binary compatible chips, for example with the Roofline methodology [START_REF] Williams | Roofline: an insightful visual performance model for multicore architectures[END_REF].

Use Cases

In this section, we illustrate with several use cases the usefulness of a tool such as tiptop, and the insights it can easily provide. We first present how we quickly diagnosed an algorithm developed by colleague biologists in the R language and running in an interpreter. We then focus on application phase behaviors and show how we can identify them, at the full running speed of the application. The third use case illustrates how we could easily reproduce and extend recently published work. Finally, we demonstrate how CPU usage can be misleading when evaluating the performance of an application, especially in a multicore environment, and we present how we can estimate the cross-process interferences.

We stress here that these use cases are purposely simple. The goal of this section is not to present new theoretical results, but to illustrate our approach on well known phenomena. Each use case also targets a different category of user.

Evolutionary Algorithm

Our first test case is an algorithm developed by biologists to model the evolution of a population subject to external factors such as temperature, growth of plants, winds, etc. The main outer loop of the algorithm represents time steps. The population is described as a large matrix where each cell represents the number of individuals in a small geographic area. Computations consist in matrix multiplications as well as scalar operations on the matrix elements. The algorithm is implemented in the R language, a system for statistical computation [START_REF] Ihaka | R: A language for data analysis and graphics[END_REF].

The algorithm was felt to run too slowly. We experimented on an Intel Xeon W3550 clocked at 3.07 GHz, Linux 2.6.31, R 2.10.1 and measured the IPC of the R interpreter when running the algorithm. We took a sample every 5 seconds. Figure 3 (a) illustrates the evolution of the average IPC over the complete run (3327 samples, 4.6 hours). The first iterations show a noisy IPC signal, but close to 1. After 953 time steps, the IPC suddenly drops to 0.03 (with brief pulses). This algorithm is iterative, each iteration performing the same amount of work, and it is not expected to have phases. Analyzing the behavior of the algorithm during the first 1.3 hours of its execution would have shown no abnormal behavior. Knowing the instant when something changed let us focus the investigation. We quickly discovered that the algorithm is not numerically stable for particular data sets, and matrices fill with infinite and NaN (not-a-number) floating points values.

On some Intel processors, floating point computations can be assisted in microcode. This is activated by the presence of non regular floating point values. It is described as "extremely slow compared to regular FP execution" in the Intel architecture manuals [START_REF]Intel. Intel64 and IA-32 Architectures Optimization Reference Manual[END_REF]. The number of executed micro-operations can be tracked by a counter. We added a new column to tiptop in order to trace simultaneously IPC and FP assist events. Figure 3 (c) illustrates a zoom on the transition between the two phases: IPC is still reported the left axis, the number of assisting micro-operation per hundred instructions is reported on the right axis (equal to zero hence invisible for the first 953 time steps). The clear correlation confirms our analysis.

We clipped the values of the matrices to force them in a finite interval at each iteration of the main loop. the value 1. The algorithm also completes in two hours, that is a 2.3× speedup. The speedup obtained on the faulty part alone is 4.8×. The impact of non-finite values can be easily verified in a controlled environment with a micro-benchmark. Consider the (simplified) source code of Figure 4: a small loop continuously adds two floating point variables x and y, which can be initialized to finite, infinite, or NaN values. We compile this code using GCC 4.4.3 at -O2 optimization level in two different configurations: gcc -mfpmath=387 produces x87 code, and gcc -mfpmath=sse uses the SSE instruction set extension (in scalar mode, no auto-vectorization is involved). Figure 5 reports the assembly code corresponding to the loop. The IPC reported by tiptop are shown in Table 1. We also show the number of instructions which required micro-operation FP assist per hundred instructions. Infinite and NaN values produce the same result and are reported together. Since the loop consists in four instructions, we confirm that all x87 floating point additions required assist (as expected by construction of the micro-benchmark). The slowdown is as large as 87× (1.33/0.015).

We also experimented on a different kind of machine: a PowerPC PPC970 clocked at 1.8 GHz and running Linux 2.6.32. The resulting IPC for the original algorithm is shown on Figure 3 (d). The PPC970 (an older machine) takes longer to complete the Obviously, the same conclusion could be drawn by adding heartbeats to the application. This requires that the source code be available, and the programmer be willing to dive into a possibly complex application to insert the markers at the right locations. Even though R is open-source, it is worth noting that we entirely handled the analysis as if it was close-source, showing that we can handle such environments.

E. Rohou

Tiptop makes it straightforward to identify in real time a sudden change in application behavior, and helps focus the analysis. In this particular case, it is interesting that a performance problem exposed a latent bug in the algorithm, which should not have diverged towards infinite values.

Application Phases

In many scenarios, it is key to monitor applications phases. Most often, CPU usage remains close to 100 % and cannot provide much insight. Simple metrics derived from hardware counters can provide more detailed information. Figures 6 and7 illustrate the IPC of several SPEC 2006 benchmarks on Intel Nehalem and Core micro-architectures, as well as PowerPC PPC970. The horizontal axis is time, with one sample per second, the vertical axis is IPC.

Such capability lets users compare the behaviors in various conditions. Figures 6 (a) and (b) and 7 (a) show that the selected benchmarks have similar behaviors on different architectures, except for the actual value of the IPC and hence the total run time. Still, slight differences exist, for example 435.gromacs (Figure 7 (b)) shows small but still noticeable variations on Nehalem, and the relative IPC of the last phases of 473.astar differ on PowerPC.

Inria

With this information, developers can quickly identify benchmarks and data sets that result in lower performance than expected, in a limited number of runs. Moreover, this can be done at full program speed, instead of using simulators or emulators. This is in contrast to earlier work on phase tracking, such as Sherwood et al. [START_REF] Sherwood | Phase tracking and prediction[END_REF], who chose to limit their study to a subset of the benchmarks because of lengthy simulations.

More advanced users can also start running their applications at full speed, and attach a debugger or analyzer (such as a Pintool [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF]) when a particular phase has started. Similarly, many papers in computer architecture are based on simulators, and benchmarks are run after skipping the first billion instructions or so to avoid the initialization phase. Carefully looking at performance profiles can help define a more accurate number of instructions for each particular combination of architecture, compiler, and compiler flags. Figure 8 illustrates the IPC for 473.astar as a function of the number of executed instructions, for three different processors. Both Intel processors execute the same binary. The PowerPC slightly shifts compared to the other two. This very simple graph helps focus the analysis on the relevant parts of the execution, making the experiments faster and the results more sensible, for example by choosing SimPoints [START_REF] Sherwood | Automatically characterizing large scale program behavior[END_REF] based not only on the similarity of basic block vectors, but also on some dynamic properties.

Obviously, phase detection can be (and has been) done in many different ways. Alternatives include code instrumentation, simulation, and other performance monitoring tools. We show here that our tool achieves the goal with unprecedented ease of use and speed.

Impact of Code Generation

Jayaseelan et al. [START_REF] Jayaseelan | Investigating the impact of code generation on performance characteristics of integer programs[END_REF] recently published work in which they study the impact of compiler technology on the performance. In particular, they measure the total number of cycles and executed instructions for the SPEC INT 2006 benchmarks, and compute the respective IPC. Among other things, they observe -not surprisingly -that the highest IPC does not necessarily characterize the fastest program.

Tiptop makes it very easy to run such an experiment and even gather more insights. We simply run the benchmarks with the reference input set while collecting the performance counter values from the observing process. The machine is an Intel Xeon W3550 (Nehalem), and the compilers are GCC 4.4.3 and icc 11.0. Results are reported in Figure 9. Similarly to Jayaseelan et al., we observe cases where a higher IPC yields better performance (cf. Figure 9 (a), 456.hmmer), and cases where performance is better despite a lower IPC (cf. Figure 9 (b), 482.sphinx3). However, we can also observe slightly more complex behaviors, such as 464.h264ref (Figure 9 (c)) where both running times are close, but two different phases are clearly visible. In the first and shortest phase, GCC produced a higher IPC, in the second phase it produces the lowest IPC. This inversion phenomenon was not visible to the authors of the original paper [START_REF] Jayaseelan | Investigating the impact of code generation on performance characteristics of integer programs[END_REF] because they observe data aggregated over the entire run of the benchmark. Finally, the executables produced by GCC and icc for 433.milc execute exactly at the same speed, even though the IPC produced by GCC is constantly higher that icc's (Figure 9 (d)).

Our purpose here is not to entirely reproduce this previous work, but to show how the approach we propose simplifies the experimental setup. These authors had to first extract traces from different parts of the program, and then validate that they capture program behaviors before running them through their in-house cycle-accurate simulator. In contrast, our approach lets us run the entire program at full speed to collect data, with much less experimental burden.

E. Rohou

Process Conflicts

Many institutions use dedicated servers for long running computations. These facilities are often referred to as data center, compute farms, grids, or more recently clouds.

Users access these facilities by submitting jobs to execution queues. A runtime system assigns priorities to the jobs and runs them according to predefined policies. Nodes are typically binary compatible, for ease of dispatching jobs, but rarely identical, simply because they were not acquired at the same time, some fail and need to be replaced, etc. The goal of the scheduler is to maximize average throughput while maintaining some level of fairness, and accommodating special requests (task x needs a 64-bit OS, task y needs at least some amount of memory and a quad-core only...) Many heuristics apply, such as increasing priority of short running processes, dedicating some nodes for long running tasks, and so on. A sensible rule of thumb is to load a node with as many jobs as there are logical cores, and to keep memory usage below the available physical memory. Our lab's setup consists in about 100 nodes. Each node is a bi-Intel Xeon. Configurations include dual-cores and quad-cores, and clock frequencies range from 1.6 GHz to 3.4 GHz. This is a production environment where researchers submit their real workloads. The scheduler is based on Sun Grid Engine (SGE) 6.2u5. It defines sixteen queues for jobs of different wall-clock run time, memory requirements, and urgency (ASAP vs. overnight). Jobs are spawned in order in each queue, the number of concurrently running jobs is limited by the number of logical cores of each node.

We have been using tiptop to monitor the behavior or workloads on all nodes. Figure 10 illustrates a snapshot of the real life of one of the nodes. Each time step represents ten seconds of execution. This particular node is an bi-quad-core Intel Xeon E5640 clocked at 2.67 GHz (Nehalem Westmere micro-architecture), with hyperthreading. We observe that user1 has two jobs running over the entire time interval, and user2 suddenly has five jobs scheduled for roughly one hour. This is a total of seven jobs, on an 8-core machine, and we controlled that the CPU usage is above 99.3 % at all times.

It is clear that the start of the second user's jobs coincides with a drop of the IPC of the first user's jobs. Between time steps 2350 and 2580 (38 minutes), they drop respectively from 1.3 to 1.05, and from 1 to 0.8, a 20 % slowdown for both, because of additional contention of the last-level cache (not shown in the figure).

We also observe an apparent interaction between the two processes of the first user, for which we do not have any explanation. The data center being a production environment, we cannot reproduce past experiments. To analyze this behavior in a controlled environment, we considered the benchmark 429.mcf from SPEC 2006, known for exercising the memory hierarchy. We first ran mcf on our quad-core Nehalem and measured the IPC. Then, we ran two copies of mcf in parallel. Finally we ran three copies in parallel (running four copies exceeds the memory). The topology of our machine is illustrated on Figure 11 (c), as produced by the hwloc software [START_REF] Franc ¸ois Broquedis | hwloc: a Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF]. When multiple copies run, we bond each instance to a given physical core using the taskset Linux utility. Figure 11 (a) reports our findings. We checked again that, at all times, the CPU usage is above 99.3 %. Still, execution time increases and IPC decreases as the number of instances increases, with up to 30 % slowdown in the case of three instances. The reason is that all cores share the last-level cache, and processes interfere, even though they run on different physical cores. The increased contention on the cache is illustrated in Figure 11 (b): each curve shows the number of cache misses on the last-level cache per hundred instructions.

As a last experiment, we ran two instances of mcf on the same physical core (i.e. on logical cores 0 and 4). While the situation is fictitious when all other cores are idle, it is realistic when the number of threads exceeds the number of physical cores. In this case, the number of L3 misses is similar to having the two processes on different cores, which is easily explained by the fact that the L3 cache is shared across all cores. The number of L2 misses increases dramatically, and causes a 2× slowdown. Figure 11 (d) illustrates the number of L2 or L3 misses per hundred instructions in the cases of one and two processes on a single core. This example shows that execution can incur a 30 % slowdown even though the CPU usage is at the maximum.

Previous works have investigated the interference between jobs scheduled on a SMT processor. Snavely and Tullsen [START_REF] Snavely | Symbiotic jobscheduling for a simultaneous multithreaded processor[END_REF] studied symbiotic scheduling. Eyerman and Eeckhout [START_REF] Eyerman | Probabilistic job symbiosis modeling for SMT processor scheduling[END_REF] later introduced probabilistic job symbiosis modeling. Both rely on Inria simulation for the experimental evaluation, and the latter requires extra hardware for the cycle accounting. In contrast, we can detect pathological (or anti-symbiotic) interaction for free and in a real system, not only at the SMT level, but also at the multicore level. Mars et al. [START_REF] Mars | Directly characterizing cross core interference through contention synthesis[END_REF] also study cross-core interferences by generating contention from a neighboring core, and measuring the sensitivity of the IPC thanks to performance counters. We differ in the fact that we do not use any contention generator, but rather observe the behavior in its real context. Also, we do not attempt to relate the contention to any particular region of the source code, but focus on simple and coarse grain metrics.

Moscibroda et Mutlu [START_REF] Moscibroda | Memory performance attacks: denial of memory service in multi-core systems[END_REF] study the contention at the DRAM level. We currently cannot observe this event for which there is no hardware counter. However, recent processors [START_REF]Intel. Intel64 and IA-32 Architectures Software Developer's Manual -System Programming Guide[END_REF] have counters for the latency of memory accesses. We plan to use them in the future to detect similar situations.

Related Work

Performance monitoring counters have recently attracted a lot of interest. Most modern processors now provide support to collect data in hardware, and many tools exist to help collect the data [START_REF] Sprunt | The basics of performance-monitoring hardware[END_REF]. The number of available countable events, and counters vary greatly across architectures [START_REF] Maxwell | Accuracy of performance monitoring hardware[END_REF]. Counters can be used in two modes: counting or sampling. Moore [START_REF] Shirley | A comparison of counting and sampling modes of using performance monitoring hardware[END_REF] compares efficiency, accuracy and bias of each method in the PAPI library [START_REF] Browne | A scalable crossplatform infrastructure for application performance tuning using hardware counters[END_REF]. The paper shows that even though sampling is known to be less accurate, counting can also be inaccurate. Our approach is currently based on counting, however setting up and reading counters is done outside the monitored applications, and we read counters at coarse time intervals, in the order of seconds, making the overhead insignificant (see also Section 2.5 about overhead and perturbation).

Several approaches have been taken to give users access to the hardware counters. PAPI [START_REF] Browne | A scalable crossplatform infrastructure for application performance tuning using hardware counters[END_REF] is a library that encapsulates low-level access to the hardware and provides an API to programmers for setting up, starting, stopping, and reading the counters. PAPI also abstracts common events and provides a convenient cross-platform standard naming for many useful events, such as cycle count, floating point instructions, etc. Other tools include Rabbit [START_REF] Heller | Rabbit: A performance counters library for Intel/AMD processors and Linux[END_REF], OProfile [START_REF]Oprofile[END_REF], libpfm and perfmon2 [1]. LiMiT [START_REF] Demme | Rapid identification of architectural bottlenecks via precise event counting[END_REF] is a very recent proposal to reduce the overhead of reading counters, by directly reading machine registers and avoiding the system call. The authors report much lower perturbation of the analyzed applications and thus observe different behaviors on commercial workloads. Demme and Sethumadhavan [START_REF] Demme | Rapid identification of architectural bottlenecks via precise event counting[END_REF] also provide a history and review of performance counters. PAPI and LiMiT both require access to the source code of the application to be monitored. LiMiT has a much faster read, but requires changes to the Linux kernel. In comparison, our approach runs on unmodified kernel and applications. Already running applications do not need to be restarted. In particular, source code is not needed, making it possible to analyze closed-source applications or libraries.

Some tools integrate the access to the performance counters with a graphical interface. Intel offers the VTune [START_REF]Technologies for measuring software performance[END_REF] performance analyzer, which samples the execution based on hardware or operating system events and combines the results with other analyzes to provide tuning advices. Similar to our approach, VTune does not require recompilation. On Windows, it can also attach to an already running process. For most events to be available, however, installation must be done by root. WAIT [START_REF] Altman | Performance analysis of idle programs[END_REF] is another tool developed by IBM to diagnose idle time in commercial workloads. It is similar to our approach in many respects: there is no need to recompile applications, or even restart them -a key requirement in commercially deployed setups -and reasoning is based on a set of simple metrics. WAIT collects its information from the Java VM, whereas we rely on hardware performance counters.

Related work [START_REF] Hundt | MAO -an extensible micro-architectural optimizer[END_REF][START_REF] Mytkowicz | We have it easy, but do we have it right[END_REF][START_REF] Mytkowicz | Producing wrong data without doing anything obviously wrong! In 14th International Conference on Architectural Support for Programming Languages and Operating Systems[END_REF] study how the insertion of probes impacts the execution of the monitored application. We discuss them in Section 2.5. In brief, our approach avoids these phenomena by not modifying the application or its execution environment.

Performance counters have also been studied in the context of multicore: Diamond et al. [START_REF] Diamond | Evaluation and optimization of multicore performance bottlenecks in supercomputing applications[END_REF] identify a few metrics that characterize the behavior of a workload on a multicore target. They also observe that traditional optimizations may be detrimental in the multicore regime. The new metrics lead them to propose a new optimization, called microfission, that specifically addresses multicore bottlenecks. The accompanying technical report [START_REF] Diamond | Making sense of performance counter measurements on supercomputing applications[END_REF] has a survey of performance measurement tools. Another aspect of parallel programs is data races. Greathouse et al. [START_REF] Greathouse | Demand-driven software race detection using hardware performance counters[END_REF] propose to rely on hardware counters to limit the overhead of dynamic race detectors. Our approach focuses on simple metrics that can be of immediate use to the vast majority of users.

Optimization developers also have an interest in performance counters. Hundt et al. [START_REF] Hundt | MAO -an extensible micro-architectural optimizer[END_REF] rely on counters to understand how apparently benign modifications of the assembly code impacts performance on complex x86/64 micro-architecture, and to drive the development of assembly-level optimizations in the MAO tool. Cavazos et al. [START_REF] Cavazos | Rapidly selecting good compiler optimizations using performance counters[END_REF] have been using counters to characterize benchmarks. They use machine learning to derive a good set of code transformations. While we do not propose any optimization in our work, we also use counters to hint at possible causes for bad performance. Jayaseelan et al. [START_REF] Jayaseelan | Investigating the impact of code generation on performance characteristics of integer programs[END_REF] study the effect of compiler technology on integer SPEC workloads. Their study reports total number of occurrences for each particular event. As shown in Section 3.3, our approach could give more insight by showing real-time evolution of the metrics and comparing phases instead of only a global aggregated value.

The tools that appear closest to our proposal are Linux's perf [START_REF] Carvalho De Melo | Performance counters on Linux[END_REF] and Intel's PMC. Perf runs a command and records performance counter statistics from it. Raw data can then be processed to produce various reports, such as the number of events in each function or the time spent in kernel functions. In contrast to our solution, perf needs to start the application itself, and cannot attach to an already running process. Intel's PMC is also similar to our tool in that it periodically displays the number of occurring events, such as IPC, and cache misses at various levels or the memory hierarchy. However it requires root privilege, it supports only the Westmere/Nehalem micro-architecture, and it shows the total number of events per logical core, not per process.

Conclusion

This paper is concerned with users facing the increasing complexity of computing systems at many levels: architecture, hypervisor, operating systems, compilers, etc. On the one hand, complexity is the means for increased performance. On the other hand, it is becoming more difficult for users to have an understanding of how well applications perform. We advocate that performance monitoring counters can be helpful even for non-expert users to obtain a better understanding of the relative performance of applications, and we propose tiptop: a new tool, similar to the UNIX top utility, that requires no special privilege and no modification of applications. Tiptop provides more informative estimate of the actual performance than existing UNIX utilities, and better ease of use than current tools based on performance monitoring counters. With several use cases, we have illustrated possible uses of such a tool.

Figure 1 :

 1 Figure 1: Snapshot of processes (anonymized) running in our data center

Figure 2 :

 2 Figure 2: Linux system call

Figure 3 :

 3 Figure 3: IPC of R emulator

#

  i n c l u d e <math . h> d o u b l e x , y ;v o i d i n i t f i n ( ) { x = -1.0; y = 1 . 0 ; } v o i d i n i t i n f ( ) { x = 0 . 0 ; y = INFINITY ; } v o i d i n i t n a n ( ) { x = -INFINITY ; y = INFINITY ; } i n t main ( i n t a r g c , char * a r g v [ ] ) { d o u b l e z = 0 . 0 ; i n i t X X X ( ) ;/ * c h o o s e i n i t v a l u e s h e r e * / f o r ( i = 0 ; i < max ; i ++) z += x + y ; r e t u r n 0 ; }

Figure 4 :

 4 Figure 4: Micro benchmark to measure impact of non-finite FP values

Figure 5 :

 5 Figure 5: Assembly code of micro benchmark

Figure 6 :Figure 7 :

 67 Figure 6: IPC of 429.mcf and 473.astar

Figure 8 :Figure 10 :Figure 11 :

 81011 Figure 8: IPC versus the number of executed instructions for 473.astar

2 . 6

 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Perturbation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Metrics and Methodology . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Use Cases 8 3.1 Evolutionary Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Application Phases . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Impact of Code Generation . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Process Conflicts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Campus universitaire de Beaulieu 35042 Rennes Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

Table 1 :

 1 Measured behavior of the floating point micro benchmark

	finite		infinite/NaN
	IPC %FP assist	IPC %FP assist
	x87 1.33	0 0.015	25%
	SSE 1.33	0	1.33	0

RR n°7789

Non-privileged users can only watch processes they own. Ability to monitor anybody's process opens the door to side-channel attacks[START_REF] Daniel | Cache-timing attacks on AES[END_REF][START_REF] Bertoni | AES power attack based on induced cache miss and countermeasure[END_REF].RR n°7789

What really matters is the total number of cycles; poor code generation might add useless independent instructions that artificially inflate the IPC without making the program run any faster.

Multithreaded applications relying on spinlocks require special handling, since more instructions spent waiting mean lower performance.RR n°7789

Acknowledgements

We would like to thank our colleagues from the ALF project-team for the fruitful discussions, as well as the staff operating the compute grid for their support in the collection of data.


Jens Gustedt

Emmanuel Jeanvoine

Relaxed Synchronization with Ordered Read-Write Locks *

Keywords: synchronization, iterative algorithms, read-write locks, experiments

This paper promotes the first stand-alone implementation of our adaptive tool for synchronization ordered read-write locks, ORWL. It provides new synchronization methods for resource oriented parallel or distributed algorithms for which it allows an implicit deadlock-free and equitable control of a protected resource and provides means to couple lock objects and data tightly. A typical application that uses this framework will run a number of loosely coupled tasks that are exclusively regulated by the data flow. We conducted experiments to prove the validity, efficiency and scalability of our implementation.

Synchronisation à contraintes reduites avec des verrous lecture/écriture ordonnés

Résumé :

Ce papier prsente la premire implantation directe de notre outil adaptatif de synchronisation, ordered read-write locks (ORWL). Il fournit des mthodes nouvelles de synchronisation pour des algorithmes parallle ou reparties orients ressources. Il permet un contrle implicite d'une ressource protge qui est quitable et sans interblocage et fournit des moyens de coupler des objets de verrou et des donnes de faon stricte. Une application typique qui utilise ce cadre va effectuer un nombre de tches couples de faon relche et qui seraient exclusivement rguls par le flot des donnes. Nous avons conduit des expriences qui prouvent la validit, l'efficacit et le passage l'chelle de notre implantation.

Mots-clés : synchronisation, algorithmes itératifs, verrous lecture/écriture, expériences

Introduction

Lock or token based mechanisms to protect shared resources have a long tradition in parallel distributed computing. They are closely integrated into nowadays operating systems (POSIX mutex, semaphores and read-write locks), run times (OpenMP), and higher level languages (Java). They act on shared objects (POSIX rwlock), file ranges, or distributed entities (Corba, Chord, read-write locks [START_REF] Wagner | Token-based read/write-locks for distributed mutual exclusion[END_REF]).

In contrast to implicit methods such as atomic snapshots or transactional approaches, see [START_REF] Vitányi | Atomic shared register access by asynchronous hardware[END_REF][START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Herlihy | Transactional memory: Architectural support for lock-free data structures[END_REF], they require an explicit action by the programmer or algorithm designer to mark the parts of her/his code that is judged critical. This paper is based on the assumption that such a labeling of critical parts will be provided. On a longer time scale the tool presented here might be a good basis to do such annotations automatically, but such an automatic annotation is not the subject of this paper.

Many parallel or distributed computations follow data dependency patterns between their different computation tasks [START_REF] Barrett | Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods[END_REF]. Usually the output of one task (producer) is taken as input of other tasks (consumers), but write access (of the producer) and read access (of the consumer) to that data cannot be done atomically. This can occur in a shared memory setting where the data is too large to be accessible in one atomic read or in a distributed setting where data is sent and received in slices.

Algorithmically, the commonly implemented tools that we mention above are unsatisfactory with respect to at least one of the following three properties:

Liveness: Guarantees for liveness can in general not be given easily. Usually it needs supplementary tools such as barriers that come with an important cost whence they inhibit dynamic optimizations by the run time. Sporadic deadlocks are common software bugs that are quite costly to debug.

Equity: In case of contention, tools such as POSIX' reader-writer lock or semaphores voluntarily leave the order of lock acquisition either to the system implementation (in the simplest cases) or to the scheduling policy. If the order of treatment by different subtasks is fixed by the algorithm designer and may even be cyclic, guaranteeing equity and a precise flow of control can be challenging.

Efficiency: Using a lock structure (a mutex in the simplest case) introduces fixed points in the program between which a resource needs to be accessible. It usually gives no explicit indication to the run-time which resource is targeted and also what could be done proactively to represent the resource in the address space of the program. Possibilities of overlapping computation and communication (in a broad sense) are easily lost by that, exploiting such possibilities can become tedious to implement. Again in the simplest case of a mutex, a resource is only fetched and pushed when it is accessed where usually the transfer from one task P 1 to another P 2 could be done as soon as P 1 unlocks the mutex.

To target the three criteria from above, in [START_REF] Clauss | Experimenting Iterative Computations with Ordered Read-Write Locks[END_REF][START_REF] Clauss | Iterative Computations with Ordered Read-Write Locks[END_REF] we introduced the framework of ordered read write locks, ORWL, that are designed to favor algorithmic control and data consistency. This framework for inter-task synchronization is conceptually independent of the execution context and can be implemented in both shared memory or distributed environments.

A first adhoc implementation of this tool was integrated as part of the parXXL library and is only fully available for shared memory. This paper here presents a new implementation that is only based on standard languages and interfaces (C and POSIX) and that can be used in shared, distributed or mixed contexts.

The basics of our model and the designs of the underlying tool for iterative parallel algorithms are briefly reviewed in Section 2, in particular we remind the features that guarantee liveness and equity for iterative settings. Then, in Section 3, we present the three different features that distinguish the use of ORWL from other tools: the possibility to announce the future use of a resource, a comfortable interface for iterative computations and a tight binding between control structures and data. In Section 4, we present benchmarks that address the potential overhead that our implementation introduces. Finally, we conclude and discuss our next steps in Section 5.

Ordered Read-Write Locks, an Adaptive Tool for Synchronization

We call the building block of our model Ordered Read-Write Locks (ORWL), a special kind of read-write locks. All proofs on properties of the model have been presented in [START_REF] Clauss | Iterative Computations with Ordered Read-Write Locks[END_REF]. ORWL have the following features:

1. A waiting queue with FIFO-policy.

2. An explicit association of a lock with application data.

3. A distinction between request and acquire operations that replace a classical one-step lock operation. So the typical sequence for an access is request, acquire and then release.

4.

A distinction between locks (as opaque objects) and lock-handles (as user interfaces acting on locks).

5.

A distinction into exclusive or write locks and inclusive or read locks.

All of these features have been used previously for lock data structures, see e.g [START_REF] Danek | Closing the complexity gap between FCFS mutual exclusion and mutual exclusion[END_REF]. But to the best of our knowledge their intentional combination in a single framework is original. Property 1 and 2 together ensure a controlled access order of the application to its data. For an important class of applications that will iterate over their data, we must be able to control when and what data is accessed. In addition, Property 2 restricts the access to the data to the time that a lock is held, pointers become invalid outside that time window. We thus enforce data consistency: no thread may write to data that it has not locked and if a read is granted to data it is guaranteed to be invariant while the lock is held.

Property 3 allows us to reserve resources pro-actively. At first, this gives the application programmer the possibility to issue some sort of hint (a request operation) that a resource will be used in the future with a require operation. Such a hint is non-blocking and incurs only negligible cost by itself. This is Inria a big advantage for the programming logic of iterative algorithms which access data in a cyclical pattern. They may insert their request for the next iteration in the FIFO while holding a lock for the current one. The other advantage lies in performance issues. The run time system then may use this information to anticipate the access, e.g by doing a data prefetch.

When doing such a pro-active locking the Property 4 comes into play: a thread or process may define several handles (usually two in our case) on the same lock and thereby newly request a lock by means of one handle while still actively holding a lock via another handle. The type of request in view of Property 5, namely if the access will be just for reading (and thus potentially shared) or for writing must be specified when the lock is requested and that type is kept track via the handle.

Property 5 ensures that we may easily handle the case that the output of a task is read by several others. It allows for important optimizations: buffer space with read-only data can be shared among threads and processes; data that is only presented for reading may be thrown away once the lock is released and thus costly updates (or just checks for consistency) may be avoided.

Recurring tasks.

To model a recurring task of an iterative process we proceed as follows. Whenever all the lock requests that such a task has requested have been acquired, the task is said to be active and can perform its job.

After finishing the computation of the job itself, before releasing any of the locks, a second set of lock handles is used to posts copies of its requests for the next iteration, first. These guarantee the reservation of the resources for the next iteration. The task then releases the acquired locks to pass the control over to other tasks that operate on the same data. This procedure guarantees that access to the resources is given in a cyclic pattern and thus that all tasks iteratively get access to the data in an equitable way, see [START_REF] Clauss | Iterative Computations with Ordered Read-Write Locks[END_REF]. Ensuring liveness of such system needs an additional effort. It has been shown that for this property the initialization order of the lock handles in the FIFO is crucial. Any initialization that doesn't contain certain types of cyclic dependencies never will run into a deadlock and that such an initialization is always possible.

User interfaces

This section will introduce a handful of data types and functions that compose the user interface of ORWL. There are three data types: orwl mirror a representation of a local or remote resource.

orwl handle a lock handle to queue up for that resource, and orwl handle2 a pair of lock handles used for recurrent locking requests.

The function interfaces can be classified in three different sets:

❼ orwl read request (or orwl write request), orwl acquire (or orwl test)

and orwl release that form a lock sequence on the resource.

❼ orwl truncate, orwl write map and orwl read map that allow to control and access the data that is eventually associated to a resource.

❼ A set of analog functions with a "2" appended to the name that operate on pairs orwl handle2, such as orwl read request2 or orwl write map2. They suit particularly the needs for iterative tasks.

Resource protection

Simple resource protection that is analogous to a protection of a critical section through a mutex can be implemented in a straight forward manner. ✝ ✆ Here the first call to orwl write request binds handle to resource loc and announces the intent to access it. Until the time we call orwl acquire the system may satisfy other demands to the resource that have higher priority, ❼ route the corresponding data to our host ❼ allocate space in our address space or ❼ perform other operations that are needed to satisfy the demand.

During that time the application can perform any type of operation that doesn't need access to the resource.

Then, once the application comes to a point it can't proceed further without the resource, orwl acquire ensures that it is blocked until the request can be fulfilled. The critical section then ends by calling orwl release.

If the application has a variety of tasks to perform before access to the resource can't be avoided further, orwl test can be used to query for the lock acquisition and allows to adapt the application at run time, see Listing 2.

Associating data

Up to now we have introduced a use of ORWL that only uses its controlling aspect, analogous to POSIX' pthread mutex t or pthread rwlock t. In addition to that ORWL allows one to associate data to the resource directly, Listing 3. ✝ ✆ To associate data to a resource we just have to assign a non-zero size to the data (here 168 units for the type uint64 t). Per default the data is initialized to all zero values, in the example it is initialized by a special function. Data is viewed as untyped bytes (void*) and the size returned by orwl write map accounts the number of bytes in the data. To ease the underlying communication routines, data sizes are always multiples of sizeof(uint64 t), usually 8 bytes.

Inria

Another task or process may then modify the data without changing its size, Listing 4, and any number of readers may inspect the results of that modification simultaneously, see Listing 5.

Recurrent access to resources

Iterative computations need to be implemented with a lot of care if we want to guarantee liveness for all processes and equity among them. As introduced above ORWL, as an abstract tool can guarantee these properties if we issue a lock request on a resource for the next iteration before we abandon a current lock that we hold. This is facilitated by our library with the type orwl handle2.

It represents a pair of orwl handle that are used in alternation for even and odd numbered iterations. ✝ ✆ Here, before entering into the iteration, we bind the first handle of the pair to the resource. Then, at the start of each iteration the handle in the pair with the request pending is acquired and we gain exclusive access to the resource. At the end of the iteration orwl release2 first issues a new request on the handle that is currently inactive and then releases the lock on the resource. When going out of the iteration, orwl cancel2 has to be called since otherwise one of the handles in the pair would be left with a pending lock request. / ✯ w i t h d r a w f r o m t h e q u e u e s ✯/ ✝ ✆ Finally, with Listing 7, let into a more complicated pattern, namely with two resources and two pairs of handles that act on them. This can be seen as each process "owning" one resource (called hereResource) that he will update and "inspecting" one resource of a "neighboring" process (thereResource). The access pattern between different processes could then be any collection of directed circles or trees. The basic scheme is similar, only that always two calls to orwl acquire2 and orwl release2 are issued in the iteration, one for each resource. Using the mapping feature of ORWL we see how we easily can implement an iterative vector averaging on the associated data.

Experiments

Benchmark application

Livermoore Loops Kernel 23

To benchmark the library, we use the Livermoore Loops Kernel 23 (LLK23) benchmark (see http://www.netlib.org/benchmark/livermorec).

Listing 8: Core computation of the Livermoore Loops Kernel 23 benchmark.

✞ f o r ( i = 2 ; i < (N -1 ) ; ++i ) { f o r ( j = 2 ; j < (M -1 ) ; ++j ) { q = d a t a [ i -1 ] [ j ] • zb [ i ] [ j ] + d a t a [ i ] [ j -1] • z v [ i ] [ j ] + d a t a [ i ] [ j +1] • zu [ i ] [ j ] + d a t a [ i + 1 ] [ j ] • z r [ i ] [ j ] + z z [ i ] [ j ] -d a t a [ i ] [ j ] ; d a t a [ i ] [ j ] += 0 . 1 7 5 • q ; } } ✝ ✆
The core computation of the benchmark is given in Listing 8. To simplify, each element of a matrix called data is computed using four neighbors elements (N, S, E and W) and five coefficient matrices (zb, zr, zu, zv, zz).

This application has significant characteristics to test our approach. It is an iterative computation of which the different parts can be executed asynchronously and where each part shows constant progress. Furthermore, for a parallelization, some data exchange is required between the frontiers. This can be done transparently with ORWL; the nested for loops of Listing 8 would go in the place marked "application code" in Listing 7.

Inria

Parallelization with ORWL

An intuitive method to parallelize the problem is to decompose data into several blocks. For each block, the inner computation is independent from the other blocks whereas the computation of the edges and the corners depends on some neighboring blocks.

Thus, for each block, we define a main task (MT) that performs the compuand eight sub-tasks (ST) that are used to export the frontier data (edges and corners) to the neighboring MT. Figure 1 shows an example of a simple decomposition into four blocks. The four MT are numbered from 0 to 3 and the associated ST are prefixed with their direction.

Experimental Results

The experiments have been conducted on the graphene cluster of the Grid'5000 experimental testbed. Each node is composed of 4 cores at 2.53 GHz and 16 GiB of memory, and a Gigabit Ethernet interconnection network. All the following results are obtained after running 100 iterations of the LLK23 computation.

Average execution time per matrix element

In this experiment, the goal is to evaluate the average execution time per data element. First, we divide data in 4, 16, 36, 64 and 100 blocks. Then, for each division, we increase the global problem size by varying the size (in number of elements) of a block. One node is reserved for each block, such that we can reach the limit of a maximum block size that fits into RAM.

In Figure 2(a) we see that the computation cost per element decreases when the problem size increases, and that it tends to a lower limit. We note that the times corresponding to the 4 block division are below the others. This is due to the simplified connection pattern (see Figure 1) where half of the block boundaries don't participate in communication. The other running times are not distinguishable, which proves that for subdivisions into more parts this effect is already negligible.

Computation efficiency

Because our parallelization of LLK23 requires frontiers of neighboring regions, not all parallel tasks can compute simultaneously. In this experiment, see Figure 2(b), the goal is to relate the time that MT spends either to compute or to wait for some frontier data. The setup is the same as in the previous experiment. We see that for small problems, almost all the time is spent to wait. For larger problems, the computation time increases and finally reaches about 55 % of the total time. Actually, the absolute wait time itself (not shown) is basically spent in orwl acquire2 and does not vary much, but the computation partially overlaps with these waiting periods.

Overcommitting

In this experiment the global problem size is constant, 4000 × 4000 elements per blocks with a division into 64 blocks. We launch the computation successively on 64, 32, 16, 8 and 4 nodes; thus commit 1, 2, 4, 8 and 16 MT per quad-core node. The average time to compute an iteration is shown in Figure 2(c). We can see that the overcommitment of several tasks per cores allows to take full advantage of the four cores of each node. The time per iteration only increases slightly when we have much more MT per core.

So, even if the parallelization induces long waiting times for the tasks, ORWL is able to hide this cost: tasks that have received their data autonomously start their execution while other tasks are waiting for theirs.

Scalability

In this last experiment we study the impact of increasing the global problem size. We place 16 MT per quad-core node on 4 to 64 nodes. Each MT computes a 3000x3000 element block. The average time to compute an iteration is shown in Figure 2(d). We see that increasing the problem size does not increase the average computation time much. Thus, ORWL is suitable for the construction of scalable applications.

Conclusion and future work

In this paper we introduced a new library that implements the ordered readwrite lock (ORWL) paradigm to control access to shared or distributed resources. We presented the basic use patterns for that library that ranges from simple implementations of critical sections that allow a pro-active announcement to more involved patterns of alternating resource allocation in iterative computations. Macro-benchmarks show that the library behaves well on multi-core machines and clusters; it realizes almost perfect computation/communication overlap and weak scaling properties.

A forthcoming article will describe the implementation of the library in more detail and present micro-benchmarks of the individual functions and components. Future plans with ORWL include application to other types of applications and architectures. Namely we are currently implementing an application that uses ORWL to control computations on compute cluster equipped with Inria

Listing 1 :

 1 Simple exclusive protection of a resource loc through a handle handle. ✞ o r w l w r i t e r e q u e s t (& l o c , &h a n d l e ) ; / ✯ a n n o u n c e f u t u r e a c c e s s ✯/ / ✯ s o m e o p e r a t i o n w i t h o u t t h e r e s o u r c e ✯/ o r w l a c q u i r e (& h a n d l e ) ; / ✯ B l o c k u n t i l g r a n t e d ✯/ / ✯ s o m e c r i t i c a l o p e r a t i o n w i t h l o c k e d r e s o u r c e ✯/ o r w l r e l e a s e (& h a n d l e ) ; / ✯ F r e e t h e r e s o u r c e ✯/

Listing 2 :

 2 Adapted protection of a resource loc through a handle handle. ✞ o r w l r e a d r e q u e s t (& l o c , &h a n d l e ) ; / ✯ a n n o u n c e f u t u r e r e a d ✯/ w h ile ( ! o r w l t e s t (& h a n d l e ) ) { / ✯ c h e c k i f p r o d u c e d ✯/ / ✯ Do s o m e o p e r a t i o n w h i l e t h e r e s o u r c e i s p r o d u c e d ✯/ } o r w l a c q u i r e (& h a n d l e ) ; / ✯ b l o c k u n t i l g r a n t e d ✯/ / ✯ Do s o m e o p e r a t i o n w h i l e t h e r e s o u r c e i s s t a b l e ✯/ o r w l r e l e a s e (& h a n d l e ) ; / ✯ f r e e t h e r e s o u r c e ✯/ ✝ ✆

Listing 3 :

 3 Associate data to loc and initialize it properly. ✞ o r w l w r i t e r e q u e s t (& l o c , &h a n d l e ) ; / ✯ r e s e r v e t h e r e s o u r c e f o r m a i n t e n a n c e ✯/ o r w l a c q u i r e (& h a n d l e ) ; o r w l r e s i z e (& h a n d l e , 1 6 8 ✯ s i z e o f ( u i n t 6 4 t ) ) ; / ✯ w r i t e a c c e s s i s n e e d e d t o ✯/

Listing 4 :Listing 5 :

 45 Modify the data. ✞ o r w l w r i t e r e q u e s t (& l o c , &h a n d l e ) ; / ✯ r e s e r v e t h e r e s o u r c e f o r m o d i f i c a t i o n ✯/ o r w l a c q u i r e (& h a n d l e ) ; s i z e t s i z e ; / ✯ g e t a p o i n t e r t o t h e d a t a ✯/ u i n t 6 4 t ✯ d a t a = o r w l w r i t e m a p (& h a n d l e , & s i z e ) ; / ✯ i n o u r a d d r e s s s p a c e ✯/ s i z e /= s i z e o f ( ✯ d a t a ) ; f o r ( s i z e t i = 0 ; i < s i z e ; ++i ) { / ✯ d o s o m e o p e r a t i o n w i t h ✯/ d a t a [ i ] ✯= i ; / ✯ e x c l u s i v e a c c e s s ✯/ } o r w l r e l e a s e (& h a n d l e ) ; / ✯ f r e e t h e r e s o u r c e ✯/ d a t a = 0 ; / ✯ i n v a l i d a t e t h e p o i n t e r ✯/ ✝ ✆ Access the associated data. ✞ o r w l r e a d r e q u e s t (& l o c , &h a n d l e ) ; / ✯ r e s e r v e t h e r e s o u r c e f o r r e a d i n g ✯/ o r w l a c q u i r e (& h a n d l e ) ; s i z e t s i z e ; / ✯ g e t a p o i n t e r t o t h e d a t a ✯/ u i n t 6 4 t c o n s t ✯ d a t a = o r w l r e a d m a p (& h a n d l e , & s i z e ) ; / ✯ i n o u r a d d r e s s s p a c e ✯/ s i z e /= s i z e o f ( ✯ d a t a ) ; f o r ( s i z e t i = 0 ; i < s i z e ; ++i ) { / ✯ s o m e o p e r a t i o n w h i l e ✯/ p r i n t f ( s t d e r r , " i t e m %zu i s %" PRIu64 " \n " , / ✯ t h e r e s o u r c e ✯/ i , d a t a [ i ] ) ; / ✯ i s s t a b l e ✯/ } o r w l r e l e a s e (& h a n d l e ) ; / ✯ f r e e t h e r e s o u r c e ✯/ d a t a = 0 ; / ✯ i n v a l i d a t e t h e p o i n t e r ✯/ ✝ ✆

Listing 6 :

 6 A simple iterative procedure with one resource and one orwl handle2. ✞ o r w l w r i t e r e q u e s t 2 (& l o c , &h a n d l e 2 ) ; / ✯ b i n d t h e p a i r ✯/ w h i le ( ! done ) { / ✯ d o u n t i l s o m e e x t e r n a l e v e n t ✯/ o r w l a c q u i r e 2 (& h a n d l e 2 ) ; / ✯ b l o c k u n t i l o u r t u r n c o m e s ✯/ / ✯ w o r k e x c l u s i v e l y w i t h t h e r e s o u r c e ✯/ / ✯ i n s e r t o u r s e l v e s i n t h e q u e u e ✯/ o r w l r e l e a s e 2 (& h a n d l e 2 ) ; / ✯ f o r t h e n e x t i t e r a t i o n ✯/ / ✯ f r e e t h e r e s o u r c e ✯/ / ✯ p a s s c o n t r o l t o s o m e b o d y e l s e ✯/ } o r w l c a n c e l 2 (& h a n d l e 2 ) ; / ✯ w i t h d r a w f r o m t h e q u e u e ✯/

Listing 7 :

 7 An iterative procedure with two resources and two orwl handle2. ✞ o r w l w r i t e r e q u e s t 2 (& h e r e R e s o u r c e , &h e r e ) ; / ✯ b i n d t h e t w o p a i r s ✯/ o r w l r e a d r e q u e s t 2 (& t h e r e R e s o u r c e , &t h e r e ) ; w h ile ( ! done ) { / ✯ u n t i l s o m e e x t e r n a l e v e n t ✯/ o r w l a c q u i r e 2 (& h e r e ) ; o r w l a c q u i r e 2 (& t h e r e ) ; / ✯ b l o c k t w i c e ✯/ s i z e t s i z e ; / ✯ t h e d a t a a c c e s s i s ✯/ u i n t 6 4 t ✯ h e r e D a t a = o r w l w r i t e m a p 2 (& h e r e , & s i z e ) ; / ✯ e x c l u s i v e h e r e ✯/ u i n t 6 4 t c o n s t ✯ t h e r e D a t a = o r w l r e a d m a p 2 (& t h e r e , & s i z e ) ; / ✯ i n c l u s i v e t h e r e ✯/ s i z e /= s i z e o f ( ✯ t h e r e D a t a ) ; / ✯ application code: ✯/ f o r ( s i z e t i =0; i <s i z e ; ++i ) { / ✯ a v e r a g e c o m p o n e n t w i s e ✯/ h e r e D a t a [ i ] = ( h e r e D a t a [ i ]+ t h e r e D a t a [ i ] ) / 2 ; / ✯ s t o r e i n h e r e R e s o u r c e ✯/ } / ✯ i n s e r t o u r s e l v e s i n t h e q u e u e s ✯/ o r w l r e l e a s e 2 (& h e r e ) ; / ✯ f o r t h e n e x t i t e r a t i o n ✯/ o r w l r e l e a s e 2 (& t h e r e ) ; / ✯ f r e e t h e r e s o u r c e s ✯/ / ✯ p a s s c o n t r o l t o t h e o t h e r s ✯/ } o r w l c a n c e l 2 (& h e r e ) ; o r w l c a n c e l 2 (& t h e r e ) ;

Figure 1 :

 1 Figure 1: A four block decomposition example. The gray parts represent the MT parts that require some frontier data to be computed. Hatched parts are constant boundary conditions or unused.

RR n➦ 7790

rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgment

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).