Recent presentations about my research.

2015

The Judgment of Forseti: Economic Utility for Dynamic Heap Sizing of Multiple Runtimes

International Symposium on Memory Management, Portland, OR. Jun 2015.

(conference presentation of this paper)

Slides: [pdf]

The Judgment of Forseti: Economic Utility for Dynamic Heap Sizing of Multiple Runtimes

Department of Computer and Information Science, University of Oregon, Jun 2015.

(another version of earlier talk)

The Judgment of Forseti: Economic Utility for Dynamic Heap Sizing of Multiple Runtimes

Middleware Reading Group, School of Computing and Communications, Lancaster University, Jun 2015.

We introduce the Forseti system, which is a principled approach for holistic memory management. It permits a sysadmin to specify the total physical memory resource that may be shared between all concurrent virtual machines on a physical node, e.g. in a datacenter. Forseti seeks to maximize the combined throughput of the set of VMs based on concepts from economic utility theory. Our results show that Forseti enables dramatic reductions (up to 5x) in VM memory footprint without compromising application execution times. This is a practice talk for ISMM

Slides: [pdf]

2014

Mathematical Garbage: Formal Models of Memory Management

Computing Seminar, National University of Singapore, Sep 2014.

(similar to talk below).

Mathematical Memory Management

AiPL Summer School, Heriot Watt University, Aug 2014.

Garbage collection is no longer an esoteric research interest. Mainstream programming languages like Java and C# rely on high-performance memory managed runtime systems. In this talk, I will motivate the need for rigorous models of memory management to enable more powerful analysis and optimisation techniques. I will draw on a diverse range of topics including thermodynamics, economics, machine learning and control theory.

Slides: [pdf]

AspectJ for Runtime Behaviour Modification of Java Libraries

DSL Workshop, Heriot Watt University, May 2014.

AspectJ is a tool for aspect-oriented programming in Java. Aspects allow programmers to inject behaviour into code based on syntactic pattern matching on constructs from the original source program. In this talk, I will review the features of AspectJ - particularly its flexibility (good) and its user-friendliness (bad). I will report on a new project at Glasgow about modifying the behaviour of the Java Collections framework to enable graceful degradation of application performance when system memory is exhausted.

Slides: [pdf]

Compiler Optimizations: From Splendid Isolation to the Hive Mind

Glasgow Parallelism Group Seminar, University of Glasgow, Feb 2014.

This is a roadmap talk about general compiler optimisations. I will start by giving a brief overview of how compiler optimizations can be classified, discussing ahead-of-time optimization, feedback-directed optimization and runtime optimization. I will discuss how information sharing enables more effective optimization. I will argue that this trend is taking us to a Big Brother optimization utopia.

2013

ForgetMeNot

Embedded, Networked and Distributed Systems Seminar, University of Glasgow, Dec 2013.

In a future computational environment with terabytes of non-volatile RAM and petabytes of cloud-based backing store, can we avoid explicit delete/free()s and implicit garbage collection altogether? Health warning: this is a highly speculative, low-content presentation.

Slides: [pdf]

Utility-based Heap Sizing

Memory Management Network meeting, Google London, Dec 2013.

In this talk, we show how economic utility theory can be applied to heap resource allocation for multiple co-located virtual machines.

Slides: [pdf]

Elementary my dear Java: detecting patterns in object-oriented code

Software Engineering and Information Security Group Research Seminar, University of Glasgow, Nov 2013.

A brief overview of low-level patterns and their applications in code analysis.

Slides: [pdf]

Other languages on the JVM

Mostly Functional workshop at the Turing Festival Fringe, Edinburgh, Aug 2013.

This talk presents a comparative study of programs written in Java, Clojure, JRuby, Jython and Scala that execute on the JVM platform.

Slides: [pdf]

Control Theory for Adaptive Heap Resizing

Memory Management Network meeting, Heriot Watt University, May 2013.

We formulate heap sizing as a control problem, apply and tune a standard controller algorithm, and evaluate its performance on a set of well-known benchmarks. We find our controller adapts the heap size more responsively than existing mechanisms. This responsiveness allows tighter virtual machine memory footprints while preserving target application throughput, which is ideal for both embedded and utility computing domains. In short, we argue that formal, systematic approaches to memory management should be replacing ad-hoc heuristics as the discipline matures. Control-theoretic heap sizing is one such systematic approach.

Slides: [pdf]

Control Theory for Adaptive Heap Resizing

APT research group seminar, University of Manchester, May 2013.

(another version of above talk).

2012

Heap Sizing in Poly/ML

Symposium on Trends in Functional Programming, St Andrews. Jun 2012.

Typical theorem-proving workloads on the Poly/ML runtime system may execute for several hours, occupying multi-gigabyte heaps. The heap size may be fixed at execution startup time, or it may be allowed to vary dynamically. To date, runtime heap size growth has been implemented using simple hard-coded heuristics. In this talk, I will argue that a mathematically rigorous approach to heap sizing, based on control theory, is more appropriate.

