Turau, VolkerVolkerTurau1221655270000-0001-9964-8816Machens, HolgerHolgerMachens2015-05-292015-05-292015http://tubdok.tub.tuhh.de/handle/11420/1243Transactional Memory zielt darauf ab wechselseitigen Ausschluss in kritischen Abschnitten durch Transaktionen auf gemeinsamen Daten zu ersetzen, um die Skalierbarkeit nebenläufiger Anwendungen zu verbessern und traditionelle Probleme paralleler Programmierung wie Deadlocks/Livelocks zu eliminieren. Eine Schlüsselrolle in der Transaktionsverarbeitung spielt die Nebenläufigkeitskontrolle, die für das Auffinden verzahnter oder überlappender Ablaufpläne für laufende Transaktionen auf gemeinsamen Daten zuständig ist, deren Ergebnis äquivalent zu einer seriellen Ausführung derselben Transaktionen ist. In dieser Hinsicht konzentrierte sich die bisherige Forschung auf Nebenläufigkeitskontrollen für Transaktionen mit nur einem Ausführungsfaden basierend auf einem Trial and Error-Ansatz: Die Transaktion führt den kritischen Abschnitt solange wiederholt aus, bis kein Konflikt mit anderen Transaktionen für einen Durchlauf entstanden ist. Diese Arbeit unterbreitet den Vorschlag Hilfs-Threads in Transactional Memory einzusetzen, um eine parallelisierte Transaktionsverarbeitung zu erreichen, die eine gleichzeitige Bearbeitung unterschiedlicher Serialisierungsreihenfolgen auf demselben kritischen Abschnitt in Relation zu anderen laufenden Transaktionen erlaubt. Während bisher bekannte Nebenläufigkeitskontrollen die Transaktion zurücksetzen müssen, um mit dem einen verfügbaren Thread der Transaktion einen weiteren Bearbeitungsversuch hinsichtlich einer neuen Serialisierungsordnung zu starten, erlaubt der hier vorgeschlagene Ansatz den nächsten Bearbeitungsversuch bereits zu Beginn des aktuellen Bearbeitungsversuchs an einen Hilfs-Thread zu delegieren. Aufgrund der Besonderheiten von Transaktionen und nebenläufiger Anwendungen auf gemeinsamen Daten im Allgemeinen, geht die Einführung von Hilfs-Threads mit verschiedenen neuen Aspekten einher, die bei Konzeption und Implementierung zu berücksichtigen sind. Diese Arbeit präsentiert entwickelte Konzepte für Hilfs-Thread-gestützte Nebenläufigkeitskontrollen, welche unabhängig voneinander dieselbe Transaktion parallel ausführen, anstatt information mit dem Haupt-Thread der Transaktion zu teilen, um die Wechselwirkungen gering zu halten. Beispielsweise wird die Entdeckung von Konflikten an einen Hilfs-Thread delegiert, der dieselbe Transaktion auf demselben Prozesszustand parallel Ausführt, anstatt auf die Daten des Haupt-Threads zuzugreifen und jene auf Konfliktfreiheit zu prüfen. Ein weitergehender hier vorgeschlagener Ansatz mit ähnlichem Aufbau, beinhaltet die gleichzeitige Bearbeitung des kritischen Abschnitt mit unterschiedlichen Validierungsmethoden: späte Validierung (lazy) und direkte Validierung (eager). Weil die Verfahren unterschiedliche Reaktionszeiten hinsichtlich auftretender Konflikte haben, driften die beiden Threads zeitlich auseinander und verfolgen als konsequenz tendentiell unterschiedliche Serialisierungsreihenfolgen hinsichtlich konkurrierender Transaktionen. Diese Arbeit präsentiert desweiteren Anforderungen und Subsysteme, die für die Realisierung parallelisierter Transaktionen benötigt werden: Die verwendung sogenannter "Transactional Wrapper" oder "Pure Functions" muss unterbunden werden, weil die Hilfs-Threads nebenläufige Zugriffe auch auf lokalen Variablen einer Funktion erzeugen. Außerdem wurde eine Konzept zum "Clonen" des Zustands einer Transaktion entwickelt, was den Transfer des Kontrollflusses erlaubt, einerseits beim Betreten des kritischen Abschnitts vom Haupt-Thread zum Hilfs-Thread und anderseits bei einem erfolgreichen Commit vom Hilfs-Thread zurück zum Haupt-Thread. Der existierende Sandboxing-Ansatz für Transactional Memory von Dalessandro und Scott zur Unterdrückung und Vermeidung von Fehlern in der Transaktion aufgrund von später Validierung wurde verbessert und die Speicherverwaltung in Transaktionen an die Umstellungen angepasst. Während die hier entwickelten Ansätze in einigen Fällen durchaus mit konkurrieren konnten und gute Skalierbarkeit in besonderen Fällen hoher Nebenläufigkeit aufwiesen, zeigte die Evaluierung gleichermaßen unerwartet hohe Leistungseinbußen in anderen Fällen. Eine Untersuchung der Hardware-Charakteristiken in Bezug auf die Latenz von Lese und Schreibzugriffen auf Speicher und Caches enthüllte verschiedene Probleme der Skalierbarkeit von gleichzeitigen Zugriffen auf dieselben Speicheradressen. Diese Probleme haben deutlichen Einfluss auf hochgradig nebenläufige Anwendungen, was die Verwendung von Transaktionen im Allgemeinen und die Verwendung parallelisierter Transaktionen im Besonderen stark beeinträchtigt.Transactional memory aims to replace mutual exclusion in critical sections with transactions on shared data to improve the scalability of concurrent applications and eliminate traditional issues of parallel programming such as deadlocks/livelocks. One key aspect of transaction processing is the concurrency control, which is responsible to find an interleaving or overlapping schedule for running transactions accessing the same shared data and provide a result equal to some serial execution of the same transactions. In this regard, former research focused on single-threaded concurrency control schemes using a trial and error approach: The transaction repeats executing the critical section until no conflict with other transactions was detected. This thesis proposes the application of helper threads in transactional memory to achieve a parallelised transaction processing, which is able to compute the same critical section in respect to different serialisation orders with other transactions. While traditional concurrency control has to rollback and start another attempt in the same thread, this approach aims to compute the next attempt in a helper thread in parallel to the current attempt computed by a leading thread. Due to the nature of transactions and concurrent shared memory applications in general, the introduction of helper threads comes with several new aspects to be considered on the conceptional and the implementation level. The work presents concepts for helper thread aided concurrency controls independently executing the same transaction in parallel instead of sharing information of the leader thread, to lower the contention. For example, the detection of conflicts is delegated to a helper thread which executes the same transaction on the same state of shared data in parallel instead of validating the data read by the leader. In this manner parallelised transaction processing has been proposed which executes a transaction in parallel with different validation schemes: lazy and eager validation. Because the reaction time on conflicts and execution time differ, they drift apart and compute results for different serialisation orders. The work also presents several requirements and sub-systems needed to run parallelised transactions: The use of so-called transactional wrappers or pure functions to speedup access to thread private data in transactional sections cannot be granted, because the private data of the application thread is now concurrently accessed by the helper thread. Also, a concept has been developed to clone the state of the transaction start and transfer the state of the helper committed transaction back to the leader. The existing sandboxing approach of Dalessandro and Scott to suppress and prevent errors in transactions resulting from lazy validation has been improved and memory management inside transactions was adapted. While the developed approaches can compete in some cases and show good scalability especially in higher concurrency, the evaluation shows an unexpected large loss of performance, too. An investigation of hardware characteristics in respect to memory and cache read/write latency revealed several scalability issues with concurrent access to the same address. These issues have significant impact on highly concurrent applications, which seriously affects the use of transactions in general and parallelised transactions in particular.enhttps://creativecommons.org/licenses/by/4.0/Concurrent ProgrammingTransactional MemoryIngenieurwissenschaftenDoctoral Thesisurn:nbn:de:gbv:830-8821276710.15480/882.124011420/124310.15480/882.1240Schupp, SibylleSibylleSchupp930768381PhD Thesis