Back on the old day job, I developed and tested software and hardware for program profiling. Testing may sound like drudge-work, but there are ways to make things fun!
Two questions arise while testing a profiling infrastructure — software plus hardware:
- Does the hardware accurately count (or sample) performance events for a given specific workload?
- Does the software accurately display the counts or samples?
Clearly, ya need working hardware before you can build working software.
Testing requires a solid, known-good (KG) baseline in order to decide if new test results are correct. Here’s one way to get a KG baseline — a combination of static analysis and measurement:
- Static analysis: Analyze the post-compilation machine code and predict the expected number of instruction retires, cache reads, misses, etc.
- Measurement: Run the code and count performance events.
- Validation: Compare the measured results against the predicted results.
Thereafter, one can compare new measurements taken from the system under test (SUT) and compare against both predicted results and baseline measured results.
Applying this method to performance counter counting mode is straightforward. You might get a little “hair” in the counts due to run-to-run variability, however, the results should be well-within a small measurement error. Performance counter sampling mode is more difficult to assess and one must be sure to collect a statistically significant number of samples within critical workload code in order to have confidence in a result.
One way to make testing fun is to make it a game. I wrotekernel programs that exercised specific hardware events and analyzed the inner test loops. You could call these programs “test kernels.” The kernels are pathologically bad (or good!) code which triggers a large number of specific performance events. It’s kind of a game to write such bad code…
The expected number of performance events is predicted through machine code level complexity analysis known as program “microanalysis.” For example, the inner loops of matrix multiplication are examined and, knowing the matrix sizes, the number of retired instructions, cache reads, branches, etc. are computed in closed form, e.g.,
(38 inner loop instructions) * (1,000,000,000 iterations) +
(26 middle loop instructions) * (1,000,000 iterations) +
(9 outer loop instructions) * (1,000 iterations)
-----------------------------------------------------------
38,026,009,000 retired instructions expected
38,227,831,497 retired instructions measured
This formula is the closed form expression for the retired instruction count within the textbook matrix multiplication kernel. The microanalysis approach worked successfully on Alpha, Itanium, x86, x64 and (now) ARM. [That’s a short list of machines that I’ve worked on. 🙂 ]
With that background in mind, let’s write a program kernel to deliberately cause branch mispredictions and measure branch mispredict events.
The ARM Cortex-A72 core predicts conditional branch direction in order to aggressively prefetch and dispatch instructions along an anticipated program path before the actual branch direction is known. A branch mispredict event occurs when the core detects a mistaken prediction. Micro-ops on the wrong path must be discarded and the front-end must be steered down the correct program path. The Cortex-A72 mispredict penalty is 15 cycles.
What we need is a program condition that consistently fools the Cortex-A72 branch prediction hardware. Branch predictors try to remember a program’s tendency to take or not take a branch and the predictors are fairly sensitive; even a 49%/51% split between taken and not taken has a beneficial effect on performance. So, we need a program condition which has 50%/50% split with a random pattern of taken and not taken direction.
Here’s the overall approach. We fill a large array with a random pattern of ‘0’ and ‘1’ characters. Then, we walk through the array and count the number of ‘1’ characters. The function initialize_test_array() fills the array with a (pseudo-)random pattern of ones and zeroes:
void initialize_test_array(int size, char* array,
int always_one, int always_zero)
{
register char* r = array ;
int s ;
for (s = size ; s > 0 ; s--) {
if (always_one) {
*r++ = '1' ;
} else if (always_zero) {
*r++ = '0' ;
} else {
*r++ = ((rand() & 0x1) ? '1' : '0') ;
}
}
}
The function has options to fill the array with all ones or all zeroes in case you want to see what happens when the inner conditional branch is well-predicted. BTW, I made the array 20,000,000 characters long. The size is not especially important other than the desire to have a modestly long run time.
The function below, test_loop(), contains the inner condition itself:
int test_loop(int size, char* array)
{
register int count = 0 ;
register char* r = array ;
int s ;
for (s = size ; s > 0 ; s--) {
if (*r++ == '1') count++ ; // Should mispredict!
} return( count ) ;
}
The C compiler translates the test for ‘1’ to a conditional branch instruction. Given an array with random ‘0’ and ‘1’ characters, we should be able to fool the hardware branch predictor. Please note that the compiler generates a conditional branch for the array/loop termination condition, s > 0. This conditional branch should be almost always predicted correctly.
The function run_the_test() runs the test loop:
void run_the_test(int iteration_count, int array_size, char* array)
{
register int rarray_size = array_size ;
register char* rarray = array ;
int i ;
for (i = iteration_count ; i-- ; ) {
test_loop(array_size, array) ;
}
}
It calls test_loop() many times as determined by iteration_count. Redundant iterations aren’t strictly necessary when taking measurements in counting mode. They are needed, however, in sampling mode in order to collect a statistically significant number of performance event samples. I set the iteration count to 200 — enough to get a reasonable run time when sampling.
The test driver code initializes the branch condition array, configures the ARM Cortex-A72 performance counters, starts the counters, runs the test loop, stops the counters and prints the performance event counts:
initialize_test_array(array_size, array, always_one, always_zero) ;
a72MeasureInstructionEvents() ;
peStartCounting() ;
run_the_test(iteration_count, array_size, array) ;
peStopCounting() ;
a72PrintInstructionEvents(stdout) ;
The four counter configuration, control and display functions are part of a small utility module that I wrote. I will explain the utility module in a future post and will publish the code, too.
Finally, here are the measurements when scanning an array holding a random pattern of ‘0’ and ‘1’ characters:
Instructions ret'd: 45,999,735,845
Instructions spec'd: 98,395,483,123
CPU cycles: 59,010,851,259
Branch speculated : 8,012,669,711
Branch mispredicted: 2,001,934,251
Branch predicted 8,012,669,710
Instructions per cycle: 0.780
Retired/spec'd ratio: 0.467
Branches per 1000 (PTI): 174.189
Branch mispredict ratio: 0.250
Please recall that there are two conditional branches in the inner test loop: a conditional branch to detect ‘1’ characters and a conditional branch to check the array/loop termination condition. The loop check should be predicted correctly almost all the time, accounting for 50% of the total number of correctly predicted branches. The character test, however, should be incorrectly predicted 50% of the time. It’s like guessing coin flips — you’ll be right half the time on average. Overall, 25% of branch predictions should be incorrect, and yes, the measured branch mispredict ratio is 0.250 or 25%.
The number of speculated instructions is also very interesting. Cortex-A72 speculated twice as many ARMv8 instructions as it retired. Over half of the speculated instructions did not complete architecturally and were discarded. That’s what happens when a conditional branch is grossly mispredicted!
I hope you enjoyed this simple experiment. It makes the Cortex-A72 fetch and branch prediction behavior come alive. As a follow-up experiment, I suggest trying all-ones or all-zeroes.
Please check out other articles in this series:
- ARM Cortex-A72 tuning: IPC
- Cortex-A72 tuning: Data access
- ARM Cortex-A72 fetch and branch processing
- ARM Cortex-A72 execution and load/store operations
- Raspberry Pi 4 Performance Events
Don’t forget my Performance Events for Linux tutorial and learn to make your own Raspberry Pi 4 (Broadcom BCM2711) performance measurements.
Copyright © 2021 Paul J. Drongowski
ARM Cortex-A72 branch-related performance events:
Number Mnemonic Event name
------ ---------------- -----------------------------------------
0x08 INST_RETIRED Instruction architecturally executed
0x10 BR_MIS_PRED Mispredicted or not predicted branches
0x11 CPU_CYCLES Processor cycles
0x12 BR_PRED Predictable branch speculatively executed
0x1B INST_SPEC Operation speculatively executed
0x76 PC_WRITE_SPEC Software change of the PC (speculative)
0x78 BR_IMMED_SPEC Immediate branch (speculative)
0x79 BR_RETURN_SPEC Procedure return (speculative)
0x7A BR_INDIRECT_SPEC Indirect branch (speculative)
Disassembled code for test_loop():
00010678 :
10678: e92d0830 push {r4, r5, fp}
1067c: e28db008 add fp, sp, #8
10680: e24dd014 sub sp, sp, #20
10684: e50b0018 str r0, [fp, #-24] ; 0xffffffe8
10688: e50b101c str r1, [fp, #-28] ; 0xffffffe4
1068c: e3a04000 mov r4, #0
10690: e51b501c ldr r5, [fp, #-28] ; 0xffffffe4
10694: e51b3018 ldr r3, [fp, #-24] ; 0xffffffe8
10698: e50b3010 str r3, [fp, #-16]
1069c: ea000008 b 106c4
106a0: e1a03005 mov r3, r5
106a4: e2835001 add r5, r3, #1
106a8: e5d33000 ldrb r3, [r3]
106ac: e3530031 cmp r3, #49 ; 0x31
106b0: 1a000000 bne 106b8 ; Should mispredict!
106b4: e2844001 add r4, r4, #1
106b8: e51b3010 ldr r3, [fp, #-16]
106bc: e2433001 sub r3, r3, #1
106c0: e50b3010 str r3, [fp, #-16]
106c4: e51b3010 ldr r3, [fp, #-16]
106c8: e3530000 cmp r3, #0
106cc: cafffff3 bgt 106a0 ; Correctly predicted
106d0: e1a03004 mov r3, r4
106d4: e1a00003 mov r0, r3
106d8: e24bd008 sub sp, fp, #8
106dc: e8bd0830 pop {r4, r5, fp}
106e0: e12fff1e bx lr