Computer Laboratory

Large-Scale Data Processing and Optimisation (2022-2023 Michaelmas Term)

LSDPO - R244

review_log

Open Source Projects

Reading Club Papers

Mini-Project List

Contact

 

 

 

 

 

 

 

  

 

Overview

This module provides an introduction to large-scale data processing, optimisation, and the impact on computer system's architecture. Large-scale distributed applications with high volume data processing such as training of machine learning will grow ever more in importance. Supporting the design and implementation of robust, secure, and heterogeneous large-scale distributed systems is essential. To deal with distributed systems with a large and complex parameter space, tuning and optimising computer systems is becoming an important and complex task, which also deals with the characteristics of input data and algorithms used in the applications. Algorithm designers are often unaware of the constraints imposed by systems and the best way to consider these when designing algorithms with massive volume of data. On the other hand, computer systems often miss advances in algorithm design that can be used to cut down processing time and scale up systems in terms of the size of the problem they can address. Integrating machine learning approaches (e.g. Bayesian Optimisation, Reinforcement Learning) for system optimisation will also be explored in this course. On completion of this module, the students should:

  • Understand key concepts of scalable data processing approaches in future computer systems
  • Obtain a clear understanding of building distributed systems using data centric programming and large-scale data processing
  •  Understand a large and complex parameter space in computer system's optimisation and applicability of Machine Learning approach

Module Structure

The module consists of 8 sessions, with 5 sessions on specific aspects of large-scale data processing research. Each session discusses 3-4 papers, led by the assigned students. One session is a hands-on tutorial on MapReduce using data flow programming and/or Deep Neural Networks using Google TensorFlow. The first session advises on how to read/review a paper together with a brief introduction on different perspectives in large-scale data processing and optimisation. The last session is dedicated to the student presentation of open-source project studies. 

Schedule and Reading List

All the sessions will be in the class room (FW26) except Tutorial Session. We will meet every Wednesday (from October 12 to November 30) in 2022. The time slot is 10:00-12:00.1

 2022/10/12 Session 1: Introduction to Large-Scale Data Processing and Optimisation

  • Introduction to R244 (slides)
    • Assignment details
    • Guidance of how to read/review/present a paper
    • Guidance to Open Source Project
  • Overview of technologies for a large scale data processing and optimisation (slides)

 2022/10/19 Session 2: Data flow programming

  • Data flow programming, Cluster Computing

1. Yuan Yu, Michael Isard, D. Fetterly, M. Budiu, U. Erlingsson, P.K. Gunda, J. Currey:
DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language, OSDI, 2008.

2. M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, I. Stoica:
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, NSDI, 2013.

3. J. Gjengset, M. Schwarzkopf, J. Behrens, L. T. Araujo, M. Ek, E. Kohler, M. F. Kaashoek and R. Morris:
Noria: dynamic, partially-stateful data-flowfor high-performance web applications, OSDI 2018.

4. J. Dean, S. Ghemawat: MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004.

5. Derek Murray, Malte Schwarzkopf, Christopher Smowton, Steven Smith, Anil Madhavapeddy and Steven Hand:
Ciel: a universal execution engine for distributed data-flow computing, NSDI 2011. 

6. Naiad Frank McSherry's Talk on Differential Dataflow is here.

6.1. Frank McSherry, Rebecca Isaacs, Michael Isard, and Derek G. Murray,
Composable Incremental and Iterative Data-Parallel Computation with Naiad, no. MSR-TR-2012-105, 2012. 

Theo Long (slides)
6.2. D. Murray, F. McSherry, R. Isaacs, M. Isard, P. Barham, M. Abadi: Naiad: A Timely Dataflow System, SOSP, 2013. 

6.3. F. McSherry, A. Lattuada, M. Schwarzkopf, T. Roscoe: Shared Arrangements: practical inter-query sharingfor streaming dataflows, VLDB, 2020. 

7. P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquini: Incoop: MapReduce for incremental computation, ACM SOCC, 2011.

Antonia-Irina Boca (slides)
8. M. Abadi et al. Tensorflow: A system for large-scale machine learning. OSDI, 2016.

8.1   M. Abadi et al.: TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems, Preliminary White Paper, 2015.

8.2. M. Abadi, M. Isard and D. Murray: A Computational Model for TensorFlow - An Introduction, MAPL, 2017.

9. M. Looks et al.: Deep Learning with Dynamic Computation Graphs, ICLR, 2017.

10. Y. Yu et al.: Dynamic Control Flow in Large-Scale Machine Learning, EuroSys, 2017.

Kian Cross (slides)
11. R. Nishihara, P. Moritz, et al.: Ray:A Distributed Framework for Emerging AI Applications, OSDI, 2018.

Martin  Graf (slides)
12. M. Schaarschmidt, S. Mika, K. Fricke, E. Yoneki: RLgraph: Flexible Computation Graphs for Deep Reinforcement Learning, SysML, 2019.

