Tiling is a regular partitioning of a uniform index space representing either computations (e.g., the iteration space of a loop program), or data (e.g., arrays distributed over the processors of a parallel machine). Tiling can be used to achieve many different performance goals, such as exploiting data locality in hierarchical memory machines, communication optimisation by message aggregation, communication-computation overlap, and latency avoidance.

Being such a common paradigm, tiling is used by many different communities in computer science, each with slightly different perspectives. Application writers tune a given program for performance by hand using multiple instances of tiling, some times sacrificing portability and ease of programming and debugging. Compiler writers have the same performance goals, but apply tiling automatically to a wide class of programs. Hence their considerations include feasibility of an automatic solution, reasonable computation times, and efficiency and ease of automatic code generation. VLSI processor array and embedded system designers have other constraints in the global context of the application (real-time throughputs, power consumption), but are willing to accept slow compilers (or design assistant tools). And certain problems may be best resolved at run time, since all parameters may not be available at compile time.

Underlying all of these applications of tiling is the issue of optimality in the presence of limited resources, embodied as a non-linear discrete optimisation question.

• Is it possible to accurately model the machine behaviour with a few cost parameters for a wide variety of machines?
• Is it possible to use such a model to predict the cost of a given program?
• How tractable is the resulting optimisation problem (is it preferable to retain a less accurate model in the interests of tractability)?
• What are the consequences of separating multiple applications of tiling into separate optimisation problems?
• Is a more global approach needed?

Dagstuhl Seminar 98341 on Tiling was held 24 - 28 August 1998 with thirty six participants from seven countries. During the meeting there were twenty five lectures, a panel session, and several informal discussions. The outcomes of the meeting include

• Fruitful and ongoing discussion on all aspects of tiling (through the creation of a web site (http://www.irisa.fr/api/Rajopadhye/tiling/) and a mailing list (tiling@irisa.fr).
• The Dagstuhl-Seminar-Report 221, a collection of abstracts of all of the lectures.
• A panel discussion and follow-up activities on the creation of a common set of benchmarks for researchers in the community.