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,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.

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