13. T. Akidau, R. Bradshaw, C. Chambers, S. Chernyak, R.  Fernandez-Moctezuma, R. Lax, S. McVeety, D. Mills, F. Perry, E. Schmidt, S. Whittle: The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing, VLDB, 2015.

14. S. Li, Y. Zhao, R. Varma, et. al: PyTorch Distributed: Experiences on Accelerating Data Parallel Training, VLDB, 2020.

15. T. Lévai, F. Németh, and G. Rétvári: Batchy Batch scheduling Data Flow Graphs with Service level Objective, NSDI, 2020.

George Barbulescu (slides)

16 . P. Barham, et al.: Pathways: Asynchronous Distributed Dataflow for ML, MLSys, 2022.  

17 . L. Zheng, et al.: Alpa: Automating Inter- and Intra-Operator Parallelism for Distributed Deep Learning, OSDI, 2022.  

 2021/10/26 Session 3: Large-scale graph data processing.

  • Scalable distributed processing of graph structured data, processing model, and programming model

Teodora Reu (slides)
1. G. Malewicz, M. Austern, A. Bik, J. Dehnert, I. Horn, N. Leiser, and G. Czajkowski: Pregel: A System for Large-Scale Graph Processing, SIGMOD, 2010.

2. Z. Qian, X. Chen, N. Kang, M. Chen, Y. Yu, T. Moscibroda, Z.Zhang: MadLINQ: large-scale distributed matrix computation for the cloud, EuroSys, 2012.

3. Y. Low,  J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, J. Hellerstein: Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud, VLDB, 2012.

Zejian Li (slides)
4.J. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin: Powergraph: distributed graph-parallel computation on natural graphs. OSDI, 2012.

Sarah Zhao (slides)
5. J. Shun and G. Blelloch: Ligra: A Lightweight Graph Processing Framework for Shared Memory, PPoPP, 2013. 

6. J.  Gonzalez, R. Xin, A. Dave, D. Crankshaw, M. Franklin, I. Stoica: GraphX: Graph Processing in a Distributed Dataflow Framework, OSDI, 2014. 

7. B. Shao,  H. Wang, Y. Li: Trinity: A Distributed Graph Engine on a Memory Cloud, SIGMOD, 2013.

8. A. Kyrola and G. Blelloch: Graphchi: Large-scale graph computation on just a PC, OSDI, 2012.  

Sharan Agrawal (slides)
9. A. Roy, I. Mihailovic, W. Zwaenepoel:   X-Stream: Edge-Centric Graph Processing using Streaming Partitions, SOSP, 2013.

10. A. Roy, L. Bindschaedler, J. Malicevic and W. Zwaenepoel: Chaos: Scale-out Graph Processing from Secondary Storage , SOSP, 2015.

11. F. McSherry, M. Isard and D. Murray: Scalability! But at what COST? , HOTOS, 2015.

12. X. Hu, Y. Tao, C. Chung:  Massive Graph Triangulation, SIGMOD, 2013.

13. W. Xie, G. Wang, D.Bindel, A. Demers, J. Gehrke:  Fast Iterative Graph Computation with Block Updates, VLDB, 2014.

Anna Talas (slides)
14. S. Hong, H. Chafi, E. Sedlar, f K.Olukotun: Green-Marl: A DSL for Easy and Efficient Graph Analysis, ASPLOS, 2012.

15. D. Prountzos, R. Manevich, K. Pingali: Elixir: A System for Synthesizing Concurrent Graph Programs, OOPSLA, 2012.

16. D. Nguyen, A. Lenharth, K. Pingali: A Lightweight Infrastructure for Graph Analytics, SOSP 2013.

17. D. Merrill, M. Garland, A. Grimshaw: Scalable GPU Graph Traversal, PPoPP, 2012.

18. A. Gharaibeh, E. Santos-Neto, L. Costa, M. Ripeanu:  Efficient Large-Scale Graph Processing on Hybrid CPU and GPU Systems, IEEE TPC, 2014.

Ridwan Muheeb (slides)
19. Z. Jia, Y. Kwon, G. Shipman, P. McCormick, M. Erez, A. Aiken: A Distributed Multi-GPU System for Fast Graph Processing, VLDB, 2018.

20. H. Dai, Z. Kozareva, B. Dai, A. Smola and L. Song: Learning Steady-States of Iterative Algorithms over Graphs, ICML, 2018.

21. K. Nilakant, V. Dalibard, A. Roy, and E. Yoneki: PrefEdge: SSD Prefetcher for Large-Scale Graph Traversal.  ACM International Systems and Storage Conference (SYSTOR), 2014.

22. L. Bindschaedler, J. Malicevic, N. Schiper, A. Goel, W. Zwaenepoel: Rock you like a Hurricane: taming skew in large scale anaylitcs. EuroSys, 2018.

 2022/11/02 Session 4: Data Flow Programming Tutorial  

 2022/11/09 Session 5: Probabilistic Programming 

  • Role of Probabilistic Programming in computer system's optimisation.

