Cloud Service für NP-schwere Probleme

  • Typ: Praxis der Softwareentwicklung
  • Zielgruppe: Bachelor
  • Semester: SS 2022
  • Ort:

    nach Vereinbarung

  • Zeit:

    nach Vereinbarung

  • Beginn: 04.05.2022
  • Dozent:

    Dominik Schreiber, Hans-Peter Lehmann

Beschreibung

Unser System Mallob (Malleable Load Balancer) ist eine Plattform zur skalierbaren Lösung (NP-)schwieriger Probleme on demand in einer parallelen und verteilten Rechenumgebung: Die Plattform ist optimiert zur Ausführung entweder auf einer einzigen Maschine mit vielen Kernen oder in einem verteilten Netz vieler Server, z.B. auf einem Supercomputer. Neu eintreffende Aufgaben ("Jobs") werden basierend auf ihrer Priorität und ihrem individuellen Ressourcen-Bedarf einer fairen Teilmenge der verfügbaren Worker zugeordnet. Dieses Scheduling geschieht innerhalb von wenigen Millisekunden, selbst falls das System bereits voll ausgelastet ist. Die dafür genutzte Schlüsseltechnologie nennt sich Verformbarkeit (malleability): Die Fähigkeit eines verteilten Algorithmus, mit einer fluktuierenden Menge an Workern umzugehen. Dank verformbarer Anwendungen können Rechenressourcen jederzeit dynamisch umverteilt werden, um auf Änderungen in der Auslastung des Systems zu reagieren. Das Rückgrat von Mallob ist ein verteiltes, asynchrones und dezentrales Protokoll zwischen den Arbeitern, das auf dem Message Passing Interface (MPI) aufbaut.

Abb. 1: Screenshot einer prototypischen interaktiven Visualisierung eines Systemzustands in Mallob. Jeder Knoten ist ein MPI-Prozess; einer der aktiven Jobs ist mit all seinen assoziierten Arbeitern und ihren Kommunikationskanälen hervorgehoben.

Die ursprüngliche Anwendung von Mallob, nämlich das Testen aussagenlogischer Formeln auf Erfüllbarkeit (SAT Solving), wurde in den jüngsten International SAT Competitions mehrfach preisgekrönt und verspricht hohe Effizienz von Dutzenden bis hin zu Tausenden von parallelen Rechenkernen. Darüber hinaus sind wir dabei, weitere NP-schwierige Anwendungen in Mallob zu integrieren, z.B. AI Planning oder k-Means Clustering.

Abb. 2: Überblick über den Software-Stack von Mallob.

Um unser System für den Produktiveinsatz bereit zu machen und dessen Weiterentwicklung zu unterstützen, möchten wir gerne ein Web-Interface realisieren, das die folgenden Features aufweist:

  • Eine API (z.B. REST) zu einer laufenden Mallob-Instanz, die u.A. das Versenden von Aufgaben und das Erhalten von Ergebnissen unterstützt;
  • Eine Web-Oberfläche, die eine Menschen-freundliche Alternative zu dieser API darstellt;
  • Ein Dashboard, das den Systemzustand von Mallob in Echtzeit visualisiert und das Statistiken zu den Jobs des angemeldeten Nutzers sowie Informationen zu etwaigen Fehlern und Problemen anbietet.
  • Eine PlugIn-Schnittstelle, die die Integration spezieller Ansichten für spezielle Anwendungen (z.B. Statistiken über den Austausch von Klauseln im Fall von SAT Solving) ermöglicht.

Wir empfehlen die Nutzung von HTML, Javascript/Typescript und Python oder Java.
Ein Eintauchen in die verteilte C++-Implementierung von Mallob (abgesehen von kleineren Arbeiten am lokalen Job-Interface eines Knotens) ist nicht vorgesehen; wir selbst leisten Support für Mallob.