Algorithm Engineering für moderne Hardware

Abstract

Die Entwicklung von effizienten Algorithmen basiert auf der theoretischen Modellierung der Rechner, auf denen sie ausgeführt werden sollen. Noch heute werden frühe Rechnermodelle wie die Random Access Machine (RAM) verwendet, um die Güte von Algorithmen zu analysieren und untereinander zu vergleichen. Aber sich verändernde Umstände wie der rasante Anstieg von interessanten Instanzgrößen, technologischer Fortschritt sowie neue Kostenmaße stellen neue Anforderungen an die Bewertung von Algorithmen – und damit auch an ihre Enwicklung.In den letzten Jahren wurden viele Fortschritte hinsichtlich dieser neuen Herausforderungen gemacht. Seit den neunziger Jahren des vergangenen Jahrhunderts werden auf Basis des I/O-Modells Algorithmen entwickelt, die die Speicherhierarchien und -technologien moderner Rechner ausnutzen. Auch neueste Speichertechnologien wie Flash-Speicher wurden schon in einem Modell beschrieben, das es Entwicklern ermöglicht, effiziente Algorithmen dafür zu entwickeln.Der andauernde Trend zu Mehrkernprozessoren führt dazu, dass viele Ergebnisse der klassischen Parallelverarbeitung auf praktisch allen modernen Rechnern Anwendung finden. Algorithmen, die nach dem PEM-Modell entwickelt wurden können die grundlegenden Eigenschaften heutiger Prozessoren ausnutzen. Auch wenn es noch kein allgemein anerkanntes theoretisches Modell für Berechnungen auf Grafikprozessoren gibt, können Algorithmenentwickler hocheffiziente parallele Algorithmen für sie entwickeln, wenn sie sich der Eigenschaften der Hardware bewusst sind.Wirtschaftliche Notwendigkeiten haben dazu geführt, dass sich ein zusätzliches Optimierungsziel für IT-Projekte etabliert hat – die Energieeffizienz. Auch das Algorithm Engineering kann seinen Teil dazu beitragen, zum Beispiel mit der Optimierung von Algorithmen für stromsparende Hardware.