# PCERE: Fine-grained Parallel Benchmark Decomposition for Scalability Prediction

Mihail Popov, Chadi Akel, Florent Conti, William Jalby, Pablo de Oliveira Castro

► To cite this version:

Mihail Popov, Chadi Akel, Florent Conti, William Jalby, Pablo de Oliveira Castro. PCERE: Fine-grained Parallel Benchmark Decomposition for Scalability Prediction. 2015 IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2015, Hyderabad, India. 10.1109/IPDPS.2015.19 . hal-01417304

HAL Id: hal-01417304

https://uvsq.hal.science/hal-01417304v1

Submitted on 6 Nov 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
PCERE: Fine-grained Parallel Benchmark
Decomposition for Scalability Prediction

Mihail Popov, Chadi Akel, Florent Conti, William Jalby, Pablo de Oliveira Castro

Université de Versailles Saint-Quentin-en-Yvelines

Exascale Computing Research

Versailles, France

{mihail.popov,florent.conti,william.jalby,pablo.oliveira}@uvsq.fr

chadi.akel@exascale-computing.eu

**Abstract**—Evaluating the strong scalability of OpenMP applications is a costly and time-consuming process. It traditionally requires executing the whole application multiple times with different number of threads. We propose the Parallel Codelet Extractor and REplayer (PCERE), a tool to reduce the cost of scalability evaluation. PCERE decomposes applications into small pieces called *codelets*: each codelet maps to an OpenMP parallel region and can be replayed as a standalone program. To accelerate scalability prediction, PCERE replays codelets while varying the number of threads. Prediction speedup comes from two key ideas. First, the number of invocations during replay can be significantly reduced. Invocations that have the same performance are grouped together and a single representative is replayed. Second, sequential parts of the programs do not need to be replayed for each different thread configuration. PCERE codelets can be captured once and replayed accurately on multiple architectures, enabling cross-architecture parallel performance prediction. We evaluate PCERE on a C version of the NAS 3.0 Parallel Benchmarks (NPB). We achieve an average speed-up of 25 × on evaluating OpenMP applications scalability with an average error of 4.9% (median error of 1.7%).

**Keywords**—OpenMP applications; program replay; checkpoint restart; parallel code isolation; scalability prediction; cross-architecture performance prediction

# I. INTRODUCTION

Parallel applications are costly to measure and optimize. In this paper, we propose a decomposition technique that partitions OpenMP applications into small pieces called *codelets* and uses them to accelerate the benchmarking. Each independent parallel region is extracted as a codelet that can be replayed as a standalone program. Instead of studying the whole application, we focus on each codelet separately.

We propose PCERE, an Intermediate Representation (IR) level parallel code extractor based on the Low Level Virtual Machine (LLVM) [1]. PCERE is an OpenMP extension of the Codelet Extractor and REplayer (CERE) [2]. PCERE automatically isolates the parallel regions of an OpenMP application and allows each one to be replayed separately.

Benchmarking isolated parallel regions instead of whole applications is attractive because the user can concentrate on each codelet separately, with a reduced build and run cost. Codelets can be individually modified to evaluate the payoff of new optimizations or runtime parameters such as the number of threads or the thread affinity. Different codelets may expose different performance bottlenecks, and react differently

to optimizations. Isolating codelets allows tuning performance at a fine-grain level.

PCERE codelets can also be used for fast parallel performance prediction. We propose a model that predicts strong scalability of parallel regions and applications in average 25 times faster than by running the original program. This speedup is based on the two following key insights:

* A single OpenMP parallel region may be executed multiple times in an application lifetime. Invocations sharing similar execution contexts have the same performance. Therefore, a single invocation replay is sufficient to characterize the region execution time. Codelets exploit this idea as they can be directly replayed as few times as we want. This method is usable only if the execution time of a parallel region remains the same over different invocations.

* When varying the number of threads, performance of sequential regions is not strongly impacted. With codelets, scalability can be computed by only replaying parallel regions; there is no need to replay the sequential parts with different number of threads.

To predict the strong thread scalability of an application, PCERE partitions it into codelets which are then replayed with varying number of threads. A model based on Amdahl's law predicts the whole application scalability.

Parallel codelets can be replayed on micro-architectures different from the one in which they were captured. Therefore PCERE is able to predict the scalability on different target micro-architectures.

Codelet based performance evaluation is only viable if the codelets faithfully capture the original application behavior. In this paper we show that PCERE faithfully replays the C-only version of the NAS Parallel Benchmarks [3] on different architectures with different number of threads.

The current PCERE version only supports C or C++ OpenMP applications. Most of the NPB 3.0 are written in Fortran. To evaluate PCERE we propose an unofficial C version of the NPB 3.0 OpenMP that is built upon the NPB OMP 2.3 C version from the Omni Compiler Project [4].

The contributions of this paper are:

* PCERE: an open-source framework that extracts and replays parallel regions codelets (Section III)
* A pure C version of the NPB OpenMP (Section IV-A)

* A systematic evaluation of PCERE replay accuracy on the NPB OpenMP on three different architectures with varying number of threads (Section IV-B).

* A fast scalability prediction model based on parallel codelets (Section V).

## II. BACKGROUND

This section discusses the relevant background for parallel code extraction. First, we present the concept of code isolation. Second, we show how compilers turn OpenMP directives into parallel code. Third, we discuss how to apply code isolation to OpenMP programs.

### A. Code Isolation

Code isolation was proposed originally by Lee et al [5] as a method to quickly debug and tune large applications. Usually, in scientific applications, the hotspots represent a small fraction of the total source lines [6]. Code isolation finds and extracts the hotspots of an application as standalone *codelets*. Codelets can be compiled and replayed independently from the original application. For each codelet, the isolation process captures the memory working set and the relevant machine state such as the cache contents to achieve realistic replays.

Code isolation has been used to tune compiler options [7] or to accelerate architecture selection [8]. Nevertheless, most of the code isolation frameworks [5], [9], [10], [11], [12] target sequential programs. PCERE extends the concept of code isolation to multi-threaded OpenMP programs. Parallel code isolation is discussed in section VI-A.

### B. OpenMP Compiler Support

In OpenMP programs, the application concurrency is described through a set of compiler directives and library calls. For instance, a parallel region can be declared using the directive `#pragma omp parallel`. Figure 1 shows a simple C OpenMP program where each thread prints its thread identifier.

PCERE is based on the LLVM compiler infrastructure [1], which includes preliminary support for OpenMP 4.0 [13] since version 3.4. Compiling and linking an OpenMP application under LLVM requires the following steps:

1) **Translation to IR** The Clang front-end transforms C or C++ code into LLVM IR.

2) **Code Optimization** LLVM optimizations passes are applied to the IR.

3) **Object generation and linking** The IR is transformed into object code and linked with the Intel/LLVM OpenMP runtime library [14].

In most compilers, including GCC and LLVM, parallel directives are expanded in the front-end before doing any code optimization [15]. Usually, the first step in OpenMP expansion is outlining parallel regions. To outline a region the compiler moves the region code inside a separate function. The compiler preserves data dependencies by passing live-in and live-out values through the outlined function arguments. Then

