Karl Taht's Research Paper Blog

Authors: Canturk Isci, Gilberto Contreras, and Margaret Martonosi Venue:   MICRO 2006 The authors of this paper present a real-system framework which enables phase detection, phase prediction, and system reconfiguration. The phase detection is done using performance counters, more specifically, phases are classified based on their ratio of memory bus transitions to micro-ops retired. This is mapped to how compute vs. memory bound an application is, and thus, the DVFS can be adjusted accordingly. Phase prediction is done in a similar fashion to the TAGE branch predictor, using a global history table which tracks 1024 entries and a history of 8. The framework achieves an 18% EDP improvement with a 4% performance loss on average across SPEC 2000 benchmarks. Note that their phase detection framework and performance counter selection is geared specifically toward DVFS optimization, and is justified through analysis in the paper which demonstrates a specific relationship present....

Authors: Xiaofei Liao, Rentong Guo, Danping Yu Venue:    International Journal of Parallel Programming 2016 The authors present a novel dynamic cache partitioning mechanism based on the phase behavior of program. They use a similar phase detection to Sembrant et al. to detect phases. To reduce the overhead further, they make an assumption that the current phase will continue, and trigger only a phase change when the IPC deviates more than a threshold. To partition the cache, they utilize their FractalMRC algorithm, which predicts the optimal cache partitioning via a miss-rate-curve. If the phase is already seen, then the MRC will be stored in the table. They show that overall their approach nets up to 21.4% performance improvement using Spec2006 benchmarks. The authors cite low overhead ~1%-2% on average in various configurations. However, it is unclear if this also factors in the overhead of the FractalMRC algorithm, which they state has an overhead of "less than 1s to c...

Authors: Andreas Sembrant, David Black-Schaffer, Erik Hagersten Venue:    IISWC 2012 This paper extends ScarPhase to be feasible in a multi-threaded environment. This is made possible by tracking the same data as ScarPhase on a per-phase basis. The authors make note that global sharing (phase IDs, phase predictors) does not improve performance much, this seems to be due to the fact that when new "phases" arrive, they arrive simultaneously in multiple threads. Thus global sharing would not improve the accuracy or quality of the phase detection, but rather remove redundancy. However, the redundancy may be preferable from an implementation perspective. This paper primary focus on workload analysis rather than the phase detection algorithm. The authors show that PARSEC displays much less phase behavior when compared to Spec2006. Additionally, as the number of threads scales in data-parallel applications, phases becoming increasingly shorter (assuming the same data), and eventuall...

Authors: Andreas Sembrant, David Eklov, Erik Hagersten Venue:    IISWC 2011 The authors develop an online phase detection algorithm that works by approximating Basic Block Vectors (BBVs) by sampling conditional branches, made possible by PEBS. The algorithm operates on real-hardware, online, and uses fixed 100M instruction count windows. They show that while conditional branches encapsulate less information that all branches, when you are sampling, conditional branches provide better information. They evaluate their phase detection algorithms using the coefficient of variation, comparing the CoV within a phase to the global CoV. They additionally provide a metric which penalizes creating new phases. Finally, they utilize a Markov Predictor, similar to Sherwood and show accurate phase prediction as well. Overall, this paper does an excellent job of solving many off the challenges of phase detection: Feasible with real hardware with a low overhead of less than 2% Address ...

Authors:   Evelyn Duesterwald, Calin Cascaval, Sandhya Dwarkadas (IBM, Rochester) Venue:      PACT 2003 This paper makes no effort to tune hardware, but shows yet another phase detection and prediction technique. The study is done on real hardware, using IBM Power3 and Power4 architectures. Both of these are extremely outdated, but it makes for an interesting paper nevertheless. They are able to instrument their phase detection techniques on OS interrupts at a granularity of 10ms. At this time, they read various performance counter, analyzing the current hardware state and predicting the future hardware state. It is not entirely clear how they actually determine a phase, but essentially, they are able to accurately predict different performance metrics such as IPC, branch miss-predict rate, and L1 cache miss rate. They support the use of table-based predictor. They also show that most statistics are extremely correlated, so a predictor for one metric can li...

