Blocking Example: Transpose

• Problem:

• • either A or B is traversed in non-1 stride: bad spatial reuse of data
  • blocking the loops for cache will do the transpose block per block, reusing the block elements:

for(j=0; j<n; j++)

for(i=0; i<n; i++)

a[i][j] = b[j][i]

for(ti=0; ti<n; ti += s)

for(tj=0; tj<n; tj += s)

for(j=tj; j<min(tj+s-1,n); j++)

for(i=ti; i<min(ti+s-1,n); i++)

a[i][j] = b[j][i]

tj

ti

s

s

Outer loop unrolling

to improve 1st level

cache access is possible

in addition

Previous slide

Next slide

Back to first slide

View graphic version