the original region is replaced by a call that spawns multiple threads running the outlined function.

Figure 1 shows how LLVM expands a simple OpenMP directive and the IR code it produces. LLVM outlines the region code in a *microtask* function. `kmpc fork`, an OpenMP Runtime library function, spawns a pool of threads. Then, every thread runs the outlined *microtask* function which describes the region parallel work.

### C. Partitioning OpenMP Programs into Codelets

Parallel codelets should satisfy three important properties. First, each codelet must capture a specific region of code in the original application. Second, it should be possible to change the number of threads and other runtime parameters at replay and it should be possible to replay codelets across different architectures. Third, the set of extracted codelets must faithfully capture the behavior of the original application so that it can be used as a proxy for measuring performance and scalability. In particular, each codelet replay must be deterministic: different replays of the same codelet should execute the same code and have the same performance.

Multi-threaded execution is a well known source of indeterminism: race conditions and synchronization delays between threads may change the order of the operations from one execution to the next. In particular, when multiple threads are running, each one may be executing a different region of code. This makes it difficult to isolate a particular region of code.

To avoid thread indeterminism issues, PCERE codelets start at the beginning of a parallel region and finish at the end of the region. Indeed, the beginning of an OpenMP region is a global synchronization point where all threads positions in the program are known. Capturing codelets at the start of the region has another advantage: it enables changing the number of threads at replay. Indeed, the capture happens just before the call to `kmpc fork` that decides how many threads are spawned.

Another advantage of capturing codelets just before a call to `kmpc fork` is that it simplifies codelet portability. Traditional checkpoint techniques save a full dump of the memory and of the register banks, including the Program Counter. This approach requires that the replayed code keeps the same code layout and uses exactly the same registers as during the capture. It limits codelet portability to architectures sharing the same register layout and does not enable recompiling and replaying the code on a different architecture.

Because codelet capture happens just before a call to `kmpc fork`, the application binary interface guarantees that the codelet working set is either in memory or is passed as arguments to the outlined function. This simplifies the memory capture process: only the memory and arguments to the outlined function must be recorded. Also, the outlined function prototype acts as a clean interface that allows us to recompile and apply transformations to the codelet before replay. Because no assumptions about the register layout are made, codelets are portable across architectures that have similar memory layout, such as word size and endianness. Our tests have shown that our codelet replayer allows to recompile changing optimization flags (capturing on `-O0` but replaying on `-O3`) or changing
<figure><img src="image_2.png" /><figcaption>Fig. 1. Clang outlines each C parallel region as an independent IR function: `omp_microtask`. The call to `kmpc_fork` spawns a pool of threads that runs the outlined microtask.</figcaption></figure>

micro-architectures (capturing on Nehalem and replaying on Sandy Bridge, Core2, or Atom).

### III. PCERE: PARALLEL CODELET EXTRACTION AND REPLAY

This section gives an overview of PCERE architecture and details the different technical challenges of codelet extraction and replay.

#### A. Workflow Overview

Parallel code isolation consists of two main steps: capture and replay. During the capture, the original program is instrumented with calls to our memory capture library. The execution state is captured at the start of each parallel region. During the replay, the user selects a particular region to replay. PCERE generates a standalone codelet that restores the execution context and jumps to the region of interest.

Figure 2 presents how a parallel region is captured as a codelet and replayed. Both capture and replay require special compilation passes to instrument the code with calls to the capture and restore libraries, and to isolate parallel regions. PCERE leverages the LLVM compiler framework to implement the instrumentation and isolation passes. LLVM provides a rich API for manipulating the IR code, which greatly simplifies the process. PCERE instrumentation and extraction passes operate after OpenMP directive outlining but before the IR optimization passes.

The capture requires executing the application once to get the execution context of all the parallel regions. If the user wants to measure an application on a single architecture with a fixed number of threads, extracting and replaying the codelets does not pay off. It is quicker and more accurate to fully measure the benchmark. But, if the user is interested in comparing the performance of different architectures and thread configurations, the codelet approach is quickly amortized because codelets are only extracted once but replayed many times. The overhead of codelet capture is discussed in section V-A.

#### B. Capturing and Restoring the Execution Context

Before replaying a codelet, the memory state from the original execution must be restored. This ensures that the replay will be equivalent to the original run, even for data dependent branching code. Three aspects need to be considered at replay:

1. the working set of the parallel region must be restored,

2. the cache must be warmed to avoid cold-start bias [16],

3. the different data sets which induce performance variations across invocations must be considered.

Checkpointing the original memory state must be done before reaching the parallel region. In PCERE the memory is captured just before the `kmpc fork` call. Capturing before the fork allows to change at replay both the number of threads and the architecture. The capture of the thread stack and the Thread Local Storage (TLS) are also simplified as they are handled by the `kmpc fork`.

In the rest of this section, we describe how the working set and cache state are captured and restored, and how PCERE handles the capture of regions where the performance is different across working sets.

##### a) Working Set Capture:

To capture the working set, PCERE takes a full snapshot of the original application address space. The application is frozen using the `ptrace` system call, then a helper process dumps the memory contents to disk, and returns the control to the original application. Codelet Finder [11], [10], a sequential code isolator tool, uses a similar technique. Full memory dumps are large, but have the advantage of perfectly capturing the memory layout, handling pointer aliasing, and preserving the relative alignment and the offsets among data structures.

When replaying a codelet, PCERE instruments the `main` function so that it immediately jumps to a special `run_codelet` procedure. `run_codelet` restores the memory working state and runs the original parallel region by directly calling `kmpc fork` on the outlined function.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Codelet capture and replay workflow</figcaption></figure>

b) Cache warmup:

To faithfully capture the performance of the original region it is necessary to warm up the system to match the original context as much as possible. Two main approaches have been proposed in the literature. The first approach is to warm up the cache by running a few warmup executions of the codelet itself [9], [11], [10]. It is an optimistic heuristic that assumes that the codelet working set is hot in the original run.

The second approach warms up the cache by replaying the history of the memory accesses in a simulator [17] or using a warmup routine [5]. These techniques are more accurate but require tracing the memory which is costly and incurs significant slowdowns [18].

The current version of PCERE uses the first approach because it is simpler to implement and has a much lower overhead. Our warmup heuristic distinguishes two types of codelets: frequently-called codelets that have more than four invocations in the original application and infrequently-called codelets.

We assume that the working set of frequently-called codelets is hot in the original application. The rationale is that the first invocations in the original program have warmed up the region working set. Therefore, for frequently-called codelets, our warmup strategy runs the codelet four times before replaying it for real. This number was determined empirically.

For infrequently-called codelets, we assume that the working set is cold in the original run. Therefore we replay them exactly as many times as in the original application.

Our experiments in section IV show that the optimistic warmup is enough to accurately replay most of the NAS parallel benchmark on three different architectures. Yet, in future versions of PCERE we would like to offer more realistic warmup strategies as discussed in section VII.

c) Codelets with different working sets: Most of the codelets have a constant performance across invocations. Therefore, a single working state snapshot is sufficient to accurately replay all the invocations. If performance varies across invocations, this simple capture strategy is insufficient.

