Seite drucken

SCC4TM

Speculative Concurrency Control for Transactional Memory

Beginn 1. September 2011
Ende 31. Dezember 2014
Finanzierung Technische Universität Hamburg-Harburg

Projektbeschreibung

Durch die Veränderungen auf dem Markt von Personal-Computern hin zu Prozessoren mit mehreren Cores (Recheneinheiten) werden zunehmend mehr parallele Programme entwickelt, die nebenläufig mehrere Aufgaben in separaten Ausführungssträngen (Threads/Prozessen) gleichzeitig lösen. Der Zugriff auf gemeinsame Daten im Hauptspeicher muss dabei kontrolliert werden, um Inkonsistenzen zu vermeiden. Beispielsweise können hierzu die gemeinsamen Daten für die Zeit der Benutzung gesperrt werden, sodass nur ein Ausführungsstrang exklusiven Zugriff erhält. Ausführungsstränge, die nicht auf denselben Daten arbeiten, müssen dann aber ebenfalls warten. Alternativ kann der Datenraum zerlegt werden und ein Ausführungsstrang sperrt immer nur die Abschnitte, die er braucht. Bei falscher Verwendung treten dabei Verklemmungen zwischen Ausführungssträngen auf: Ausführungsstrang A besitzt eine Sperre auf ein Datum a und benötigt ein Datum b, das aber im Besitz eines Ausführungsstrangs B ist, welcher seinerseits das Datum a benötigt -- beide Ausführungsstränge warten ewig. Eine Alternative zum manuellen kontrollieren nebenläufiger Datenzugriffe durch den Programmierer ist die Verwendung von sogenanntem Transaktionalen Speicher (engl. Transactional Memory, abk. TM). Dabei werden die kritischen Operationen auf gemeinsamen Daten in sogenannten Transaktionen zusammen gefasst und der Datenzugriff wird durch eine Nebenläufigkeitskontrolle (engl. Concurrency Control, abk. CC) automatisch kontrolliert. Charakteristische Eigenschaft von CC für Transaktionen ist das Rollback: Bei auftretenden Inkonsistenzen oder Verklemmungen wird die in einer Transaktion bisher geleistete Arbeit verworfen und von vorn begonnen. Damit werden auch einige Operationen verworfen, die nicht Ursache des Konflikts waren. Daher existieren Verfahren, die Transaktion in Teilabschnitte zu zerlegen und bei einem Rollback möglichst nahe an den Punkt der Entstehung des Konflikts zurückzufahren. Diese Vorschläge sind von der Programmstruktur abhängig und machen dadurch die parallele Programmierung komplizierter. Auch verursachen sie Mehraufwand für das CC, der im gleichen Ausführungsstrang geleistet werden muss. Ziel dieses Vorhabens ist es, durch den Einsatz von zusätzlichen Cores, das CC für TM weiter zu optimieren. Dazu soll ein Ausführungsstrang in einer Transaktion in mehrere Ausführungsstränge aufgespalten werden, die jeweils auf eigenen Cores ausgeführt werden. Die Ansätze zur Optimierung reichen von der einfachen Verlagerung des Arbeitsaufwandes des CC in separate Ausführungsstränge über die Lösung von Problemen von CC im gleichen Ausführungsstrang bis hin zur gleichzeitigen, spekulativen Ausführung alternativer Programmverläufe für eine einzige Transaktion.

Publikationen

Holger Machens und Volker Turau. Opacity of Memory Management in Software Transactional Memory. Technical Report Report arXiv:1308.2881, arXiv.org e-Print Archive - Computing Research Repository (CoRR), Cornell University, August 2013.
@TechReport{Telematik_MT_2013_OPACITY_of_MM_in_TM, author = {Holger Machens and Volker Turau}, title = {Opacity of Memory Management in Software Transactional Memory}, number = {Report arXiv:1308.2881}, institution = {arXiv.org e-Print Archive - Computing Research Repository (CoRR)}, address = {Cornell University}, month = aug, year = 2013, }
Abstract: Opacity of Transactional Memory is proposed to be established by incremental validation. Quiescence in terms of epoch-based memory reclamation is applied to deal with doomed transactions causing memory access violations. This method unfortunately involves increased memory consumption and does not cover reclamations outside of transactions. This paper introduces a different method which combines incremental validation with elements of sandboxing to solve these issues.

Studentische Arbeiten

Abgeschlossene Arbeiten