Reduktion von False-Sharing in Software-Transactional-Memory

Abstract

Software-Transactional-Memory (STM) erleichtert das parallele Programmieren, jedoch hat STM noch einen zu hohen Laufzeitaufwand, da gegenseitiger Ausschluss beim Zugriff auf gemeinsame Daten meist mittels einer Lock-Tabelle fester Gr¨ oße realisiert wird. F¨ ur Programme mit wenigen konkurrierenden Zugriffen und ¨ berwiegend Lesezugriffen ist diese Tabelle gr¨ u oßer als notwendig, so dass beim Commit einer Transaktion mehr Locks zur Konsistenzpr¨ ufung zu inspizieren sind als n¨ otig. F¨ ur große Datenmengen ist die Tabelle zu klein. Dann begrenzt False-Sharing (unterschiedliche Adressen werden auf das gleiche Lock abgebildet) die Parallelit¨ at, da sogar unabh¨ angige Transaktionen sich gegenseitig ausschließen. Diese Arbeit beschreibt eine Technik, die die Lock-Tabelle bei False-Sharing vergr¨ oßert. Zus¨ atzlich kann ein Programmierer mit Annotationen unterschiedliche Lock-Tabellen f¨ ur voneinander unabh¨ angige Daten verlangen, was die M¨ oglichkeit von False-Sharing und den Speicherbedarf f¨ ur die Locks weiter verringert In Benchmarks erreichen wir einen maximalen Speedup von 10.3 gegen¨ uber TL2, wobei die Lock-Tabelle bis zu 1024 mal kleiner ist.