<figure><img src="image_4.png" /><figcaption>Fig. 3. MG resid execution time over the different invocations replayed with 4 threads on Nehalem. resid has three distinct performance classes. To faithfully replay the parallel region, PCERE captures one working set per performance class. Here the first, second, and seventh invocations were captured and replayed.</figcaption></figure>

Figure 3 presents the execution time across the different invocations of *resid* which represents more than 50% of MG execution time and is invoked 42 times. We observe that *resid* has three different performance behaviors. Each performance class corresponds to a different working set. Performance classes can be automatically detected with a clustering algorithm such as CLARA [19]. When a codelet has different performance classes, we select a representative invocation per class. During capture, PCERE saves a separate memory dump for each representative invocation. The right box in figure 3 shows the replay time of the three selected representatives in *resid*. To predict the codelet whole replay time, PCERE adds each representative execution time weighted by the number of invocations that fall in its performance class.

C. Lock Support

To fully support replay of codelets using OpenMP lock primitives, a special *lock capture* step is required.

OpenMP uses mutex (fast userspace mutexes) calls to implement the lock support on Linux. Each mutex requires a kernel space wait queue. System calls are used to request operations on the wait queue from user space. Our memory capture only
<table><caption>TABLE I. THE TEST ARCHITECTURES USED IN THIS PAPER.</caption><thead><tr><th></th><th>Core2</th><th>Nehalem</th><th>Sandy Bridge</th></tr></thead><tbody><tr><td>CPU</td><td>E7500</td><td>Xeon E5620</td><td>E5</td></tr><tr><td>Frequency (GHz)</td><td>2.93</td><td>2.40</td><td>2.7</td></tr><tr><td>Sockets</td><td>1</td><td>2</td><td>2</td></tr><tr><td>Cores per socket</td><td>2</td><td>4</td><td>8</td></tr><tr><td>Threads per core</td><td>1</td><td>1</td><td>2</td></tr><tr><td>L1 cache (KB)</td><td>32</td><td>32</td><td>32</td></tr><tr><td>L2 cache (KB)</td><td>3MB</td><td>256</td><td>256</td></tr><tr><td>L3 cache (MB)</td><td>-</td><td>12</td><td>20</td></tr><tr><td>Ram (GB)</td><td>4</td><td>24</td><td>64</td></tr></tbody></table>

saves the user space process memory, therefore it does not preserve the state of the `futex` wait queue.

To properly support OpenMP locks, we need a special lock capture step that detects all the locks accessed by a codelet. This is achieved by intercepting calls to the lock OpenMP library during capture.

Before replaying the codelet, the replay wrapper takes care to properly initialize all the required locks in kernel space.

## IV. PCERE EVALUATION

This section evaluates PCERE replay accuracy. The evaluation is done on an unofficial C version of the NAS Parallel Benchmarks OpenMP.

### A. Experimental Setup

The NAS Parallel Benchmarks (NPB) are an established OpenMP benchmark suite and a good target to evaluate PCERE prediction accuracy. Yet, most of the NPB are written in Fortran and PCERE is built upon Clang which only supports C and C++ OpenMP programs.

The Omni Compiler Project (OCP) [4] maintains an unofficial C version of NPB 2.3. Unfortunately, it is based on an outdated NPB 2.3 which was released in 1997. In particular, in the NPB 2.3 version the OpenMP parallelism is coarse grained: most of the benchmarks only have one huge parallel region. This makes them a poor choice to evaluate PCERE. To overcome this problem, we have updated the OCP unofficial NAS benchmarks so that they mimic the structure of the NPB 3.0 OpenMP official version. This effort involved carefully porting the changes in the official Fortran version to the unofficial C version. Our 3.0 C version of NPB is publicly available at http://benchmark-subsetting.github.io/cNPB.

The CG benchmark was slightly modified to overcome a bug in LLVM OpenMP frontend. A global barrier was added after `omp for reduction` clauses. According to the OpenMP specification, this synchronization is implicit and mandatory, but the current LLVM OpenMP implementation does not honor it. This issue has since been reported and corrected [20].

In this paper all the benchmarks were compiled at the `-O3` optimization level using Clang 3.4 and linked against the Intel/LLVM runtime. The benchmarks were run using the class A working set sizes. The thread affinity was set to `Scatter` with a static work scheduling.

Table I presents our test architectures. They belong to three different Intel CPU generations (Core2 Duo, Nehalem, and

Sandy Bridge) and possess quite distinct memory hierarchies. These machines were selected to validate that PCERE replay process is portable across micro-architectures.

### B. Replay Accuracy

The codelet based benchmarking process is only viable if the codelets faithfully capture the original application behavior. In this section we evaluate the *accuracy* of the codelet replay.

Accuracy is defined as the relative difference between the *in vivo* and *in vitro* execution times of a codelet. The *in vivo* time is the time spent inside the codelet parallel region in the original application. The *in vitro* time is the time measured during the codelet standalone replay.

To evaluate accuracy, we extracted the full set of codelets from all the NPB applications. As discussed in section II-C, the extracted codelet set maps exactly to the parallel regions of the original OpenMP application. We reduced this full set, by removing the codelets that represent less than 5% of the original execution time. Originally 59 codelets were captured, and after filtering only 25 were kept. Then we measured the *in vivo* and *in vitro* execution time for each codelet, and computed the replay accuracy.

For the NPB benchmarks, the number of threads used during capture had no impact on replay: the number of threads can be freely changed at replay. Therefore, the thread number during capture can be chosen arbitrarily. In our experiments we ran capture using a single thread run.

Table II summarizes the replay accuracy over the NPB codelet set measured on Nehalem. PCERE faithfully replays most of the parallel regions: the *in vivo* and *in vitro* performance is close. A single working set was enough to faithfully replay the benchmarks parallel regions except for MG for which we needed to extract multiple working sets to accurately replay its *in vivo* execution time.

Only two codelets are misreplayed: SP `xsolve` and CG `residual norm`. In both benchmarks, the error is due to cache state differences between the *in vivo* and the *in vitro* executions. Our optimistic warmup strategy is not accurate enough for these two benchmarks. For instance, CG `residual norm` working set is cold in the original run but incorrectly warmed-up during replay. Section VII briefly discusses how the warmup strategy could be improved.

## V. PCERE SCALABILITY PREDICTION

Through fast codelet replay, PCERE is able to quickly estimate the strong scalability of a parallel application. This section evaluates the scalability prediction on the NPB 3.0. Using PCERE scalability evaluation is 25 × cheaper than measuring the original NPB and maintains a low 1.7% median prediction error.

### A. Prediction Model

