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: 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:     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: 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 ...