Transactional Memory

Mit Transactional Memory bezeichnet man ein neues Hauptspeicherkonzept für parallele Berechnungseinheiten, welche auf gemeinsame Speicherbereiche zugreifen, wie z. B. Threads oder Mehrprozessorsysteme. Ziel ist es, die Schwierigkeiten der Synchronisierung und Koordination, die bei parallelen Berechnungen entstehen, vom Programmierer in den Compiler und Hardware zu verlagern. Bisher befindet sich Transactional Memory noch im Forschungsstadium. Mit seiner Serienreife wird erst in einigen Jahren gerechnet. Transactional Memory kann entweder komplett in Software (STM), als Hardware (HTM) oder mit Hardware-Unterstützung (Hybrid-HTM) implementiert werden. Bestehende Systeme mit Hardware Transactional Memory gibt es zurzeit nur als Forschungsprototypen, zum Beispiel das ATLAS-System der Universität Stanford.^[1]

Motivation

Moderne Desktop-Computer und Notebooks haben einen Hauptprozessor mit mehreren Prozessorkernen, doch nur wenige Programme sind in der Lage diese auch auszunutzen. Bei bisherigen Speicherkonzepten hatte ein Prozessor oder ein Programm seine Speicherbereiche stets exklusiv für sich beansprucht. Andere, parallel laufende Software konnten darauf nicht zugreifen. Darüber hinaus bieten gemeinsame Speicherbereiche Möglichkeiten der parallelen Programmierung, was jedoch oft zu Deadlocks oder Livelocks führt und schlecht skaliert. Transactional Memory soll diese Probleme reduzieren und die Parallelisierung vereinfachen.

Die Idee des Transactional Memory stammt aus der Architektur von Datenbanksystemen. Eine Transaktion bündelt Befehle, die auf gemeinsame Ressourcen zugreift. Falls zwei Transaktionen auf die gleiche Ressource zugreifen möchten, wird eine der beiden Transaktionen abgebrochen. Diese gibt die besetzten Ressourcen frei und setzt alle gemachten Änderungen zurück. Welche Transaktion abgebrochen wird, entscheidet ein intelligenter Verwaltungsmechanismus, das Herzstück eines Transactional-Memory-Systems.

Transaktion

Eine Transaktion ist eine Sequenz von Aktionen, die für den außenstehenden Beobachter atomar erscheint. Sie muss drei grundlegende Eigenschaften erfüllen:

• Atomarität verlangt, dass die Aktionen einer Transaktion entweder komplett und erfolgreich ausgeführt werden oder aber bei einem Abbruch keine Spuren davon im System übrig bleiben.
• Konsistenz sorgt dafür, dass das System immer in einem konsistenten Zustand ist. Eine Transaktion hat keine Information darüber, welche Transaktionen bisher ausgeführt wurden. Wenn eine Transaktion beginnt, geht sie davon aus, dass das System in einem konsistenten Zustand ist, und konsistent muss das System auch wieder sein, wenn die Transaktion endet.
• Isolation erfordert, dass jede Transaktion ein korrektes Resultat produziert, ganz egal, wie viele andere Transaktionen parallel dazu ausgeführt werden.

Verschachtelte Transaktionen

Eine verschachtelte Transaktion ist eine Transaktion, die vollständig von einer anderen Transaktion umschlossen wird. Die innere Transaktion sieht die Veränderungen, die von der äußeren gemacht werden. Für das Verhalten der beiden Transaktionen gibt es mehrere Varianten.

Falls die Transaktionen flach sind, führt der Abbruch der inneren Transaktion auch zu einem Abbruch der äußeren Transaktion. Die Änderungen der inneren Transaktion sind nicht gültig falls die äußere Transaktion nicht erfolgreich abgeschlossen wird.

Sind die Transaktionen geschlossen, führt ein Abbruch der inneren Transaktion nicht automatisch zu einem Abbruch der äußeren Transaktion. Schließt die innere Transaktion ihre Aktionen erfolgreich ab, sind die gemachten Änderungen nur für die äußere Transaktion sichtbar. Für das ganze System ist die Änderung erst sichtbar, wenn die äußerste Transaktion erfolgreich terminiert.

Im Gegensatz dazu wird bei offenen Transaktionen die Änderung der inneren Transaktion sofort nach deren Termination im ganzen System sichtbar. Diese Änderungen bleiben bestehen auch wenn die äußere Transaktion später abgebrochen wird.

Verfügbarkeit

Bisher existieren nur softwarebasierte Verfahren zur Verwaltung parallel genutzten Speichers, sog. Software Transactional Memory. Diese sind jedoch naturgemäß langsamer als hardwarebasierte Konzepte und zeigen keine gute Skalierbarkeit. Der Overhead, der bei den Programmen, die STM nutzen, entsteht ist im Moment noch zu groß um den Systemen mit traditionellen Locks Konkurrenz zu bieten.

Der Computerchiphersteller Intel demonstrierte den Geschwindigkeitsvorteil von Transactional Memory erstmals auf einer Entwicklerkonferenz Anfang 2006, allerdings nur anhand einer Software-Simulation. Bis zur Verfügbarkeit von handelsüblichen Speicherbausteinen und Geräten werden noch mehrere Jahre vergehen.

Auf der ISSCC 2008 stellte Sun Microsystems mit dem ROCK-Prozessor^[2] Details eines 16-kernigen Sparc-Prozessors mit Hardware-Transactional-Memory vor. Dessen Entwicklung wurde jedoch mit der Übernahme von Sun durch Oracle im Jahr 2010 eingestellt^[3][4].

Forschungsmodelle

• UTM - Unbounded Transactional Memory ^[5]
• LTM - Large Transactional Memory
• VTM - Virtual Transactional Memory
• LogTM - Log-based Transactional Memory
• TCC - Transactional Memory Coherence and Consistency

Literatur

• Maurice Herlihy, J. Eliot B. Moss: Transactional memory: Architectural support for lock-free data structures. In: Proceedings of the 20th International Symposium on Computer Architecture (ISCA). 1993, S. 289–300 (pdf).
• Larus, J.R. and Rajwar, R. Transactional Memory, Morgan & Claypool, 2006.

Einzelnachweise

1. ↑ TCC Prototypes
2. ↑ vgl. Artikel in der englischsprachigen Wikipedia
3. ↑ http://www.opensparc.net/pubs/preszo/08/RockISSCC08.pdf
4. ↑ Special Report: Can that guy in Ironman 2 whip IBM in real life?. Reuters (12. Mai 2010). Abgerufen am 21. Mai 2011.
5. ↑ http://www.cs.wisc.edu/trans-memory/