Karl Taht's Research Paper Blog

Authors: Bryan Donyanavard, Tiago Muck, Amir M. Rahmani, Nikil Dutt, Armin Sadighi, Florian Mauer, Andreas Herkersdorf Venue: MICRO 2019 This work presents a control theory / reinforcement learning hybrid approach to solve online parameter tuning for SoC's called SOSA. While controllers are typically known for being light weight, and RL expensive, the authors build the hierarchy opposite from what you might expect. The RL models, Learning Classifier Tables (LCTs), are used as low-level controllers, and high level supervisor controller uses Supervisory Control Theory (SCT). The SCT controls a high-level system model abstraction, which must be consistent with the low-level system "as defined in the Ramadge-Wonham control mechanism" [1]. This assumption requires further investigation. LCTs are a simpler RL algorithm compared to today's deep neural network approaches. They utilize rule-based learning to to target an objective function, which may be multi-variate. The...

Authors: Stephen J. Tarsa, Gautham Chinya, Hong Wang, et. al. Venue:    ISCA 2019 Preface : Before I begin, I'd like to preface that this is one of my favorite papers of 2019; it is well-written, shows poise in the application of machine learning techniques, and consideration of real-world applicability. I read this paper and produced my own slides for it, which can be found here . Overview: This paper presents an adaptive architecture controlled by a machine learning solution. Adaptive architecture itself is not a novel idea, there have been several works regarding tile-based clock gating, heterogenous core scheduling, pipeline gating, etc. This core chooses a simple adaptive piece of hardware, a binary decision to enable to disable a cluster. In this case, a cluster comprises of instruction cache, a decoder, memory execution unit, register file, ROB, and execution units. The authors hint at this being something like a modern SMT core, which can use all it's resource fo...

Venue: T ransactions on Autonomous and Adaptive Systems (TAAS) Authors: Gabriel A. Moreno, Javier Camara, David Garlan, Bradley Schmerl The title essentially encapsulates the problem which this paper is addressing. The setting is a Markov Decision Process, but with deterministic adaptations that do not effect the evolution of the environment. Restated another way, decisions do not impact the state, but rather the reward (and penalty). This leads to a separate notion of environment state  and system state . Note that the utility (reward) may be a factor of both. The innovation of this paper lies specifically in encapsulating that while deterministic, the different actions have different delays in terms of system state. The environment evolution is modeled via a discrete time markov chain (DTMC), which can be used to generate a partial probability tree. Specifically, an Extended Pearson-Tukey (EP-T) three point approximation. To encode latency, the progress of an adaptation is e...

Authors: G. E. Suh, L. Rudolph, S. Devadas Venue:    SuperComputing 2004 This paper was released around the same era in which multi-core CPUs began to go mainstream. As a result, this is one of the first works to address resource partitioning, specifically, LLC partitioning. The authors utilize a framework to partition the cache based of marginal gains by allocating more cache. The work proposes a framework to allocate cache chunks (groups of blocks) by this scheme. However, to minimize hardware overhead, they are only able to sample marginal gains by way-granularity. They mention that this is one of the reasons in which their scheme performs sub-optimally. The results show a few outliers with significant gains (30%+), but excluding these, the results are lackluster. The significance of this work is primarily that it addresses the subject and emphasizes the importance in the future. Full Text

Authors: David Lo, Liqun Cheng, Rama Govindaraju, Parthasarathy Ranganathan, Christos Kozyrakis Venue:    ISCA 2015 This work presents a resource controller and scheduler that works to improve the throughput of best-effort tasks while preserving the SLO for latency-sensitive applications. The work combines tuning by addressing many fronts: core isolation (taskset), LLC isolation (CAT), power isolation (DVFS), and network traffic isolation (qdisc). They show that because of the unique property that these form a convex function, each can be optimized individually by understanding the current load of the system and available slack, which is polled by the top-level controller every 15 seconds. Overall, they increase machine utilization to 90% without sacrificing SLO agreements, which is defined for 60-second windows. The authors demonstrate three latency-critical workloads: websearch, ml_cluster, and memkeyval, which each stress different combinations of cache, bandwidth, pow...

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: Ravi Iyer, Ramesh Illikkal, Omesh Tickoo, Li Zhao, Padma Apparo, Don Newell Venue:   Computer Networks 2009 The authors of this paper seek to understand the importance of resource allocation in a VM/cloud environment. At the time of publishing, only time-multiplexing and core allocation isolated VMs from a performance standpoint, which they refer to as a Virtual Platform Architecture (VPA) . The authors suggest that cache space, memory, bandwidth and power equally need to be virtualized as well. They focus on memory bandwidth and cache allocation. They motivate the problem by performing measurements and effects of resource contention and show significant performance degradation. Then then show that a simplistic model can perform fairly accurate predictions of cache occupancy, MPI, and cache contention. Perhaps the most elegant part of the paper is the description of the cache and memory bandwidth monitoring and allocation technology, which I assume laid foundatio...