Traditionally the scalability of an application is evaluated by plotting the application execution time against the number of parallel threads. This requires measuring one application run for each thread configuration.
<table><caption>TABLE II. CODELET REPLAY ACCURACY</caption><thead><tr><th>Benchmark</th><th>1</th><th>2</th><th>4</th><th>8</th><th>weight %</th></tr></thead><tbody><tr><td><strong>CG</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>conj grad iteration loop</td><td>11.18</td><td>8.05</td><td>0.23</td><td>2.66</td><td>95.8</td></tr><tr><td>conj grad residual norm</td><td>12.26</td><td>11.27</td><td>31.756</td><td>3.08</td><td>66.4</td></tr><tr><td><strong>MG</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>resid</td><td>0.68</td><td>0.03</td><td>1.19</td><td>0.46</td><td>53.5</td></tr><tr><td>psinv</td><td>1.42</td><td>1.07</td><td>0.57</td><td>1.43</td><td>22.8</td></tr><tr><td>interp</td><td>8.76</td><td>8.09</td><td>8.18</td><td>1.75</td><td>07.2</td></tr><tr><td>rpri3</td><td>1.31</td><td>3.15</td><td>2.09</td><td>7.27</td><td>05.8</td></tr><tr><td>norm2u3</td><td>0.12</td><td>0.89</td><td>1.53</td><td>0.14</td><td>05.6</td></tr><tr><td>zero3</td><td>4.03</td><td>4.86</td><td>5.46</td><td>10.50</td><td>05.4</td></tr><tr><td><strong>EP</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>main</td><td>0.01</td><td>2.00</td><td>0.10</td><td>1.36</td><td>99.99</td></tr><tr><td><strong>IS</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>main random generator</td><td>0.22</td><td>0.50</td><td>0.52</td><td>3.76</td><td>80.6</td></tr><tr><td>rank</td><td>0.28</td><td>0.84</td><td>1.64</td><td>5.30</td><td>39.9</td></tr><tr><td><strong>SP</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>x solve</td><td>23.27</td><td>17.37</td><td>10.59</td><td>4.37</td><td>33.4</td></tr><tr><td>z solve</td><td>2.64</td><td>1.30</td><td>1.86</td><td>2.07</td><td>30.9</td></tr><tr><td>y solve</td><td>8.46</td><td>5.55</td><td>6.66</td><td>5.61</td><td>32.7</td></tr><tr><td>compute rhs</td><td>1.61</td><td>1.60</td><td>2.1</td><td>0.57</td><td>26.8</td></tr><tr><td><strong>BT</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>z solve</td><td>0.14</td><td>3.52</td><td>2.5</td><td>10.80</td><td>33.6</td></tr><tr><td>y solve</td><td>0.20</td><td>3.76</td><td>1.82</td><td>6.25</td><td>32.3</td></tr><tr><td>x solve</td><td>0.33</td><td>0.26</td><td>4.16</td><td>11.13</td><td>30.5</td></tr><tr><td>compute rhs</td><td>0.84</td><td>0.77</td><td>0.08</td><td>2.34</td><td>11.1</td></tr><tr><td><strong>FT</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>cffts2</td><td>0.38</td><td>2.58</td><td>3.29</td><td>3.20</td><td>31.3</td></tr><tr><td>cffts3</td><td>5.12</td><td>4.71</td><td>5.06</td><td>5.27</td><td>30.9</td></tr><tr><td>cffts1</td><td>1.29</td><td>0.99</td><td>0.11</td><td>0.84</td><td>30.7</td></tr><tr><td>compute indexmap</td><td>3.09</td><td>5.20</td><td>0.32</td><td>3.82</td><td>06.6</td></tr><tr><td><strong>LU</strong></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>ssor iteration</td><td>0.03</td><td>0.86</td><td>0.53</td><td>0.03</td><td>98.7</td></tr><tr><td>rhs</td><td>0.89</td><td>1.09</td><td>0.58</td><td>2.01</td><td>27.4</td></tr></tbody></table>

The table shows the relative error between the in vivo and in vitro execution time for each NPB codelet over different thread configurations. Measures were performed on Nehalem. The weight % column is the contribution of the region to the total running time (the weight changes across thread configurations, here we consider the maximum).

Amdahl's law stipulates that the execution time $T(n)$ of an application being executed on $n$ threads is,

$$T(n) = T(1) \times \left(S + \frac{1-S}{n}\right),$$

where $S$ is the fraction of the algorithm that is strictly serial. In other words, increasing the number of threads will only speedup parallel regions. Our scalability prediction model is built upon this assumption. The invariant sequential regions are measured only once. Thanks to codelets, only the parallel regions are replayed for each different number of threads.

Our prediction method has two steps. First, initialization extracts the codelet set and measures the sequential part of each application, $T_{seq}$. Second, prediction replays the codelets with different number of threads to predict the scalability of the original applications.

Let $C$ be the set of all the codelets of an application. Our model estimates the application execution time with $m$ threads as,

$$T_{predicted}(m) = T_{seq} + \sum_{c \in C} T_{c}^{vitro}(m) \times invoc_{c},$$

where $invoc_c$ is the number of invocations of codelet $c$ in

<figure><img src="image_5.png" /><figcaption>Fig. 4. Real vs. PCERE execution time predictions on Sandy Bridge for the SP compute rhs codelet</figcaption></figure>

the original application, and $T_c^{vitro}(m)$ is the in vitro execution time per invocation measured by replaying codelet $c$ with $m$ threads.

PCERE accelerates the benchmarking process because:

1) the sequential part is only measured once during the initialization,

2) codelet replay is faster because the number of invocations of the parallel regions is reduced.

PCERE scalability prediction acceleration is computed as the ratio between the replay cost and the original application execution time. The replay cost is the time needed to replay all of the extracted codelets, it includes warmup time.

We do not take into account the cost of the initialization step into the quantification of PCERE acceleration over the benchmarking process. Indeed, codelets might be reused and the extraction cost is only paid once. Codelets can even be shared among different users, quickly amortizing the initialization cost. For reference, the cost of the initialization step is comparable to a full run of the initial benchmarks, with a small overhead attributable to our additional compiler passes and capture library calls. On the NPB suite BT has the worst initialization overhead: $1.25 \times$ the original execution time.

The prediction accuracy is quantified for $m$ threads as the relative error between $T_{predicted}(m)$ and $T_{real}(m)$, the real execution time of the application with $m$ threads. The lower this value is, the better our predictions are. The next section evaluates the acceleration and prediction error on the NPB 3.0 on three test architectures.

## B. Scalability Prediction Per Architecture

Table III details NPB prediction and benchmarking acceleration over three different architectures. As explained in section IV, codelets were extracted on a single thread.

Overall PCERE scalability prediction is fast and accurate. Table IV summarizes the average accuracy and acceleration over all the NPB. In figure 4 we compare the real and predicted
<table><caption>TABLE IV. AVERAGE SCALABILITY PREDICTION ACCURACY AND ACCELERATION ON NPB</caption><thead><tr><th></th><th>Core2</th><th>Nehalem</th><th>Sandy Bridge</th></tr></thead><tbody><tr><td>Accuracy</td><td>1.84%</td><td>2.9%</td><td>7.4%</td></tr><tr><td>Acceleration</td><td>25.2</td><td>27.4</td><td>23.7</td></tr></tbody></table>

Sandy Bridge higher prediction error comes from the inability of PCERE to correctly predict scalability when hyper-threads are used. Not considering hyper-threaded runs lowers Sandy Bridge error to 5.9%.

