1、Transactional Collection Classes Brian D. CarlstromTransactional Collection ClassesBrian D. Carlstrom, Austen McDonald, Michael CarbinChristos Kozyrakis, Kunle OlukotunComputer Systems LaboratoryStanford Universityhttp:/tcc.stanford.eduTransactional Collection Classes 2Transactional MemoryPromise of
2、 Transactional Memory (TM) Make parallel programming easier Better performance through concurrent executionHow does TM make parallel programming easier? Program with large atomic regions Keep the performance of fine-grained lockingTransactional Collection Classes Transactional versions of Map, Sorte
3、dMap, Queue, Avoid unnecessary data dependency violations Provide scalability while allowing access to shared dataTransactional Collection Classes 3Evaluating Transactional MemoryPast evaluations Convert fine-grained locks to fine-grained transactions Convert barrier style applications with little c
4、ommunicationPast results TM can compete given similar programmer effortWhat happens when we use longer transactions?Transactional Collection Classes 4TM hash table micro-benchmark comparisonOld: Many short transactions that each do only one Map operationNew: Long transactions containing one or more
5、Map operationsTransactional Collection Classes 5New: High contention - All threads in 1 warehouse All transactions touch some shared MapTM SPECjbb2000 benchmark comparisonOld: Measures JVM scalability, but app rarely has communication 1 thread per warehouse, 1% inter-warehouse transactionsTransactio
6、nal Collection Classes 6Unwanted data dependencies limit scalingData structure bookkeeping causing serialization Frequent HashMap and TreeMap violations updating size and modification countsWith short transactions Enough parallelism from operations that do not conflict to make up for the ones that d
7、o conflictWith long transactions Too much lost work from conflicting operationsHow can we eliminate unwanted dependencies?Transactional Collection Classes 7Reducing unwanted dependenciesCustom hash table Dont need size or modCount? Build stripped down Map Disadvantage: Do not want to custom build da
8、ta structuresOpen-nested transactions Allows a child transaction to commit before parent Disadvantage: Lose transactional atomicitySegmented hash tables Use ConcurrentHashMap (or similar approaches) Compiler and Runtime Support for Efficient STM, Intel, PLDI 2006 Disadvantage: Reduces, but does not
9、eliminate, unnecessary violationsIs this reduction of violations good enough?Transactional Collection Classes 8Composing Map operationsSuppose we want to perform two Map operations atomically With locks: take a lock on Map and hold it for duration With transactions: one big atomic block Both lousy p
10、erformance Use ConcurrentHashMap? Wont help lock version Probabilistic approach hurts as number of operations per transaction increasesCan we do better?Example compound operation:atomic int balance = map.get(acct);balance += deposit;map.put(acct, balance);Transactional Collection Classes 9Semantic C
11、oncurrency ControlDatabase concept of multi-level transactions Release low-level locks on data after acquiring higher-level locks on semantic concepts such as keys and sizeExample Before releasing lock on B-tree node containing key 7record dependency on key 7 in lock table B-tree locks prevent races
12、 lock table provides isolation421 3 5 76TX# Key Mode #23177 Read Transactional Collection Classes 10Semantic Concurrency ControlApplying Semantic Concurrency Control to TM Avoid retaining memory level dependencies Replace with semantic dependencies Add conflict detection on semantic propertiesTransa
13、ctional Collection Classes Avoid memory level dependencies on size field, Replace with semantic dependencies on keys, size, Only detect semantic conflicts that are necessaryNo more memory conflicts on implementation details Transactional Collection Classes 11Transactional Collection ClassesOur gener
14、al approach Read operations acquire semantic dependency Open nesting used to read class state Writes buffered until commit Check for semantic conflicts on commit Release dependencies on commit and abortSimplified Map example Read operations add dependencies on keys Write operations buffer inserts an
15、d updates On commit we applied buffered changes, violating transactions that read values from keys that are changing On commit and abort we remove dependencies on the keys we have readTransactional Collection Classes 12c = 23c = 23c = 1size=4a = 50,b = 17,c = 23,d = 42size=2b = 17d = 42d = 2c = 1,d
16、= 23c = 23Example of non-conflicting put operationsUnderlying MapWrite BufferDepend-enciesput(c,23) open-nested transactionWrite Bufferput(d,42) open-nested transactionTX #2 startingTX #1 startingTX #1 commit and handler executionTX #2 commit and handler executionTransactional Collection Classes 13c
17、 = 1c = 1,2size=3a = 50,b = 17,c = 23c = 23c = 23size=2b = 17Example of conflicting put and get operationsUnderlying MapWrite BufferDepend-enciesput(c,23) open-nested transactionWrite Bufferget(c) open-nested transactionTX #2 startingTX #1 startingTX #1 commit and handler executionTX #2 abort and ha
18、ndler executionTransactional Collection Classes 14Benefits of Semantic Concurrency ApproachWorks with any conforming implementation HashMap, TreeMap, Avoids implementation specific violations Not just size and mod count HashTable resizing does not abort parent transactions TreeMap rotations invisibl
19、e as wellTransactional Collection Classes 15Making a Transactional Class Categorize primitive versus derivative methods Derivative methods such as isEmpty can be ignored Often only a small fraction of methods are primitive Categorize read versus write methods Read methods do not conflict with each o
20、ther Need to focus on how write operations cause conflicts Define semantic dependencies Most difficult step, although still not rocket science For Map, this involved deciding to track keys and size Implement!Transactional Collection Classes 16Making a Transactional Class Implementation Derivative me
21、thods call primitive methods Read operations use open nesting Avoid memory dependencies on committed state Record semantic dependencies in shared state Consult buffered state for local changes of our own write operations Write operations record changes in local state Commit handler Transfers local s
22、tate to committed state Abort other transactions with conflicting dependencies Releases dependencies Abort handler Cleans up local state Releases dependenciesTransactional Collection Classes 17Library focused solutionProgrammer just uses the usual collection interfaces Code change as simple as repla
23、cingMap map = new HashMap(); with Map map = new TransactionalMap();We provide similar interface coverage to util.concurrent Maps: TransactionalMap, TransactionalSortedMap Sets: TransactionalSet, TransactionalSortedSet Queue:TransactionalQueuePrimarily only library writers need to master implementati
24、on Seems more manageable work than util.concurrent effortTransactional Collection Classes 18Paper detailsTransactionalMap Discussion of full interface including dealing with iteration TransactionalSortedMap Adds tracking of range dependenciesTransactionalQueue Reduces serialization requirements Most
25、ly FIFO, but if abort after remove, simple pushbackTransactional Collection Classes 19Evaluation Environment The Atomos Transactional Programming Language Java - locks + transactions = Atomos Implementation based on Jikes RVM 2.4.2+CVS GNU Classpath 0.19 Hardware is simulated PowerPC chip multiproce
26、ssor 1-32 processors with private L1 and shared L2 For details about the Atomos programming language See PLDI 2006 For details on hardware for open nesting, handlers, etc. See ISCA 2006 For details on simulated chip multiprocessor See PACT 2005Transactional Collection Classes 20TestMap results TestM
27、ap is a long operation containing a single map operation Java HashMap with single lock scales because lock region is small compared to long operation TransactionalMap with semantic concurrency control returns scalability lost to memory level violationsTransactional Collection Classes 21TestCompound
28、results TestCompound is a long operation containing two map operations Java HashMap protects the compound operations with a lock, limiting scalability TransactionalMap preserves scalability of TestMap Transactional Collection Classes 22High-contention SPECjbb2000 resultsJava Locks Short critical sec
29、tionsAtomos Baseline Full protection of logical opsPerformance Limit? Data dependency violations on unique ID generator for new order objectsTransactional Collection Classes 23High-contention SPECjbb2000 resultsJava Locks Short critical sectionsAtomos Baseline Full protection of logical opsAtomos Op
30、en Use simple open-nesting for UID generationPerformance Limit? Data dependency violations on TreeMap and HashMapTransactional Collection Classes 24High-contention SPECjbb2000 resultsJava Locks Short critical sectionsAtomos Baseline Full protection of logical opsAtomos Open Use simple open-nesting f
31、or UID generationAtomos Transactional Change to Transactional Collection ClassesPerformance Limit? Semantic violations from calls to SortedMap.firstKey()Transactional Collection Classes 25High-contention SPECjbb2000 resultsSortedMap dependency SortedMap use overloaded Lookup by ID Get oldest ID for
32、deletionReplace with Map and Queue Use Map for lookup by ID Use Queue to find oldestTransactional Collection Classes 26High-contention SPECjbb2000 resultsWhat else could we do? Split larger transactions into smaller ones In the limit, we can end up with transactions matching the short critical regio
33、ns of JavaReturn on investment Coarse grained transactional version is giving 8x on 32 processors Coarse grained lock version would not have scaled at allTransactional Collection Classes 27ConclusionsTransactional memory promises to ease parallelization Need to support coarse grained transactionsNee
34、d to access shared data from within transactions While composing operations atomically While avoiding unnecessary dependency violations While still having reasonable performance!Transactional Collection Classes Provides needed scalability through familiar library interfaces of Map, SortedMap, Set, SortedSet, and Queue
