Unroll-and-jam using uniformly generated sets
Steve Carr, Yiping Guan · 1997
Modern architectural trends in instruction-level paral-lelism (ILP) are to increase the computational power of microprocessors significantly. As a result, the demands on nzemoq have increased. Unfortunately, memory systems have not kept pace. Even hierarchical cache structures are ineffective if programs do not exhibit cache locality. Be-cause of this compilers need to be concerned not only with finding ILP to utilize machine resources effective & but also with ensuring that the resulting code has a high degree of cache locality. One compiler transformation that is essentialfo? a com-piler to meet the above objectives is unroll-and-jam, or outer-loop unrolling. Previous work either has used a dependence-based model [7] to compute unroll amounts, significantly increasing the size of the dependence graph, or has applied a more brute force technique [Is], In this paper; we present an algorithm that uses a linear-algebra-based technique to compute unroll amounts. This technique results in an 84 % reduction over dependence-based tech-niques in the total number of dependences needed in our benchmark suite. Additionall]; there is no loss in opti-mization performance over previous techniques and a more elegant solution is utilized. 1.