execution time on SP compute rhs codelet which has the biggest execution time per invocation within SP.

Problems are highlighted in gray on table III and explained below:

* EP benchmark shows no acceleration at all with our method. EP sequential part is negligible and its single parallel region is only invoked once. Therefore PCERE replay strategy is not faster than the original run.

* IS has low accuracy on Sandy Bridge. This is because the memory layout in IS depends on the number of threads. A higher number of threads changes the blocking and impacts the execution time of sequential regions as demonstrated in [21]. This violates our base assumption of invariant sequential execution time.

* On Sandy Bridge, replays running with 32 threads show high misprediction errors. The test machine has only 16 physical cores. PCERE warmup and replay strategy is not accurate when hyper-threads are used. We are investigating this issue.

### C. Cross Architecture Prediction

PCERE codelets are portable: they can be extracted on an architecture and replayed on another one. Architectures should share the same memory layout, word size and endianness; but the register layout and ISA can be different because our checkpointing happens just before a function call, so only the memory and function arguments need to be captured. Therefore, it is possible to do cross architecture codelet replay and scalability prediction.

To demonstrate cross-architecture portability, we extracted the NPB codelets on Nehalem and replayed them on Sandy Bridge. Table V summarizes the results. Overall accuracy is high, except for CG replays and 32 threads replays.

As before, the misprediction with 32 threads is caused by the inability of PCERE to correctly predict scalability when hyper-threads are used. CG misprediction is caused by our heuristic warmup which, in this case, proves to be insufficient. Indeed our warmup strategy is optimistic: it assumes that the working set is hot in the original execution, which is not true in this scenario. Perspectives for improving the warmup strategy are discussed in section VII.

## VI. RELATED WORK

Our work builds upon two different lines of research: code isolation and sampled simulation of programs. Both share the same objective: accelerating performance evaluation

of programs. Code isolation extracts pieces of a program as standalone codelets whereas sampled simulation uses a hardware simulator to replay a small set of representatives phases in a program.

### A. Code Isolation

Many sequential code isolation frameworks [5], [9], [10], [11], [2] have been proposed. But to the best of our knowledge, only Liao et al. [22] also study parallel code isolation. Their approach is based on the ROSE [23] compiler infrastructure. Isolation is achieved through a source to source outliner which extracts tunable kernels out of OpenMP programs. They use the isolator to accelerate computation kernel tuning and show how to find the best parameters for the number of OpenMP threads, the schedule policy, and the chunk sizes. Liao et al. isolates parallel for loops at the source level. Outlining a source loop from a parallel region removes the loop from the lexical extent of the parallel region and alters the semantics of the program because the scope of OpenMP data clauses (private, shared, or reduction) is lost. The source outlining approach requires an additional step that repairs the lost scopes. On the contrary, PCERE IR level outlining is simpler because it is done after OpenMP data clauses expansion. Unlike PCERE which is evaluated on all the NPB, Liao et al. outliner is demonstrated on a single OpenMP for loop from the SMG2000 benchmark.

Yang et al. [24] proposes a partial execution framework without code isolation based on relative performance between platforms. They manually insert probes around the kernels of the application. The probes allow to stop the execution during replay after a large enough number of invocations has been measured. Like PCERE, this method reduces the number of invocations of the kernels but it is not automatic. The user must hand-tag the computation kernels with source annotations.

### B. Sampled Simulation

Sampling techniques identify and cluster similar program phases to reduce simulation time. These techniques are already mature for single threaded applications [25], [26]. Similar phases are usually detected by comparing their Basic Block Vectors (BBV).

Extending sampling techniques to multi-threaded simulations is difficult because of the threads interactions. Wenisch et al. [27] and Van Biesbrouck et al. [28] both propose techniques to accelerate multi-threaded simulations. They both build their model under the assumption that each thread is independent. Therefore, they do not support explicit threads synchronization.

Perelman [29] applies the SimPoint [25] methodology to parallel applications using instruction-based sampling. However, Carlson et al. [30] and Ardestani et al. [31] both show that instructions are not a good proxy for execution time in multi threaded programs. Instead, they propose a time based sampling method. Carlson et al. [30] provide a methodology for sampling multi-threaded workloads with up to a 5.8 × simulation time reduction over the NPB and Parsec benchmarks with an average absolute error of 3.5%.

Carlson et al. [32] also propose BarrierPoint, a sampling methodology which detects globally synchronizing barriers in
<table><caption>TABLE III. SCALABILITY PREDICTION ON NPB</caption><thead><tr><th rowspan="2"></th><th colspan="4">CORE2</th><th colspan="4">NEHALEM</th></tr><tr><th colspan="2">Accuracy</th><th colspan="2">Acceleration</th><th colspan="2">Accuracy</th><th colspan="2">Acceleration</th></tr><tr><th>Threads</th><th>1</th><th>2</th><th>1</th><th>2</th><th>1</th><th>2</th><th>4</th><th>8</th><th>1</th><th>2</th><th>4</th><th>8</th></tr></thead><tbody><tr><td>CG</td><td>0.25</td><td>1.72</td><td>28.77</td><td>19.55</td><td>10.64</td><td>5.38</td><td>0.38</td><td>22.62</td><td>40.41</td><td>23.07</td><td>12.65</td><td>8.07</td></tr><tr><td>MG</td><td>1.94</td><td>1.13</td><td>0.55</td><td>1.14</td><td>0.32</td><td>0.74</td><td>1.25</td><td>0.11</td><td>1.81</td><td>1.94</td><td>2.26</td><td>2.73</td></tr><tr><td>EP</td><td>0.11</td><td>0.13</td><td>1.0</td><td>1.0</td><td>0.01</td><td>0.19</td><td>0.1</td><td>1.13</td><td>1.0</td><td>1.0</td><td>1.0</td><td>0.99</td></tr><tr><td>IS</td><td>4.16</td><td>4.29</td><td>1.01</td><td>1.23</td><td>0.37</td><td>1.63</td><td>2.08</td><td>4.89</td><td>1.12</td><td>1.12</td><td>1.15</td><td>1.2</td></tr><tr><td>SP</td><td>1.22</td><td>2.38</td><td>92.82</td><td>81.58</td><td>8.32</td><td>5.69</td><td>4.49</td><td>5.38</td><td>103.02</td><td>97.52</td><td>94.69</td><td>92.74</td></tr><tr><td>BT</td><td>0.87</td><td>4.1</td><td>36.48</td><td>26.41</td><td>0.16</td><td>3.1</td><td>0.59</td><td>7.98</td><td>38.33</td><td>41.05</td><td>44.26</td><td>49.18</td></tr><tr><td>FT</td><td>1.26</td><td>3.34</td><td>1.76</td><td>1.22</td><td>0.93</td><td>0.75</td><td>0.05</td><td>0.21</td><td>1.93</td><td>1.96</td><td>2.11</td><td>2.32</td></tr><tr><td>LU</td><td>1.72</td><td>1.0</td><td>54.44</td><td>54.2</td><td>0.24</td><td>1.0</td><td>0.63</td><td>0.67</td><td>52.91</td><td>52.53</td><td>51.81</td><td>50.25</td></tr></tbody></table><table><thead><tr><th rowspan="2"></th><th colspan="10">SANDY BRIDGE</th></tr><tr><th colspan="5">Accuracy</th><th colspan="5">Acceleration</th></tr><tr><th>Threads</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th></tr></thead><tbody><tr><td>BT</td><td>1.51</td><td>2.47</td><td>2.64</td><td>12.99</td><td>18.28</td><td>15.66</td><td>35.83</td><td>39.83</td><td>43.86</td><td>51.13</td><td>55.47</td><td>46.99</td></tr><tr><td>EP</td><td>0.1</td><td>0.09</td><td>5.06</td><td>0.31</td><td>2.81</td><td>0.7</td><td>1.0</td><td>1.0</td><td>1.05</td><td>1.0</td><td>1.02</td><td>0.98</td></tr><tr><td>LU</td><td>0.01</td><td>2.08</td><td>1.96</td><td>1.95</td><td>0.19</td><td>2.43</td><td>51.86</td><td>50.9</td><td>50.67</td><td>47.7</td><td>45.39</td><td>20.78</td></tr><tr><td>FT</td><td>3.09</td><td>1.35</td><td>0.91</td><td>1.3</td><td>0.68</td><td>2.52</td><td>1.9</td><td>1.98</td><td>2.17</td><td>2.49</td><td>2.96</td><td>2.77</td></tr><tr><td>SP</td><td>0.78</td><td>0.06</td><td>0.14</td><td>0.05</td><td>3.38</td><td>0.67</td><td>92.19</td><td>88.72</td><td>85.89</td><td>83.01</td><td>75.04</td><td>49.21</td></tr><tr><td>CG</td><td>15.15</td><td>3.37</td><td>9.51</td><td>18.77</td><td>13.86</td><td>26.62</td><td>37.28</td><td>17.95</td><td>9.64</td><td>5.29</td><td>4.31</td><td>4.82</td></tr><tr><td>IS</td><td>1.53</td><td>6.22</td><td>24.83</td><td>17.14</td><td>30.57</td><td>27.57</td><td>1.12</td><td>1.08</td><td>1.61</td><td>1.61</td><td>1.0</td><td>0.99</td></tr><tr><td>MG</td><td>1.07</td><td>6.08</td><td>4.24</td><td>2.3</td><td>4.73</td><td>54.24</td><td>1.88</td><td>1.92</td><td>2.32</td><td>3.01</td><td>3.77</td><td>1.7</td></tr></tbody></table>

