Analytical modeling of codes with arbitrary data-dependent conditional structures

Several analytical models that predict the memory hierarchy behavior of codes with regular access patterns have been developed. These models help understand this behavior and they can be used successfully to guide compilers in the application of locality-related optimizations requiring small computing times. Still, these models suffer from many limitations. The most important of them is their restricted scope of applicability, since real codes exhibit many access patterns they cannot model. The most common source of such kind of accesses is the presence of irregular access patterns because of the presence of either data-dependent conditionals or indirections in the code. This paper extends the Probabilistic Miss Equations (PME) model to be able to cope with codes that include data-dependent conditional structures too. This approach is systematic enough to enable the automatic implementation of the extended model in a compiler framework. Validations show a good degree of accuracy in the predictions despite the irregularity of the access patterns. This opens the possibility of using our model to guide compiler optimizations for this kind of codes.