1 Executive Summary

This report presents:

• Information regarding generation of workloads for the 541.leela_r benchmark.
• New workloads for the benchmark and an analysis of these workloads.

Important take-away points from this report:

• The amount of work done by the benchmark on a workload is primarily determined by the size of the board.
• The behavior of the benchmark varies little between workload with the exception of memory accesses.
• Changing compilers may potentially result in a considerable change in the execution of the benchmark but these cases are rare.

2 Benchmark Information

The 541.leela_r benchmark is an advanced Go playing engine featuring many of the most recent advances in computer go. It has attained ratings of 1 kyu in Internet server play.

2.1 Inputs

The input for this benchmark consists of a incomplete game of go in the Smart Game Format.¹

2.2 Generating Workloads

The process of generating and running workloads is, for the most part, completely automated. Place a compiled version of the 541.leela_r benchmark in the gen-input directory and call it leela_r. Following this simply cd into the gen-input directory and run make-wklds.sh.

3 New Workload

All of the generated workloads are randomly-generated sets of go positions taken from the defunct No-Name Go Server’s archive.²

Each of the workloads generated by the system contains exactly six go positions. Moves must be culled from the end of the game to ensure that the AI plays the game to its completion. The size of the board and number of moves culled vary between inputs.

The system is configured so that all input generated will fall into one of the categories in Table 1.

4 Analysis

This section presents an analysis of the workloads created for the 541.leela_r benchmark. All data was produced using the Linux perf utility and represents the mean of three runs. In this section the following questions will be addressed:

1. How much work does the benchmark do for each workload?
2. How does the behavior of the benchmark change between inputs?
3. How is the benchmark’s behavior affected by different compilers and optimization levels?

4.1 Work

In order to ensure a clear interpretation the analysis of the work done by the benchmark on various workloads will focus on the results obtained with GCC 4.8.4 at optimization level -O3. The execution time was measured on machines equipped with Intel Core i7-2600 processors at 3.4 GHz with 8 GiB of memory running Ubuntu 14.04 LTS on Linux Kernel 3.16.0-71.

Figure 1 shows the mean execution time of 3 runs of 541.leela_r on a certain workload. From this figure it is clear that there is an increase in execution time when the size of the board is increased. Since increasing the board size increases the number of game states this result is as would be expected.

It can also be observed that there is a relationship between the number of moves culled from the end of the game and execution time of the benchmark.

Figure 2 displays the mean instruction count and Figure 3 gives the mean clock cycles per instruction. Both means are taken from 3 runs of the corresponding workload. The most striking thing about Figure 2 is that it appears no altogether different from Figure 1. This observation is explained by Figure 3. If the CPI is relatively consistent between all workloads then the difference in execution times for the workloads should be, for the most part, explained by their instruction count. This suggests that the instruction mix is more or less independent of the input.

Figure 1: The mean execution time from three runs for each workload.

Figure 2: The mean instruction count from three runs for each workload.

Figure 3: The mean clock cycles per instruction from three runs for each workload.

4.2 Workload Behavior

The analysis of the workload behavior is done using two different methodologies. The first section of the analysis is done using Intel’s top down methodology.³ The second section is done by observing changes in branch and cache behavior between workloads.

To collect data GCC 4.8.4 at optimization level -O3 is used on machines equipped with Intel Core i7-2600 processors at 3.4 GHz with 8 GiB of memory running Ubuntu 14.04 LTS on Linux Kernel 3.16.0-71. All data remains the mean of three runs.

4.2.1 Intel’s Top Down Methodology

Intel’s top down methodology consists of observing the execution of micro-ops and determining where CPU cycles are spent in the pipeline. Each cycle is then placed into one of the following categories:

Front-end Bound

Cycles spent because there are not enough micro-operations being supplied by the front end.

Back-end Bound

Cycles spent because there are not enough resources available to process pending micro-operations, including slots spent waiting for memory access.

Bad Speculation

Cycles spent because speculative work was performed and resulted in an incorrect prediction.

Retiring

Cycles spent actually carrying out micro-operations.

Using this methodology the program’s execution is broken down in Figure 4. When the various workloads are compared it is clear that there are no real differences in either the percentage of micro-ops that retire or the percentage of cycles that are spent because of bad speculation.

4.2.2 Branch and Cache

By looking at the behavior of branch predictions and cache hits and misses we can gain a deeper insight into the execution of the program between workloads.

Figure 5 summarizes the percentage of instructions that are branches and exactly how many of those result in a miss. It is clear that there is minimal fluctuation between different workloads.

Figure 6 summarizes the percentage of LLC accesses and exactly how many of those result in LLC misses. Here there are two important trends. The first is that a larger board appears to increase both the number of LLC accesses and the number of overall LLC misses. The second is that increasing the number of moves removed seems to lessen the penalty of a larger board in regards to both LLC access and overall LLC misses.

Figure 5: Breakdown of branch instructions in each workload.

Figure 6: Breakdown of LLC accesses in each workload.

4.3 Compilers

Limiting the experiments to only one compiler can endanger the validity of the research. To compensate for this a comparison of results between GCC (version 4.8.4) and the Intel ICC compiler (version 16.0.3) has been conducted. Furthermore, due to the prominence of LLVM in compiler technology a comparison between results observed through only GCC (version 4.8.4) and results observed using the Clang frontend to LLVM (version 3.6) has also been conducted.

Due to the sheer number of factors that can be compared, only those that exhibit a considerable difference have been included in this section.

4.3.1 LLVM

Figure 7 summarizes some interesting differences gained as the result of swapping GCC out with an LLVM based compiler. The first noteworthy characteristic of the results is that the only difference between GCC and LLVM appears to occurs at the optimization level -O1. As such the remainder of the analysis of LLVM will consider only the optimization level -O1.

At this optimization level LLVM takes approximately twice as long to execute. Furthermore there are considerably more branch instructions executed overall but with a lower miss rate. Furthermore LLVM has fewer page faults per instruction.

This information appears to indicate that LLVM is performing more work on the same data then GCC does. Though this cannot be confirmed without further experiments.

4.3.2 ICC

Figure ?? summarizes some interesting differences gained as the result of swapping GCC out with the Intel ICC compiler. It is clear that the only large difference between the two in regards to the execution of this benchmark lies in dTLB load misses and dTLB store misses when the optimization level is set to -O0.

5 Conclusion

The execution of the 541.leela_r benchmark is primarily affected by the size of the board it receives as input and is only marginally affected by the number of moves culled from the end of the game. The existing train workload is an accurate model of one case of the benchmark’s execution but does not adequately represent all viable inputs to the program. The set of new workloads presented here along with the already existing workloads provide a comprehensive exercise of the benchmark.

Appendix

(c) for long-9

(e) for medium-19

(g) for refrate

(i) for short-19