Overall PCERE accurately predicts the scalability on the three architectures. The average prediction error is 4.9%. The prediction is in average 25 × faster with PCERE. In this experiment a separate initialization step was performed on each architecture. In Sandy Bridge the error is higher on IS and with 32 threads. IS misprediction is due to the fact that changing the number of threads changes the memory layout which impacts the sequential regions violating our model assumptions. Higher misprediction on 32 threads is due to PCERE being less reliable when hyper-threads are used.

<table><caption>TABLE V. CROSS ARCHITECTURE REPLAY ACCURACY</caption><thead><tr><th>Benchmark</th><th>Parallel region</th><th colspan="5">Threads</th><th>weight %</th></tr><tr><th></th><th></th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th></tr></thead><tbody><tr><td>CG</td><td>conj grad iteration loop</td><td>7.57</td><td>4.44</td><td>1.69</td><td>1.35</td><td>5.44</td><td>3.06</td><td>95.6</td></tr><tr><td></td><td>conj grad residual norm</td><td>18.86</td><td>15.65</td><td>6.99</td><td>24.3</td><td>42.63</td><td>36.7</td><td>93.5</td></tr><tr><td>MG</td><td>resid</td><td>1.34</td><td>1.64</td><td>1.72</td><td>1.59</td><td>1.03</td><td>63.20</td><td>56.0</td></tr><tr><td></td><td>psinv</td><td>20.27</td><td>3.13</td><td>2.09</td><td>37.25</td><td>10.06</td><td>80.41</td><td>23.1</td></tr><tr><td></td><td>zero3</td><td>6.98</td><td>3.20</td><td>8.12</td><td>8.23</td><td>3.33</td><td>71.06</td><td>09.2</td></tr><tr><td></td><td>interp</td><td>7.13</td><td>6.55</td><td>6.22</td><td>2.48</td><td>7.50</td><td>92.03</td><td>07.4</td></tr><tr><td></td><td>rprj3</td><td>7.53</td><td>6.50</td><td>9.86</td><td>11.93</td><td>15.38</td><td>94.72</td><td>05.6</td></tr><tr><td>EP</td><td>main</td><td>0.04</td><td>0.10</td><td>0.05</td><td>0.03</td><td>0.26</td><td>0.44</td><td>99.99</td></tr><tr><td>IS</td><td>main random generator</td><td>0.63</td><td>1.09</td><td>0.67</td><td>9.59</td><td>29.14</td><td>1.98</td><td>82.4</td></tr><tr><td></td><td>rank</td><td>0.69</td><td>0.42</td><td>0.24</td><td>0.22</td><td>1.49</td><td>8.24</td><td>42.8</td></tr><tr><td>SP</td><td>z solve</td><td>2.54</td><td>0.01</td><td>6.02</td><td>10.4</td><td>3.94</td><td>4.77</td><td>35.1</td></tr><tr><td></td><td>x solve</td><td>2.80</td><td>2.21</td><td>4.84</td><td>4.25</td><td>0.90</td><td>9.48</td><td>31.9</td></tr><tr><td></td><td>compute rhs</td><td>2.04</td><td>1.60</td><td>1.30</td><td>0.19</td><td>1.42</td><td>0.53</td><td>27.7</td></tr><tr><td></td><td>y solve</td><td>0.51</td><td>0.03</td><td>5.23</td><td>10.94</td><td>1.84</td><td>3.72</td><td>27.1</td></tr><tr><td>BT</td><td>z solve</td><td>0.30</td><td>2.00</td><td>1.58</td><td>12.51</td><td>21.08</td><td>24.02</td><td>33.7</td></tr><tr><td></td><td>x solve</td><td>0.87</td><td>3.97</td><td>5.01</td><td>12.53</td><td>19.78</td><td>15.56</td><td>33.4</td></tr><tr><td></td><td>y solve</td><td>0.13</td><td>1.75</td><td>5.58</td><td>16.30</td><td>22.39</td><td>13.05</td><td>33.1</td></tr><tr><td></td><td>compute rhs</td><td>0.19</td><td>0.99</td><td>1.96</td><td>1.43</td><td>2.30</td><td>3.619</td><td>09.5</td></tr><tr><td>FT</td><td>cffts2</td><td>1.66</td><td>0.47</td><td>1.57</td><td>0.80</td><td>0.70</td><td>0.91</td><td>30.5</td></tr><tr><td></td><td>cffts3</td><td>9.49</td><td>7.93</td><td>7.83</td><td>7.58</td><td>7.13</td><td>2.10</td><td>30.4</td></tr><tr><td></td><td>cffts1</td><td>0.03</td><td>0.84</td><td>1.5</td><td>0.08</td><td>1.16</td><td>0.34</td><td>30.2</td></tr><tr><td></td><td>compute indexmap</td><td>0.80</td><td>1.39</td><td>2.70</td><td>0.30</td><td>0.83</td><td>8.78</td><td>10.1</td></tr><tr><td>LU</td><td>ssor iteration</td><td>1.44</td><td>0.01</td><td>2.58</td><td>2.27</td><td>0.32</td><td>0.48</td><td>76.8</td></tr><tr><td></td><td>rhs</td><td>0.12</td><td>0.54</td><td>0.26</td><td>0.11</td><td>0.45</td><td>0.73</td><td>26.1</td></tr></tbody></table>

In this experiment, codelets were extracted on Nehalem and replayed on Sandy Bridge, enabling quick cross architecture scalability prediction. The table shows the relative error between the in vivo and in vitro execution time for each NPB codelet over different threads configurations. The prediction error is low, except for CG residual norm codelet and 32 threads. CG misprediction is caused by our heuristic warmup which, in this case, proves to be insufficient. Misprediction on 32 threads is again due to PCERE inability to predict thread configurations requiring hyper-threads. The weight % column is the contribution of the region to the total running time (the weight changes across thread configurations, here we consider the maximum).
multi-threaded applications. BarrierPoint estimates total application execution time through detailed simulation of the most representative inter-barrier regions. Regions representativeness is defined with micro-architecture independent information and data signatures. BarrierPoint achieves an average speed up of 24.7 × over the NPB and Parsec benchmarks with an average error of 0.9%. The speedup is similar to the one achieved by PCERE, yet the accuracy of BarrierPoint is better. Nevertheless, accuracies are not directly comparable since BarrierPoint measures accuracy on a functional simulator whereas PCERE measures accuracy on real hardware.

Sampling techniques are similar to our work in that they extract representative phases from applications and allow accelerate replay. Nevertheless, all of these sampling techniques must be used in a simulator, whereas our method is more versatile since it produces IR codelets that can be recompiled and run both on simulators and on real hardware. Another key difference is that BarrierPoint and the other sampling techniques do not allow changing the number of threads at replay. Each thread configuration requires a separate capture. Therefore, unlike PCERE, they cannot be easily used to evaluate parallel scalability.

## VII. LIMITATIONS AND FUTURE WORK

Our methodology successfully accelerates performance evaluation of multi-threaded programs on different architectures. In this section we discuss its drawbacks and outline promising future work.

In this paper, PCERE evaluates scalability of the NAS NPB. PCERE evaluation could be extended to real industrial applications.

PCERE fast codelet replay could also be used to accelerate the space exploration of other OpenMP parameters such as the schedule policy, the chunk sizes of parallel regions, or the thread affinity mapping [22]. PCERE could also be used to tune compiler flags for parallel programs [33] since flags can be changed at replay time.

PCERE does not handle extraction of nested parallel regions. This was a deliberate choice that simplifies the implementation of the extraction compiler passes. We hope to remove this limitation in future versions of PCERE.

One of PCERE strong features is allowing change of the number of threads during replay. This is possible for most of the OpenMP applications tested, in particular it is true for all the NPB 3.0. Nevertheless, there are cases in which the replay thread number is constrained by the capture. For instance, `qsomp`, a quick sort benchmark in OMPSCR v2.0 suite [34], can only be replayed on a smaller number of threads than the one used during capture. This is because `qsomp` serial initialization depends on the number of threads. Instead of using the TLS, it manually allocates a reserved slot in a global vector for each thread. If the replay is done with more threads than during capture, there are not enough reserved slots and replay fails. Fortunately, this design pattern is infrequent in OpenMP, which encourages to write thread-number agnostic code. PCERE could automatically detect those problematic cases by tracking calls to `omp_get_max_threads` that are later used as argument to memory allocating functions.

PCERE uses an optimistic warmup strategy to reproduce the original cache state when replaying a region. The main problem of the method is that sometimes its optimistic assumption is not true: the working set is cold in the original program. In those programs, optimistic warmup introduces discrepancies between in vivo and in vitro performance. Future versions of PCERE should offer more realistic warmup techniques, that replay the history of past memory accesses to restore the cache state [16], [35], [36].

Through program similarity analysis, de Oliveira Castro et al. [8] find a minimal set of representative codelets. They cluster together codelets that have the same performance behavior, and keep only one representative copy for each group. Similarly, Zhai et al. [37] propose Phantom, a sampling methodology that clusters together similar processes in MPI applications to reduce performance evaluation cost. These benchmark reduction techniques could be extended and applied to PCERE codelets, achieving even higher cost reductions in parallel performance evaluation. However, they require defining a set of program similarity metrics that are relevant in the context of OpenMP parallel regions.

## CONCLUSION

This paper presents a methodology to reduce the cost of strong scalability evaluation. Instead of executing the whole application with different thread configurations, we outline and replay only parallel codelets. Unlike previous work, codelets allow changing the thread number at replay. A single codelet capture can be replayed with different thread configurations.

PCERE reduces the strong scalability evaluation time up to 25 × with an average prediction error of 4.9%. The prediction method can successfully be used across different architectures. Parallel codelet replay offers other interesting applications such as fast OpenMP runtime parameters auto-tuning.

PCERE will soon be released at http://benchmark-subsetting.github.io/pcere under an open source license. Detailed reports from our experiments with NPB benchmarks are also available at the above address. We propose a C OpenMP version of the 3.0 NAS Parallel Benchmarks. The benchmark suite is available at http://benchmark-subsetting.github.io/cNPB.

## ACKNOWLEDGMENTS

The authors would like to thank Eric Petit for his insightful comments.

This work has been conducted by the Exascale Computing Research laboratory, thanks to the support of CEA, GENCI, Intel, UVSQ. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the CEA, GENCI, Intel, or UVSQ.

## REFERENCES

[1] C. Lattner and V. Adve, "LLVM: A compilation framework for lifelong program analysis & transformation," in *Code Generation and Optimization, 2004. CGO 2004. International Symposium on*. IEEE, 2004, pp. 75-86.
[2] P. de Oliveira Castro, C. Akel, E. Petit, M. Popov, and J. William, "CERE: LLVM based codelet extractor and R�uner for piecewise benchmarking and optimization," *ACM Transactions on Architecture and Code Optimization (to appear)*, 2015.

[3] D. H. Bailey, *Nas parallel benchmarks*. Springer, 2011.

[4] "Omni Compiler Project Benchmarks." [Online]. Available: http://www.hpcs.cs.tsukuba.ac.jp/omni-compiler/

[5] Y.-J. Lee and M. Hall, "A code isolator: Isolating code fragments from large programs," in *Languages and Compilers for High Performance Computing*. Springer, 2005, pp. 164–178.

[6] D. E. Knuth, "An empirical study of Fortran programs," *Software: Practice and Experience*, vol. 1, no. 2, pp. 105–133, 1971.

