2010
The Economics of Garbage Collection
Economics and Computation Group Seminar, University of Liverpool. May 2010.We argue that economic theory can improve our understanding of automatic memory management for Java applications. We introduce the allocation curve, as an analogue of the demand curve from microeconomics. An allocation curve for a program characterizes how the amount of garbage collection activity required during execution varies in relation to the heap size associated with that program. The standard treatment of microeconomic demand curves (shifts and elasticity) can be applied directly and intuitively to our new allocation curves. As an application of this new theory, we show how allocation elasticity can be used to control the heap growth rate for variable sized heaps.
Slides:![[pdf]](pics/acrobat.png)
The Economics of Garbage Collection
Advanced Processor Technologies Group Meeting, University of Manchester. Apr 2010.Memory costs money and programs are customers. We draw an analogy between memory management and micro-economic supply-and-demand theory, which is hopefully entertaining, if not entirely practical.
Slides:
2009
Intelligent Thread-Level Speculation
Cambridge Programming Research Group Meeting, University of Cambridge. Jul 2009.Thread-level speculation (TLS) is a mechanism for improving the execution of sequential programs on multi-core processors. TLS relies on the insertion of potential thread-spawn points into sequential programs, either statically or dynamically. Spawned threads generate parallelism, but they are only effective if (a) the parallel execution saving outweighs the thread management overhead, and (b) there are few data dependence vioations with other concurrent threads.
Until now, spawn points have been identified via (a) exhaustive profiling of programs, and/or (b) heuristics devised by human experts. We have recently begun a project that uses machine learning techniques to generate spawning heuristics automatically, with less program profiling. This presentation reports on the use of Java programs' static attributes and dynamic behaviour as features for learning effective TLS spawning policies.
Slides:
Intelligent Thread-Level Speculation
Logic and Semantics Seminar, Queen Mary University of London, Jun 2009.(earlier version of above talk)
Slides:
A metrics-based evaluation of SSA
Static Single-Assignment Form Seminar, Autrans, France, Apr 2009.Over the past 20 years, SSA has risen to become the compiler intermediate representation of choice. Compiler developers cite many qualitative reasons for choosing SSA. However in this study, we present clear quantitative benefits of SSA, by applying several standard software metrics to compiler intermediate code in both SSA and non-SSA forms. The average complexity reduction in using SSA ranges from 7% to 23% with our software metrics, over a set of standard SPEC benchmarks.
Slides:
Fundamental nano-patterns to characterize and classify Java methods
Workshop on Language Descriptions, Tools and Applications, York, Mar 2009.This talk describes simple, low-level patterns in Java methods that can be discovered via cheap static analysis of bytecode. Various nano-patterns are described, and then we present example applications for which these nano-patterns may be used.
Slides:
Using Java method patterns to predict runtime behaviour
Advanced Processor Technologies Group Meeting, University of Manchester. Mar 2009.We introduce a set of simple patterns that may be found in Java method source code. Examples include "method contains loop", "method makes recursive call", and "method throws exception". We can use the set of patterns that a method exhibits as an abstract summary of that method's source code characteristics. Next we perform runtime profiling to discover dynamic properties about each method as it executes. We use machine learning to link the simple source code patterns with the dynamic properties. This general approach has several exciting applications - at present we are concentrating on optimizing thread-level speculation.
Slides:
2008
Value Prediction (aka Calculated Guesswork)
Advanced Processor Technologies Group Meeting, University of Manchester. Jun 2008.Many-core machines have arrived. Speculative execution is a popular technique for speeding up sequential programs on such parallel hardware. Value prediction enables more effective speculation. We will review several schemes for value prediction in Java programs, and evaluate these on standard benchmark suites.
Slides:
Meaningful Type Names as a Basis for Object Lifetime Prediction
ASTReNet meeting on Information Retrieval and Program Analysis, King's College London. Mar 2008.This talk explains that extracting information from object type names can give a reliable and efficient way to make such object lifetime predictions. We use this approach to optimize a generational garbage collector in the Jikes RVM system.
Slides:
Metrics-Based Object Lifetime Prediction
Advanced Processor Technologies Group Meeting, University of Manchester. Feb 2008.An investigation of how various object-oriented metrics correlate with object lifetime in Java benchmark programs.
2007
Intelligent Garbage Collection
Advanced Processor Technologies Group Meeting, University of Manchester. Oct 2007.A general overview of how machine learning can be applied to optimize generational garbage collection. Reports on preliminary work to identify objects with similar lifetimes based on similar class names.
Slides:
Intelligent Selection of Application-Specific Garbage Collectors
Systems Group Seminar, Computing Laboratory, University of Kent at Canterbury. Sep 2007.Java program execution times vary greatly with different garbage collection algorithms. Until now, it has not been possible to determine the best GC algorithm for a particular program without exhaustively profiling that program for all available GC algorithms. Our new approach uses machine learning techniques to build a prediction model that, given a single profile run of a previously unseen Java program, can predict an optimal GC algorithm for that program.
Slides:
Towards Intelligent Techniques for Object Pretenuring
International Conference on Principles and Practice of Programming in Java, Sep 2007.Object pretenuring involves the identification of long-lived objects at or before their instantiation. It is a key optimization for generational garbage collection systems, which are standard in most high performance Java virtual machines. This talk presents a new study of factors that are used to indicate object lifespans. We adopt the information theory measurement of normalized mutual information to compare these various different factors in a common framework. A study of garbage collection traces from four standard Java benchmark programs shows that there is high dependence on some of these factors such as allocation site and object type. We also identify and measure new factors based on object-oriented metrics.
Slides:
Intelligent Selection of Garbage Collection Algorithms
Advanced Processor Technologies Group Meeting, University of Manchester. Apr 2007.(earlier version of above talk)
Slides:
Branch Prediction with Bayesian Networks
SMART workshop, Ghent, Belgium. Jan 2007.We study the architectural problem of branch prediction. We analyse the popular technique of two-level adaptive prediction, relating it to the state-of-the-art Machine Learning technique of Bayesian Networks (BNs). We show that a two-level predictor is an approximation to the BN formalism. This link allows us to explore the wider family of BN predictors. We investigate how to adapt BN techniques to operate within realistic hardware constraints, using the same primitive components that are present in existing branch predictors. We systematically study how performance is affected by these simplifications. We aim to use these ideas to reduce the storage overhead of BN predictors without losing significant prediction accuracy. The key motivating factor is that storage required in two-level predictors grows exponentially with branch history length, whereas BNs provide a framework to reduce this overhead.
Slides:
Branch Prediction with Bayesian Networks
Advanced Processor Technologies Group Meeting, University of Manchester. Jan 2007.(earlier version of above talk)
2006
Trends in JVM Software Development
Jamaica Group Meeting, University of Manchester. Dec 2006.I will give a high-level overview of some trends in JVM development practice. My basic premise is that JVMs are becoming increasingly complex software systems. At present, there are few effective mechanisms in place to manage this complexity. I think this problem presents an interesting research challenge!
Slides:
Garbage Collection, Program Comprehension and Machine Learning
UK Memory Management Network Workshop, Cambridge. Nov 2006.Take the best techniques from two diverse areas of computer science research - (1) program comprehension and (2) machine learning. Mix together and apply to memory management. Program comprehension allows us to study why garbage collection happens. Machine learning allows us to control how garbage collection happens. Preliminary results have been carefully cooked up in the Jikes RVM system, and taste delicious!
Slides:
Branch Prediction using Bayesian Networks
Advanced Processor Technologies Group Meeting, University of Manchester. Nov 2006.Successful branch predictors have three properties: high accuracy, low latency and low implementation complexity. This talk shows how branch prediction can be solved using the machine learning technique of bayesian networks. However the vanilla bayesian network classifier requires serious hackery to achieve the necessary levels of accuracy/latency/complexity for branch prediction.
Slides:
Dynamic Analysis of Program Concepts in Java
International Conference on Principles and Practices of Programming in Java , Aug 2006.Concept assignment identifies units of source code that are functionally related, even if this is not apparent from a syntactic point of view. Until now, the results of concept assignment have only been used for static analysis, mostly of program source code. This paper investigates the possibility of using concept information as part of dynamic analysis of programs. There are two case studies involving (i) a small Java program used in a previous research study; (ii) a large Java virtual machine (the popular Jikes RVM system). These studies demonstrate the usefulness of concept information for dynamic approaches to profiling, debugging and comprehension. This paper also introduces the new idea of feedback-directed concept assignment.
Slides:
Branch Prediction - folklore and facts
Advanced Processor Technologies Group Meeting, University of Manchester. May 2006.I will review basic concepts of branch prediction, then show how the Fano inequality can be used to bound predictor performance. I hope to describe two studies I have recently carried out. The first study involves optimal branch prediction for the quicksort algorithm. The second study uses trace files from the Championship Branch Prediction, a sort of World Cup for branch prediction designers.
Supporting Higher-Order Virtualization
Workshop on Compilers for Parallel Computers. Jan 2006.Virtualization is ubiqitous, with the global availability of the Java Virtual Machine and other similar virtual machine platforms. Higher-order virtualization involves building a stack of virtual machine layers. This provides obvious advantages such as: flexibility; separation of concerns; reuse of existing functionality; support for legacy platforms. However, the benefits of higher-order virtualization come at a price in terms of efficiency. This paper examines different techniques to increase the efficiency of higher-order virtualization on chip multiprocessor architectures. These techniques embrace hardware, software and virtual machine interaction. Some techniques (such as just-in-time compilation) are employed in existing virtual machine systems. Other techniques (such as hints-based speculative parallelism) have not been previously considered. We examine how to use these perfomance-enhancing techniques in the context of stacked virtual machine layers.
Slides:
Higher-Order Virtualization
Advanced Processor Technologies Group Meeting, University of Manchester. Jan 2006.(earlier version of above talk)
2005
Probabilistic Program Slicing
Dagstuhl Seminar on Beyond Program Slicing. Nov 2005.Probabilistic program slicing is a proposal for a new form of slicing. In this talk we will see that other program analyses have been adapted to handle probabilities. We will provide motivation for a probabilistic form of slicing. Then we give a simple walk-through example of probabilistic slicing. We conclude with a survey of the future work required.
Slides:
Entropy as a Measure of Predictability for Method Return Values
Advanced Processor Technologies Group Meeting, University of Manchester. Sep 2005.Highly predictable method return values provide tremendous scope for speculative parallelism. But how do we measure predictability? The most fundamental indicator is provided by the information-theoretic notion of entropy. In this talk, I will discuss entropy measurements for method return values from a set of standard Java benchmarks. The results have implications for both architecture and virtual machine.
Slides:
Concept Assignment as a Debugging Technique for Code Generators
Advanced Processor Technologies Group Meeting, University of Manchester. Apr 2005.Concept assignment is a program comprehension technique that relates high-level "human-oriented" concepts with low-level "implementation-oriented" source code. I will describe ongoing research that applies concept assignment to the analysis of code generators, such as those found in compiler backends. Anomalies in this analysis often indicate bugs in a code generator. I will show examples using my concept assignment tool operating on an experimental ARM code generator for the IBM Jikes RVM.
Slides:
Concept Assignment as a Debugging Technique for Code Generators
Cambridge Programming Research Group Meeting, University of Cambridge. Feb 2005.(earlier version of above talk)
Slides:
2004
Slicing the Static Single Information Form
ASTReNeT Slicing Day Workshop, Goodenough College. Nov 2004.Static single information form (SSI) is a recently proposed program intermediate representation that augments the classical control flow graph with dependence information. SSI encodes the dependence information in its variable naming scheme, in the same manner as static single assignment form (SSA). However, SSI encodes both control and data dependence, whereas SSA encodes only data dependence. In this talk, I will review SSI and show how it can form the basis for two efficient slicing algorithms.
Slides: