Recently, some researchers have proposed a novel cache organization where cache partitions can be allocated to data objects by the compiler. It is shown that such cache architectures can provide the same performance as a conventional data cache many times larger. By partitioning the cache, significant amounts of interference and pollution are avoided. They propose efficient hardware implementations and show how necessary informations can be generated by the compiler from analyzing nested loops.

In this work, we consider the existence of such a cache organization, for which the compiler has to generate the number of partitions, their sizes and the data allocations. We use our concept of data sequence locality in order to develop an efficient cache partition allocation algorithm. Before generating the convenient informations, the original nested loops are transformed in order to improve temporal locality for reused data sequences that are made as small as possible. We show that informations issued from our precise analysis step can directly be used as parameters for the cache controller. Our approach has the effect of minimizing the sizes of the partitions while improving temporal locality. Hence, more partitions can be allocated and better cache locality is obtained. Moreover, sizes of the partitions can further be reduced by improving spatial locality: array data layouts are transformed such that accesses to data inside referenced reused data sequences are made with stride-one for a maximum number of references. Hence, these reused data sequences fill their allocated cache lines, and no useless data has to be stored while bringing data into the cache. We use for that our spatial locality optimization method.