Improving the computational intensity of unstructured mesh applications

Although unstructured mesh algorithms are a popular means of solving problems across a broad range of disciplines - from texture mapping to computational fluid dynamics - they are often dominated not by computation, but by mesh overhead. Our study of an object-oriented mesh-based benchmark reveals that 72% of its execution time is spent on mesh-related operations, such as iterating over faces or chasing pointers. We report a series of optimizations - some traditional, some novel - that dramatically improve the benchmark's computational intensity - the ratio of floating point operations to memory accesses. This improvement is attributable to an eight-fold reduction in memory operations and results in a 4.7× speedup in execution time. Our work demonstrates that common subexpression elimination and code motion are important optimizations for mesh-based codes. However, conservative analysis prevents their application. We discuss these barriers to analysis and argue that an understanding of mesh semantics complements more traditional analyses, such as pointer alias analysis, and certifies the correctness of these optimizations. Our identification of overheads in mesh-based codes, optimizations that address them, and limitations of current compiler analyses are required for our eventual goal of automating these optimizations in a semantics-aware compiler.