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
mersrelyonconservativelocking,oftenattheexpenseofperformance.
Lockinggranularity.Acarefulprogramdesignmustchooseappropriatelevelsoflockingtooptimizethetrade-offbetweenperformanceandeaseofreasoningaboutpro-gramcorrectness.Earlyparallelprogramsweretypicallydesignedwithfewlocksandprogrammersdidnothavetoreasonaboutcorrectnessbecauseallmemorywaspro-tectedbytheselocks.Asparallelismincreasedandlockingbecamefrequent,performancedegradedandfinergrainedlockswereused.Finergranularitylockingcanimproveperformancebutintroducesprogrammingcomplexityandmakes program management dif cult.
Thread-unsafelegacylibraries.Animportantsourceofserializationinsomeenvironmentsisthepresenceofnon-reentrantlegacysoftwarebinaries.Ifathreadcallsalibrarynotequippedtodealwiththreads,agloballockingmecha-nismisusedtopreventconflicts,thusserializingaccessand resulting in a performance degradation.
2.2 Mutual exclusion in microprocessors
Mutualexclusioniscommonlyimplementedusingatomicread-modify-writeprimitivessuchasSWAP,COM-PARE&SWAP,LOAD-LOCKED/STORE-CONDITIONAL(LL/SC),andEXCHANGE.Theseinstructionsallowprocessorsto—sometimesconditionally—atomicallyswaparegistervalueand a memory location.
ThesimplestmutualexclusionconstructisaTEST&SETlock.TEST&SETperformsanatomicswaponamemorylocation.TEST&TEST&SET[32],anextensiontoTEST&SET,performsareadofthelocktotestit,beforeattemptingtheTEST&SEToperation.AnexampleimplementationoftheTEST&TEST&SET sequence is shown in Figure2.
Whilenumerouslockconstructs,bothhardwareandsoftware,havebeenproposed,thesimplicityandportabil-ityofTEST&TEST&SETlocksmakethemquitepopular.Hardwarearchitecturemanualsrecommend[8,10,33,18],anddatabasevendorsareadvised[22]tousethesesimplelocksasaportablelockingmechanism(ofcourse,afewothersoftwareprimitivesarealsousedwhencircumstancesdictatetheiruse).ThePOSIXthreadsstandardrecommendssynchronizationbeimplementedinlibrarycallssuchas
T
SET{
L1:1.ldl t0, 0(t1)#t0 = lock
2.bne t0, L1:#if not free, goto L13.ldl_l t0, 0(t1)#load locked, t0 = lockT
E4.bne t0, L1:#if not free, goto L1S&5.lda t0, 1(0)#t0 = 1
T
6.stl_c t0, 0(t1)#conditional store, lock = 1SET{
7.beq t0, L1:#if stl_c failed, goto L1,8-15.T<critical section>ESN{
16.stl 0 ,0(t1)#lock = 0, release lock
UFigure2.Typicalcodeforlock-acquireandreleasesusingtheAlphaISA[9].ThisisaTEST&TEST&SETlockconstruct.Inst.1through 7 form the lock-acquire, inst. 16 is the lock release.
pthread_mutex_lock()andthesecallsimplementthe
TEST&SET
orTEST&TEST&SET locks.
3 Enabling concurrent critical sections
Inthissection,wediscusstheconceptofSpeculativeLockElision.WeusethecodesequenceinFigure2andLL/SCforeaseofexplanation;theideasarereadilyappliedusingothersynchronizationprimitives.Wefirstdiscusslock-enforcedfalsedependences.InSection3.2andSection3.3weshowhowthesedependencescanbeover-come and we step through an example in Section3.4.
3.1 How locks impose false dependences
Alockisacontrolvariabledeterminingwhetherathreadcanexecuteacriticalsection—itenforcesacontroldependenceamongthreadsbutdoesnotproduceanyusefulresult.Additionally,thelockformsadatadependencewithinthesinglethread—thevalueofthelockdeterminesthecontrolflowforthethread.Thelock-enforcedcontroldependenceismanifestedasadatadependencebecausethelockisamemorylocationcheckedandoperateduponbythethreads.Thisdependenceisanalogoustodatadepen-denceswhereaninstructionwaitsforalogicallyprecedinginstruction, on which it may depend, to complete.
3.2 How to remove false dependences due to locks
Atomicitymeansallchangesperformedwithinacriti-calsectionappeartobeperformedinstantaneously.The
appearanceofinstantaneouschangeiskey.Byacquiringalock,athreadcanpreventotherthreadsfromobservinganymemoryupdatesbeingperformedwithinthecriticalsec-tion.Whilethisconventionalapproachtriviallyguaranteesatomicityofallupdatesinthecriticalsection,itisonlyoneway to guarantee atomicity.
Lockscanbeelidedandcriticalsectionsconcurrentlyexecutedifatomicitycanbeguaranteedforallmemoryoperationswithinthecriticalsectionsbyothermeans.Forguaranteeingatomicity,thefollowingconditionsmustholdwithin a critical section:
1.Datareadwithinaspeculativelyexecutingcriticalsec-tionisnotmodi edbyanotherthreadbeforethespecu-lative critical section completes.
2.Datawrittenwithinaspeculativelyexecutingcriticalsectionisnotaccessed(readorwritten)byanotherthread before the speculative critical section completes.Aprocessorcanprovidetheappearanceofatomicityformemoryoperationswithinthecriticalsectionwithoutacquiringthelockbyensuringthatpartialupdatesper-formedbyathreadwithinacriticalsectionarenotobservedbyotherthreads.Theentirecriticalsectionappearstohaveexecutedatomically,andprogramseman-tics are maintained.
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...
热门文档