Locality Optimizations

Question 1

Loop nest optimization

Answer 1

an optimization technique that applies a set of loop transformations for the purpose of locality optimization or parallelization or another loop overhead reduction of the loop nests.

Question 2

Loop fission

Answer 2

a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop’s body.[1][2] The goal is to break down a large loop body into smaller ones to achieve better utilization of locality of reference. This optimization is most efficient in multi-core processors that can split a task into multiple tasks for each processor.

int i, a[100], b[100];
for (i = 0; i < 100; i++) {
    a[i] = 1;
    b[i] = 2;
}
is equivalent to:

int i, a[100], b[100];
for (i = 0; i < 100; i++) {
    a[i] = 1;
}
for (i = 0; i < 100; i++) {
    b[i] = 2;
}