How does it work?

The IOLB tool takes as an input a polyhedral program (written in C), and (optionally) a list of small parameters, whose product is at least an order of magnitude below the cache size. It returns a symbolic lower bound of the I/O complexity of this program.

Description of the inputs

The input is a C function, in which the polyhedral fragment to be analyzed is delimited by #pragma scop/endscop. "S" is a reserved parameter name (for the size of the cache), which cannot be used by the program.

You can provide the information that some parameters (and their product) are guaranteed to be very small compared to the symbolic cache size and the rest of the parameters. In that case, check the "Enable small dimensions" box and provide a list of parameters (and an hypothetical small value that will only be used to estimate which component of an expression dominates asymptotically).

The "Enable reduction detection" box allows the tool to gather the reduction dependencies together in its dataflow graph. This is useful for reductions of at least 2 dimensions.

The "Enable hourglass pattern detection" triggers the hourglass detection pattern, a specific pattern that occurs in several linear algebra application and imposes constraints on the tile shape. See this paper for the full details.

Description of the output

The IOUB tool provides:

• Inputs: the size of the inputs of the program, which is a trivial lower bound of the I/O complexity.
• Full expression: the full inferred I/O complexity lower bound.
• Asymptotic bound: the asymptotically dominant term of the inferred I/O complexity lower bound.
• Simplified expression: the asymptotically dominant term, when all non-small parameters are equal

"S" is a reserved parameter name, which corresponds to the size of the cache.