文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 外语学习 > 英语学习 > 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

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.

上一页第3页

你可能喜欢

热门文档

相关文档

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