Categories and Subject Descriptors D.1.3 [Programming Techni(2)

privatization

Performancegraphscanbefoundinourforthcomingpa-perinthebenchmarkstrackofIISWC2007[10].Brie y,onan8-core,32-threadSunNiagaraCMP,maximumspeedupisobtainedwhentriangulatingabout200,000points.HeretheCGLbackendtakes8.9swithoneactivethread(inwhichcaseitreducestoDwyer’ssequentialalgorithm),2.4swith8activethreads(speedupof3.7),and2.2s(speedupof4.1)with16activethreads.Bothabsolutetimesandspeedupsarebetteronour16-processorSunFireSMP:theCGLbackendachievesaspeedupof7.7at16threads.FGLandredo-locktimesaresimilartothoseofCGL.TheoriginalRSTMbackend,however,isroughly2×slower.Thisisadirectconsequenceofitsuseofindirection:theapplicationismemorybound;private(geometricallyparti-tioned)workconsumeswellover90%oftotalruntime;andindirectiondoublesthecostofaccessingtransactionalob-jects,eveninprivatecode.(Thememory-boundnatureoftheapplicationalsoaccountsforbetterscalingontheSMPmachine,despitecomparativelyhighpenaltiesforcoherencemisses.)Ourresultsprovideperhapsthestrongestevidencetodateinsupportofindirection-freeSTM.

4.PROGRAMMINGEXPERIENCE

TheRSTMAPIisbasedonsmartpointers[2]andac-cessormethods(“getters”and“setters”).Theseprovidebothinitial-accessandper-access“hooks”intotherun-timesystem,andservetocatchawidevarietyofaccesserrors.Getterstakeanextra,“validator”argumentthatallowsustoperformpost-accessconsistencychecksinredo-lockandotherzero-indirectionsystems.

WehavefoundtheAPItobeasigni cantimprovementoveritspredecessor,whichwasborrowedfromDSTM[7].Inparticular,smartpointersallowus,usinggenerics,tocreategeneral-purposefunctionsthatcanbeusedinbothtransactionalandnontransactionalcontexts.Thereare11suchfunctionsinthemeshapplication.Unfortunately,eventhenewAPIisstillquitedi culttouse[3].

Themostobviousproblemissimpleawkwardness.Acces-sorsarenotanaturalwaytoaccess eldsinC++,thoughtheycouldeasilybemadesowithcompilersupport,asinC#.Validators,likewise,arepuresyntacticclutter.Backendsthatcopyobjectsrequiremethodstocreate,deacti-vate,andcopyclones.Askingtheusertowritetheseexposesimplementationdetailsthatideallyshouldalsobehidden.Ouruseofgenericsfortransactional/privatecodesharingisalsocumbersome;asimilare ectcouldbeachievedwithcompiler-basedfunctioncloning.Moreproblematically,oursmartpointers,whichcomeinfourdi erentvarieties,in-troducealevelofcomplexitythatseemsoutofplaceinaprogrammingmodelintendedtosimplifyconcurrency.

Awkwardnessaside,transactionalprogramsthatuseourAPImustrespectseveralsigni cantrestrictions.Onecan-notsafelyescapeatransactioninanywayotherthanfallingo theend—nogotos,nobreaks,noreturns.Moresignif-icantly,transactionalobjectsmustgenerallyhaveonlytriv-ialconstructorsanddestructors,andonlystaticmethods:Aconstructormustnot,underanycircumstances,throwanexceptionorcon ictwithanothertransaction(whichmightcauseittoabort).Adestructormustnotdoanythingthathastohappenatdeletetime—thememorymanagerdelaysspacereclamationtoavoiderrorsinconcurrenttransactions.Andsince eldsmustbeaccessedthroughsmartpointers,“this”cannotsafelybeused.

Privatizationcanbeachievedviaglobalconsensus(asinthebarriersofthemeshapplication)orbyusingatrans-actiontoremoveanobjectfromasharedcontainer.Such“privatizingtransactions”mustbeexplicitlylabeledinourAPI,toavoidimposingoverheadsonnon-privatizingcode.Finally,becauseweareabletoinstrumentonlyexplic-itlyidenti edtransactionalobjects,nontransactional(non-shared)objectsdonotreverttheirvaluesonabort.Thismeans,amongotherthings,thatatransactioncansafelyreadorwriteanontransactionalvariable(assuming,inthelattercase,italwayswritesbeforecommitting),butnotboth.Likethesourcesofawkwardnessabove,almostalltheselimitationscouldbeeliminatedwithappropriatecompilersupport.Weconcludethatlibrary-basedSTMcanbeavaluabletoolforexperimentationwithback-endimplemen-tationtechniques,butthattheendgoal—simple,scalablethreadcoordination—willrequirelanguageintegration.

5.REFERENCES

[1]TheRochesterSoftwareTransactionalMemory

Runtime,2006.

www.cs.rochester.edu/research/synchronization/rstm/.[2]A.Alexandrescu.SmartPointers.InModernC++

Design:GenericProgrammingandDesignPatternsApplied,C++In-DepthSeries,chapter7.AddisonWesleyProfessional,2001.

[3]L.Dalessandro,V.J.Marathe,M.F.Spear,and

M.L.Scott.CapabilitiesandLimitationsof

Library-BasedSoftwareTransactionalMemoryinC++.2ndACMSIGPLANWorkshoponTransactionalComputing,Aug.2007.[4]B.Delaunay.SurlaSph`ereVide.BulletinoftheUSSR

AcademyofSciences,ClassedesSciencesMath´ematiquesetNaturelles,7:793–800,1934.

[5]R.A.Dwyer.AFasterDivideandConquerAlgorithm

forConstructingDelaunayTriangulation.Algorithmica,2:137–151,1987.

[6]L.GuibasandJ.Stol .Primitivesforthe

ManipulationofGeneralSubdivisionsandthe

ComputationofVoronoiDiagrams.ACMTrans.onGraphics,4(2):74–123,Apr.1985.

[7]M.Herlihy,V.Luchangco,M.Moir,andW.N.

SchererIII.SoftwareTransactionalMemoryfor

Dynamic-sizedDataStructures.22ndACMSymp.onPrinciplesofDistributedComputing,July2003.[8]M.Kulkarni,L.P.Chew,http://www.77cn.com.cning

TransactionsinDelaunayMeshGeneration.WorkshoponTransactionalMemoryWorkloads,June2006.[9]V.J.Marathe,M.F.Spear,C.Heriot,A.Acharya,

D.Eisenstat,W.N.SchererIII,andM.L.Scott.LoweringtheOverheadofSoftwareTransactional

Memory.ACMSIGPLANWorkshoponTransactionalComputing,June2006.

[10]M.L.Scott,M.F.Spear,L.Dalessandro,andV.J.

Marathe.DelaunayTriangulationwithTransactionsandBarriers.IEEEIntl.Symp.onWorkloadCharacterization,Benchmarkstrack,Sept.2007.[11]M.F.Spear,A.Shriraman,L.Dalessandro,

S.Dwarkadas,andM.L.Scott.NonblockingTransactionsWithoutIndirectionUsingAlert-on-Update.19thACMSymp.onParallelisminAlgorithmsandArchitectures,June2007.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Categories and Subject Descriptors D.1.3 [Programming Techni(2)在线全文阅读。