Authors:     Xipeng Shen, Yutao Zhong, Chen Ding  (University of Rochester) Venue:        ASPLOS 2004 Locality Phase Prediction presents an offline phase detection and prediction scheme. While, previous phase detection works use repeating branches or performance counters to identify program phases, locality phases are defined by the data locality. More formally "a locality phase ... [is] a period of program execution that has stable or slow changing data locality inside the phase but disruptive transition periods between phases." Additionally, it is important to note their definition of a phase: "a phase is a unit of repeating behavior rather than a unit of uniform behavior." The claim is that these types of phases are particularly common in simulation-type programs, which will often process over a (data) structure many times, as they calculate behavior at each time-step. In order to extract the phases, they use data reuse distance, which is va...

Authors:     Priya Nagpurkar ...et.al ...  V.T. Rajan (UC Santa Barbara, IBM Research) Venue:        International Symposium on Code Generation and Optimization, 2006 The paper presents a novel phase detection algorithm The main claims are: a client- and machine-independent baseline methodology for evaluating the accuracy of an online phase detector, a metric to compare phase detectors, empirical evaluation of numerous phase detectors (using Java applications). The phase detection in this paper builds off the idea that during execution, there exist two key states: stable phase, and transition period. They use a model which constant accepts inputs, and then when in a stable phase, grows the "trailing window" size to the size of the stable phase. They call this notion an adaptive trailing window policy. The paper uses an offline baseline to evaluate the online phase detection algorithms. The biggest contributions this paper seems to make is: ...

Authors:      Ashutosh S. Dhodapkar and James E. Smith (U. Wisconsin - Madison) Venue:         ISCA 2002 This paper is one of the first to propose working set signatures to detect and recall program phases. This eliminates the need for re-training phases, and can also be used to predict features like proper cache size. The signature is generated by hashing each branches into an N-bit vector. The vector is unweighted meaning that, it simply encapsulates whether or not the hash of a branch was seen. They use 128 byte vectors for 100K instruction windows (fine grain). This paper should mainly be seen as a building block, as it is some of the earlier work in phase detection. Key issues are: too frequently sampling (every branch committed), too frequent changes (100K instructions, doesn't account for cost of context switch), and targeted reconfiguration (instruction cache size -- typical programs now multiple MB). This paper has good informatio...

Authors: Tim Sherwood, Suleyman Sair, Brad Calder Venue:    ISCA 2003 The primary goal of this paper is to develop a phase detection and prediction mechanism that can guide optimizations for large-scale program behavior. The phases are detected based on the code being executed. Unlike Dhodapkar and Smith's work, their technique uses a basic block vector approach that also encapsulates time spent executing each code block. This paper also uses branch IP's to build basic block vectors, but, hashes them rather than using random projection. They show that a relatively small hash (32 buckets) is sufficient. Additionally, most of the programs execution can be captured using just 20 unique phase ID/signatures. To determine is a new vector is a new phase, they use the L1 distance set to an emperically determined threshold value. To determine the quality of phases, they look at the standard deviation of various counters on the global scale and for individual phases, showing that each ...

Authors:   Tim Sherwood, Erez Perelman, Brad Calder (UC San Diego) Venue:      PACT 2001 As the title states, the key problem this paper seeks to solve is finding simulation points. To do this, they come up with basic block vectors analysis (BBVA). BBVA uses BBV's, which can be collected in an environment more similar to running the default program than simulation, and as a result, is many orders of magnitude quicker than simulation. They use the BBV's to determine the relative sizes of each phase, i.e., how much duration of program execution they represent. Then using other tricks such as Fourier analysis, they are also able to analyze the cyclic behavior. Full Text

Authors:   Tim Sherwood, Erez Perelman, Greg Hamerly, Brad Calder (UC San Diego) Venue:      ASPLOS 2002 This paper introduces the concept of Basic Block Vectors (BBV). A basic block is defined as a piece of code with one entry and one exit. A basic block vector consists of an element for each basic block. The value in that block corresponds to the number of times the block was seen multiplied by the number of instructions in the block. Similar phases, or basic blocks, need not be temporally adjacent. One particularly interesting components is there phase detection algorithm. There basic block vectors are often millions of dimensions, and they use random linear projection to reduce the dimensionality 15. They use k-means multiples times and score the result using BIC - Bayesian Information Criterion. Full Text