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,http://www.77cn.com.cningDwyer’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.