Adaptive Lastverteilungsstrategien für aktuelle und zukünftige Multicore- Clustersysteme und deren Einbettung in ein mehrstufiges Programmiermodell

• Applicant: Professor Dr. Thomas Rauber
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2008 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 92279901

• Final Report Year: 2017

Final Report Abstract

Die zweite Projektphase verfolgte einen konsequent nachrichtenbasierten Ansatz zur effizienten Ausführung taskbasierter Programme. Das entwickelte Laufzeitsystem verwendet Channels, über die Steal- Requests und Tasks asynchron ausgetauscht werden. Damit wird eine stärkere Abstraktion von plattformspezifischen Details erreicht, was die Portabilität des Laufzeitsystems und der entwickelten Lastverteilungsstrategien begünstigt. Eine Erkenntnis ist, dass explizite Kommunikation, die zunächst nur für den Austausch von Tasks zwischen verteilten Adressräumen gedacht war, auch für den gemeinsamen Adressraum in Frage kommt und neue, effiziente Lastverteilungsstrategien ermöglicht, die mit bisherigen Ansätzen nicht umsetzbar waren. Im Hinblick auf verteilte Systeme ist ein einheitlicher, Channel-basierter Ansatz einfacher zu realisieren als die zuerst angestrebte Kombination unterschiedlicher Work-Stealing-Verfahren. Dank expliziter Kommunikation sind diverse Optimierungen und Erweiterungen denkbar, darunter das späte Allokieren von Channels beim Stehlen von Futures, das Senden mehrerer Steal-Requests pro Worker-Thread, um die Suche nach Tasks zu beschleunigen, und die Integration von “Lifelines”, mit dem Ziel, dynamisch zwischen Work-Stealing und Work-Sharing wechseln zu können. Darüberhinaus empfiehlt sich eine Portierung des Laufzeitsystems in andere Programmiersprachen wie Go und Rust, bei denen Channels Teil der Sprache bzw. Standardbibliothek sind. Channels selbst bieten Optimierungspotenzial: je effizienter der Nachrichtenaustausch, desto performanter das Laufzeitsystem und dessen Lastverteilungsstrategien. Dabei müssen Channels nicht immer herkömmlich implementiert sein (rein in Software), sondern können auch auf Hardware-Unterstützung, falls vorhanden, zurückgreifen.

Publications

• Dynamic Task Scheduling and Load Balancing on Cell Processors. Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, Pisa, Italy, 2010
  Ralf Hoffmann, Andreas Prell und Thomas Rauber
  
• Exploiting Fine-Grained Parallelism on Cell Processors. Proceedings of the 16th International Euro-Par Conference, Ischia, Italy, 2010
  Ralf Hoffmann, Andreas Prell und Thomas Rauber
  
• Adaptive Task Pools: Efficiently Balancing Large Number of Tasks on Shared-address Spaces. International Journal of Parallel Programming, Vol. 39, Nr. 5, S. 553–581, 2011
  Ralf Hoffmann und Thomas Rauber
  
• Task Parallel Programming on the Cell Processor. it - Information Technology, Bd. 53, Hnr. 2, S. 76–83, 2011
  Andreas Prell
  
• Task Parallelism on the SCC. Proceedings of the 3rd Many-core Applications Research Community (MARC) Symposium, Ettlingen, Germany, 2011
  Andreas Prell und Thomas Rauber
  
• Go’s Concurrency Constructs on the SCC. Proceedings of the 6th Many-core Applications Research Community (MARC) Symposium, Toulouse, France, 2012
  Andreas Prell und Thomas Rauber
  
• Embracing Explicit Communication in Work-Stealing Runtime Systems. Dissertation, Fakultät für Mathematik, Physik und Informatik, Universität Bayreuth, 2016
  Andreas Prell