Compositional parallel programming languages

CompositionalParallelProgrammingLanguagesIANFOSTERArgonneNationalLaboratoryAuthor’saddress:I.Foster,MathematicsandComputerScienceDivision,ArgonneNationalLaboratory,Argonne,IL60439.Permissiontomakedigital/hardcopyofallorpartofthismaterialwithoutfeeisgrantedprovidedthatthecopiesarenotmadeordistributedforprotorcommercialadvantage,theACMcopyright/servernotice,thetitleofthepublication,anditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheAssociationforComputingMachinery,Inc.(ACM).Tocopyotherwise,torepublish,topostonservers,ortoredistributetolistsrequirespriorspecicpermissionand/orafee.c1999ACM0164-0925/99/0100-0111$00.75ACMTransactionsonProgrammingLanguagesandSystems,Vol.8,No.1,January1999,Pages111{134.112IanFosterIntask-parallelprograms,diverseactivitiescantakeplaceconcurrently,andcommunicationandsynchronizationpatternsarecomplexandnoteasilypredictable.Previousworkhasidentiedcompositionalityasanimportantdesignprinciplefortask-parallelprograms.Inthispaper,wediscussalternativeapproachestotherealizationofthisprinciple,whichholdsthatpropertiesofprogramcomponentsshouldbepreservedwhenthosecomponentsarecomposedinparallelwithotherprogramcomponents.Wereviewtwoprogramminglanguages,StrandandProgramCompositionNotation,thatsupportcompositionalityviaasmallnumberofsimpleconcepts,namelymonotoneoperationsonsharedobjects,auniformaddressingmechanism,andparallelcomposition.Bothlanguageshavebeenusedextensivelyforlarge-scaleapplicationdevelopment,allowingustoprovideaninformedassessmentoftheirstrengthsandweaknesses.Weobservethatwhilecompositionalitysimpliesdevelopmentofcomplexapplications,theuseofspecializedlanguageshindersreuseofexistingcodeandtools,andthespecicationofdomaindecompositionstrategies.Thissuggestsanalternativeapproachbasedonsmallextensionstoexistingsequentiallanguages.Weconcludethepaperwithadiscussionoftwolanguagesthatrealizethisstrategy.CategoriesandSubjectDescriptors:D.3.2[ProgrammingLanguages]:LanguageClassica-tions|Concurrent,distributed,andparallellanguages;D.3.3[ProgrammingLanguages]:Lan-guageConstructsandFeatures|ConcurrentprogrammingstructuresGeneralTerms:LanguagesAdditionalKeyWordsandPhrases:Compositionality,ParallelLanguages,ParallelProgrammingACMTransactionsonProgrammingLanguagesandSystems,Vol.8,No.1,January1999.CompositionalParallelProgrammingLanguages1131.INTRODUCTIONParallelprogrammingiswidelyregardedasdicult:moredicultthansequentialprogramming,andperhaps(atleastthisisourview)moredicultthanitneedstobe.Inadditiontothenormalprogrammingconcerns,theparallelprogrammerhastodealwiththeaddedcomplexitybroughtaboutbymultiplethreadsofcontrol:managingtheircreationanddestruction,andorchestratingtheirinteractionsviasynchronizationandcommunication.Parallelprogramsmustalsomanagearichersetofresourcesthansequentialprograms,controlling,forexample,themappingandschedulingofcomputationontomultipleprocessors.Asinsequentialprogramming,complexityinprogramdevelopmentcanbeman-agedbyprovidingappropriateprogramminglanguageconstructs.Languagecon-structscanhelpbothbysupportingencapsulation,soastopreventunwantedin-teractionsbetweenprogramcomponents,andbyprovidinghigher-levelabstrac-tionsthatleverageprogrammereortbyallowingcompilerstohandlemundane,error-proneaspectsofparallelprogramimplementation.Forexample,thevariouslanguagesthathavebeendevelopedtosupportdata-parallelprogrammingachieveboththesegoals,albeitforarestrictedclassofprograms[Chapmanetal.1992;Foxetal.1990;Koelbeletal.1994].Data-parallelprogramsexploittheparallelisminherentinapplyingthesameoperationtoallormostelementsoflargedatastruc-ACMTransactionsonProgrammingLanguagesandSystems,Vol.8,No.1,January1999.114IanFostertures.Data-parallellanguagesavoidunwantedinteractionsbyenforcingsequentialsemantics.Theyusedatadistributionstatementstoprovideahigh-level,abstractsyntaxforspecifyingdataplacement,freeingtheprogrammerfromthelaborofpartitioningcomputationandtranslatingbetweenglobalandlocaladdresses.Ourresearchgoalistodeveloplanguageconstructsandassociatedtoolstosup-portthemoregeneralclassoftask-parallelapplications,inwhichmultipleunrelatedactivitiescantakeplaceconcurrently.Taskparallelismarisesintime-dependentproblemssuchasdiscrete-eventsimulation,inirregularproblemssuchasthoseinvolvingsparsematrices,andinmultidisciplinarysimulationscouplingmultiple,possiblydata-parallel,computations.Thechallengewhendevelopinglanguagecon-structsfortask-parallelprogrammingistoprovidethemodularityandabstractionneededforeaseofprogrammingwhilemaintainingthegeneralityneededtosupportarbitraryparallelcomputations.Compositionalityhasbeenproposedasadesignprinciplefortask-parallelpro-grams[ChandyandTaylor1991].Acompositionalprogrammingsystemisoneinwhichpropertiesofprogramcomponentsarepreservedwhenthosecomponentsarecomposedinparallelwithotherprogramcomponents.Thatis,thebehaviorofthewholeisalogicalcombinationofthebehavioroftheparts.Onepropertythatweoftenwanttobepreservedinthiswayisdeterminism,sothatprogramsconstructedACMTransactionsonProgrammingLanguagesandSystems,Vol.8,No.1,January1999.Compos