Compiler and Runtime Support for Efficient SoftwareTransactional MemoryAli-Reza Adl-Tabatabai1Brian T. Lewis1Vijay Menon1Brian R. Murphy2Bratin Saha1Tatiana Shpeisman11Intel Labs2Intel China Research CenterSanta Clara, CA 95054 Beijing, China{ali-reza.adl-tabatabai,brian.t.lewis,vijay.s.menon,brian.r.murphy,bratin.saha,tatiana.shpeisman}@intel.comAbstractProgrammers have traditionally used locks to synchronize concur-rent access to shared data. Lock-based synchronization, however,has well-known pitfalls: using locks for fine-grain synchroniza-tion and composing code that already uses locks are both difficultand prone to deadlock. Transactional memory provides an alter-nate concurrency control mechanism that avoids these pitfalls andsignificantly eases concurrent programming. Transactional mem-ory language constructs have recently been proposed as extensionsto existing languages or included in new concurrent language spec-ifications, opening the door for new compiler optimizations thattarget the overheads of transactional memory.This paper presents compiler and runtime optimizations fortransactional memory language constructs. We present a high-performance software transactional memory system (STM) inte-grated into a managed runtime environment. Our system efficientlyimplements nested transactions that support both composition oftransactions and partial roll back. Our JIT compiler is the first tooptimize the overheads of STM, and we show novel techniquesfor enabling JIT optimizations on STM operations. We measurethe performance of our optimizations on a 16-way SMP runningmulti-threaded transactional workloads. Our results show that thesetechniques enable transactional memory’s performance to competewith that of well-tuned synchronization.Categories and Subject Descriptors D.3.4 [Programming Lan-guages]: Processors—Compilers, Optimization, Run-time environ-mentsGeneral Terms Algorithms, Measurement, Performance, Design,Experimentation, LanguagesKeywords Transactional Memory, Synchronization, Locking,Compiler Optimizations, Code Generation, Virtual Machines1. IntroductionAs single thread performance hits the power wall, hardware ar-chitects have turned to chip level multiprocessing (CMP) for in-creasing processor performance. Future processor generations willPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee.PLDI’06 June 10–16, 2006, Ottawa, Ontario, CanadaCopyrightc 2006 ACM 1-59593-320-4/06/0006. ..$5.00.use the exponentially increasing transistor budget to provide in-creasing amounts of thread-level parallelism, thus bringing parallelprogramming into the mainstream. Today, programmers use lock-based synchronization to control concurrent access to shared data.Lock based synchronization is difficult to compose, and can lead toproblems such as deadlock. Transactional memory (TM) providesan alternate concurrency control mechanism that eliminates or alle-viates these pitfalls, and significantly eases parallel programming.TM can be provided as either a library or a first-class languageconstruct. A library approach allows language designers to experi-ment with different TM abstractions and implementations beforebaking TM into a language or hardware. A first-class TM lan-guage construct, on the other hand, enables compiler optimizationsto improve performance and enables static analyses that providecompile-time safety guarantees. Although several researchers haveimplemented TM language constructs [16, 33, 17] and languagedesigners have included TM constructs in new concurrent languagespecifications[2, 11, 9], no prior work has addressed how to supporttransactions in an optimizing compiler.In this paper, we focus on compiler and runtime optimizationsfor transactional memory language constructs. We present a high-performance TM system integrated into a managed runtime envi-ronment. We show that a highly tuned software TM applicationstack performs comparably to well-tuned locking code. Our TMsystem makes the following novel contributions:•Our TM implementation is the first TM system to integratean optimizing JIT compiler with a runtime STM library. Wepresent a new runtime STM interface tailored for JIT-compiledcode in a managed environment. We present compiler optimiza-tions to reduce the overhead of STM and show how the com-piler intermediate representation can expose STM operations insuch a way that existing global optimizations can safely elim-inate redundant STM operations. Our results show that theseoptimizations substantially reduce STM overheads to less than20% over synchronized code on a single thread.•We are the first STM to provide language constructs for com-posable memory transactions [17] in an imperative Java-likelanguage. We demonstrate how common transactional idioms(e.g., conditional critical regions) map onto these constructs.Moreover, we demonstrate how to map these constructs ontoJava’s built-in exception mechanisms in order to model trans-actional control flow due to nested transactions, user-initiatedretry operations, and data conflicts.•Our TM system is the first to implement and evaluate conflictdetection at both object and word granularity; the first to bal-ance conflict detection overhead with conflict detection granu-26larity by allowing object and word granularity conflict detectionto co-exist on a per-type basis; and the first to implement thisin a general way that supports a moving garbage collector. Ourresults show that this strategy is crucial to lowering the over-heads of STM while at the same time achieving good scalabilitywhen multiple threads concurrently access disjoint elements ofa shared object.•Our TM system efficiently implements nested transactions andpartial undos. Our runtime STM structures help implementnesting efficiently by making it easy to merge or discard readand write sets on nested transaction commits and aborts. Weshow how to model nesting in the intermediate representationso that the compiler can correctly optimize STM operationsacross nesting depths.We have implemented our STM in a managed runtime environ-ment that supports multithreaded Java programs employing
View Full Document
Unlocking...