Register Blocking: An Analytical Modelling Approach for Affine Loop Kernels

For the past several decades, optimizing compilers have been a
primary area of focus in both industry and academia. This continued research interest is a testament to the complexity of this
task, primarily stemming from the vast number of parameters that
must be explored to attain near-optimal results. One of the key
compiler optimizations is "Register Blocking (RB)" also known as
"Register-level Tiling" or "unroll-and-jam". RB can strongly reduce
the number of executed Load/Store (L/S) instructions, and as a
consequence the number of data accesses in memory hierarchy,
but due to its inherent complexities, fine-tuning is essential for its
effective implementation. To address this problem, in this work a
new methodology is proposed for RB. The RB factors, the loops
to apply RB, the number of allocated variables/registers per array
reference, and the loops’ ordering are generated by an analytical
model, leveraging the target hardware (HW) architecture details and
loop kernel characteristics. The proposed methodology has been
evaluated on both embedded and general-purpose CPUs across
seven well-known loop kernels, achieving high speedups and L/S
instruction gains over GCC compiler, handwritten optimized codes,
and the popular Pluto tool.