Authors: Andreas Sembrant, Trevor Carlson, Erik Hagersten, David Black-Shaffer, Arthur Perais, Andre Seznec, and Pierre Michaud Venue:    MICRO 2015 The authors of this paper explore the utility of large instruction queues, load-store queues, register files, and other processor structures. These resources significantly boost performance by leveraging ILP and MLP. However, when resources are allocated to instructions that are not yet ready to be executed, it wastes significant energy. The authors spend significant effort to determine that a IQ of half-size (64->32), with a "Long Term Parking" structure for non-ready and non-urgent instructions, has negligible impacts on performance. Furthermore, the authors find that a majority of this benefit can be acquired via non-urgent instructions only. The authors then propose a solution to leverage this benefit, and find a design which is 1% slower, but 40% lower E(D^2)P for MLP-sensitive applications, and 3% slower but 38% l...

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:  Raghavendra Pothukuchi, Sweta Pothukuchi, Petros Voulgaris, Josep Torrellas Venue:     ISCA 2018 This work targets optimization of difference resources within a computer. The specific example used targets minimizing the energy-delay product via thread scheduling and DVFS on an Arm big.LITTLE board. This paper is done by the same authors of "Using MIMO Formal Control to Maximize Resource Efficiency in Architectures". While the prior work synthesizes many simultaneous optimization problems into a single controller, this work separates out the controllers into coordinated multi-layer formal controllers, specifically Structured Singular Value controllers. The SSV controllers offer the benefits of uncertainty guardbands for safety, max and min settings, discrete value support, and allow for passing information between multiple controllers. They call their generic framework Yukta (possibly named after the 1999 Miss World winner). The key idea is that this ap...

Authors: Ramazan Bitirgen, Engin Ipek, Jose F. Martinez Venue:    MICRO 2008 This paper presents a scheme to dynamically allocate system resources. The paper focuses on LLC cache partitioning via ways, bandwidth partitioning, and DVFS. They propose Coordinated Hill-climbing , to dynamically allocate these resources. The system profiles first in the default fair-share configuration. If the prediction framework has a high CoV (coeffient of variation) for the baseline performance, the algorithm does nothing. However, if the CoV is accurate, a profiling phase occurs. Once the initial training set is provided, the controller continues to sample for every 1 and 5 intervals. The model itself is a ensemble of fifty, 2-layer FC ANN's, each of which have 9 inputs (power, cache usage, read hits/misses, write hits/misses, bandwidth usage and L2 cache dirty ratio). The model attempts to predict the performance given the statistics. The model guides the search, such that search is shifte...

Authors: Raghavendra Pradyumna Pothukuchi, Amin Ansari, Petros Voulgaris, and Josep Torellas Venue:    ISCA 2016 This paper using control theory to design an adaptive system. While many approaches exist, the key novelty to this work is the multiple-input, multiple-output coordination which considers multiple trade-offs simultaneously to tune the system. The framework essentially uses several "training set" workloads to train a controller which is able to predict power and performance. Then, a "test set" of workloads is used to evaluate the controller's performance when trying to tune the power-performance trade-offs. The benefit is formal guarantees, however, the cost is the user requirement to specify reference values. More specifically, rather than "maximize x  trade-off", MIMO controller works best by specifying "achieve values x1, x2, with weights w1 and w2" for importance. Overall, this work excellently integrates considerations such a...

Authors:  Lisa R. Hsu, Steven Reinhardt (U Michigan), Ravi Iyer, Srihari Makinei (Intel) Venue:     PACT 2006 This paper examines the resultant partition of different LLC cache allocation policies on an multi-core (CMP) system. The overall finding is that while LRU-like policies tend to degrade into something like utilitarian policies. While at first glance this is may sound good, the metric of utility is raw-IPC, which gives bias toward program with high levels of ILP. The paper also explains that utilitarian policies can result in bad fairness, and likewise fairness policies can result in poor utility. Additionally, the paper goes on to show that different metrics (raw-IPC, misses-per-access, misses-per-instruction) result in drastically different cache partitioning schemes. The paper is more a case study than a proposed solution, and suggest that a more complicated, online policy will be required to target either utility- or fairness-based cache partitioning sc...

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