[7] Y. Kashnikov, P. de Oliveira Castro, E. Oseret, and W. Jalby, "Evaluating architecture and compiler design through static loop analysis," in *High Performance Computing and Simulation (HPCS), 2013 International Conference on*. IEEE, 2013, pp. 535–544.

[8] P. de Oliveira Castro, Y. Kashnikov, C. Akel, M. Popov, and W. Jalby, "Fine-grained benchmark subsetting for system selection," in *Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization*. ACM, 2014, p. 132.

[9] E. Petit, G. Papaure, F. Bodin et al., "Astex: a hot path based thread extractor for distributed memory system on a chip," in *Proceedings of Compilers for Parallel Computers workshop (CPC2006)*, 2006.

[10] C. Akel, Y. Kashnikov, P. de Oliveira Castro, and W. Jalby, "Is Source-code Isolation Viable for Performance Characterization?" in *International Workshop on Parallel Software Tools and Tool Infrastructures (PSTI)*. IEEE Computer Society, 2013.

[11] CAPS entreprises. (CAPS) Codelet finder. [Online]. Available: http://www.caps-entreprise.com/

[12] T. Lafage and A. Seznec, "Choosing representative slices of program execution for microarchitecture simulations: A preliminary application to the data stream," in *Workload characterization of emerging computer applications*. Springer, 2001, pp. 145–163.

[13] A. B. A. Bataev, "Towards OpenMP Support in LLVM," in *2013 European LLVM Conference*, 2013.

[14] "LLVM OpenMP runtime," https://www.openmprtl.org/, accessed: 2014-09-01.

[15] C. Liao, O. Hernandez, B. Chapman, W. Chen, and W. Zheng, "Openuh: An optimizing, portable openmp compiler," *Concurrency and Computation: Practice and Experience*, vol. 19, no. 18, pp. 2317–2332, 2007.

[16] R. E. Kessler, M. D. Hill, and D. A. Wood, "A comparison of trace-sampling techniques for multi-megabyte caches," *Computers, IEEE Transactions on*, vol. 43, no. 6, pp. 664–675, 1994.

[17] T. Sherwood, E. Perelman, and B. Calder, "Basic block distribution analysis to find periodic behavior and simulation points in applications," in *Parallel Architectures and Compilation Techniques, 2001. Proceedings. 2001 International Conference on*. IEEE, 2001, pp. 3–14.

[18] X. Gao, M. Laurenzano, B. Simon, and A. Snavely, "Reducing overheads for acquiring dynamic memory traces," in *Workload Characterization Symposium, 2005. Proceedings of the IEEE International*. IEEE, 2005, pp. 46–55.

[19] L. Kaufman and P. J. Rousseeuw, *Finding groups in data: an introduction to cluster analysis*. John Wiley & Sons, 2009, vol. 344.

[20] "LLVM implicit barrier issue report," https://github.com/clang-omp/clang/issues/52, accessed: 2015-01-01.

[21] S. N. Natarajan, B. Swamy, A. Seznec et al., "Modeling multi-threaded programs execution time in the many-core era," 2013.

[22] C. Liao, D. J. Quinlan, R. Vuduc, and T. Panas, "Effective source-to-source outlining to support whole program empirical optimization," in

*Languages and Compilers for Parallel Computing*. Springer, 2010, pp. 308–322.

[23] D. Quinlan and C. Liao, "The rose source-to-source compiler infrastructure," in *Cetus Users and Compiler Infrastructure Workshop, in conjunction with PACT*, vol. 2011, 2011, p. 1.

[24] L. T. Yang, X. Ma, and F. Mueller, "Cross-platform performance prediction of parallel applications using partial execution," in *Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference*. IEEE, 2005, pp. 40–40.

[25] T. Sherwood, E. Perelman, G. Hamerly, and B. Calder, "Automatically characterizing large scale program behavior," in *ACM SIGARCH Computer Architecture News*, vol. 30, no. 5. ACM, 2002, pp. 45–57.

[26] L. Eeckhout, J. Sampson, and B. Calder, "Exploiting program microarchitecture independent characteristics and phase behavior for reduced benchmark suite simulation," in *Workload Characterization Symposium, 2005. Proceedings of the IEEE International*. IEEE, 2005, pp. 2–12.

[27] T. F. Wenisch, R. E. Wunderlich, M. Ferdman, A. Ailamaki, B. Falsafi, and J. C. Hoe, "Simflex: statistical sampling of computer system simulation," *IEEE Micro*, vol. 26, no. 4, pp. 18–31, 2006.

[28] M. Van Biesbrouck, T. Sherwood, and B. Calder, "A co-phase matrix to guide simultaneous multithreading simulation," in *Performance Analysis of Systems and Software, 2004 IEEE International Symposium on-ISPASS*. IEEE, 2004, pp. 45–56.

[29] E. Perelman, M. Polito, J.-Y. Bouguet, J. Sampson, B. Calder, and C. Dulong, "Detecting phases in parallel applications on shared memory architectures," in *Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International*. IEEE, 2006, pp. 10–pp.

[30] T. E. Carlson, W. Heirman, and L. Eeckhout, "Sampled simulation of multi-threaded applications," in *Performance Analysis of Systems and Software (ISPASS), 2013 IEEE International Symposium on*. IEEE, 2013, pp. 2–12.

[31] E. K. Ardestani and J. Renau, "Esesc: A fast multicore simulator using time-based sampling," in *High Performance Computer Architecture (HPCA2013), 2013 IEEE 19th International Symposium on*. IEEE, 2013, pp. 448–459.

[32] T. E. Carlson, W. Heirman, K. Van Craeynest, and L. Eeckhout, "Barrierpoint: Sampled simulation of multi-threaded applications," in *Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)*, 2014.

[33] Y. Kashnikov, J. C. Beyler, and W. Jalby, "Compiler optimizations: Machine learning versus o3," in *Proceedings of the 25th international conference on Languages and Compilers for Parallel Computing*, ser. LCPC'12, Tokyo, Japan, 2012.

[34] A. J. Dorta, C. Rodriguez, and F. de Sande, "The openmp source code repository," in *Parallel, Distributed and Network-Based Processing, 2005. PDP 2005. 13th Euromicro Conference on*. IEEE, 2005, pp. 244–250.

[35] T. M. Conte, M. A. Hirsch, and K. N. Menezes, "Reducing state loss for effective trace sampling of superscalar processors," in *Computer Design: VLSI in Computers and Processors, 1996. ICCD'96. Proceedings.*, 1996 IEEE International Conference on. IEEE, 1996, pp. 468–477.

[36] J. W. Haskins Jr and K. Skadron, "Memory reference reuse latency: Accelerated warmup for sampled microarchitecture simulation," in *Performance Analysis of Systems and Software, 2003. ISPASS. 2003 IEEE International Symposium on*. IEEE, 2003, pp. 195–203.

[37] J. Zhai, W. Chen, and W. Zheng, "Phantom: predicting performance of parallel applications on large-scale parallel machines using a single node," in *ACM Sigplan Notices*, vol. 45, no. 5. ACM, 2010, pp. 305–314.