Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Bachelorseminar: Machine Learning for Performance Prediction in Complex Software Systems

Prof. Dr. Ulf Leser, Carl Witt

Verteiltes Rechnen macht Datenanalysen im größten Maßstab möglich. Das umfasst heute Berechnungen auf Millionen von CPU-Kernen unter Verwendung von Hauptspeicher im Petabyte-Bereich [1]. Eine Schlüsselaufgabe in verteilten Systemen ist das Scheduling von Ressourcen, das heißt die Zuweisung von z.B. CPU-Kernen und Hauptspeicher zu Benutzern für bestimmte Zeiträume. Um Scheduling-Entscheidungen zu treffen, können verschiedene Zielkriterien herangezogen werden, es ist aber in jedem Fall schwierig, (nahezu) optimale Entscheidungen zu treffen, da die verteilte Ausführung von Software mit vielen Unsicherheiten belegt ist. So ist z.B. unklar, wie lange einzelne Tasks und Jobs benötigen, welche Wartezeiten sich z.B. durch Dateitransfers oder durch Ressourcenknappheit ergeben. Dieses Seminar behandelt angewandtes Machine Learning um Vorhersagen über den Ausführungsverlauf in verteilten Systemen zu treffen. Da sowohl verteilte Systeme (Cluster, Cloud, Grid) als auch ihre Workloads (Simulationen, spezifische Paradigmen wie MapReduce, etc) sehr heterogen sind, wird eine große Spannbreite an Themen abgedeckt und Einblicke in verschiedene Aspekte des verteilten Rechnens gegeben.

[1] TOP 500 Computing Systems

Das Seminar findet im wesentlichen als Blockseminar am Ende des Semesters statt. Vorher sind aber Einführungstermine und individuelle Themenbesprechungen zu besuchen.

Schein und Anrechenbarkeit

Das Seminar ist anrechenbar für

  • Bachelor Informatik
  • Diplom Informatik

Voraussetzungen für den Schein sind:

  • der Besuch der Einführungsveranstaltungen
  • die regelmäßige Kommunikation mit dem jeweiligen Betreuer
  • eine Kurzpräsentation des Themas in der Mitte des Semesters
  • das Halten eines wissenschaftlichen Vortrags im Blockseminar am Ende des Semesters
  • das Erstellen einer schriftlichen Ausarbeitung (Seminararbeit)

Anmeldung

Die Teilnehmerzahl ist begrenzt, die Anmeldung erfolgt über AGNES.

Termine und Ablauf

Am Dienstag, den 24.10.2017 findet die Einführungsveranstaltung statt, die für alle Teilnehmenden verpflichtend ist. Dort werden die Themen erläutert und vergeben.

Das Seminar wird als Blockseminar am Ende des Semesters abgehalten. Jede(r) Studierende muss dort einen ca. 25-minütigen Vortrag über das zugewiesene Thema halten. Für jeden Vortrag stehen außerdem 5 Minuten Diskussionszeit zur Verfügung. Vorher finden mindestens zwei Treffen mit dem/der Betreuer(in) statt, einmal zur Vorbesprechung des Themas und einmal zur Besprechung der Folien. Außerdem wird es in der Mitte des Semesters einen Termin geben, in dem alle Studierenden in einer 5-minütigen Flash-Präsentation ihr Thema vorstellen, um Querverbindungen zu erkennen und die rechtzeitige Beschäftigung mit dem Thema sicherzustellen. Schließlich muss zu jedem Thema eine ca. 10 seitige Seminararbeit verfasst werden. Als Sprache für den Vortrag und die Seminararbeit sind deutsch und englisch zugelassen.

Zusätzlich zu der themenspezifischen Literatur, über die die Vorträge gehalten werden, gibt es für alle Teilnehmer verpflichtende Einführungslektüre.

Alle Pflichttermine in der Übersicht:

  • 24.10.17, 15-17 Uhr: Einführung und Themenvergabe, Raum: 1'307 Rudower Chaussee 26 (Seminar- und Unterrichtsraum)
  • Bis 30.11.2017: Treffen mit dem Betreuer zur Themenbesprechung und -eingrenzung.
  • Freitag, 15. Dezember 2017, 13:00 bis 15:00: Flash-Präsentationen, Raum 4.410
  • Bis 2. Februar 2018: Treffen mit dem Betreuer zur Besprechung der Folien
  • Do, 15.2. (12-15 Uhr) + 16.2. (9-12 Uhr) Blockseminar (Raum 4.410)
  • Bis 31. März 2018: Abgabe Seminararbeit