Slides: [pdf]

Heap Sizing in Poly/ML

EdLambda Meeting, Edinburgh. Jun 2012.

(An earlier version of above talk)

Slides: [pdf]

Control Theoretic Heap Sizing

UK Memory Management Network meeting, Imperial College. Apr 2012.

I will motivate the need for mathematical models for heap memory usage, and outline how control theory can be applied to adaptive heap sizing. I will report on our experiences in Jikes RVM and Poly/ML runtime systems.

Slides: [pdf]

Bottom-Up Cloud Optimization using Control Theory

18th Crest Open Workshop on Multiplicity Computing, UCL. Mar 2012.

I discuss dynamic resources (threads, heap) required for program execution, and how varying the amount of resource allocated affects execution characteristics. I show how control theory may be used to optimize execution time, by controlling heap size. Then I go on to discuss how such tuneable resource allocation techniques can form the basis for holistic optimization of a cloud data center.

Video: MP4 (15mins)

2011

Java heap resizing: from hacked-up heuristics to mathematical models

Scottish Programming Languages Seminar, Heriot Watt University. Nov 2011.

In this talk, I review current heuristic approaches to setting the heap size in Java virtual machines. Then I outline two mathematical models for heap-resizing, based on microeconomic theory and control theory. I will argue that These rigorous mathematical models give a more principled approach to heap sizing.

Slides: [pdf]

A Literate Experimentation Manifesto

Onward! conference talk, Oct 2011.

Our concept of a literate experiment is to have a single, rich, human-generated, text-based description of a particular experiment. We aim to weave together the description with the meta-description of the experimental process.

Slides: [pdf]

Auto-tuning MapReduce Applications for Multicores

Computer Science Research Seminar, Heriot Watt University. June 2011.

The success of Google's MapReduce parallel programming pattern has led to alternative implementations for various scenarios. In this talk we present MRJ, a MapReduce Java framework for multicore architectures. We also explore the significant impact that Java runtime garbage collection has on the performance and scalability of MRJ. We advocate the use of machine-learning based auto-tuning techniques to reduce the performance deficit caused by garbage collection.


Slides: [pdf]

n-body Java fork/join implementation

SICSA Multicore Challenge Phase II Workshop, Glasgow University. May 2011.

Overview of my Java fork/join implementation of a planetary n-body simulation.


Slides: [pdf]

Flexi-Futures

EuroTM Plenary Meeting, Paris. May 2011.

This project investigates a novel extension to the Java programming language, providing support for flexible parallelism on next-generation many-core processors. The flexibility of our system is based on: (1) encoding descriptions of the level of accuracy provided by alternative implementations of a program module, allowing trade-offs between computational cost and precision; and (2) enabling the runtime system to determine adaptively when new parallel threads should be spawned. I argue that this kind of programming extension fits naturally in a transactional memory system setting.

Slides: [pdf]

Auto-tuning MapReduce Applications for Multicores

Computing Science Seminar, Stirling University. April 2011.

(earlier version of above talk)

Multicore data flow analysis

Institute for Computer Systems Architecture Colloquium, Edinburgh University. Feb 2011.

In current compilers, data flow analysis and code optimization are generally implemented using sequential algorithms. Given the commoditization of many-core platforms, it should be possible to use parallel algorithms instead. This talk describes how the standard sequential algorithm for constructing static single assignment form (SSA) may be parallelized. Then we demonstrate how this parallel algorithm may be realized in an existing compiler infrastructure, using light-weight threading mechanisms for Java.

Slides: [pdf]

2010

Java fork/join concordance implementation

SICSA Multicore Challenge Workshop, Heriot Watt University. Dec 2010.

Overview of my Java fork/join implementation of a text-file concordance application. Full code at http://sicsaconcordance.googlecode.com

Slides: [pdf]

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: [pdf]

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: [pdf]

Intelligent Thread-Level Speculation

Logic and Semantics Seminar, Queen Mary University of London, Jun 2009.

(earlier version of above talk)

Slides: [pdf]

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: [pdf]

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: [pdf]

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: [pdf]

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: [pdf]

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: [pdf]

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: [pdf]

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: [pdf/240K]

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: [pdf/160K]

Intelligent Selection of Garbage Collection Algorithms

Advanced Processor Technologies Group Meeting, University of Manchester. Apr 2007.

(earlier version of above talk)

Slides: [pdf/170K]

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: [pdf/340K]

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: [pdf/180K]

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: [pdf/295K]

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: [pdf/360K]

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: [pdf/405K]

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: [pdf/125K]

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: [pdf/895K]

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: [pdf/1.6M]

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: [pdf/272K]

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: [pdf/40K]

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: [pdf/94K]