Guest lecture: Brooks Paige (UCL, ATI). FW26 at 11:00.   

Title: Programs as probabilistic models 

Abstract: Probabilistic models used in quantitative sciences have historically co-evolved with methods for performing inference: specific modeling assumptions are made not because they are appropriate to the application domain, but because they are required to leverage existing software packages or inference methods. The emerging field of probabilistic programming aims to reduce the technical and cognitive overhead for writing and designing novel probabilistic models, by introducing a specialized programming language as an abstraction barrier between modeling and inference. While we would ideally be able to provide “automatic” inference for any probabilistic model, this proves severely challenging for models written in sufficiently expressive languages. In this talk I will discuss some of these difficulties, and provide an introduction and overview of different approaches to probabilistic programming.

Bio: Brooks Paige is an associate professor in machine learning at the University College London AI Centre. He is also a Turing fellow at the Alan Turing Institute, and a statistical ambassador for the Royal Statistical Society. He holds a D.Phil in Engineering Science from the University of Oxford, where he was supervised by Frank Wood; an M.A. in Statistics from Columbia University; and a B.A. in Mathematics from Amherst College.

Reading Club @10:00

1. E. Bingham et al.: Pyro: Deep Universal Probabilistic Programming, Journal of Machine Learning Research, 2019. 

2. D. Tran et al.: Edward: A library for probabilistic modeling, inference, and criticism, arXiv, 2017.

3. N. Goodman, V. Mansinghka, D. Roy, K. onawitz, J. Tenenbaum: Church: a language for generative models. In Proceedings of the Conference on Uncertainty in Arti cial Intelligence, UAI, 2008.

4. F. Wood, J. van de Meent, V. Mansinghka: A new approach to probabilistic programming inference, AISTATS, 2014.

5. B. Paige and F. Wood: A compilation target for probabilistic programming languages, ICML, 2014.

6. J. Ai et al.: HackPPL: a universal probabilistic programming language, MAPL, 2019.

Jakob Hartmann (slides)
7. V. Dalibard, M. Schaarschmidt, and E. Yoneki: BOAT: Building Auto-Tuners with Structured Bayesian Optimization, WWW, 2017. 

8. Ge, H., Xu, K. and Ghahramani, Z.: Turing: A language for flexible probabilistic inference, AISTATS, 2018. 

9. W. Neiswanger et al.: ProBO: Versatile Bayesian Optimization Using Any Probabilistic Programming Language, Arxiv, 2019. 

10. T. Rainforth et al.: Bayesian Optimization for Probabilistic Programs, NIPS, 2016. 

11. M. Balandat et al.: BOTORCH: Bayesian Optimization in PyTorch, Arxiv 2020. 

12. D. Tran, M. D. Hoffman, D. Moore, C. Suter, S. Vasudevan, A. Radul, M. Johnson, and R. A. Saurous: Simple, Distributed, and Accelerated Probabilistic Programming, NeurIPS, 2018. 

13. G. Baydin et al.: Etalumis: Bringing Probabilistic Programming to Scientific Simulators at Scale, SC, 2018. 

Shuntian Liu (slides)

14 . J. Shao, et al.: Tensor Program Optimization with Probabilistic Programs, NeurIPS, 2022. 

Ridwan Muheeb (slides)

15 . X. Wan, et al.: Bayesian Generational Population-Based Training, ALOE, ICLR, 2022.  

 2022/11/16/ Session 6: Optimisation in Computer Systems I

  • Auto-Tuner, Hi-dimensional Parameter Space, Bayesian Optimisation, ML Compiler, SuperOptimisation.

1. J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, Q. Le, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, A. Ng.: Large scale distributed deep networks. NIPS, 2012.

2. J. Ansel et al. Opentuner: an extensible framework for program autotuning. PACT, 2014.

3. J. Ansel et al.: Petabricks: A language and compiler for algorithmic choice. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI, 2009.

4. J. Snoek, H. Larochelle, and R. Adams: Practical Bayesian Optimization of Machine Learning Algorithms, NIPS, 2012.

5. G. Tesauro et al.: A Hybrid Reinforcement Learning Approach to Autonomic Resource Allocation, ICAC, 2006.

Teodora Reu (slides)
6. O. Alipourfard et al.: CherryPick: Adaptively Unearthing the Best Cloud Configurations for Big Data Analytics, NSDI, 2017.

7. A. Klein, S. Falkner, S. Bartels, P. Hennig, F. Hutter: Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets, AISTAS, 2017.

8.T. Domhan, J. T. Springenberg, F. Hutter: Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves, IJCAI, 2015.

9. F. Hutter et al.: Algorithm runtime prediction: Methods&evaluation, Elsevier J. AI, 2014.

10. Z. Jia, M. Zaharia, and A. Aiken: Beyond Data and Model Parallelism for Deep Neural Networks, SYSML, 2019.

