Poly.jl Documentation

Runs a Polyhedral model on the input for loop. May reorder instructions (including loop orderings) and vectorize code. Only the outermost loop should use the macro. By default, will also tile code. See below for more details.

Example

@poly_loop for i = 1:n
    for j = 1:m
        for k = 1:r
            out[i, j] += A[i, k] * B[k, j]
        end
        out[i, j] *= 2
    end
end

(runs a matrix multiplication and double)

Tiling

Loops will be automatically tiled based on l1 cache sizes unless tile=0 is set.

Example No Tiling:

@poly_loop tile=0 for i=1:n
    arr[i] = 1.0
end

Tiling is usually faster, but in cases where the loop bounds are small it will just introduce more loop overhead. Unless tile=0 is set, the outermost band (grouping of permutable loops) will be tiled.

Threading

To enable multithreading of the outermost loop, pass thread=true (disabled by default):

Example:

@poly_loop thread=true for i=1:n
    arr[i] = 1.0
end

Debugging

Debugging and verbosity options (see runpolyhedralmodel for details) can be passed like:

julia> @poly_loop debug=true verbose=2 for i=1:4:n-1
    arr[i] *= arr[i + 1]
end

This will print out the following information, depending on the verbosity level set:

• 0: no printing (unless debug=true, where ISL errors are printed)
• 1: final Julia expression is printed
• 2: initial C code, loop orderings, new schedule, final C code, and final Julia expression printed
• 3: all of 2 plus domain, access relations, dependence relations, original schedule, and new schedule constraints printed

Functions

If a function modifies any inputs, then there is no way to know which inputs are modified or how those inputs are modified. If a function returns an output such as a matrix, the write to each individual index of the matrix (for example A[i, j]) cannot be inferrred by ISL. In addition, @inbounds is not neccessary (or allowed) as the aggresive transformation will add @inbounds automatically.

Loop Bounds

This also applies to loop bounds. One easy workaround is something like:

juila> n = size(out, 1)
julia> @poly_loop for i = 1:n
    out[i] += 1.0
end

Exceptions

The only exceptions are the following functions (which can be used in loop bounds and in instructions): min():

@poly_loop for i=1:min(n, m)
    arr[i, i] = 1.0
end

max():

@poly_loop for i=1:max(n, m)
    arr[i, i] -= 1.0
end

floor() -> DO NOT cast to Int() (will be added later):

@poly_loop for i=1:floor(n/2)
    arr[i] += 1.0
end

Example

@poly_loop for i=1:n
    for j=1:floor(n/2)
        arr[i, j] += 1.0
    end
    for jj=floor(n/2):n
        arr[i, j] *= 2.0
    end
end

Interpolation

As a workaround, this macro supports interpolating the values into the function so that ISL has access to the numerical values (and non-numerical strides MUST be interpolated). This delays the analysis to runtime, so it is advised that interpolated values are typically constant so that compilation does not occur over and over.

Examples:

@poly_loop for i=1:$c:n
    arr[i] = 1
end

@poly_loop for i=1:$c:$n
    arr[i] = 1
end

In addition, any constants can be interpolated, and sometimes this may improve the performance of ISL. Numerical bounds can help with tiling and inference on spaces. However, it is important that interpolated values are actually constants, or very rarely change, so that this delayed compilation does not occur regularly during runtime.

Example:

julia> c = i + j
julia> A[c]

Must become

julia> A[i + j]

Example:

NUM_TILES = Int(N/TILE_SIZE)
@poly_loop for t=1:NUM_TILES
    A[TILE_SIZE*t] = 1
end

Would need to become this:

@poly_loop for t=1:$TILE_SIZE:N
    A[t] = 1
end

If/elseif/else blocks:

Example:

@poly_loop for i=1:n
    if i%2 == 0
        A[i] = 1
    else
        A[i] = 2
    end
end