Notes from the second wild and crazy session.
Dan Knights:
Develop a probabilistic generative model for a program's instruction trace similar to the topic model described by Blei, Ng, and Jordan ("Latent Dirichlet Allocation", 2003). I have envisioned several options. (1) The "vocabulary" consists of all unique instruction addresses, and each topic is a distribution over all vocab words. The "documents" are phases of the program, and there is only one topic per phase. The most naive approach here would be to use relatively short fixed-length "phases", although it would be better to infer the start and end of each phase jointly with the topics by adding some sort of scrolling window to each topic. The result would consist of (a) the topics, each corresponding to the behavior of the program during a particular phase of the program, and (b) the labels of the phases; (2) The "vocabulary" consists of general instruction types (add, sub, mov, branches, etc.). Each phase corresponds to a "document", and can be a mixture of topics. Alternatively an entire program can be considered a "document", and the inference will be performed on multiple programs.
Amer Diwan: Performance Semantics
When we design an optimization (e.g., a compiler optimization) we do it with a particular intention: e.g., to eliminate instructions that are redundant with other instructions. When we evaluate an optimization, we often ignore that intent and take whatever speedups we get happily.
The question is: how do we know that the speedups are due to what we intended and not something accidental? E.g., eliminating instructions may not be giving us the benefit but the change in code layout as a result of the eliminated instructions may be responsible.
The idea is to come up with a way of expressing the "intended performance semantics" of an optimization and then using dynamic checks to make sure that the speedups we are getting matches what we intended. E.g., we may use HPMs and if we find that the reduction in instruction counts matches the number of instructions we eliminated and other factors have not changed and that the speedup is approximately of the range we would expect from those eliminated instructions, we can believe that our optimization is doing what we intended it to do. Otherwise, something else may be happening which is worth exploring.