11. H. Liu, K. Simonyan, and Y. Yang: DARTS: Differentiable Architecture Search, arXiv, 2018.  

12. M. Jaderberg, V. Dalibard, S. Osindero, W.M. Czarnecki: Population based training of neural networks, arXiv, 2017.  

13. S. Palkar, J. Thomas, D. Narayanan, P. Thaker, R. Palamuttam, P. Negi, A. Shanbhag, M. Schwarzkopf, H. Pirk, S. Amarasinghe, S. Madden, M. Zaharia: Evaluating End-to-End Optimization for Data Analytics Applications in Weld, VLDB, 2018.

14. R. Liaw, E. Liang, R. Nishihara, P. Moritz, J. Gonzalez, I. Stoica: Tune: A Research Platform for Distributed Model Selection and Training, ICML, 2018.  

15. T. Chen et al.: Learning to Optimize Tensor Programs, NIPS, 2018.

Kian Cross (slides)

16. T. Chen, T. Moreau, Z. Jiang, L. Zheng, S. Jiao, E. Yan, H. Shen, M. Cowan, L. Wang, Y. Hu, L. Ceze, C. Guestrin, and A. Krishnamurthy: TVM: An Automated End-to-End Optimizing Compiler for Deep Learning, OSDI, 2018. 

17. T. Chen, T. Moreau, Z. Jiang, L. Zheng, S. Jiao, E. Yan, H. Shen, M. Cowan, L. Wang, Y. Hu, L. Ceze, C. Guestrin, and A. Krishnamurthy: TVM: End-to-End Compilation Stack for Deep Learning, SysML, 2017.

18. H. Zhang et al.: Poseidon: An Efficient Communication Architecture for Distributed Deep Learning on GPU Clusters, ATC, 2017.

20. L. Li te al.: A System for Massively Parallel Hyperparameter Tuning, MLSys, 2020. 

21. Z. Wang, C. Li, S. Jegelka, and P. Kohli: Batched High-dimensional Bayesian Optimization via Structural Kernel Learning, PLMR, 2017.  

22. Z. Wang, C. Gehring, P. Kohli, and S. Jegelka: Batched Large-scale Bayesian Optimization in High-dimensional Spaces, AISTATS, 2018.  

23. Grosnit et al.: High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning, arxiv, 2021.  

24. E. Siivola, J. Gonzalez, A. Paleyes, A. Vehtari: Good practices for Bayesian Optimization of high dimensional structured spaces, arxiv, 2021.  

25. J. Grosse, C. Zhang, and P. Hennig: Probabilistic DAG Search, UAI, 2021.  

26. C. Lin, J. Miano, and E. Dyer: Bayesian optimization for modular black-box systems with switching costs, UAI, 2021.  

27. E. H. Lee, D. Eriksson, V. Perrone and M. Seeger: A Nonmyopic Approach to Cost-Constrained Bayesian Optimization, UAI, 2021.  

28. Z. Jia, J. Thomas, T. Warszawski, M. Gao, M. Zaharia,  A. Aiken: Optimizing DNN Computation with Relaxed Graph Substitutions, SYSML, 2019.

Martin Graf (slides)
29. Z. Jia, O. Padon, J. Thomas, T. Warszawski, M. Zaharia,  A. Aiken:
TASO: Optimizing Deep Learning Computation with Automated Generation of Graph Substitutions: SOSP, 2019.

30. S. Venkataraman et al.: Ernest: Efficient Performance Prediction for Large-Scale Advanced Analytics, NSDI, 2016.

31. H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, M. Alizadeh: Learning Scheduling Algorithms for Data Processing Clusters, SIGCOMM, 2019.

Zejian Li (slides)
32. KH. Wang, J. Zhai, M. Gao, Z. Ma, S. Tang, L. Zheng, Y. Li, K. Rong, Y. Chen, and Z. Jia: PET: Optimizing Tensor Programs with Partially Equivalent Transformations and Automated Corrections, ODSI, 2021.

33. A. Qiao, S. K. Choe, S. Subramanya, W. Neiswanger, Q. Ho, H. Zhang, G. R. Ganger, E. Xing: Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning, OSDI, 2021.

34. S. Cereda, S. Valladares, P. Cremonesi and S. Doni: CGPTuner: a Contextual Gaussian Process Bandit Approach for the Automatic Tuning of IT Configurations Under Varying Workload Conditions, VLDB, 2021.

Sarah Zhao (slides)
35.
Y. Yang, et al.: Equality Saturation for Tensor Graph Superoptimization, MLSys, 2021.  

36. L. Zheng, et al.: TenSet: A Large-scale Program Performance Dataset for Learned Tensor Compilers, NeurIPS, 2021.  

Theo Long (slides)
37.
Z. Jia, et al.: Unity: Accelerating DNN Training Through Joint Optimization of Algebraic Transformations and Parallelization, OSDI, 2022.  

38. C. Nandi, et al.: Rewrite Rule Inference Using Equality Saturation, OOPSLA, 2021.  

