Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Bsp dev guide Practical aspects BSPlib The BSP programming library Jonathan M D Hill a Bill McColl a Dan C Stefanescu b c Mark W Goudreau d Kevin Lang e Satish B Rao e Torsten Suel f Thanasis Tsantilas g Rob H Bisseling h aOxford University Computing Labo

Practical aspects BSPlib The BSP programming library Jonathan M D Hill a Bill McColl a Dan C Stefanescu b c Mark W Goudreau d Kevin Lang e Satish B Rao e Torsten Suel f Thanasis Tsantilas g Rob H Bisseling h aOxford University Computing Laboratory Oxford OX QD UK bHarvard University Cambridge USAcSu ?olk University Boston USA dUniversity of Central Florida Orlando USAeNEC Research Institute Princeton USA fBell Laboratories Lucent Technologies N J USA gColumbia University New York USA hUtrecht University Utrecht The Netherlands Received October received in revised form April Abstract BSPlibis a small communications library for bulk synchronous parallel BSP program- ming which consists of only basic operations This paper presents the full de nition of BSPlibin C motivates the design of its basic operations and gives examples of their use The library enables programming in two distinct styles direct remote memory access DRMA using put or get operations and bulk synchronous message passing BSMP Currently im- plementations ofBSPlibexist for a variety of modern architectures including massively parallel computers with distributed memory shared memory multiprocessors and networks of workstations BSPlibhas been used in several scienti c and industrial applications this paper brie y describes applications in benchmarking Fast Fourier Transforms FFTs sorting and molecular dynamics Ó Elsevier Science B V All rights reserved Keywords Bulk synchronous parallel Parallel communications library One-sided communication ParallelComputing Correspondingauthor E-mail jonathan hill comlab ox ac uk - seefrontmatterÓ ElsevierScienceB V Allrightsreserved PII S - - Introduction Sincetheearliestdaysofcomputingithasbeenclearthat soonerorlater se- quentialcomputingwouldbesupersededbyparallelcomputing Thishasnotyet happened despitetheavailabilityofnumerousparallelmachinesandtheinsatiable demandforincreasedcomputingpower Forparallelcomputingtobecomethe normalformofcomputingwerequireamodelwhichcanplayasimilarroletothe onethatthevonNeumannmodelhasplayedinsequentialcomputing Theemer- genceofsuchamodelwouldstimulatethedevelopmentofanewparallelsoftware industry andprovideaclearfocusforfuturehardwaredevelopments Foramodel tosucceedinthisroleitmusto ?erthreefundamentalproperties Scalability theperformanceofsoftwareandhardwaremustbescalablefroma singleprocessortoseveralhundredsofprocessors Portability softwaremustbeabletorununchanged withhighperformance on anygeneralpurposeparallelarchitecture Predictability theperformanceofsoftwareondi ?erentarchitecturesmustbe predictableinastraightforwardway Itshouldalso ideally permitthecorrectnessofparallelprogramstobede- terminedinawaywhichisnotmuchmoredi ?cultthanforsequentialpro- grams RecentresearchonBulkSynchronousParallel BSP algorithms architectures andlanguageshasshownthattheBSPmodelcanachievealloftheserequirements TheBSPmodeldecouplesthetwofundamentalaspectsofparallelcomputation communicationandsynchronisation Thisdecouplingisthekeytoachievinguni- versalapplicabilityacrossthewholerangeofparallelarchitectures ABSPcompu- tationconsistsofasequenceofparallelsupersteps Eachsuperstepissubdividedinto threeorderedphasesconsistingof simultaneouslocalcomputationineach process usingonlyvaluesstoredinthememoryofitsprocessor communication actionsamongsttheprocesses causingtransfersofdatabetweenprocessors and abarriersynchronisation whichwaitsforallofthecommunicationactionsto complete andwhichthenmakesanydatatransferredvisibleinthelocalmemoriesof thedestinationprocesses Thisapproachtoparallelprogrammingisapplicabletoallkindsofparallel architecture distributedmemoryarchitectures sharedmemorymultiprocessors andnetworksofworkstations Itprovidesaconsistent andverygeneral frame- workwithinwhichtodevelopportableparallelsoftwareforscalableparallelar- chitectures Inthiswork wedescribeBSPlib asmallcommunicationslibraryforBSPpro- gramminginaSingleProgramMultipleData SPMD manner Themainfeaturesof BSPlibaretwomodesofcommunication onecapturingaone-sideddirectremote memoryaccess DRMA paradigmandtheotherre ectingabulksynchronous messagepassing BSMP approach BSPlibisnottheonlycommunicationlibraryforparallelcomputing One prominentalternativeistheMessagePassingInterface MPI J M D Hilletal ParallelComputing MPIandBSPlibaresimilarinthattheyarebothdesignedforthedevelopmentof scalableandportableparallelcode Thefundamentaldi ?erencebetweenthetwois thatBSPlibisbasedonthesuperstepprogrammingdiscipline whileMPIisnot AssociatedwithBSPlib'sprogrammingdisciplineisasimplecostmodelforthe transmissionofbulkedmessages Incontrast MPIhasnoexposedcostmodel andif onewereexposeditwouldnecessarilybebaseduponsinglemessagesratherthan supersteps OneconsequenceoftheBSPlibphilosophyisthatBSPlibisconciseandconsis- tent makingiteasytoimplemente ?ciently MPI'sgreater exibilityleadstoahuge librarywithcompetingfunctionalities makinge ?cientimplementationfarmore problematic Thespeci csofBSPlibwerein uencedbyexperiencewiththeOxfordBSPlibrary theCraySHMEMlibrary thesplit-phaseassignmentsinSplit-C and theGreenBSPlibrary Thispaperpresentsthefullde nitionoftheCinterfacetoBSPlibinSections theFortraninterfaceisdescribedinRef Aquickreferencetableofallthe primitivescanbefoundonpage Section presentsabriefdescriptionandresults ofapplicationsinbenchmarking FastFourierTransforms sorting andmolecular dynamics ThepaperisconcludedinSection whichdiscussespossiblefutureex- tensions SPMDframework Likemanyothercommunicationslibraries BSPlibadoptsanSPMDpro- grammingmodel ThetaskofwritinganSPMDprogramwilltypicallyinvolve mappingaproblemthatmanipulatesadatastructureofsizenintopinstancesof aprogramthateachmanipulateann psizedblockoftheoriginaldomain The roleofBSPlibistoprovidetheinfrastructurerequiredfortheusertotakecareof thedatadistribution andanyimpliedcommunicationnecessarytomanipulate partsofthedatastructurethatareonaremoteprocess Analternativerolefor BSPlibistoprovideanarchitectureindependenttargetforhigher-levellibrariesor programmingtoolsthatautomaticallydistributetheproblemdomainamongthe processes Startingand nishingSPMDcode ProcessesarecreatedinaBSPlibprogrambytheoperationsbsp beginand bsp end TheybracketapieceofcodetoberuninanSPMDmanneronanumber ofprocessors Therecanonlybeoneinstanceofabsp begin bsp endwithina program Ifbsp beginandbsp endarethe rstandlaststatementsinapro- gram thentheentireBSPlibcomputationisSPMD Analternativemodeisavailable whereasingleprocessstartsexecutionanddeterminesthenumberofparallelpro- cessesrequiredforthecalculation SeeSection fordetails J M D Hilletal ParallelComputing Syntaxandparameters voidbsp begin intmaxprocs voidbsp end void maxprocsisthenumberofprocessesrequestedbytheuser Example AtrivialBSPlibprogramisshownbelow Theprogramstartsasmanyparallel processesasthereareavailable eachofwhichprintsthestring HelloBSP Worldwide'' TheexampleillustratestheminimumrequirementsofBSPlibwith respecttoI O Whenanumberofprocessesprintamessageoneitherstandard outputorstandarderror themessagesaremultiplexedtotheuser'sterminalina non-deterministicmanner Therefore thisexampleprintsthestringsinanarbitrary order AllothertypesofI O e g userinputand leaccess areonlyguaranteedto workcorrectlyifperformedbyprocesszero voidmain void bsp begin bsp nprocs printf HelloBSPWorldwidefromprocess dof d '' bsp pid bsp nprocs bsp end Notes AnimplementationofBSPlibmayspawnlessthanmaxprocsprocesses Theac- tualnumberofprocessesstartedcanbefoundbytheenquiryfunction bsp nprocs Therecanonlybeasinglebsp begin bsp endpairwithinaBSPlibprogram Thisexcludesthepossibilityofstarting stopping andthenrestartingparallel taskswithinaprogram oranyformofnestedparallelism Theprocesswithbsp pid ? isacontinuationofthethreadofcontrolthat initiatedbsp