An essential step in designing a new computer architecture is the careful examination of different design options. It is critical that computer architects have efficient means by which they may estimate the impact of various design options on the overall machine. This task is complicated by the fact that different programs, and even different parts of the same program, may have distinct behaviors that interact with the hardware in different ways. Researchers use very detailed simulators to estimate processor performance, which models every cycle of an executing program. Unfortunately, simulating every cycle of a single benchmark program takes on the order of months to complete. To address this problem we developed analysis techniques for characterizing the time varying program behavior. Using data clustering algorithms from machine learning to automatically find repetitive patterns in a program's execution we can avoid simulating the same behavior many times. By simulating one representative of each repetitive behavior pattern, simulation time can be reduced to hours instead of months for standard benchmark programs, with very little cost in terms of accuracy.This dissertation describes this important problem and the tool we created, called SimPoint, to automatically find simulation points in programs. Additionally, we describe data-mining and statistical advances in doing phase analysis that optimize both the runtime and accuracy of SimPoint as well as target the overall simulation time. We present an approach that finds a single set of simulation points to be used across all binaries for a single program. This allows for simulation of the same parts of program execution despite changes in the binary due to ISA changes or compiler optimizations. Finally, we present a method of characterizing the behavior of parallel applications and use it to pick simulation points to guide multi-threaded simulations

An essential step in designing a new computer architecture is the careful examination of different design options. It is critical that computer architects have efficient means by which they may estimate the impact of various design options on the overall machine. This task is complicated by the fact that different programs, and even different parts of the same program, may have distinct behaviors that interact with the hardware in different ways. Researchers use very detailed simulators to estimate processor performance, which models every cycle of an executing program. Unfortunately, simulating every cycle of a single benchmark program takes on the order of months to complete. To address this problem we develop analysis techniques for characterizing the time varying program behavior. Using data clustering algorithms from machine learning to automatically find repetitive patterns in a program's execution we can avoid simulating the same behavior many times. By simulating one representative of each repetitive behavior pattern, simulation time can be reduced to hours instead of months for standard benchmark programs, with very little cost in terms of accuracy. This dissertation describes this important problem and the tool we created, called SimPoint, to automatically find simulation points in programs. Additionally, we describe data-mining and statistical advances in doing phase analysis that optimize both the runtime and accuracy of SimPoint as well as target the overall simulation time. We present an approach that finds a single set of simulation points to be used across all binaries for a single program. This allows for simulation of the same parts of program execution despite changes in the binary due to ISA changes or compiler optimizations. Finally, we present a method of characterizing the behavior of parallel applications and use it to pick simulation points to guide multi-threaded simulations.

Pre-2018 CSE ID: CS2007-0896

SimPoint is a technique used to pick what parts of the program's execution to simulate in order to have a complete picture of execution. SimPoint uses data clustering algorithms from machine learning to automatically find repetitive (similar) patterns in a program's execution, and it chooses one sample to represent each unique repetitive behavior. These samples when taken together represent an accurate picture of the complete execution of the program. SimPoint is based on the k-means clustering algorithm, and recent work has proposed using a different clustering method based on multinomial models, but only provided a preliminary comparison and analysis. In this work we provide a detailed comparison of using k-means and multinomial clustering for SimPoint. We show that k-means performs better than the recently proposed multinomial clustering approach. We then propose two improvements, in the areas of feature reduction and the picking of simulation points, to the prior multinomial clustering approach, which allows multinomial clustering to perform as well as k-means. We then conclude by examining how to potentially combine multinomial clustering with k-means.

Pre-2018 CSE ID: CS2005-0841

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). This realization has ramifications for many architectural and complier techniques, from thread scheduling, to feedback directed optimizations, to the way that programs are simulated. However, in order to take advantage of time-varying behavior, we must first develop the analytical tools necessary to automatically and efficiently analyze program behavior over large sections of execution. Our goal is to develop automatic techniques that are capable of finding and exploiting the Large Scale Behavior of programs (behavior seen over billions of instructions). The first step towards this goal is the development of a hardware independent metric that can concisely summarize the behavior of an arbitrary section of execution in a program. To this end we examine the use of {\em Basic Block Vectors}. In this paper we quantify the effectiveness of Basic Block Vectors in capturing program behavior across several different architectural metrics (such as cache hit rates), explore the large scale behavior of several programs, develop a set of algorithms based on clustering capable of analyzing this behavior and automatically breaking the execution into a set of classes. We then demonstrate an application of this technology to automatically determine where to simulate for a program to help guide computer architecture research.

Pre-2018 CSE ID: CS2002-0701

Modern architecture research relies heavily on detailed pipeline simulation. The section of the program simulated is of great importance to the relevance and correctness of a study, since the behavior of the program can vary significantly during different phases of a program's execution. In this paper we propose Basic Block Distribution Analysis as a semi-automatic approach for determining where to simulate in order to achieve a representative sample of the program. This approach is based upon using the profiles of a program's code structure (basic blocks) to uniquely identify different phases of execution in the program. We show that this analysis accurately finds the periodic (cyclic) behavior exhibited during a program's execution across several different architectural metrics (e.g., IPC, branch miss rate, cache miss rates, value misprediction, address misprediction, and reorder buffer occupancy). More importantly, our basic block analysis finds simulation points representative of the whole program's execution for these different architectural features.

Pre-2018 CSE ID: CS2001-0667

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

Modern architecture research relies heavily on detailed pipeline simulation. Simulating the full execution of an industry standard benchmark can take weeks to months to complete. To address this issue researchers have recently proposed using Simulation Points (SimPoints) to increase the efficiency and accuracy of simulation. SimPoints are a small subset of execution intervals that are representative of a program's phases, so that when combined they accurately represent the complete execution of the program. These SimPoints are found using clustering techniques based on the structure of the executed code. The prior work on SimPoints assumed a somewhat advanced simulation environment that supported check-points, had perfect warm-up ability, and focused only on simulating single threaded architectures. In this research we explore what happens when you break these assumptions and provide techniques that are capable of dealing with more complex simulation environments. We focus on environments that have the ability to fast-forward, but to not checkpoint, and we extend the use of SimPoints to multi-threaded architectures. We present results comparing our improved SimPoint techniques with past SimPoint work and in addition provide a comparison to Random Sampling.

Pre-2018 CSE ID: CS2002-0727

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 examine applying these phase analysis algorithms and how to adapt them to parallel applications running on shared memory processors. Our approach relies on a separate representation of each thread's activity. We first focus on showing its ability to identify similar intervals of execution across threads for a single run. We then show that it is effective at identifying similar behavior of a program when the number of threads is varied between runs. This can be used by developers to examine how different phases scale across different number of threads. Finally, we examine using the phase analysis to pick simulation points to guide multi-threaded simulation.

Pre-2018 CSE ID: CS2005-0844