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
Nomechanismscurrentlyexisttodetectthisparallelism.Frequentserializationhurtsperformanceofeventunedmultithreadedapplications[37,20],andthedegradationcanbemuchworseinthepresenceofconservativesyn-chronization.
Indevelopingthreadedprograms,programmersmustmaketrade-offsbetweenperformanceandcodedevelop-menttime.Althoughmultithreadedprogrammingcanimprovethroughput,acertainlevelofexpertiseisrequiredtoensurecorrectinterplayamongprogramthreads.Suchrequiredexpertiseisgenerallyhigherthanformostsingle-threadedprogramsbecausesharingofdatastructuresamongthreadsisoftensubtleandcomplex.Programmersmayavoidmuchofthecomplexitywhileensuringcorrect-nessbyusingconservativetechniques[17].Doingsopro-videsafasterandeasierpathtoacorrectlyworkingprogram,butlimitsthread-levelparallelisminprogramsbecauseofunnecessary,synchronization-inducedserializa-tionconstraintsonthreadexecution:inthedynamicexecu-tion, no data hazards may have existed among the threads.Ideally,programmerswouldbeabletousefrequentandconservativesynchronizationtowriteobviouslycorrectmultithreadedprograms,andatoolwouldautomaticallyremoveallsuchconservativeuse.Thus,eventhoughpro-grammersusesimpleschemestowritecorrectcode,syn-chronizationwouldbeperformedonlywhennecessaryforcorrectness;andperformancewouldnotbedegradedbythe presence of dynamically unnecessary synchronization.Inthispaper,weshowhowhardwaretechniquescanbeusedtoremovedynamicallyunnecessaryserializationfromaninstructionstreamandtherebyincreaseconcurrentexe-cution.InSpeculativeLockElision(SLE),thehardwaredynamicallyidenti essynchronizationoperations,predictsthemasbeingunnecessary,andelidesthem.Byremovingtheseoperations,theprogrambehavesasifsynchroniza-tionwerenotpresentintheprogram.Ofcourse,doingsocanbreaktheprograminsituationswheresynchronizationisrequiredforcorrectness.Suchsituationsaredetectedusingpre-existingcachecoherencemechanismsandwith-outexecutingsynchronizationoperations.Inthiscase,recoveryisperformedandthelockisexplicitlyacquired.Synchronizationisperformedonlywhenthehardwaredetermines that serialization is required for correctness.Safedynamiclockremovalisperformedbyexploitingapropertyoflocksandcriticalsectionsastheyarecom-monlyimplemented.Ifmemoryoperationsbetweenthelockacquireandreleaseappeartooccuratomically,thetwowritescorrespondingtothelockacquireandreleasecanbeelidedbecausethesecondwrite(ofthelockrelease)undoesthechangesofthefirstwrite(ofthelockacquire).Section3.3discussesthisconceptindetail.Atomicityvio-lations,discussedfurtherinSection5.3,canbedetected
usingcachecoherenceprotocolsalreadyimplementedinmost modern processors.
SLE has the following key features:1. Enables highly concurrent multithreaded execution:Multiplethreadscanconcurrentlyexecutecriticalsec-tionsguardedbythesamelock.Additionally,correct-nessisdeterminedwithoutacquiring(ormodifying)thelock.
2. Simpli es correct multithreaded code development:Programmerscanuseconservativesynchronizationtowritecorrectmultithreadedprogramswithoutsigni cantperformanceimpact.Ifthesynchronizationisnotrequiredforcorrectness,theexecutionwillbehaveasifthe synchronization were not present.3. Can be implemented easily:
SLEcanbeimplementedentirelyinthemicroarchitec-ture,withoutinstructionsetsupportandwithoutsystem-levelmodi cations(e.g.,nocoherenceprotocolchangesarerequired)andistransparenttoprogrammers.Exist-ingsynchronizationinstructionsareidenti eddynami-cally.Programmersdonothavetolearnanewprogrammingmethodologyandcancontinuetousewellunderstoodsynchronizationroutines.Thetechniquecanbeincorporatedintomodernprocessordesigns,indepen-dent of the system and the cache coherence protocol.Toourknowledge,thisisthefirstproposedtechniqueforremovingdynamicallyunnecessaryandconservativesynchronizationoperationsfromadynamicexecutionwithoutperformingthelock-acquireandreleaseopera-tions,andwithoutrequiringexclusiveownershipofthelock variable.
InSection3andSection4wediscusstheideaofSLEandprovideimplementationstrategiesinSection5.Muchoftheadditionalfunctionalityrequirediseitherpresentinmodernmicroarchitecturesorinvolveswellunderstoodtechniquesdevelopedforothermicroarchitecturaloptimi-zations.
2 Background
Inthissection,weprovideabackgroundintolockingandperformance/complexitytrade-offsinmultithreadedprogramming that can bene t from SLE.
2.1 Performance/complexity trade-offs in multi-threaded programming
Conservativelocking.Inanymultithreadedprogram-mingeffort,programmingcomplexityisthemostsignifi-cantproblemtoconsider[7]andcareisrequiredtoensurecorrectsynchronizationandinteractionamongthreads.Lackofappropriatesynchronizationcanresultinanincor-rectprogramexecution.Toensurecorrectness,program-
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...
热门文档