Parallel Logic Programming Systems

ParallelLogicProgrammingSystemsJACQUESCHASSINDEKERGOMMEAUXIMAG/LGI,46al~enueFtilmVlallct,F-38031GrenobleCedex7,FrancePHILIPPECODOGNETINRIA,DomawzedeVoluceuu,Rocquencourt,F-78153LeGhesna.vCedexParallelizinglogicprogramminghasattractedmuchinterestintheresearchcommunity,becauseoftheintrinsicOR-andAND-parallelismsoflogicprograms.OneresearchstreamaimsattransparentexploitationofparallelisminexistinglogicprogramminglanguagessuchasProlog,whalethefamilyofconcurrentlogiclanguagesdevelopslanguageconstructsallowingprogrammerstoexpresstheconcurrency—thatis,thecommunicationandsynchronizationbetweenparallelprocesses—withintheiralgorithms.Thisarticleconcentratesmainlyontransparentexploitationofparallelismandsurveysthemostmaturesolutionstotheproblemstobesolvedinordertoobtainefficientimplementations.Thesesolutionshavebeenimplemented,andthemostefficientparallellogicprogrammingsystemsreacheffectivespeedupsoverstate-of-the-artsequentialPrologimplementations.Thearticlealsoaddressescurrentandprospectiveresearchissuesinextendingtheapplicabilityandtheefficiencyofexistingsystems,suchasmodelsmergingthetransparentparallehsmandtheconcurrentlogiclanguagesapproaches,combinationofconstraintlogicprogrammingwithparallelism,anduseofhighlyparallelarchitectures.CategoriesandSubjectDescriptors:B.3.2[MemoryStructures]:DesignStyles—sharedmemory,C.1.2[ProcessorArchitectures]:MultipleDataStreamArchitectures;D.1.3[ProgrammingTechniques]:ConcurrentProgramming-paraltelprogrammmg;D.1.6[ProgrammingTechniques]:LogicProgramming:D.3.2[ProgrammingLanguages]:LanguageClassifications-concurrent,distributed,andparallellanguages;D.3,4[ProgrammingLanguages]:Processors—compzlers;interpreters;preprocessors;F.4.1[MathematicalLogicandFormalLanguages]:MathematicalLo~c—logzcprogrammingGeneralTerms:LanguagesAdditionalKeyWordsandPhrases:AND-parallelism,bmdmgarrays,concurrentconstraintprogramming,constraints,guard,hashwindows,loadbalancing,massiveparallelism,memorymanagement,multisequentialimplementationtechniques,nondeterminism,OR-parallelism,Prolog,schedulingparalleltasks,staticanalysis,WarrenAbstractMachine1.INTRODUCTIONsentthemostpromisingwaytoincreasethecomputingpowerofcomputersintheLogicprogramscanbecomputedsequen-future.Sincemultiprocessorsremaindif-tiallyorinparallelwithoutchangingficulttouseefficiently,animplicitlypar-theirdeclarativesemantics.Forthisrea-allelprogramminglanguageoffersaveryson,theyareoftenconsideredwellsuitedattractivemeanofexercisingtheparal-toprogrammingmultiprocessors.Atthelelismofmultiprocessorsoftodayandsametime,parallelarchitecturesrepre-tomorrow.Permissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeordistributedfordirectcommercialadvantage,theACMcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheAssociationforComputingMachinery.Tocopyotherwise,ortorepublish,requiresafeeand/orspecificpermission.01994ACM0360-0300/94/0600-0295$01.50ACMComputingSurveys,Vol.26,No,3,September1994296-J.ChassindeKergommeauxandP.CodognetCONTENTS1.2,3.4567?)INTRODUCTIONPARALLELISMSINLOGICPROGRAMMING2.1LogicPrograms‘22SourcesofParallehsmmLogicPrograms23OR-ParallehsmmProlog2.4AND-ParallehsmmPrologLANGUAGEISSUES3.1Parallehz]ngProlog3.2Delays,Synchronlzatlon,andConcurrency3.3ConcurrentLogicLanguages34UmfymgPrologandConcurrentLanguagesIMPLEMENTATIONISSUES41FromEarlyModelstoMultisequentialSystems42EfficientSequentialImplementationTechniques43OR-Parallelism4.4AND-Parallehsm45ScheduhngofParallelTasksSYSTEMSEXPLOITINGONETYPEOFPARALLELISM51SystemsExploitingOR-Parallehsm~2ASystemExploitingIndependentAND-Parallehsm:&-Prolog53SystemsExploitingDependentAND-Parallelism54PerformanceofSystemsExploitingOneTypeofParallelismSYSTEMSCOMBININGSEVERALTYPESOFPARALLELISM61SystemsCombmingIndependentAND-WithOR-Parallelism62SystemsCombmmgDependentAND-WithOR-ParallelismC~TRRENTRESEARCHANDPERSPECTIVES71StatwAnalysisofLogicPrograms72ParallelismandConstraintLogicProgramming73ConcurrentConstraintLanguages74UseofMassivelyParallelMultiprocessorsCONCLUSIONACKNOWLEDGMENTSREFERENCESLogicprogramminglanguagesareveryhigh-levellanguagesenablingprogramstobedevelopedmorerapidlyandcon-ciselythanwithimperativelanguages.However,inspiteofimportantprogressincompilationtechniquesfortheselan-guages,theyremainlessefficientthanimperativelanguages,andtheiruseismainlyconstrainedtoprototyping.In-creasingtheefficiencyoflogicprogram-mingtothelevelofimperativelanguageswouldcertainlyenlargetheirdomainofuseandraisetheproductivityofproduc-tionprogrammers.ThesereasonspersuadedtheICOTtochooselogicprogrammingasthebasicprogramminglanguageoftheFifthGen-erationComputerSystemsproject(FGCS)[Furukawa1992;ShapiroandWarren1993].Oneaimofthisprojectwastoproducemultiprocessorsdeliver-ingmorethanonegigs-lips,one“lip”beingonelogicalinferencepersecond,andoneinferencebeingsimilartoapro-cedurecallofanimperativelanguage.Thegigs-lipslevelofperformanceseemedoutofscopewhentheFGCSprojectstartedin1982,sincethemostefficientPrologsystemsofthatperiodwerelim-itedtosever