Performance comparisons are ubiquitous in computer science. The proceedings of most conferences are filled with bar charts comparing the performance of some computer system to another. For example, computer architects compare the performance of processors, and compiler writers compare the performance of generated code. It is difficult to prove that one computer system is always faster than another for all possible workloads, so these performance comparisons are used as predictors: performance is compared on several representative workloads, and the results are used to argue that one computer system is generally faster than another. Unfortunately, there are many scenarios where it is difficult to make a fair performance comparison. This dissertation focuses on two such scenarios. The first scenario involves simulations in computer architecture. Computer architects typically evaluate new processor designs through slow cycle-level simulation. Because of the poor performance of cycle-level simulators, accelerated simulation methodologies are very popular, where small samples of a program's behavior are simulated, and the results are extrapolated to predict the results of a whole-program simulation. But with these accelerated simulation techniques, it is difficult to meaningfully compare performance estimates when multiple compilations of a program are involved. This dissertation will show that simulation samples must be selected consistently across compilations to produce comparable results, and a technique will be presented to apply accelerated simulation across compilations to produce comparable results. The second scenario involves dynamic optimization systems. Dynamic optimizers must predict if their optimizations will actually improve performance before applying them --- if an optimization is unlikely to improve performance, or if an optimization will degrade performance, the optimization should not be applied. This dissertation presents a new approach to guide dynamic optimization decisions by performing empirical performance evaluations as programs execute. The performance of differently-compiled versions of the same code are measured, and the results of the measurements directly guide optimization decisions. The challenge is that these performance measurements are collected as programs execute, so individual measurements are not directly comparable, because the program may run the code under analysis with different inputs over time. If a single pair of performance measurements indicates that one version of the code is faster than another, it may actually be faster, or it may be that the program chose to run one version on a smaller input than the other. To overcome this challenge, this dissertation presents a statistical technique to analyze pools of timing data to determine which version is the fastest

Performance comparisons are ubiquitous in computer science. The proceedings of most conferences are filled with bar charts comparing the performance of some computer system to another. For example, computer architects compare the performance of processors, and compiler writers compare the performance of generated code. It is difficult to prove that one computer system is always faster than another for all possible workloads, so these performance comparisons are used as predictors: performance is compared on several representative workloads, and the results are used to argue that one computer system is generally faster than another. Unfortunately, there are many scenarios where it is difficult to make a fair performance comparison. This dissertation focuses on two such scenarios. The first scenario involves simulations in computer architecture. Computer architects typically evaluate new processor designs through slow cycle-level simulation. Because of the poor performance of cycle-level simulators, accelerated simulation methodologies are very popular, where small samples of a program's behavior are simulated, and the results are extrapolated to predict the results of a whole-program simulation. But with these accelerated simulation techniques, it is difficult to meaningfully compare performance estimates when multiple compilations of a program are involved. This dissertation will show that simulation samples must be selected consistently across compilations to produce comparable results, and a technique will be presented to apply accelerated simulation across compilations to produce comparable results. The second scenario involves dynamic optimization systems. Dynamic optimizers must predict if their optimizations will actually improve performance before applying them - if an optimization is unlikely to improve performance, or if an optimization will degrade performance, the optimization should not be applied. This dissertation presents a new approach to guide dynamic optimization decisions by performing empirical performance evaluations as programs execute. The performance of differently-compiled versions of the same code are measured, and the results of the measurements directly guide optimization decisions. The challenge is that these performance measurements are collected as programs execute, so individual measurements are not directly comparable, because the program may run the code under analysis with different inputs over time. If a single pair of performance measurements indicates that one version of the code is faster than another, it may actually be faster, or it may be that the program chose to run one version on a smaller input than the other. To overcome this challenge, this dissertation presents a statistical technique to analyze pools of timing data to determine which version is the fastest.

Pre-2018 CSE ID: CS2007-0895

