Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths

Question

I was playing with the code in this answer, slightly modifying it: ``` BITS 64 GLOBAL _start SECTION .text _start: mov ecx, 1000000 .loop: ;T is a symbol defined with the CLI (-DT=...) TIMES T imul eax, eax lfence TIMES T imul edx, edx dec ecx jnz .loop mov eax, 60 ;sys_exit xor edi, edi syscall ``` Without the `lfence` I the results I get are consistent with the static analysis in that answer. When I introduce a single `lfence` I'd expect the CPU to execute the `imul edx, edx` sequence of the k-th iteration in parallel with the `imul eax, eax` sequence of the next (k+1-th) iteration. Something like this (calling A the `imul eax, eax` sequence and D the `imul edx, edx` one): ``` | | A | D A | D A | D A | ... | D A | D | V time ``` Taking more or less the same number of cycles but for one unpaired parallel execution. When I measure the number of cycles, for the original and modified version, with `taskset -c 2 ocperf.py stat -r 5 -e cycles:u '-x ' ./main-$T` for `T` in the range below…

Accepted Answer

I'll present an analysis for the case where T = 1 for both codes (with and without `lfence`). You can then extend this for other values of T. You can refer to Figure 2.4 of the Intel Optimization Manual for a visual.

Because there is only a single easily predicted branch, the frontend will only stall if the backend stalled. The frontend is 4-wide in Haswell, which means up to 4 fused uops can be issued from the IDQ (instruction decode queue, which is just a queue that holds in-order fused-domain uops, also called the uop queue) to the reservation station (RS) entires of the scheduler. Each `imul` is decoded into a single uop that cannot be fused. The instructions `dec ecx` and `jnz .loop` get macrofused in the frontend to a single uop. One of the differences between microfusion and macrofusion is that when the scheduler dispatches a macrofused uop (that are not microfused) to the execution unit it's assigned to, it gets dispatched as a single uop. In contrast, a microfused uop needs to be split into its constituent uops, each of which must be separately dispatched to an execution unit. (However, splitting microfused uops happens on entrance to the RS, not on dispatch, see Footnote 2 in @Peter's answer). `lfence` is decoded into 6 uops. Recognizing microfusion only matters in the backend, and in this case, there is no microfusion in the loop.

Since the loop branch is easily predictable and since the number of iterations is relatively large, we can just assume without compromising accuracy that the allocator will always be able to allocate 4 uops per cycle. In other words, the scheduler will receive 4 uops per cycle. Since there is no micorfusion, each uop will be dispatched as a single uop.

`imul` can only be executed by the Slow Int execution unit (see Figure 2.4). This means that the only choice for executing the `imul` uops is to dispatch them to port 1. In Haswell, the Slow Int is nicely pipelined so that a single `imul` can be dispatched per cycle. But it takes three cycles for the result of the multiplication be available for any instruction that requires (the writeback stage is the third cycle from the dispatch stage of the pipeline). So for each dependence chain, at most one `imul` can be dispatched per 3 cycles.

Because`dec/jnz` is predicted taken, the only execution unit that can execute it is Primary Branch on port 6.

So at any given cycle, as long as the RS has space, it will receive 4 uops. But what kind of uops? Let's examine the loop without lfence:

```
imul eax, eax
imul edx, edx
dec ecx/jnz .loop (macrofused)
```

There are two possibilities:

- Two `imul`s from the same iteration, one `imul` from a neighboring iteration, and one `dec/jnz` from one of those two iterations.

- One `dec/jnz` from one iteration, two `imul`s from the next iteration, and one `dec/jnz` from the same iteration.

So at the beginning of any cycle, the RS will receive at least one `dec/jnz` and at least one `imul` from each chain. At the same time, in the same cycle and from those uops that are already there in the RS, the scheduler will do one of two actions:

- Dispatch the oldest `dec/jnz` to port 6 and dispatch the oldest `imul` that is ready to port 1. That's a total of 2 uops.

- Because the Slow Int has a latency of 3 cycles but there are only two chains, for each cycle of 3 cycles, no `imul` in the RS will be ready for execution. However, there is always at least one `dec/jnz` in the RS. So the scheduler can dispatch that. That's a total of 1 uop.

Now we can calculate the expected number of uops in the RS, XN, at the end of any given cycle N:

XN = XN-1 + (the number of uops to be allocated in the RS at the beginning of cycle N) - (the expected number of uops that will be dispatched at the beginning of cycle N) = XN-1 + 4 - ((0+1)*1/3 + (1+1)*2/3) = XN-1 + 12/3 - 5/3 = XN-1 + 7/3 for all N > 0

The initial condition for the recurrence is X0 = 4. This is a simple recurrence that can be solved by unfolding XN-1.

XN = 4 + 2.3 * N for all N >= 0

The RS in Haswell has 60 entries. We can determine the first cycle in which the RS is expected to become full:

60 = 4 + 7/3 * N N = 56/2.3 = 24.3

So at the end of cycle 24.3, the RS is expected to be full. This means that at the beginning of cycle 25.3, the RS will not be able to receive any new uops. Now the number of iterations, I, under consideration determines how you should proceed with the analysis. Since a dependency chain will require at least 3*I cycles to execute, it takes about 8.1 iterations to reach cycle 24.3. So if the number of iterations is larger than 8.1, which is the case here, you need to analyze what happens after cycle 24.3.

The scheduler dispatches instructions at the following rates every cycle (as discussed above):

```
1
2
2
1
2
2
1
2
.
.
```

But the allocator will not allocate any uops in the RS unless there are at least 4 available entries. Otherwise, it will not waste power on issuing uops at a sub-optimal throughput. However, it…

Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths

Solution

Problem

Related problems