Instance-based locality optimization[6] is a semi-automatic program estructuring method that reduces the number of cache misses. The method imitates the human approach of condisering several small program instances, optimizing the instnaces, and generalizingthe structure of the solutions to the program under consideration. A program instance appears as a sequence of statement instances that are reordered for better locality. In [6], a local search algorithm was introduced that reorders the statement instances automatically. This paper supplements [6] by introducing a second objective into the optimization alogrithm ofr program instances: regularity. A sequence of statement instances is called regular if it can be written compacly using loops. We uantify the intuitive notion of regularity in an objective function, and inorporate this function into the local search algorithm. The functionality of th compound algorithm is demonstrated with examples, that also show trade-offs between locality and regularity.
展开▼
