Serialization of threads due to critical sections is a fundamental bottleneck to achieving high performance in multithreaded programs. Dynamically, such serialization may be unnecessary because these critical sections could have safely executed concurrentl
Appears in the proceedings of the 34th International Symposium on Microarchitecture (MICRO), Dec. 3-Dec. 5, 2001, Austin, Texas.
Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution
Ravi Rajwar and James R. GoodmanComputer Sciences DepartmentUniversity of Wisconsin-Madison
Madison, WI 53706 USA{rajwar, goodman}@cs.wisc.edu
Abstract
Serializationofthreadsduetocriticalsectionsisafun-damentalbottlenecktoachievinghighperformanceinmul-tithreadedprograms.Dynamically,suchserializationmaybeunnecessarybecausethesecriticalsectionscouldhavesafelyexecutedconcurrentlywithoutlocks.Currentproces-sorscannotfullyexploitsuchparallelismbecausetheydonothavemechanismstodynamicallydetectsuchfalseinter-thread dependences.
WeproposeSpeculativeLockElision(SLE),anovelmicro-architecturaltechniquetoremovedynamicallyunnecessarylock-inducedserializationandenablehighlyconcurrentmultithreadedexecution.Thekeyinsightisthatlocksdonotalwayshavetobeacquiredforacorrectexe-cution.Synchronizationinstructionsarepredictedasbeingunnecessaryandelided.Thisallowsmultiplethreadstoconcurrentlyexecutecriticalsectionsprotectedbythesamelock.Misspeculationduetointer-threaddatacon- ictsisdetectedusingexistingcachemechanismsandroll-backisusedforrecovery.Successfulspeculativeelisionisvalidated and committed without acquiring the lock.
SLEcanbeimplementedentirelyinmicroarchitecturewithoutinstructionsetsupportandwithoutsystem-levelmodi cations,istransparenttoprogrammers,andrequiresonlytrivialadditionalhardwaresupport.SLEcanprovideprogrammersafastpathtowritingcorrecthigh-perfor-mance multithreaded programs.
1 Introduction
Explicithardwaresupportformultithreadedsoftware,eitherintheformofsharedmemorymultiprocessorsorhardwaremultithreadedarchitectures,isbecomingincreas-inglycommon[9,21,38,2].Assuchsupportbecomesavailable,applicationdevelopersareexpectedtoexploitthesedevelopmentsbyemployingmultithreadedprogram-ming.Whileserverworkloadshavetraditionallydisplayedabundantthread-levelparallelism,increasingevidenceindicatesdesktopapplicationsmayalsodisplaysuchparal-lelismifprogrammersfocuseffortsonexploitingtheseemerging architectures.
Inmultithreadedprograms,synchronizationmecha-nisms—usuallylocks—areoftenusedtoguaranteethreadshaveexclusiveaccesstoshareddataforacriticalsectionofcode.Athreadacquiresthelock,executesitscriticalsec-tion,andreleasesthelock.Allotherthreadswaitforthelockuntilthefirstthreadhascompleteditscriticalsection,serializingaccessandthusmakingtheentirecriticalsec-tion appear to execute atomically.
Foravarietyofreasons,concurrentaccessestoashareddatastructurebymultiplethreadswithinacriticalsectionmayinfactnotconflict,andsuchaccessesdonotrequireserialization.TwosuchexamplesareshowninFigure1.Figure1ashowsanexamplefromamultithreadedapplica-tionocean[40].Sinceastoreinstruction(line3)toasharedobjectispresent,thelockisrequired.However,mostdynamicexecutionsdonotperformthestoreopera-tionandthusdonotrequirethelock.Additionally,multiplethreadsmayupdatedifferentfieldsofasharedobject,whileholdingthesharedobjectlock,andoftentheseupdatesdonotconflict.Suchanexample,involvingupdatesofahashtable,isshowninFigure1b.Thisexam-pleissimilartoathread-safehash-tableimplementationfromSHORE, a database object repository [5].
Intheseexamples,conventionalspeculativeexecutioninout-of-orderprocessorscannottakeadvantageoftheparallelismpresentbecausethethreadswillfirstwaitforafreelockandthenacquirethelockinaserializedmanner.
a)
1.LOCK(locks->error_lock)
2.if (local_error > multi->err_multi)3.multi->err_multi = local_err;4.UNLOCK(locks->error_lock)b)
Thread 1
Thread 2
LOCK(hash_tbl.lock)
var = hash_tbl.lookup(X)if (!var)
hash_tbl.add(X);UNLOCK(hash_tbl.lock)
LOCK(hash_tbl.lock)
var = hash_tbl.lookup(Y)if (!var)
hash_tbl->add(Y);UNLOCK(hash_tbl.lock)
Figure1.Twoexamplesofpotentialparallelismmaskedbydynamically unnecessary synchronization.
Speculative Lock Elision (SLE) is a micro-...and enable highly concurrent multithreaded execution....(TLR) uses SLE as an enabling mechanism but in...
Speculative Lock Elision: Enabling highly concurrent multithreaded execution. pages 294–305, Austin, TX, December 2001. [8] G.S. Sohi, S.E. Breach, ...
Speculative Lock Elision (SLE) is a micro-...and enable highly concurrent multithreaded execution....(TLR) uses SLE as an enabling mechanism but in...
热门文档