IO Complexity lower and upper bounds

is a tool that computes symbolic bounds on the I/O complexity of a program, which is the minimal volume of communication required to perform a computation. It is composed of two parts:

Read about all the details here:

Research article - Automatic derivation of a lower bound of IO complexity [PLDI'2020] Research article - Automatic derivation of an upper bound of IO complexity [PLDI'2021]

What is I/O complexity ?

Let us consider a simple memory model composed of:

IO Complexity

Because of the limited size of the cache, some data might need to be transferred several times between the Cache and the Memory. The I/O complexity is the minimal amount of data needed to be transferred, for any schedule of the computation.

Here is an example of upper and lower bounds which were derived for the matrix multiplication computation. The Nx are the sizes of the matrices, and S is the size of the small memory:

Bounds on IO complexity for matrix multiplication

Try it!

Try the IOLB demo Try the IOUB demo

The code is also available on Gitlab: IOLB and IOUB

Additional Resources

Who are we?

is made by the CORSE Inria team. It is part of the PhD of Auguste Olivry and under the supervision of Fabrice Rastello. Guillaume Iooss (CRCN in CORSE) has also contributed to the IOLB tool.