I was playing with loop unrolling, and decided to investigate it a
little. The basis is this very simple program which looks like it
could do with some loop unrolling.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define SIZE (1500 * 1024 * 1024)
int fn(int *buf)
int i;
for(i=0; i < (SIZE/sizeof(int)); i+=1)
buf[i] = i;
return 0;
int main(void)
int *buf = malloc(SIZE);
assert(buf);
return fn(buf);
Firstly, lets have a look at what happens to the function when
-funroll-loops is applied. Below is the de-compilation with
some comments on what each line is doing.
Non-optimised
nop.m 0x0
r14=0 mov r14=r0
save the "loop counter" mov.i r2=ar.lc
nop.m 0x0
one less than iterations movl r15=0x176fffff;;
nop.m 0x0
initalise loop counter mov.i ar.lc=r15
nop.i 0x0;;
loop:
*buf = i, buf++ st4 [r32]=r14,4
i++ adds r14=1,r14
dec lc, branch if > 0 br.cloop.sptk.few .loop
nop.m 0x0
restore loop counter mov.i ar.lc=r2
|
Loop unrolled
nop.m 0x0
r26 = 0 mov r26=r0
save lc mov.i r2=ar.lc
nop.m 0x0
iter / 32 movl r14=0x2edffff;;
nop.m 0x0
setup loop counter mov.i ar.lc=r14
nop.i 0x0
loop:
r3 = buf mov r3=r32
r8 = 1 adds r8=1,r26
r25 = 3 adds r25=3,r26
r23 = buf[3] adds r23=12,r32
r24 = 4 adds r24=4,r26
r22 = buf[4] adds r22=16,r32;;
buf[0] = 0; r3=buf+1 st4 [r3]=r26,4
r21 = 5 adds r21=5,r26
r19 = buf[5] adds r19=20,r32
r20 = 6 adds r20=6,r26
r18 = buf[6] adds r18=24,r32
r16 = 7 adds r16=7,r26;;
nop.m 0x0
buf[1] = 1, r3=buf+2 st4 [r3]=r8,4
r15 = buf[7] adds r15=28,r32
r17 = 2 adds r17=1,r8
r26 += 8 adds r26=8,r26
buf += 8 (for next iter) adds r32=32,r32;;
buf[2] = 2 st4 [r3]=r17
buf[3] = 3 st4 [r23]=r25
nop.i 0x0
buf[4] = 4 st4 [r22]=r24
buf[5] = 5 st4 [r19]=r21
nop.i 0x0
buf[6] = 6 st4 [r18]=r20
buf[7] = 7 st4 [r15]=r16
loop, dec branch br.cloop.sptk.few .loop
nop.m 0x0
restore lc mov.i ar.lc=r2
br.ret.sptk.many b0;;
|
We can see that in the first case the loop counter is setup to run
393216000 times (e.g. 1500*1024*1024/sizeof(int)) and a very simple
loop of storing the value and incrementing is undertaken. In the
second version, the code becomes more complex. We can see the loop
now executes 49152000 times (e.g. 1500*1024*1024/sizeof(int)/8) so we
can infer that for each loop iteration, 8 values have been unrolled to
be written into our
buf array. Indeed, when pulled apart we
can see the 8 stores (numbers just reflect the first time through).
So, is it faster?
$ time ./loop
real 0m1.209s
user 0m0.388s
sys 0m0.820s
$ timme ./loop-unroll
real 0m1.056s
user 0m0.244s
sys 0m0.812s
Yes! Great. We can suggest a number of reasons why, but it would
be interesting to get some hard statistics on why this is so. Thanks
to the Itanium performance counters, we can. Firstly, lets start by
seeing how cycles are being spent.
$ pfmon -e cpu_cycles,ia64_inst_retired_this,nops_retired,back_end_bubble_all ./loop
547923609 CPU_CYCLES
1179995250 IA64_INST_RETIRED_THIS
104431 NOPS_RETIRED
154285534 BACK_END_BUBBLE_ALL
$ pfmon -e cpu_cycles,ia64_inst_retired_this,nops_retired,back_end_bubble_all ./loop-unroll
311570590 CPU_CYCLES
1327451286 IA64_INST_RETIRED_THIS
147560435 NOPS_RETIRED
16088889 BACK_END_BUBBLE_ALL
Now, the Itanium can issue up to six instructions
(IA64_INST_RETIRED_THIS) in two bundles of three instructions per
cycle (CPU_CYCLES). However, you can't have dependencies between
registers within a 3-instruction bundle (and branches and interruptions
play havoc) so sometimes you need to pad with no-ops (this is why you
need a good compiler). We can work out some figures from this, namely
the useful instructions per cycle (e.g. instructions retired - nop
instructions / cycles).
| Test | Useful instructions/cycle |
|---|
| loop | 1179995250 - 104431 / 547923609 = 2.15 |
| unroll | 1327451286 - 147560435 / 311570590 = 3.78 |
This tells us that for each given cycle, the unrolled-loop version
is doing more work (ideally we'd like that to be a the theoretical
maximum of 6). So what is the unrolled version doing for all this
time? Bubbles are where the CPU is waiting for something; a prime
candidate is moving data from caches to registers. Bubbles make up
(154285534/547823609) 28% of the cycles on the loop version, but only
(16088889/311570590) 5% of the time for the unrolled version. This
means the processor is spending a lot less time waiting for things to
happen with the unrolled loop version.
We can drill down further to see what bubbles are occurring.
$ pfmon -e be_l1d_fpu_bubble_all,be_exe_bubble_all,be_RSE_bubble_all,Back_end_bubble_fe ./loop
14229581 BE_L1D_FPU_BUBBLE_ALL
97669 BE_EXE_BUBBLE_ALL
1260 BE_RSE_BUBBLE_ALL
131354866 BACK_END_BUBBLE_FE
$ pfmon -e be_l1d_fpu_bubble_all,be_exe_bubble_all,be_RSE_bubble_all,Back_end_bubble_fe ./loop-unroll
22676169 BE_L1D_FPU_BUBBLE_ALL
83064 BE_EXE_BUBBLE_ALL
1263 BE_RSE_BUBBLE_ALL
718850 BACK_END_BUBBLE_FE
We are now breaking the stalls down to see where they are occuring.
L1D_FPU_BUBBLES are essentially related to micro-architectural issues
with the caches; things like the L1D cache being overwhelmend and
interactions with the hardware page-table walker. BE_EXE bubbles are
more simply described a waiting for data to come from caches (or even
main memory) to registers. BE_RSE bubbles are related to the register
stack engine, and "front end" bubbles (BACK_END_BUBBLE_FE) are where
there are not enough instructions coming from the "front-end" for the
"back-end" to issue out to functional units in the processor.
In this case, the major cause of problems for the simple loop seems
to be not being able to get enough instructions through to keep the
processor busy. We can try to pin down what is happening in the
front-end:
$ pfmon -e fe_bubble_imiss,fe_bubble_tlbmiss,fe_bubble_branch,fe_bubble_bubble ./loop
27727 FE_BUBBLE_IMISS
4910 FE_BUBBLE_TLBMISS
98094189 FE_BUBBLE_BRANCH
52615907 FE_BUBBLE_BUBBLE
$ pfmon -e fe_bubble_imiss,fe_bubble_tlbmiss,fe_bubble_branch,fe_bubble_bubble ./loop-unroll
780729 FE_BUBBLE_IMISS
4858 FE_BUBBLE_TLBMISS
291620 FE_BUBBLE_BRANCH
111089 FE_BUBBLE_BUBBLE
What we can see here is that the increased code size of the
unrolled version causes us a lot more i-cache misses, as expected.
However, the problem for the unrolled version seems to be the time
spent by the front-end dealing with the branch. This is not
surprising since there is a rumor that there is a front-end buffer
which fills up after 3 repeated cycles with branch instructions;
apparently this is a problem addressed in the new Montecito chips (if
anyone has one, I'll update this if you send me the numbers). Since
we are doing 393216000 branches all within a single bundle its not
surprising we've hit it!
Just to confirm, we can break-down the BE_EXE bubbles. Remember,
BE_EXE bubbles are caused by stalls in the execution phase primarily
due to cache latencies or inter-register dependencies. Looking at our
code, we don't re-use the same register over-and-over so we would not
expect to spend a long time waiting for registers, and indeed this is
what we see.
$ pfmon -e be_exe_bubble_grall,be_exe_bubble_grgr ./loop
79601 BE_EXE_BUBBLE_GRALL
919 BE_EXE_BUBBLE_GRGR
$ pfmon -e be_exe_bubble_grall,be_exe_bubble_grgr ./loop-unroll
76627 BE_EXE_BUBBLE_GRALL
918 BE_EXE_BUBBLE_GRGR
Therefore in this case, the speed increase isn't coming from
better cache behaviour as we might have expected, but greater ability
to keep the processor busy with instructions between branches.
We can also examine the major events happening with the unrolled
case. Here we see BE_L1D_FPU bubbles being the major overhead. On
Itanium floating-point avoids the L1 cache (it is too big, and not
re-used enough to make it useful) hence the concatenation of the event
acronym. These bubbles can be broken down into the following events
(measured in two runs, since you can only do 4 at a time).
$ pfmon -e be_l1d_fpu_bubble_l1d,be_l1d_fpu_bubble_l1d_dcurecir,\
be_l1d_fpu_bubble_l1d_tlb,be_l1d_fpu_bubble_l1d_stbufrecir ./loop-unroll
9623193 BE_L1D_FPU_BUBBLE_L1D_DCURECIR
414 BE_L1D_FPU_BUBBLE_L1D_TLB
282 BE_L1D_FPU_BUBBLE_L1D_STBUFRECIR
$ pfmon -e be_l1d_fpu_bubble_l1d_fullstbuf,\
be_l1d_fpu_bubble_l1d_l2bpress,be_l1d_fpu_bubble_l1d_tlb ./loop-unroll
23 BE_L1D_FPU_BUBBLE_L1D_FULLSTBUF
17220177 BE_L1D_FPU_BUBBLE_L1D_L2BPRESS
425 BE_L1D_FPU_BUBBLE_L1D_TLB
These events expose micro-architectural details, the full extent of
which is only gleaned by reading the processor manuals (a PhD in
computer architecture probably helps too!). The store buffers are not
an issue here -- the caches are more than able to keep up with our few
writes. The TLB is also not involved; we have pretty good TLB
coverage thanks to the virtual-linear page table and hardware
page-table walker.
The two clues are DCURECIR and L2BPRESS. Essentially DCURECIR
happens when references have to "re-circulate"; this is a side-effect
of the data not being available. The L2BPRESS figure suggests why
this is so; this event happens when the L2 cache can not handle any
more requests. The L2 cache keeps a queue of outstanding requests;
when this queue is full (for example, full of long latency requests to
get data from main memory) the L2 cache causes "back-pressure" which
stops the L1 cache from issuing new requests. This suggests the
program is chewing through a lot of data and not using the cache very
effectively, which is exactly what we are doing. Pre-fetching hints
can help (but as described in a
previous
entry on hacking Enigma may not always help), but in this case
there probably isn't any spare bandwidth to pre-fetch in because
essentially no processing is happening.
What does all this mean? I don't know, but playing with
performance monitors is fun!