Blocking: Example

• The following loop nest:

• • z[j] is reused for each i iteration
  • For large n the array z will not be reused from the cache

• Blocking the loops for cache:

• • nb elements of z array will be brought in to the cache and reused nb times before moving on to the next tile

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

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

x[i][j] = y[i] + z[j]

x[i][j] is traversed in order

y[I] is loop invariant

z[j] is traversed sequentially

changing loop order is not beneficial

in this case

For(it=0; it<n; it += nb)

for(jt=0; jt<m; jt += nb

for(i=it; i<min(jt+nb,n); i++)

for(j=jt; j<min(jt+nb,m); j++)

x[i][j] = y[i] + z[j]

Previous slide

Next slide

Back to first slide

View graphic version