Understanding program behavior is at the foundation of computer architecture and program optimization. Many programs have wildly different behavior on even the very largest of scales (over the complete execution of the program). Even so, programs tend to have repetitive behavior, where different parts of a program's execution behave in a similar manner. These similar intervals of execution can be grouped into phases, where the intervals in a phase have homogeneous behavior and similar resource requirements. This phase behavior can be exploited by tailoring architecture or compiler optimizations to a given phase, rather than at average or aggregate behavior as is typically done. In this paper, we compare using many different types of information for performing phase classification. The goal is to try to find the minimal amount of information to collect to accurately perform phase classification, and to do this without using architecture performance metrics. We compare using basic blocks, loop branches, procedures, opcode frequencies, register usage, register definitions, memory addresses, and working code and data set sizes. We also examine collecting this information in different data structures from working set bit vectors to frequency vectors. We compare these different structures in terms of their ability to create homogeneous phases. We then evaluate the performance of using the more promising of these structures to guide SimPoint.

Pre-2018 CSE ID: CS2003-0772

Most programs are repetitive, where similar behavior can be seen at different execution times. Algorithms have been proposed that automatically group similar portions of a program's execution into phases, where samples of execution in the same phase have homogeneous behavior and similar resource requirements. In this paper, we present an automated profiling approach to identify code locations whose executions correlate with phase changes. These ``software phase markers'' can be used to easily detect phase changes across different inputs to a program without hardware support. Our approach builds a combined hierarchical procedure call and loop graph to represent a program's execution, where each edge also tracks the average hierarchical execution variability on paths from that edge. We search the annotated call-loop graph for instructions in the binary that accurately identify phase changes across different inputs. We show that our phase markers can be used to accurately partition execution into units of repeating homogeneous behavior by counting cycles and data cache hits. We also use the markers to guide dynamic data cache reconfiguration, and show cache size reductions comparable to more complex cache reconfiguration techniques.

Pre-2018 CSE ID: CS2004-0804

Understanding program behavior is at the foundation of computer architecture and program optimization. Many programs have wildly different behavior on even the very largest of scales (over the complete execution of the program). Even so, programs tend to have repetitive behavior, where different parts of a program's execution behave in a similar manner. These similar intervals of execution can be grouped into phases, where the intervals in a phase have homogeneous behavior and similar resource requirements. This phase behavior can be exploited by tailoring architecture or compiler optimizations to a given phase, rather than at average or aggregate behavior as is typically done. In this paper, we compare using different levels of information for performing phase classification from the memory address stream to the code being executed, and their combination. We also compare using different representations of the information for performing phase classification from working set size, to working set bit vectors, and frequency vectors. We combine this with a comparison of different algorithms for creating a phase classification. We consider the use of vector difference and the k-means algorithms from machine learning to classify phases. For the code analysis, we examine the tradeoffs of tracking phase behavior with different code constructs from using only procedures, to only loop branches, to using basic blocks, and their combination. Finally, we examine using data stream profiles to improve the homogeneity of code-based phase classification.

Pre-2018 CSE ID: CS2003-0757

Most programs are repetitive, where similar behavior can be seen at different execution times. Proposed algorithms automatically group these similar intervals of execution into phases, where the intervals in a phase have homogeneous behavior and similar resource requirements. These prior techniques have focused on using fixed intervals for finding phase behavior. Using fixed length intervals can make finding the true periodic repeating phase behavior difficult, since the fixed length intervals can be out of sync with the size of the ideal phase behavior. In addition, focusing only on a single fixed interval size limits the phase behavior to the phase behavior seen at that interval size, when in reality there is a whole hierarchy of phase behavior at many different intervals sizes. In this paper, we present an automated approach for breaking the program's execution up into variable length intervals that match the phase behavior of the program. We then provide an algorithm for creating a hierarchy of variable length intervals and use this hierarchy to expose a program's phase behavior from small to large time scales.

Pre-2018 CSE ID: CS2004-0781