文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 外语学习 > 英语学习 > Speculative Lock Elision Enabling Highly Concurrent Multithreaded Execution
侵权投诉

Speculative Lock Elision Enabling Highly Concurrent Multithreaded Execution

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-

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email