Computer Laboratory

MPhil, Part III, and Part II Project Suggestions (2021-2022)

Contact

 

 

 

 

 

 

 

  

 

Please contact Eiko Yoneki (email: eiko.yoneki@cl.cam.ac.uk) if you are interested in any project below. * indicates high recommendation!

1.   Bayesian optimisation tuning with transfer Learning from simulation to databases **  

Contact: Eiko Yoneki (with Sami Alabed)

Databases come with a large number of tunable configurations [1]. We successfully used Bayesian optimisation in tuning varying numbers of parameters. However, a common issue when tuning these parameters is that a single experiment takes a long time to evaluate. One way to deal with the long evaluation time is to leverage other data sources. This project goal is to study using fast-to-execute simulators to aid the convergence speed of the optimiser. FoundationDB [2] is a recent popular database built as a simulator first and provides first-class support to performance and simulation testing at 1/10th the actual execution time [3]. This project proposes using Multi-fidelity [4] as an optimisation method to integrate the simulator in the Bayesian optimisation loop. This framework enables transfer learning from a low-accuracy-cheap model (simulator) to a high-accuracy-expensive model (FoundationDB).

[1] https://github.com/apple/foundationdb/blob/master/flow/Knobs.cpp
[2] https://www.foundationdb.org/
[3] https://apple.github.io/foundationdb/testing.html
[4] Song, J., Chen, Y. and Yue, Y., 2019, April. A general framework for multi-fidelity Bayesian optimization with gaussian processes. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 3158-3167). PMLR.

2.   Structured Bayesian optimisation with probabilistic programs  **

Contact: Eiko Yoneki

Bayesian optimisation (e.g., [1]) offers a data-efficient approach to global optimisation of black-box functions by building a model of the unknown function, including our uncertainty about its values we have yet to observe. [2] introduces a general framework for performing structured Bayesian optimisation, where a probabilistic programming language provides a flexible means for defining surrogate models that can incorporate prior knowledge of structure in the underlying problem. In [5], we have further integrated the structure of the performance model as Directed Acyclic Graph (DAG) with BoTorch, where the experts can encode their understanding of the system in probabilistic models connected by edges denoting dependencies. The DAG model incorporates the parametric models defined in Pyro or PyTorch.

The goal of this project is to further extend [5] with the ability to deal with high dimension parameter space, as well as adding multi-objective functionality, where you need to extend the design of DAG.

[1] Practical Bayesian Optimization of Machine Learning Algorithms
[2] BOAT: Building Auto-Tuners with Structured Bayesian Optimization
[3] Pyro
[4] Performance tuning of systems
[5] Auto-tuning Spark with Bayesian optimisation


3.   Model-based Reinforcement Learning in Computer Systems  **

Contact: Eiko Yoneki (with Sami Alabed)

Reinforcement learning (RL) is gaining interest as a generic optimisation and control method in data management tasks such as resource management/scheduling, database tuning, or stream processing. A central challenge in applying RL to such problems are long decision evaluation times. A single step in a real system may take multiple minutes, as opposed to simulators for standard benchmark tasks (e.g. Atari games), which can execute thousands of steps per second.

One way of improving sample efficiency is model-based RL [1], wherein a model of the environment is learned and subsequently used to plan and evaluate decisions. A 'world-model' approach first learns a compressed version of a state representation, then a recurrent mixture density network to predict future state / reward distributions of compressed states which can be used in place of a simulator [2]. In this project, the student will evaluate a world-model based approach against a model free approach using software infrastructure built in our group [3]. In [3], A2C (Advantage Actor Critic) algorithm is used. However the world model is algorithm agnostic and you can further investigate other algorithms such as the Rainbow comparison [7], which was used Model-Based Reinforcement Learning for Atari paper for their comparisons. You can explore PPO or C51, which could yield better sample complexity and/or max performance.

Example applications include stream processing scheduling, static graph rewriting (e.g. TensorFlow, LLVM IRs), and various database administration tasks. The aim of the project is to evaluate different representations (e.g. graph neural networks) and planning modes to gain novel insights into cost/benefits of model-based deep RL for this domain. The previous project work on Neural network subgraph transformation has built a solid codebase on WM and it can be used as a starting point. The suggestive project is selection of LLVM compiler optimisation on selection of the pass list, which requires dealing with the combinatorial problem shown in our previous work on LLVM optimisation used Bayesian Optimisation [6].

[1] https://arxiv.org/abs/1803.10122
[2] https://worldmodels.github.io
[3] https://arxiv.org/abs/1810.09028
[4] H. Brown, K. Fricke and E. Yoneki: World-Models for Bitrate Streaming. MDPI: Special Issue on AI in Mobile Networks 2020.
[5] J. Jiang and S. Sen, A New Abstraction for Internet QoE Optimization, 2020.
[6] Optimising Clang compiler with auto-tuners leveraging Structured Bayesian Optimisation.
[7] Hessel, M. et al. Rainbow: Combining Improvements in Deep Reinforcement Learning. AAAI, 2018.


4.   Optimisation of DNN Accelerators using Bayesian optimisation  *

Contact: Eiko Yoneki (with Sami Alabed)

A recent trend in deep neural network (DNN) development is to extend the reach of deep learning applications to platforms that are more resource and energy constrained, e.g., mobile devices. In order to reduce the DNN model size and improve the hardware processing efficiency, and have resulted in DNNs that are much more compact in their structures and/or have high data sparsity. These compact or sparse models are different from the traditional large ones in that there is much more variation in their layer shapes and sizes, and often require specialised hardware to exploit sparsity for performance improvement. Therefore, many DNN accelerators designed for large DNNs do not perform well on these models.

