Fast Enumeration of Solutions for Data Dependence Analysis and Data Locality Optimization

Most of the sophisticated optimization tools dealing with data dependence analysis, parallelization and data locality exploitation cannot provide satisfactory solutions to a number of problems because they are, in general, unable to precisely handle some complex systems of linear equations coming from dependence equations between array subscripts. For such cases, these algorithms either provide rough estimates or resort to unefficient and therefore costly enumeration strategies. In this paper, we present an efficient technique, named Fast Determination, for dealing with the enumeration problem which degrades the behavior of sophisticated algorithms. Incorporating Fast Determination would enhance the performance and accuracy of existing algorithms, and widen their scope of application.