To understand performance behavior requires an inference process that correlates application trends to implementation decisions. This process can be divided into two tasks: (1) generate models that capture application trends, and (2) correlate application trends to implementation decisions.
Before we can understand performance behavior, we must provide support for model generation, which we plan to accomplish by integrating the Lost Cycles Toolkit into Carnival, as discussed in Section 5.3.
Descriptive models capture application trends. Also, they are usually accurate, since they represent the internal structure of the application (i.e., they are not just mathematical approximations of performance behavior). In order to generate descriptive models we plan to use static and dynamic information, and exploit the code hierarchy (i.e., the hierarchy of basic blocks and scopes). We intend to start by generating models for basic blocks (defined in Section 3.3.1), which are at the bottom of the hierarchy. Some of these models can be obtained statically, using symbolic timing analysis (discussed in Section 6.2.1), code inspection, or complexity analysis. Other models can be determined by analysis of dynamic information. In Section 4.4.2, we showed the use of Waiting Time Analysis to identify dynamic trends and generate waiting time models. These basic models are composed according to the code hierarchy, producing more complex models. The combination of simpler models is ruled by the relationships among the models that are being combined. If there is no interaction among the models (e.g., basic blocks that compose a scope), the composed model is just the summation of its components. Interactions among models must be identified and the combination must reflect the interactions, as was the case for waiting time models. We continue combining models until we reach the top of the hierarchy and generate a model for the whole application. The result we want to obtain from this modeling process is the code hierarchy augmented with models, where each model is described by a function and a set of components that contribute to the model. Components may be simple models, or static (e.g., symbolic analysis results) or dynamic explanations (e.g., waiting time characterizations).
Correlating performance trends to implementation decisions is also a bottom-up process, which augments the model hierarchy with implementation decisions that explain each model. Each implementation decision is assigned a weight function that expresses its quantitative influence on the model. We start by identifying implementation decisions that are responsible for each basic model. As we compose models according to the hierarchy, we also aggregate implementation decisions that explain the components that are being combined. This aggregation recalculates the weight functions associated with each component in order to reflect the influence of the component on the new model. For basic models generated using static information, the implementation decisions are the static features considered during the analysis. If it is possible, the implementation decisions are also assigned weight functions, otherwise they are grouped in a unique implementation decision. The implementation decisions responsible for a loop model, for example, include the loop's iteration space, which can be determined by the data distribution of a structure accessed within the loop. Basic models derived from dynamic information use their dynamic explanations (e.g., waiting time characterizations) to identify the components to be aggregated.
Figure 6.1: Understanding trends
A programmer can understand the performance behavior of an application by traversing its model hierarchy and inspecting models and their explanations. In Figure 6.1, we present a model for waiting time at a barrier as a function of the data size and the explanations for the model. This model has basically two components: (1) the data distribution of the variable A and its effects on the loop in lines 20 to 32, and (2) the loop in lines 234 to 257, whose contribution to the waiting time model does not vary with data size. This information can guide the programmer to reduce the waiting time (and therefore improve the application's performance) by changing the data distribution of variable A and the scheduling of the loop in lines 234 to 257. Note that the explanations direct the programmer to specific implementation decisions and also provide quantitative data about the importance of each decision.