Categories and Subject Descriptors D.1.3 [Programming Techni

privatization

BriefAnnouncement:

TransactionsandPrivatizationinDelaunayTriangulation

MichaelL.Scott,MichaelF.Spear,LukeDalessandro,andVirendraJ.Marathe

DepartmentofComputerScience,UniversityofRochester

{scott,spear,luked,vmarathe}@cs.rochester.edu

CategoriesandSubjectDescriptors:

D.1.3[ProgrammingTechniques]:ConcurrentProgramming—ParallelProgrammingGeneralTerms:algorithms,experimentation,

measurement,performance

Keywords:synchronization,transactionalmemory,

benchmarks,privatization

1.INTRODUCTION

Withtheriseofmulticoreprocessors,muchrecentatten-tionhasfocusedontransactionalmemory(TM).Unfortu-nately,the eldhasyettodevelopstandardbenchmarkstocaptureapplicationcharacteristicsortofacilitatesystemcomparisons.Thisnotedescribesonecandidatebenchmark:animplementationofDelaunaytriangulation[4].SourceforthisbenchmarkispackagedwithVersion3oftheRochesterSoftwareTransactionalMemory(RSTM)open-sourceC++library[1,9].Itemploysoneofthefastestknownsequentialalgorithmstotriangulategeometricallypartitionedregionsinparallel;itthenemploysalternating,barrier-separatedphasesoftransactionalandpartitioned(“privatized”)worktostitchthoseregionstogether.Experimentsonmultipro-cessorandmulticoremachinescon rmgoodspeedupandexcellentsingle-threadperformance.Theyalsohighlightthecostofextraindirectionintheimplementationoftransac-tionaldata:sinceexecutiontimeisdominatedbyprivatizedphases,performanceislargelyinsensitivetotheoverheadoftransactionsperse,buthighlysensitivetoanycostsim-posedonprivatizeddata.Experiencewiththeapplication-writingprocessprovidesstronganecdotalevidencethatTMwilleventuallyrequirelanguageandcompilersupport.

2.OVERVIEWOFTHEBENCHMARK

GivenasetofpointsPintheplane,atriangulationparti-tionstheconvexhullofPintoasetoftrianglessuchthat(1)theverticesofthetriangles,takentogether,areP,and(2)notwotrianglesintersectexceptbysharinganedge.ADe-launaytriangulationhastheaddedpropertythatnopointliesintheinteriorofanytriangle’scircumcircle.Delaunaytriangulationiswidelyusedin niteelementanalysis,where

ThisworkwassupportedinpartbyNSFgrantsCNS-0411127andCNS-0615139,equipmentsupportfromSunMicrosystemsLaborato-ries,and nancialsupportfromIntelandMicrosoft.

Copyrightisheldbytheauthor/owner(s).

PODC’07,August12–15,2007,Portland,Oregon,USA.ACM978-1-59593-616-5/07/0008.

itpromotesnumericalstability,andingraphicalrendering,whereitpromotesaestheticallypleasingshadingofcomplexsurfaces.Inpractice,Delaunaymeshesaretypicallyre nedbyintroducingadditionalpointswhereneededtoeliminateremainingnarrowtriangles.

Atthe2006WorkshoponTransactionalWorkloads,Kulka-rnietal.proposedre nementofanexistingDelaunaymeshasapotentialapplicationoftransactionalmemory[8].Ourcodeaddressesthecomplementaryproblemofconstructingtheinitialtriangulation;wedonotyetconsiderre nement.Webeginbysortingpointsintogeometricregions,ingDwyer’sre nement[5]ofGuibasandStol ’sdivide-and-conqueralgorithm[6],eachworkerthentriangulatesitsownregion.Finally,weemployamixoftransactionsandthread-localcomputationto“stitch”theregionstogether,updatingpreviouslychosentriangleswhennecessarytomaintainthecircumcircleproperty.

Alltold,ourapplicationcomprisessome3200linesofC++,in24source les.Therearethreetransactionalobjecttypesandthreestaticoccurrencesoftransactions.The rsttransactionaltyperepresentsanedgebetweentwopoints.Thesecondcontains,foragivenpoint,areferencetosomeadjacentedge,fromwhichotherscanbefoundbyfollowingneighborlinks.Thethirdisusedtocreatelinksinthechainsofaglobalhashset,usedtoholdcreatededges.

The rststatictransactionprotectsacalltotheedgecon-structor.Thesecondprotectsthebodyofasubroutineusedwhenstitchingregionstogether.Thethirdisusedto“recon-sider”edgesthatmaynotsatisfythecircumcirclepropertyinlightofsubsequentregionstitching.Togetherwithcalledroutines,thesetransactionscomprise72,155,and214linesofcode,respectively.

3.PERFORMANCESUMMARY

Wehavemeasuredtheperformanceofthemeshapplica-tiononbothmultiprocessorandmulticoremachines,using2di erentSTMsystemsandbothcoarseand ne-grainlocks.TheoriginalRSTMlibrary[9]usesalevelofindirectionforatomic,nonblockingreplacementofobjectversions.Theredo-locklibrary[11]copiesnewversionsbackontopoftheoriginalsatcommittime,avoidingtheneedforindirectionwhenreading.TheCGL(coarse-grain-lock)libraryforces“transactions”tocompeteforasingle,globallock,yield-ingverylowoverheadintheuncontendedcase,butnocon-currency.Finally,ourFGL( ne-grain-lock)resultsusetheCGLbackendtoavoidbothoverheadandindirection,anduse#ifdefstoreplacetransactionswithcriticalsectionsthatacquireper-pointlocks.

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-a …… 此处隐藏：6288字，全部文档内容请下载后查看。喜欢就下载吧 ……