Über die Kosten der Nebenläufigkeit in Transactional Memory

Aktuelle Allzweck-CPUs haben mehrere Rechenkerne innerhalb eines einzelnen Chipsatzes. Allerdings erhöht sich die Leistung der Programme auf diesen Architekturen nicht notwendigerweise proportional in der Anzahl der Kerne. Das Entwerfen nebenläufiger Programme um diese Multicores zu nutzen, erfordert die Überwindung einiger nicht-trivialer Herausforderungen; die wichtigste ist, eine effiziente Synchronisierung der Threads der Berechnung herzustellen. Greifen mehrere Threads gleichzeitig auf dieselben Daten zu, müssen diese ihre Aktionen koordinieren, um ein korrektes Programmverhalten zu gewährleisten. Die traditionelle Methode zur Synchronisierung ist "Locking", welches jeweils nur einem einzelnen Thread Zugriff auf gemeinsam genutzten Daten gewährt. Bei grobkörnigem "Locking" erfolgt der Zugang zu einer großen Menge von Daten meist seriell, sodass die Hardware-Parallelität nich in vollem Unfang ausgenutzt wird. Auf der anderen Seite stellt programmspezifisches feinkörniges Locking, oder auch nicht-blockierende (d.h. keine Locks benutzende) Synchronisierung, eine dunkle Kunst für die meisten Programmierer dar, welche auf die Weisheit weniger Computerexperten vertraut. So ist es angebracht, einen Mittelweg zwischen diesen beiden Extremen zu suchen: einen Synchronisierungsmechanismus, der den Programmierer bezüglich der Datenkonflikte, die aus gleichzeitigen Operationen entstehen, entlastet, ohne jedoch die Leistung des Programms zu stark zu beeinträchtigen. Die Transactional Memory (TM) Abstraktion wird als solcher Mechanismus vorgeschlagen: ihr Ziel ist es, eine einfach zu bedienende Programmierschnittstelle mit einer effizienten Nutzung der gleichzeitigen Computing-Fähigkeiten von Multicore-Architekturen zu kombinieren. TM erlaubt es dem Programmierer, Sequenzen von Operationen auf dem gemeinsamen Speicher als atomare Transaktionen mit Alles-oder-Nichts Semantik zu erklären: Die Transaktion wird entweder übergeben, und somit sequentiell ausgeführt, oder abgebrochen, sodass ihre Operationen nicht durchgeführt werden. Dies ermöglicht dem Programmierer, Software mit nur sequentieller Semantik zu konzipieren, und die aus gleichzeitiger Ausführung entstehenden Konflikte TM zu überlassen. Intuitiv sollen die TMs so viel Nebenläufigkeit wie möglich berücksichtigen: Falls keine Datenkonflikte vorhanden sind, sollen alle Transaktionen parallel ausgeführt werden. Gibt es in TMs Kosten, die durch diesen hohen Grad an Nebenläufigkeit entstehen? Das ist die zentrale Frage dieser Arbeit. Um diese Frage zu beantworten, konzentrieren wir uns zunächst auf das Kriterium der Konsistenz, welche von der TM-Implementierung erfüllt werden muss. Wir charakterisieren auf präzise Art, was es für eine TM-Implementierung heißt, sicher zu sein, d.h. zu gewährleisten, dass die Sicht einer jeden Transaktion auch von einer sequentiellen Transaktion hätte beobachtet werden können. Danach präsentieren wir mehrere untere und obere Schranken für die Komplexität dreier Klassen von sicheren TMs: blockierende TMs, die Blockierungen oder Abbrüche der Transaktionen erlauben, sollten diese sich überlappen, nicht-blockierende TMs die einen schrittweisen Zugriffskonflikt berücksichtigen, d.h. Transaktionen, die keinen Zugriff überlappender anderer Transaktionen beobachten, müssen übergeben, und partiell nicht-blockierende TMs, die nur für eine Teilmenge von Transaktionen nicht-blockierend sind. Wir schlagen daraufhin ein Modell für hybride TM-Implementierungen vor, welches die Hardware Transaktionen mit Software Transaktionen ergänzt. Wir beweisen, dass es eine inherente Trade-Off zwischen Grad der erlaubten Nebenläufigkeit zwischen Hard- und Software Transaktionen und den Kosten der Hardware gibt. Schlussendlich beweisen wir, dass optimistische, auf spekulativen Ausführungen basierende, Synchronisierungstechniken, in einem präzisen Sinne, besser geeignet sind um Nebenläufigkeit auszunutzen als pessimistische Techniken, die auf "Locking" basieren.Current general-purpose CPUs are multicores, offering multiple computing units within a single chip. The performance of programs on these architectures, however, does not necessarily increase proportionally with the number of cores. Designing concurrent programs to exploit these multicores emphasizes the need for achieving efficient synchronization among threads of computation. When there are several threads that conflict on the same data, the threads will need to coordinate their actions for ensuring correct program behaviour. Traditional techniques for synchronization are based on locking that provides threads with exclusive access to shared data. Coarse-grained locking typically forces threads to access large amounts of data sequentially and, thus, does not fully exploit hardware concurrency. Program-specific fine-grained locking or non-blocking (i.e., not using locks) synchronization, on the other hand, is a dark art to most programmers and trusted to the wisdom of a few computing experts. Thus, it is appealing to seek a middle ground between these two extremes: a synchronization mechanism that relieves the programmer of the overhead of reasoning about data conflicts that may arise from concurrent operations without severely limiting the program's performance. The Transactional Memory (TM) abstraction is proposed as such a mechanism: it intends to combine an easy-to-use programming interface with an efficient utilization of the concurrent-computing abilities provided by multicore architectures. TM allows the programmer to speculatively execute sequences of shared-memory operations as atomic transactions with all-or-nothing semantics: the transaction can either commit, in which case it appears as executed sequentially, or abort, in which case its update operations do not take effect. Thus, the programmer can design software having only sequential semantics in mind and let TM take care, at run-time, of resolving the conflicts in concurrent executions. Intuitively, we want TMs to allow for as much concurrency as possible: in the absence of severe data conflicts, transactions should be able to progress in parallel. But what are the inherent costs associated with providing high degrees of concurrency in TMs? This is the central question of the thesis. To address this question, we first focus on the consistency criteria that must be satisfied by a TM implementation. We precisely characterize what it means for a TM implementation to be safe, i.e., to ensure that the view of every transaction could have been observed in some sequential execution. We then present several lower and upper bounds on the complexity of three classes of safe TMs: blocking TMs that allow transactions to delay or abort due to overlapping transactions, non-blocking TMs which adapt to step contention by ensuring that a transaction not encountering steps of overlapping transactions must commit, and partially non-blocking TMs that provide strong non-blocking guarantees (wait-freedom) to only a subset of transactions. We then propose a model for hybrid TM implementations that complement hardware transactions with software transactions. We prove that there is an inherent trade-off on the degree of concurrency allowed between hardware and software transactions and the costs introduced on the hardware. Finally, we show that optimistic synchronization techniques based on speculative executions are, in a precise sense, better equipped to exploit concurrency than inherently pessimistic techniques based on locking