This project aims at optimising the design of DNN accelerators, where Eyeriss [1] is used as a DNN accelerator architecture model designed for running compact and sparse DNNs. The model involves various parameters and based on the goal such as the processing speed or energy efficiency the model will be different. Bayesian optimisation (e.g., [2]) offers a data-efficient approach to global optimisation of black-box functions by building a model of the unknown function, including our uncertainty about its values we have yet to observe.

The tasks of the project starts writing a simulator from the model described in [1]. Using simulation, various objective functions will be examined exploring a large parameter space for the model. It will be good to add multi objective function for BO. The result could be compared to other blackbox optimisation tools.

If time allows, the structured BO described in [3] could be explored to deal with high dimensional parameter space.

[1] Yu-Hsin Chenet al.: Eyeriss v2: A Flexible Accelerator for Emerging Deep Neural Networks on Mobile Devices.
[2] Practical Bayesian Optimization of Machine Learning Algorithms.
[3] BOAT: Building Auto-Tuners with Structured Bayesian Optimization.


5.   Explainable Reinforcement Learning for Device Placement  *

Contact: Eiko Yoneki (with Sami Alabed)

Task scheduling over a finite number of resources in order to maximise resources efficiency is a traditionally difficult problem with heuristics made to approximate it. Previous work used Hierarchical Reinforcement Learning [1] to find optimal task scheduling for TensorFlow graph operations.

This project proposes to investigate Contextual Multi-Armed bandit [2] with Bayesian learning (possible Bayesian neural networks) to allow injecting expert knowledge in the system. Using Bayesian models to define a hierarchy of the system allows it to converge faster and be easier to understand.

For this project, Park [3] provides a simulation-based environment to test task scheduling on a TensorFlow graph. TensorFlow Probability [2] provides a probabilistic programming language that makes it possible to define Bayesian models that interacts with deep learning models.

[1] https://ai.google/research/pubs/pub46646
[2] https://arxiv.org/pdf/1510.00757
[3] https://github.com/park-project/park


6. Optimisation of JVM Garbage Collection using ML (Bayesian Optimisation) *

Contact: Eiko Yoneki

This project extends the Cassandra case study [1,2] in incremental ways:

1)     Cassandra database was only executed in one setting. We could create an auto-tuner that is able to deal with a wider variety of settings. This includes:

 

-        Changing the heap size of the JVM

-        Changing the underlying hardware of Cassandra

-        Changing the underlying hardware of YCSB (Yahoo! Cloud Serving Benchmark)

 

2)     Applying it to other JVM applications (such as other databases, anything where we have a rigorous benchmark for throughput and latency)

 

3)     Looking at some of the other JVM flags (we only tuned three) as well as the other JVM garbage collector

For evaluation following two points are evaluated.

1)     No GC option as baseline

2)     Various GC implementations (i.e. some are good on certain workloads)

[1] https://www.cl.cam.ac.uk/~ey204/pubs/2017_WWW.pdf
[2] https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-900.html
[3] Auto-tuning Spark with Bayesian optimisation


7.   Hierarchical Device Placement from Probabilistic Perspective  

Contact: Eiko Yoneki (with Sami Alabed)

This project tackles the hierarchical device placement from probabilistic perspective to seek further improvement to the original work by Google [1]. In [1], two networks, one a grouper and one a placer are used. The grouper learns valid grouping of TensorFlow operations and the placer learns optimal placement on multiple devices. The idea in this project is to replace the grouper network with a Variational Autoencoder (VAE) network that in the latent space and using Bayesian Optimisation (BO) to generate valid grouping representation, similar approach to [2]. The output will be fed into another BO that learns the optimal placement, which is a similar approach described in our BOAT project 3] learning the placement for distributed SGD. Furthermore you can add the second placer learning multiple objectives rather than just the runtime improvement: by making it learn more correlated tasks it should be expected to be converged faster.

[1] A. Mirhoseini et al.: A Hierarchical Model for Device Placement, LCLR, 2018
[2] https://arxiv.org/pdf/1610.02415.pdf
[3] BOAT: Building Auto-Tuners with Structured Bayesian Optimization

8.   Building Permutation-Structured Action Spaces in Reinforcement Learning  

Contact: Eiko Yoneki

In this project, you will explore indexing tasks with Reinforcement Learning. The park project has a simulator for indexing task [3] and you can see a series of indexing projects at https://github.com/park-project/park. You would apply the algorithm used in our previous work [1] to one of the park projects for transforming action space to permutation-structured action spaces. You could plug the agent code from [1] into the simulator. This will enable a scalable experiments. There is some other query processing tasks with a simulated query optimiser [2].

Ideally you would run a case study addressing the performance improvement (i.e. speed-up) of database queries by optimising database compound index selection, which requires complex decision making operation including what to index and when to index. Index selection-specific action representations arise when the problem is reformulated in terms of permutation learning and we rely on recent work for learning RL policies on permutations. Through this approach, you can build an indexing agent that is able to achieve improved indexing and validate its behaviour with task-specific statistics. The project can start from [1] and further build up tuning system.

[1] J. Welborn et al.: Learning Index Selection with Structured Action Spaces. 2019.
[2] https://github.com/park-project/park/tree/master/park/envs
[3] Park project: https://github.com/park-project/park/tree/master/park/envs/multi_dim_index.

Contact Email

Please email to eiko.yoneki@cl.cam.ac.uk for any question.