39. R. Senanayake, et al.: A sparse iteration space transformation framework for sparse tensor algebra, OOPSLA, 2020.  

40. L. Zheng, et al.: Ansor : Generating High-Performance Tensor Programs for Deep Learning, OSDI, 2020.  

41. M. Li, et al.: AdaTune: Adaptive Tensor Program Compilation Made Efficient, NeurIPS, 2020.  

43. S. Zheng, et al.: FlexTensor: An Automatic Schedule Exploration and Optimization Framework for Tensor Computation on Heterogeneous System, ASPLOS, 2020.  

44. J. Turner, et al.: Neural Architecture Search as Program Transformation Exploration, ASPLOS, 2021.  

45. Y. Zhou, et al.: Transferable Graph Optimizers for ML Compilers, NEURIPS, 2020.  

46. X. Chen, et al.: Learning to Perform Local Rewriting for Combinatorial Optimization, NeurIPS, 2019.  

47. J. Xing, et al.: Bolt: Bridging the Gap between Auto-tuners and Hardware-native Performance, MLSYS, 2022.  

48. M. Lindauer, et al.: SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization, Journal of Machine Learning Research, JMLR, 2021.  

 2022/11/23 Session 7: Optimisation in Computer Systems II 

  • Reinforcement Learning, Optimisation in Database, Devie Placement/Scheduling.

Sharan Agrawal (slides)
1.1 A. Mirhoseini et al.: Device Placement Optimization with Reinforcement Learning, ICML, 2017.
1.2. A. Mirhoseini, A. Goldie, H. Pham, B. Steiner, Q. Le and J. Dean: A Hierarchical Mode for Device Placement, ICLR, 2018.  

2.1 A. Mirhoseini, A. Goldie, et al.: A graph placement methodology for fast chip design, Nature, 2021.  
2.2 A. Mirhoseini, A. Goldie, et al.: Chip Placement with Deep Reinforcement Learning, ISPD, 2020.  

3. R. Addanki, S. B. Venkatakrishnan, S. Gupta, H. Mao, M. Alizadeh: Placeto: Learning Generalizable Device Placement Algorithms for Distributed Machine Learning, arXiv, 2019. 

4. R. Marcus, P. Negi, Parimarjan, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul: Neo: A Learned Query Optimizer, VLDB, 2019. 

5. D. Aken et al.: Automatic Database Management System Tuning Through Large-scale Machine Learning, SIGMOD, 2017. 

6. A. Pavlo et al.: Self-Driving Database Management Systems, CIDR, 2017.

7. H. Mao et al.: Park: An Open Platform for Learning-Augmented Computer Systems, OpenReview, 2019.

8. A. Floratou et al.: Dhalion: self-regulating stream processing in Heron, VLDB, 2017.

Antonia-Irina Boca (slides)
9. G. Li, X. Zhou, S. Li, and B. Gao: Qtune: RL for DB query optimisation, VLDB, 2019.

10. D Van Aken, A Pavlo, GJ Gordon, and B Zhang: Automatic database management system tuning through large-scale machine learning, SIGMOD, 2017.

11. A. Pavlo, M. Butrovich, L. Ma, P. Menon, W. Shen Lim, D. Van Aken, W. Zhang: Make Your Database System Dream of Electric Sheep: Towards Self-Driving Operation, VLDB, 2021.

Jakob Hartmann (slides)
12. D. Aken , D. Yang, S. Brillard, A. Fiorino, B. Zhang, C. Bilien, and A. Pavlo: An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems, VLDB, 2021.

13. Ł. Kaiser et al.: Model Based Reinforcement Learning for Atari, arXiv, 2019.  

14. H. Dai, E. Khalil, Y. Zhang, B. Dilkina, L. Song: Learning Combinatorial Optimization Algorithms over Graphs, NIPS, 2017.

15. E. Liang et al.: RLlib: Abstractions for Distributed Reinforcement Learning, ICML, 2018.

16. Kraska, T., Alizadeh, M., Beutel, A., Chi, E.H., Ding, J., Kristo, A., Leclerc, G., Madden, S., Mao, H. and Nathan, V.: SageDB: A learned database system, CIDR, 2019. 

17. Ma, L., Ding, B., Das, S. and Swaminathan, A.: Active Learning for ML Enhanced Database Systems, SIGMOD, 2020. 

18. A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann: SOSD: A Benchmark for Learned Indexes, NeurIPS Workshop on ML for Systems, 2019. 

