| Many applications access memory in an irregular manner, causing poor cache performance due to the lack of data locality. In complex scientific applications such as computational fluid dynamics and N-body simulation, irregular and/or dynamic accesses are abundant. Most research has been focused on improving locality in regular codes through computation and data reorganization. Unfortunately, since irregular codes have different computation structures, transformation techniques for regular computations are not directly applicable to irregular codes.; In my thesis, I present locality transformations of computation and data to exploit locality in irregular computations. Codes are first classified according to the number of irregular accesses in each unit of computation (e.g., loop iteration). Transformations are then applied appropriately. For sequential codes, data and computation reordering is applied. Computations are sorted based on the location of data being accessed. Elements of data are partitioned according to access patterns. For parallel codes, locality-conscious data and computation distribution is applied. Co-locating computation and data improves the parallel performance of irregular codes. Computations are replicated to avoid interprocessor communication when profitable.; Adaptive codes (whose access patterns change at run time) must rerun locality transformations after changes to retain the benefits of locality. However, data and computation reordering is not necessary after every change. A cost model is presented to take into account the overhead and benefit. All optimizations use an inspector/executor paradigm to combine compile-time and run-time optimizations. |
