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.