Anna Talas (slides)
19. D. Ha and J. Schmidhuber: World Models, arXiv, 2018 (https://worldmodels.github.io). 

George Barbulescu (slides)
20. R. Marcus, P. Negi, H. Mao, N. Tatbul, M. Alizadeh, and T. Kraska: Bao: Learning to Steer Query Optimizers, VLDB, 2020.

21 . E. Liang, Z. Wu, M. Luo, S. Mika, J. Gonzalez, and I. Stoica: RLlib Flow: Distributed Reinforcement Learning is a Dataflow Problem, NeurIPS, 2021.  

22 . X. Zhang, et al.: Restune: Resource oriented tuning boosted by meta-learning for cloud databases, SIGMOD, 2021.  

23 . F. Hutter, et al.: An evaluation of sequential model-based optimization for expensive blackbox functions, GECCO, 2013.  

24 . j. Ding, et al.: Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads, ArXiv, 2020.  

25 . Ng and S. Russell: Algorithms for inverse reinforcement learning, ICML 2000.  

26. L. Espeholt et al.: IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures, ICML, 2018.

27. T. Li, Z. Xu, J. Tang and Y. Wang: Model-Free Control for Distributed Stream Data Processing using Deep Reinforcement Learning, VLDB, 2018.  

Shuntian Liu (slides)
28. A. Paliwal et al.: REGAL: Transfer Learning For Fast Optimization of Computation Graphs, arxiv, 2019.

  Optimisation in Computer System: Additional Reference Papaers.

  • Additional papers for Optimisation in Computer Systems

A1. G. Venkates et al.: Accelerating Deep Convolutional Networks using low-precision and sparsity,  ICASSP, 2017.

A2. V. Mnih et al.: Asynchronous Methods for Deep Reinforcement Learning, ICML, 2016.

A3. B. Bodin, L. Nardi, MZ Zia et al.: Integrating Algorithmic Parameters into Benchmarking and Design Space Exploration in 3D Scene Understanding, PACT, 2016. 

A4. V. Mnih et al.: Playing Atari with Deep Reinforcement Learning, NIPS, 2013.

A5.. S. Palkar, J. Thomas, A. Shanbhagy, D. Narayanan, H. Pirky, M. Schwarzkopfy, S. Amarasinghey, and M. Zaharia:
Weld: A Common Runtime for High Performance Data Analytics, CIDR, 2017.

A6. D. Kingma, J. Ba: Adam: A Method for Stochastic Optimization, ICLR, 2015.

A7. Z. Jia, S. Lin, R. Ying, J. You, J. Leskovec,  A. Aiken: Redundancy-Free Computation Graphs for Graph Neural Networks: ArXiv, 2019.

A8. N. K. Ahmed, et al.: On Sampling from Massive Graph Streams, VLDB, 2017.

A9. G. Malkomes, B. Cheng, E. Hans Lee, and M. McCourt: Beyond the Pareto Efficient Frontier: Constraint Active Search for Multi-objective Experimental Design, PLMR, 2021.  

A10. J. Maronas, O. Hamelijnck, J. Knoblauch, and T. Damoula: Transforming Gaussian Processes With Normalizing Flows, , AISTATS, 2021.  

A11. F. Yang et al.: LFTF: A Framework for Efficient Tensor Analytics at Scale, VLDB, 2017.

9. C. Delimitrou et al.: Quasar: Resource-Efficient and QoS-Aware Cluster Management, ASPLOS, 2014.

A12. H. Mao et al.: Neural Adaptive Video Streaming with Pensieve, SIGCOMM, 2017.

A13.. K. LaCurts et al.: Cicada: Introducing Predictive Guarantees for Cloud Networks, HOTCLOUD, 2014.

A14. H. Hoffmann et al.: Dynamic Knobs for Responsive Power-Aware Computing, Asplos, 2011.

A15. N.J. Yadwadkar, B. Hariharan, J. Gonzalez and R. Katz: Faster Jobs in Distributed Data Processing using Multi-Task Learning, SDM, 2015.

A16. X. Dutreih et al.: Using Reinforcement Learning for Autonomic Resource Allocation in Clouds: Towards a Fully Automated Workflow, ICAS, 2011.

A17. J. Eastep et al.: Smart Data Structures: An Online Machine Learning Approach to Multicore Data Structures, ICAC, 2011.

A18. E. Ipek et al.: Self-Optimizing Memory Controllers: A Reinforcement Learning Approach, ISCA, 2008.

A19. S. Teerapittayanon et al.: Distributed Deep Neural Networks over the Cloud, the Edge and End Devices, ICDCS, 2017.

A20. D. Baylor et al.: TFX: A TensorFlow-Based Production-Scale Machine Learning Platform, KDD, 2017.

A21. H. Mao et al.: Resource Management with Deep Reinforcement Learning, HotNets, 2016.

A22. M. Raghu et al.: On the Expressive Power of Deep Neural Networks, PMLR, 2017. 

A23. E. Lambart et al.: Low Level Control of a Quadrotor with Deep Model-Based Reinforcement Learning, IEEE Robotics and Automation Letters, 2019.

A24. Y. Kang et al.: Neurosurgeon: Collaborative Intelligence Between the Cloud and Mobile Edge, ASPLOS, 2017.

A25. Y. You et al.: Scaling Deep Learning on GPU and Knights Landing clusters, SC, 2017.

A26. Kunjir, M. and Babu, S.: Black or White? How to Develop an AutoTuner for Memory-based Analytics, SIGMOD, 2020.

A27. K. Tzoumas, A. Deshpande, and C. S. Jensen: Efficiently adapting graphical models for selectivity estimation, VLDB, 2013.

A28. L. Spiegelberg, R. Yesantharao, M. Schwarzkopf, T. Kraska: Tuplex: Data Science in Python at Native Code Speed, SIGMOD, 2021., SIGMOD, 2021.

A29. U. MisraRichard, L. Dunlap et al.: RubberBand: Cloud-based Hyperparameter Tuning, EuroSys, 2021.

A30. F. Hutter, H.H. Hoos, and K. Leyton-Brown: Sequential model-based optimization for general algorithm configuration, International conference on learning and intelligent optimization, 2011.

A31. J. Bergstra, Y. Bengio: Random search for hyper-parameter optimization, Journal of machine learning research, 2012.

A32. B. Teabe et al.: Application-specific quantum for multi-core platform scheduler, EuroSys, 2016.

A33. L. Ma, W. Zhang, J. Jiao, W. Wang, M. Butrovich, W.S. Lim, P. Menon, and A. Pavlo: MB2: Decomposed Behavior Modeling for Self-Driving Database Management Systems, SIGMOD, 2021.  

A34. R. Krishna, M.S. Iqbal, M.A. Javidian, B. Ray, and P. Jamshidi: CADET: Debugging and Fixing Misconfigurations using Counterfactual Reasoning, UAI, 2021.  

A35. I. Gog, M. Schwarzkopf, A. Gleave, R. Watson, S. Hand: Firmament: fast, centralized cluster scheduling at scale, OSDI, 2016.

A36. B. Zoph et al.: Learning Transferable Architectures for Scalable Image Recognition, arXiv, 2017.

A37. D. Golovin et al.: Google Vizier: A Service for Black-Box Optimization, KDD, 2017.

A38. M. Carvalho et al.: Long-term SLOs for reclaimed cloud computing resources, SOCC, 2014.

A39. A. Ratner, S. Bach, H. Ehrenberg, J. Fries, S. Wu, and C. Ré: Snorkel: Rapid Training Data Creation with Weak Supervision, VLDB, 2017.

A40. A. Ratner, B. Hancock, J. Dunnmon, R. Goldman, and C. Ré: Snorkel MeTaL: Weak Supervision for Multi-Task Learning, DEEM, 2018.

A41. A. Koliousis, P. Watcharapichat, M. Weidlich, L. Mai, P. Costa, P. Pietzuch: CROSSBOW: Scaling Deep Learning with Small Batch Sizes on MultiGPU Servers, VLDB, 2019.

 2022/11/30 Session 8: Presentation of Open Source Project Study

      Presentation of Mini Project (work in progress, plan).

    1. Sharan Agrawal (TensorFlow)   Agent Based Modelling in TensorFlow (slides)
    2. George Barbulescu (Emukit etc.)   Enhancing Active Learning in Emukit: an extended experimental analysis (slides)
    3. Antonia-Irina Boca (PyTorch, pytorch-geometric, FlexFlow, TenSat)   Tensor graph superoptimization for graph neural networks (slides)
    4. Kian Cross (TVM)   Evaluating and Improving Scheduling Times in TVM (slides)
    5. Martin Graf (Bao)   Improving BAO’s worst-case performance (slides)
    6. Jakob Hartmann (NAS-MCTS, SMAC3, Ray-Tune, Gymnasium)   Comparison of Hyperparameter Optimization Approaches for Deep Reinforcement Learning (slides)
    7. Zejian Li (PyTorch, PyTorch Geometric)   Exploring PyTorch Geometric: a geometric deep learning library built on top of PyTorch (slides)
    8. Shuntian Liu (Apache Flink)   FlinkCoin: Comparative analysis of Apache Flink and other general purpose data processing frameworks (slides)
    9. Theodore Long (FABOLAS)   Flexible, Parallelized, Bayesian Optimization for Large Datasets (slides)
    10. Ridwan Muheeb (Spark)   Spark: Fast Cluster Computing (slides)
    11. Teodora Reu (BoTorch and PyTorch Geometric)   Tuning Graph Neural Networks with Bayesian Optimization (slides)
    12. Anna Talas (World Model)   Build a working prototype on a WORLD for Gaming (slides)
    13. Sarah Zhao (Pyro, GPyTorch and BoTorch)   An Extended Comparison of Pyro and PyTorch (Exploring some gaps in Pyro experiments) (slides)

       
      Wrap-up Discussion             

                       

Coursework 1 (Reading Club)

The reading club will require you to read between 1 and 3 papers every week. You need to fill out simple review_log (MS word format, text format) prior to each session and email me by Wednesday 12:00 (noon). The minimum requirement of review_log is one per session, but you can read as many as you want and fill the review_log for each paper you read. review_log is not marked but 'tick'.

At each session, 3 - 4 papers are selected under the session topic, and if you are assigned to present your review work, please prepare 15-20 minutes slides for presenting your review work. Your presented material should also be emailed by the following day Wednesday. You would present your review work approximately twice during the course. The paper includes following two types and you can focus on the specified aspects upon reviewing the paper.

  1. Full length papers 
    • What is the significant contribution?
    • What is the difference from the existing works?
  2. Short length papers 
    • What is the novel idea?
    • What is required to complete the work?

 Coursework 2 (Reports)

The following three reports are required, which could be extended from the reading assignment of the reading club or a different one within the scope of data centric networking.

  1. Review report on a full length of paper (max 1800 words)
    • Describe the contribution of paper in depth with criticism
    • Crystallise the significant novelty in contrast to the other related work
    • Suggestion for future work
  2. Survey report on sub-topic in data centric networking (~1800 - max 2000 words)
    • Pick up to 5 papers as core papers in your survey scope
    • Read the above and expand your reading through related work
    • Comprehend your view and finish as your survey paper
    • See 'how to write a survey paper' in Assessment section.
  3. Project study and exploration of a prototype (max 2500 words)
    • What is the significance of the project in the research domain?
    • Compare with the similar and succeeding projects
    • Demonstrate the project by exploring its prototype
    • Please email your project selection (MS word format or text format <150 words) by 16:00 on November 11, 2022.
    • Project presentation on November 30, 2022.

The report 1 should be handed in by November 11, 2022 - 16:00 and the report 2 by December 9, 2022 - 16:00 . The report 3 by January 18,  2023 - 16:00 - (Try to finish the mini project by the end of 2022!).

 Assessment

The final grade for the course will be provided as a letter grade or percentage and the assessment will consist of two parts:

  1. 25%: for reading club (Participation,  Presentation + tick of review_log and hands-on tutorial)
    • 10%: Presentation
    • 15%: Participation
  2. 75%: for the three reports
    • 15%: Intensive review report
    • 25%: Survey report
    • 35%: Project study

Open Source Projects

See the candidates of Open Source Projects in data centric networking. The list is not exhausted. If you take anything other than the one in the list, please discuss with me. The purpose of this assignment is to understand the prototype of the proposed architecture, algorithms, and systems through running an actual prototype and present/explain to the other people how the prototype runs, any additional work you have done including your own applications and setup process of the prototype. This experience will give you better understanding of the project. These Open Source Projects come with a set of published papers and you should be able to examine your interests in the paper through running the prototype. Some projects are rather large and may require extensive environment and time; make sure you are able to complete this assignment.

How to Read/Review a Paper

The following papers aid how to read/review a paper.

Further supplement: see ‘how to read/review a paper’ section in Advanced Topics in Computer Systems by Steven Hand.

Presentations

Presentations should be about 15-20 minutes long, where you need to cover the following aspects.

  1. What are the background and the problem domain of the paper? What is the motivation of the presented work? What is the difference from the existing works?  What is the novel idea? How did the paper change/unchange the research in the research community?

  2. What is the significant contribution? How did the authors tackle the problem? Did the authors obtain expected result from their trial?

  3. How do you like the paper and why? What is the takeaway message to you (and to research community)? What is required to complete the work?

The following document aids in presenting a review.

How to write a survey paper

A survey paper provides the readers with an exposition of existing work that is comprehensive and organized. It must expose relevant details associated in the surveying area, but it is important to keep a consistent level of details and to avoid simply listing the different works. Thus a good survey paper should demonstrate a summary of recent research results in a novel way that integrates and adds understanding to work in the field. For example, you can take an approach by classifying the existing literature in your own way; develop a perspective on the area, and evaluate trends. Thus, after defining the scope of your survey, 1) classify and organize the trend, 2) critical evaluation of approaches (pros/cons), and 3) add your analysis or explanation (e.g. table, figure). Also adding reference and pointer to further in-depth information is important (summary from Rich Wolski’s note).

Papers for OS Principles (Distributed Storage and Deterministic Parallelism)

  • Following papers will help you to understand distributed storage and parallelism.
  • Systems Research and System Design
1.  B. Lampson: Hints for Computer Systems Design (Revised), ACM OSR 1983.

  • Distributed Storage
2. S. Ghemawat, H. Gobioff, and S. Leung: The Google File System, ACM SOSP 2003.
3. F. Chang et al: BigTable: A Distributed Storage System for Structured Data, USENIX OSDI 2006.
4. G. DeCandia et al:  Dynamo: Amazon's Highly Available Key-value Store, ACM SOSP 2007.

  • Deterministic Parallelism
5. J. Devietti et al: DMP: Deterministic Shared Memory Multiprocessing, ACM ASPLOS 2009.
6. A. Aviram, et al: Efficient System-Enforced Determistic Parallelism, USENIX OSDI 2010.
7. T. Liu et al: Dthreads: Efficient and Determistic Multithreading, ACM SOSP 2011.

Contact Email

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