Performance understanding resembles a cause-and-effect inference process where we ``learn'' about an application's behavior. The results of this process are explanations that relate implementation decisions to an application's poor performance. One way to determine these explanations is to organize the understanding process as a set of questions that we pose about the application. By answering these questions, we get information about the application's behavior and its internals, up to the point where we identify implementation decisions that are causing performance problems and should be reevaluated (e.g., data distribution, loop parallelization).
Consider an execution of a simple application that consists of a synchronization-free loop followed by a barrier. We start by checking whether our application is efficient via global performance metrics such as speedup and efficiency. Checking the application's speedup, we see that it is performing poorly. We proceed and find out (using observation techniques) that the processors wait at the barrier longer than the time to release the barrier if all of them arrive simultaneously. Considering the application structure, we can suggest three possible causes for this imbalance (among others): (1) the loop iterations are evenly divided among processors, but they have different costs; (2) the loop iterations are not evenly divided; and (3) external factors are disturbing the execution of some processors (e.g., one of the processors is delayed at the beginning of the execution because of multiprogramming). The imbalance we are observing can be caused by one or more of these factors and determining the real causes and their contribution to the observed imbalance can be very hard, since it requires complete knowledge of the program characteristics and detailed analysis of performance data.
We might also observe that the synchronization time at the barrier increases linearly with respect to the number of processors (p) employed. Then we find out that load imbalance in the preceding loop is the main cause of synchronization time at the barrier for all instances of p, and also increases linearly with p, which explains the behavior at the barrier. We proceed and discover, for example, that the loop exhibits that behavior because of the data distribution adopted for certain data structures accessed within the loop.
Note that the explanations for performance phenomena of particular executions are used to explain trends across multiple executions. Thus, although the two understanding tasks seem different, they use the same information for providing explanations at both levels.
The performance understanding process can be seen as many steps, and one cause-effect relation is determined in each step. We can divide each of these steps into two actions:
Thus, for each performance phenomenon we do cause-effect analysis, which results in a relation that associates the phenomenon to its causes. Knowing these cause-effect relations, we can improve application performance by addressing the primary causes of performance problems. Considering the simple example given earlier, if we find out that the idle time at the barrier is caused by an uneven distribution of loop iterations, the next step in the inference process would identify the work distribution in the loop as the cause for the load imbalance. We can reduce this load imbalance and improve the program's performance by adopting a more appropriate work distribution.
This inference process is not always tractable however, since it must consider the application's dynamic behavior and interactions with the execution environment. The simplest approach to determine these relations is based on trial-and-error, where we guess the causes of observed performance problems, modify the program, and observe the results. If the problem persists, we make another guess. This approach presents three basic problems: (1) The programmer must determine the explanations, which rely on his knowledge of the application and parallel system. (2) There is no maximum number of trial iterations that must be performed in order to determine the cause-effect relations. Also, some performance problems are inherent to the parallelization (e.g., loop serialization) and cannot be alleviated. Thus, without knowing the real causes of performance problems, we may try exhaustively to solve them when it is not possible. (3) In trying to alleviate a performance problem, it may become worse (i.e., as the programmer does not know the real cause, his trial solution may contribute to the performance problem) or new problems may arise. All these problems are caused by the difficulty of determining the cause-effect relations, which can be explained by three characteristics of these relations:
In order to find cause-effect relations easily, we need techniques that are able to handle large amounts of data, keeping track of performance phenomena. Such techniques are good candidates for being automated, to make the inference process faster, easier, more accurate, and less dependent on the user's skills and knowledge.