The problem

• Processing Speed is improving faster then memory speed
• Cache fetches take time
• Especially on parallel machines

Computer Memory Architecture

• Registers
• L1 cache
• L2 cache
• RAM
• Disc
• Carved in stone by monkeys

Matrix Multiplication

for i = 1 -> n
    for j = 1 -> n
        for k = 1 -> n
            c[i][k] += a[i][j] + b[j][k]

• Problem:
• Fetches a block of i's and j's at the same time
• Flushed out before they are used - does j * k operators before using i.2
• But by the it walks the j and k loops, it will have flushed them out

Tiling

• Idea
• Do blocks of i, j's to minimize caching

for J = 1 -> n by s
    for K = 1 -> n by s
        for i = 1 -> n
            for j = J -> min(J + s - 1, n)
                for K = K -> min(K + s - 1, n)
                    c[i][k] += a[i][j] + b[j][k]

• Uses the block of memory that has already been fetched:

Spatial representation of a loop

Types of Reuse

• Self-Temporal Re-use

for i = 0 -> 10
    arr[i] = y + i;
}

• Self-Spatial Re-use

for i = 0 -> 10
    A[i] = y[i]

• Group-Temporal Re-use

for i = 0 -> 10
    A[i] = y[i]
    B[i] = y[i]

• Group-Spatial Re-use

for i = 0 -> 10
    A[i]   = y[i*2]
    A[i+1] = y[i*2+1]

Transformations

• Skew
• Reversal
• Permutation Transformation

Algorithm

• Goal - Re-order loops in order to allow for tiling
• Input - N : loops, D: dependdencies
• Move serializing loops out
• Construct fully permutable loop nest F
• Search for permutation which allows for a fully permutable loop
• If found - Move to outside of the loop
• Repeat