Vorlagen


Themen

Topic Paper Vortragende(r) Betreuer(in)
Einführungsliteratur für alle TeilnehmerInnen D. G. Feitelson, L. Rudolph, U. Schwiegelshohn, K. C. Sevcik, and P. Wong, “Theory and Practice in Parallel Job Scheduling.,” JSSPP, vol. 1291, no. 1, pp. 1–34, 1997. (Abschnitte 1 bis 3)
Optionale Einführungsliteratur C. Witt, M. Bux, W. Gusew, and U. Leser, “Predictive Performance Modeling in Distributed Computing using Black-Box Monitoring and Machine Learning,” submitted to The VLDB Journal.
Seminareinführung Einführungsfolien Ulf Leser, Carl Witt
Runtime Prediction M. V. Devarakonda and R. K. Iyer, “Predictability of Process Resource Usage: A Measurement-Based Study on UNIX,” IEEE Trans. Software Eng., vol. 15, no. 12, pp. 1579–1586, 1989. Friedo Witt
M. A. Iverson, F. Özgüner, and L. Potter, “Statistical Prediction of Task Execution Times through Analytic Benchmarking for Scheduling in a Heterogeneous Environment,” IEEE Trans. Comput., vol. 48, no. 12, pp. 1374–1379, Dec. 1999. Leser
K. Hoste, A. Phansalkar, L. Eeckhout, A. Georges, L. K. John, and K. De Bosschere, “Performance Prediction based on Inherent Program Similarity,” presented at the International Conference on Extending Database Technology, New York, New York, USA, 2006, p. 114. Leser
M. P. Mesnier, M. Wachs, R. R. Sambasivan, A. X. Zheng, and G. R. Ganger, “Modeling the Relative Fitness of Storage,” SIGMETRICS, p. 37, 2007. Lemke Leser
A. Matsunaga and J. A. B. Fortes, “On the Use of Machine Learning to Predict the Time and Resources Consumed by Applications,” presented at the IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, 2010, pp. 495–504. Witt
D. A. Monge, M. Holec, F. Z̆elezný, and C. G. Garino, “Ensemble learning of runtime prediction models for gene-expression analysis workflows,” CLUSTER, vol. 18, no. 4, pp. 1317–1329, Sep. 2015. Roeseler Leser
S. Venkataraman, Z. Yang, M. J. Franklin, B. Recht, and I. Stoica, “Ernest - Efficient Performance Prediction for Large-Scale Advanced Analytics,” presented at the 13th USENIX Symposium on Networked Systems Design and Implementation, 2016. Ermshaus Witt
S. Pumma, W.-C. Feng, P. Phunchongharn, S. Chapeland, and T. Achalakul, “A runtime estimation framework for ALICE,” FGCS, vol. 72, pp. 65–77, Jul. 2017. Große Witt
Adaptive Systems G. Tesauro, N. K. Jong, R. Das, and M. N. Bennani, “A Hybrid Reinforcement Learning Approach to Autonomic Resource Allocation,” presented at the 2006 IEEE International Conference on Autonomic Computing, 2006, pp. 65–73. Zajler Witt
H. Herodotou, H. Lim, G. Luo, N. Borisov, and L. Dong, “Starfish: A Self-tuning System for Big Data Analytics.,” CIDR, pp. 261–272, 2011. Grushetskaja Leser
C. Delimitrou and C. Kozyrakis, “Quasar: resource-efficient and QoS-aware cluster management.,” ASPLOS, pp. 127–144, 2014. Bornstein Witt
Job Queues and Backfilling A. B. Downey, “Predicting Queue Times on Space-Sharing Parallel Computers.,” IPPS, pp. 209–218, 1997. Heiden Leser
D. Tsafrir, Y. Etsion, and D. G. Feitelson, “Backfilling Using System-Generated Predictions Rather than User Runtime Estimates.,” TPDS, vol. 18, no. 6, pp. 789–803, 2007. Leser
É. Gaussier, D. Glesser, V. Reis, and D. Trystram, “Improving backfilling by using machine learning to predict running times.,” SC, pp. 64–10, 2015. Schrader Witt
Network Prediction R. Wolski, N. T. Spring, and J. Hayes, “The network weather service: a distributed resource performance forecasting service for metacomputing.,” FGCS, pp. 757–768, 1999. Witt
Z. Liu, P. Balaprakash, R. Kettimuthu, and I. T. Foster, “Explaining Wide Area Data Transfer Performance,” HPDC, pp. 167–178, 2017. Grund Leser