Umgekehrt Rechnen? Was ist das denn?

Reverse Computing erlaubt es Programme rückwärts laufen zu lassen! In einem durch den Strategischen Forschungsfonds der THM geförderten Projekt haben Prof. Meyer sowie die Studierenden Pia-Doreen Ritzke, Niklas Deworetzki und Marc Schuster am Fachbereich MNI eine Compiler-Suite entwickelt, die es erlaubt genau das zu tun, nämlich Programme rückwärts laufen zu lassen.

Jeder von uns kennt Algorithmen zum Verschlüsseln und Entschlüsseln, Komprimieren und Dekomprimieren, Quadrieren und Wurzelziehen und viele mehr. Bisher war es immer nötig, dafür zwei Programme zu schreiben – mit Reverse Computing schreibt man nur noch ein Programm und lässt es dann vorwärts oder rückwärts auszuführen.

Reverse Computing ist ein Forschungsgebiet der Informatik, das in den letzten 15 Jahren stark an Aufmerksamkeit gewonnen hat, weil es nämlich das Potential hat den Energieverbrauch von Computern drastisch zu senken. Rolf Landauer postulierte bereits 1961, dass das Löschen eines Bits an Information zur Freisetzung von Energie führen muss – man kann sich vorstellen, dass ähnlich wie beim Energieerhaltungssatz die Information nicht rückstandsfrei verlorengehen kann – kompensiert wird der Informationsverlust durch die Entstehung einer kleinen (sehr kleinen) Menge an Energie (ungefähr 10−21 Joule). Wenn man aber berücksichtigt, wie viele Bits in einem heutigen Rechner stecken und wie hoch die Taktrate der CPU ist, addiert sich die verlorengegangene Energie in kürzester Zeit zu einer relevante Menge auf. Eine Gruppe von deutschen und französischen Physikern konnte diesen Effekt 2012 auch experimentell nachweisen. Michael P. Frank vom MIT schrieb daher in einem Artikel in der Fachzeitschrift IEEE Spectrum: „The Future of Computing Depends on Making It Reversible“.

Kann man jede Berechnung umkehren? Leider nein, wie man an dem einfachen Beispiel der Addition schon sieht: Vorwärts berechnen wir aus zwei Zahlen x und y die Summe x+y. Aber kann man nur aus der Kenntnis der Summe rückwärts auf die Summanden schließen? Nein! Die Addition erzeugt aus 2 Eingaben 1 Ergebnis und verliert somit Information. Solche Operationen, die nicht umkehrbar sind, dürfen also in sogenannten reversiblen Programmen nicht verwendet werden, sodass die oben genannte Energiemenge nicht verloren geht.

Am California Institute of Technology wurde die Programmiersprache Janus entwickelt, die wie eine prozedurale Sprache aussieht, aber solche nicht umkehrbaren Operationen verbietet. Janus wurde seit 2007 an der Universität Kopenhagen weiterentwickelt. Das MNI Team hat einen Janus-Compiler entwickelt, der in mehrere Zielsprachen („backends“) übersetzt. Neu ist dabei, dass der Compiler als erster Compiler eine reversible Sprache optimieren kann, das heißt, dass der Compiler selbst erkennt, wie er das Programm verbessern kann, so dass es schneller ausgeführt wird. Mit einer virtuellen Maschine kann man sogar das Programm Schritt-für-Schritt ausführen und dabei beliebig zwischen Vorwärts und Rückwärts wechseln.

Dem Team gelang es (tw. in Kooperation mit der JLU-Gießen) die Ergebnisse auf 3 international renommierten Tagungen im Jahre 2021 vorzustellen.

Die Compiler-Suite ist als öffentliches Projekt unter https://git.thm.de/thm-rc3/release verfügbar und kann heruntergeladen werden.

Wie geht es weiter? Zum einen gibt es natürlich noch viele Optimierungstechniken, die erforscht werden können, zum anderen aber ist das reversible Programmieren ungewohnt und daher zeitaufwändig. Wir wollen daher untersuchen, ob die Programmiersprache vereinfacht werden kann oder ob eine hybride Sprache, die „manchmal“ reversibel ist, realisierbar ist.

Mehr Informationen findet man unter:

  1. https://git.thm.de/thm-rc3/release
  2. Landauer, R. Irreversibility and heat generation in the computing process. IBM J. Res. Develop. 5, 183–191 (1961).
  3. Frank, Michael P., - It’s time to embrace reversible computing, which could offer dramatic improvements in energy efficiency, IEEE Spectrum, https://spectrum.ieee.org/computing/hardware/the-future-of-computing- depends-on-making-it-reversible
  4. Kutrib, M., Meyer, U., Deworetzki, N., & Schuster, M. (2021, July). Compiling Janus to RSSA. In International Conference on Reversible Computation (pp. 64-78). Springer, Cham.
  5. Deworetzki, N., & Meyer, U. (2021, June). Program analysis for reversible languages. In Proceedings of the 10th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis (pp. 13-18).
  6. Kutrib M., Meyer U. (2021) Reversible Top-Down Syntax Analysis. In: Moreira N., Reis R. (eds) Developments in Language Theory. DLT 2021. Lecture Notes in Computer Science, vol 12811. Springer, Cham. https://doi.org/10.1007/978-3-030-