A study of loop nest structures and locality in scientific programs

grantor: University of TorontoThis study evaluates four techniques that improve the structures of loop nests, in order to make transformations targeting perfect loop nests more applicable. These techniques are code sinking, loop distribution, loop distribution with scalar expansion, and loop fusion. This study also examines the subscript expressions of array references, in order to conclude whether spatial locality can be enhanced. This research is conducted on 23 applications from the Perfect Club, Nas, Spec92 and NCSA benchmark suites. The results indicate that code sinking and loop distribution--with or without scalar expansion--can be effective in increasing perfect nests, in more than half of the benchmark applications. The overhead introduced by loop distribution is negligible, while the overheads of code sinking and especially of loop distribution with scalar expansion are found to be prohibitive for some applications. Furthermore, in more than half of the benchmark applications, it is found that the array references exploit locality effectively. In only a quarter of the applications, loop permutation may be beneficial to spatial locality. Similarly, flexible data layout may be beneficial in only a quarter of the applications.M.A.Sc