Friday, June 17, 2005

The optimal memory tiling problem

Given a (rectangular???)loop nest, with uniform dependences, further, with all dependences in first orthant (with enough skewing), find a time optimal running of the loop nest with the following model
r number of registers with access time of each as t_r (for the registers)
n types of memory references all of access times t_n (for )
further, a memory reference l accesses m[l] number of times its memory
given a schedule, for example, iteration order: i_1 ... i_d
split the iteration space into two types of accesses: i_1 ... i_d and t_1 ... t_d

find the following:
a permutation order for the inter tile and intra tile
given a permutation, give a size of tile in that dimension s_1 ... s_d (each of them could be maximal or of unit size)

No comments: