Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor
Identifieur interne : 000051 ( Istex/Corpus ); précédent : 000050; suivant : 000052Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor
Auteurs : J. Briat ; M. Favre ; C. Geyer ; J. Chassin De KergommeauxSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1991.
Abstract
Abstract: The OPERA project aims at efficiently implementing Prolog on a scalable, reconfigurable distributed-memory architecture. The OPERA computational model exploits OR-parallelism following a classical multisequential approach: each processor executes a complete Prolog engine based on the WAM; inter-processor communication is reduced to work installation, the complete state of an active Prolog engine being copied to an idle one. Scheduling is performed by a hierarchy of specialized processors, operating in parallel of the computation of the Prolog program. To avoid costly synchronization, schedulers use an approximate representation of the state of the system. Because of the important overhead of task installation in a distributed-memory system, only workers having a large amount of work to execute can give work to idle workers. Several dynamic work regulation strategies have been designed and are currently being tested. The prototype implementation of OPERA on a transputer-based Supernode is one of the most efficient existing Prolog implementations on the transputer and reaches effective speed-ups in parallel over efficient sequential Prolog systems.
Url:
DOI: 10.1007/3-540-54152-7_76
Links to Exploration step
ISTEX:21A37369D25D3F96C68D9EF3B8122264041C5ED6Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title><author><name sortKey="Briat, J" sort="Briat, J" uniqKey="Briat J" first="J." last="Briat">J. Briat</name><affiliation><mods:affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: briat@imag.fr</mods:affiliation></affiliation></author><author><name sortKey="Favre, M" sort="Favre, M" uniqKey="Favre M" first="M." last="Favre">M. Favre</name><affiliation><mods:affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: favre@imag.fr</mods:affiliation></affiliation></author><author><name sortKey="Geyer, C" sort="Geyer, C" uniqKey="Geyer C" first="C." last="Geyer">C. Geyer</name><affiliation><mods:affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</mods:affiliation></affiliation><affiliation><mods:affiliation>CPGCC-USRGS, University of Porto Alegre, caixa postal 1501, 90000, Porto Alegre RS, Brasil</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: geyer@SBU.USRGGS.ANRS.BR</mods:affiliation></affiliation></author><author><name sortKey="Chassin De Kergommeaux, J" sort="Chassin De Kergommeaux, J" uniqKey="Chassin De Kergommeaux J" first="J." last="Chassin De Kergommeaux">J. Chassin De Kergommeaux</name><affiliation><mods:affiliation>CAP-Gemini-Innovation, 7, chemin du Vieux Chêene, ZIRST, F-38240, Meylan</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: chassin@capsogeti.fr</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:21A37369D25D3F96C68D9EF3B8122264041C5ED6</idno><date when="1991" year="1991">1991</date><idno type="doi">10.1007/3-540-54152-7_76</idno><idno type="url">https://api.istex.fr/document/21A37369D25D3F96C68D9EF3B8122264041C5ED6/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000051</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title><author><name sortKey="Briat, J" sort="Briat, J" uniqKey="Briat J" first="J." last="Briat">J. Briat</name><affiliation><mods:affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: briat@imag.fr</mods:affiliation></affiliation></author><author><name sortKey="Favre, M" sort="Favre, M" uniqKey="Favre M" first="M." last="Favre">M. Favre</name><affiliation><mods:affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: favre@imag.fr</mods:affiliation></affiliation></author><author><name sortKey="Geyer, C" sort="Geyer, C" uniqKey="Geyer C" first="C." last="Geyer">C. Geyer</name><affiliation><mods:affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</mods:affiliation></affiliation><affiliation><mods:affiliation>CPGCC-USRGS, University of Porto Alegre, caixa postal 1501, 90000, Porto Alegre RS, Brasil</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: geyer@SBU.USRGGS.ANRS.BR</mods:affiliation></affiliation></author><author><name sortKey="Chassin De Kergommeaux, J" sort="Chassin De Kergommeaux, J" uniqKey="Chassin De Kergommeaux J" first="J." last="Chassin De Kergommeaux">J. Chassin De Kergommeaux</name><affiliation><mods:affiliation>CAP-Gemini-Innovation, 7, chemin du Vieux Chêene, ZIRST, F-38240, Meylan</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: chassin@capsogeti.fr</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1991</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">21A37369D25D3F96C68D9EF3B8122264041C5ED6</idno><idno type="DOI">10.1007/3-540-54152-7_76</idno><idno type="ChapterID">Chap22</idno><idno type="ChapterID">22</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The OPERA project aims at efficiently implementing Prolog on a scalable, reconfigurable distributed-memory architecture. The OPERA computational model exploits OR-parallelism following a classical multisequential approach: each processor executes a complete Prolog engine based on the WAM; inter-processor communication is reduced to work installation, the complete state of an active Prolog engine being copied to an idle one. Scheduling is performed by a hierarchy of specialized processors, operating in parallel of the computation of the Prolog program. To avoid costly synchronization, schedulers use an approximate representation of the state of the system. Because of the important overhead of task installation in a distributed-memory system, only workers having a large amount of work to execute can give work to idle workers. Several dynamic work regulation strategies have been designed and are currently being tested. The prototype implementation of OPERA on a transputer-based Supernode is one of the most efficient existing Prolog implementations on the transputer and reaches effective speed-ups in parallel over efficient sequential Prolog systems.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>J. Briat</name><affiliations><json:string>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</json:string><json:string>E-mail: briat@imag.fr</json:string></affiliations></json:item><json:item><name>M. Favre</name><affiliations><json:string>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</json:string><json:string>E-mail: favre@imag.fr</json:string></affiliations></json:item><json:item><name>C. Geyer</name><affiliations><json:string>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</json:string><json:string>CPGCC-USRGS, University of Porto Alegre, caixa postal 1501, 90000, Porto Alegre RS, Brasil</json:string><json:string>E-mail: geyer@SBU.USRGGS.ANRS.BR</json:string></affiliations></json:item><json:item><name>J. Chassin de Kergommeaux</name><affiliations><json:string>CAP-Gemini-Innovation, 7, chemin du Vieux Chêene, ZIRST, F-38240, Meylan</json:string><json:string>E-mail: chassin@capsogeti.fr</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><abstract>Abstract: The OPERA project aims at efficiently implementing Prolog on a scalable, reconfigurable distributed-memory architecture. The OPERA computational model exploits OR-parallelism following a classical multisequential approach: each processor executes a complete Prolog engine based on the WAM; inter-processor communication is reduced to work installation, the complete state of an active Prolog engine being copied to an idle one. Scheduling is performed by a hierarchy of specialized processors, operating in parallel of the computation of the Prolog program. To avoid costly synchronization, schedulers use an approximate representation of the state of the system. Because of the important overhead of task installation in a distributed-memory system, only workers having a large amount of work to execute can give work to idle workers. Several dynamic work regulation strategies have been designed and are currently being tested. The prototype implementation of OPERA on a transputer-based Supernode is one of the most efficient existing Prolog implementations on the transputer and reaches effective speed-ups in parallel over efficient sequential Prolog systems.</abstract><qualityIndicators><score>6.98</score><pdfVersion>1.3</pdfVersion><pdfPageSize>468 x 684 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1174</abstractCharCount><pdfWordCount>6064</pdfWordCount><pdfCharCount>35167</pdfCharCount><pdfPageCount>18</pdfPageCount><abstractWordCount>165</abstractWordCount></qualityIndicators><title>Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title><chapterId><json:string>Chap22</json:string><json:string>22</json:string></chapterId><genre><json:string>review-article</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><genre></genre><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1991</copyrightDate></serie><host><editor><json:item><name>Emile H. L. Aarts</name></json:item><json:item><name>Jan van Leeuwen</name></json:item><json:item><name>Martin Rem</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Processor Architectures</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Special Purpose and Application-Based Systems</value></json:item><json:item><value>System Performance and Evaluation</value></json:item><json:item><value>Programming Techniques</value></json:item><json:item><value>Operating Systems</value></json:item></subject><isbn><json:string>978-3-540-54152-3</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>PARLE '91 Parallel Architectures and Languages Europe</title><bookId><json:string>3540541527</json:string></bookId><volume>506</volume><pages><last>402</last><first>385</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>Book Series</json:string></genre><eisbn><json:string>978-3-540-47472-2</json:string></eisbn><copyrightDate>1991</copyrightDate><doi><json:string>10.1007/3-540-54152-7</json:string></doi></host><publicationDate>1991</publicationDate><copyrightDate>1991</copyrightDate><doi><json:string>10.1007/3-540-54152-7_76</json:string></doi><id>21A37369D25D3F96C68D9EF3B8122264041C5ED6</id><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/21A37369D25D3F96C68D9EF3B8122264041C5ED6/fulltext/pdf</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/21A37369D25D3F96C68D9EF3B8122264041C5ED6/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/21A37369D25D3F96C68D9EF3B8122264041C5ED6/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title><respStmt xml:id="ISTEX-API" resp="Références bibliographiques récupérées via GROBID" name="ISTEX-API (INIST-CNRS)"></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>SPRINGER</p></availability><date>1991</date></publicationStmt><notesStmt><note>This work has been partially sponsored by the Centre National d'Etude des Télécommunications (CNET) and ESPRIT project P1085.</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title><author><persName><forename type="first">J.</forename><surname>Briat</surname></persName><email>briat@imag.fr</email><affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</affiliation></author><author><persName><forename type="first">M.</forename><surname>Favre</surname></persName><email>favre@imag.fr</email><affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</affiliation></author><author><persName><forename type="first">C.</forename><surname>Geyer</surname></persName><email>geyer@SBU.USRGGS.ANRS.BR</email><affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</affiliation><affiliation>CPGCC-USRGS, University of Porto Alegre, caixa postal 1501, 90000, Porto Alegre RS, Brasil</affiliation></author><author><persName><forename type="first">J.</forename><surname>Chassin de Kergommeaux</surname></persName><email>chassin@capsogeti.fr</email><affiliation>CAP-Gemini-Innovation, 7, chemin du Vieux Chêene, ZIRST, F-38240, Meylan</affiliation></author></analytic><monogr><title level="m">PARLE '91 Parallel Architectures and Languages Europe</title><title level="m" type="sub">Volume II: Parallel Languages Eindhoven, The Netherlands, June 10–13, 1991 Proceedings</title><idno type="pISBN">978-3-540-54152-3</idno><idno type="eISBN">978-3-540-47472-2</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/3-540-54152-7</idno><idno type="BookID">3540541527</idno><idno type="BookTitleID">27799</idno><idno type="BookVolumeNumber">506</idno><idno type="BookChapterCount">27</idno><editor><persName><forename type="first">Emile</forename><forename type="first">H.</forename><forename type="first">L.</forename><surname>Aarts</surname></persName></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><editor><persName><forename type="first">Martin</forename><surname>Rem</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="1991"></date><biblScope unit="volume">506</biblScope><biblScope unit="page" from="385">385</biblScope><biblScope unit="page" to="402">402</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><biblScope><date>1991</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesId">558</idno></series><idno type="istex">21A37369D25D3F96C68D9EF3B8122264041C5ED6</idno><idno type="DOI">10.1007/3-540-54152-7_76</idno><idno type="ChapterID">Chap22</idno><idno type="ChapterID">22</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1991</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: The OPERA project aims at efficiently implementing Prolog on a scalable, reconfigurable distributed-memory architecture. The OPERA computational model exploits OR-parallelism following a classical multisequential approach: each processor executes a complete Prolog engine based on the WAM; inter-processor communication is reduced to work installation, the complete state of an active Prolog engine being copied to an idle one. Scheduling is performed by a hierarchy of specialized processors, operating in parallel of the computation of the Prolog program. To avoid costly synchronization, schedulers use an approximate representation of the state of the system. Because of the important overhead of task installation in a distributed-memory system, only workers having a large amount of work to execute can give work to idle workers. Several dynamic work regulation strategies have been designed and are currently being tested. The prototype implementation of OPERA on a transputer-based Supernode is one of the most efficient existing Prolog implementations on the transputer and reaches effective speed-ups in parallel over efficient sequential Prolog systems.</p></abstract><textClass><keywords scheme="Book Subject Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book Subject Group"><list><label>I</label><label>I13014</label><label>I13022</label><label>I13030</label><label>I13049</label><label>I14010</label><label>I14045</label><item><term>Computer Science</term></item><item><term>Processor Architectures</term></item><item><term>Computer Communication Networks</term></item><item><term>Special Purpose and Application-Based Systems</term></item><item><term>System Performance and Evaluation</term></item><item><term>Programming Techniques</term></item><item><term>Operating Systems</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1991">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-3-1">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><original>false</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/21A37369D25D3F96C68D9EF3B8122264041C5ED6/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540541527</BookID><BookTitle>PARLE '91 Parallel Architectures and Languages Europe</BookTitle><BookSubTitle>Volume II: Parallel Languages Eindhoven, The Netherlands, June 10–13, 1991 Proceedings</BookSubTitle><BookVolumeNumber>506</BookVolumeNumber><BookDOI>10.1007/3-540-54152-7</BookDOI><BookTitleID>27799</BookTitleID><BookPrintISBN>978-3-540-54152-3</BookPrintISBN><BookElectronicISBN>978-3-540-47472-2</BookElectronicISBN><BookChapterCount>27</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1991</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I13014" Priority="1" Type="Secondary">Processor Architectures</BookSubject><BookSubject Code="I13022" Priority="2" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I13030" Priority="3" Type="Secondary">Special Purpose and Application-Based Systems</BookSubject><BookSubject Code="I13049" Priority="4" Type="Secondary">System Performance and Evaluation</BookSubject><BookSubject Code="I14010" Priority="5" Type="Secondary">Programming Techniques</BookSubject><BookSubject Code="I14045" Priority="6" Type="Secondary">Operating Systems</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Emile</GivenName><GivenName>H.</GivenName><GivenName>L.</GivenName><FamilyName>Aarts</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Martin</GivenName><FamilyName>Rem</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap22" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>22</ChapterID><ChapterDOI>10.1007/3-540-54152-7_76</ChapterDOI><ChapterSequenceNumber>22</ChapterSequenceNumber><ChapterTitle Language="En">Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</ChapterTitle><ChapterCategory>Submitted Presentations</ChapterCategory><ChapterFirstPage>385</ChapterFirstPage><ChapterLastPage>402</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1991</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>8</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540541527</BookID><BookTitle>PARLE '91 Parallel Architectures and Languages Europe</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Briat</FamilyName></AuthorName><Contact><Email>briat@imag.fr</Email></Contact></Author><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>M.</GivenName><FamilyName>Favre</FamilyName></AuthorName><Contact><Email>favre@imag.fr</Email></Contact></Author><Author AffiliationIDS="Aff1 Aff3"><AuthorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Geyer</FamilyName></AuthorName><Contact><Email>geyer@SBU.USRGGS.ANRS.BR</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Chassin de Kergommeaux</FamilyName></AuthorName><Contact><Email>chassin@capsogeti.fr</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>Projet CMaP, LGI</OrgName><OrgAddress><Postbox>BP 53 X</Postbox><Postcode>38041</Postcode><City>Grenoble Cedex</City></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>CAP-Gemini-Innovation</OrgName><OrgAddress><Street>7, chemin du Vieux Chêene, ZIRST</Street><Postcode>F-38240</Postcode><City>Meylan</City></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgDivision>CPGCC-USRGS</OrgDivision><OrgName>University of Porto Alegre</OrgName><OrgAddress><Postbox>caixa postal 1501</Postbox><Postcode>90000</Postcode><City>Porto Alegre RS</City><Country>Brasil</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>The OPERA project aims at efficiently implementing Prolog on a scalable, reconfigurable distributed-memory architecture. The OPERA computational model exploits OR-parallelism following a classical multisequential approach: each processor executes a complete Prolog engine based on the WAM; inter-processor communication is reduced to work installation, the complete state of an active Prolog engine being copied to an idle one. Scheduling is performed by a hierarchy of specialized processors, operating in parallel of the computation of the Prolog program. To avoid costly synchronization, schedulers use an approximate representation of the state of the system. Because of the important overhead of task installation in a distributed-memory system, only workers having a large amount of work to execute can give work to idle workers. Several dynamic work regulation strategies have been designed and are currently being tested. The prototype implementation of OPERA on a transputer-based Supernode is one of the most efficient existing Prolog implementations on the transputer and reaches effective speed-ups in parallel over efficient sequential Prolog systems.</Para></Abstract><KeywordGroup Language="En"><Heading>Keywords</Heading><Keyword>OPERA</Keyword><Keyword>OR-parallel Prolog</Keyword><Keyword>WAM</Keyword><Keyword>distributed-memory</Keyword><Keyword>Supernode</Keyword><Keyword>scalable multiprocessor</Keyword><Keyword>reconfigurable multiprocessor</Keyword></KeywordGroup><ArticleNote Type="Misc"><SimplePara>This work has been partially sponsored by the Centre National d'Etude des Télécommunications (CNET) and ESPRIT project P1085.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor</title></titleInfo><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Briat</namePart><affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</affiliation><affiliation>E-mail: briat@imag.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">M.</namePart><namePart type="family">Favre</namePart><affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</affiliation><affiliation>E-mail: favre@imag.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Geyer</namePart><affiliation>Projet CMaP, LGI, BP 53 X, 38041, Grenoble Cedex</affiliation><affiliation>CPGCC-USRGS, University of Porto Alegre, caixa postal 1501, 90000, Porto Alegre RS, Brasil</affiliation><affiliation>E-mail: geyer@SBU.USRGGS.ANRS.BR</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Chassin de Kergommeaux</namePart><affiliation>CAP-Gemini-Innovation, 7, chemin du Vieux Chêene, ZIRST, F-38240, Meylan</affiliation><affiliation>E-mail: chassin@capsogeti.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="review-article" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">1991</dateIssued><copyrightDate encoding="w3cdtf">1991</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: The OPERA project aims at efficiently implementing Prolog on a scalable, reconfigurable distributed-memory architecture. The OPERA computational model exploits OR-parallelism following a classical multisequential approach: each processor executes a complete Prolog engine based on the WAM; inter-processor communication is reduced to work installation, the complete state of an active Prolog engine being copied to an idle one. Scheduling is performed by a hierarchy of specialized processors, operating in parallel of the computation of the Prolog program. To avoid costly synchronization, schedulers use an approximate representation of the state of the system. Because of the important overhead of task installation in a distributed-memory system, only workers having a large amount of work to execute can give work to idle workers. Several dynamic work regulation strategies have been designed and are currently being tested. The prototype implementation of OPERA on a transputer-based Supernode is one of the most efficient existing Prolog implementations on the transputer and reaches effective speed-ups in parallel over efficient sequential Prolog systems.</abstract><note>This work has been partially sponsored by the Centre National d'Etude des Télécommunications (CNET) and ESPRIT project P1085.</note><relatedItem type="host"><titleInfo><title>PARLE '91 Parallel Architectures and Languages Europe</title><subTitle>Volume II: Parallel Languages Eindhoven, The Netherlands, June 10–13, 1991 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Emile</namePart><namePart type="given">H.</namePart><namePart type="given">L.</namePart><namePart type="family">Aarts</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Martin</namePart><namePart type="family">Rem</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="Book Series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1991</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book Subject Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book Subject Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I13014">Processor Architectures</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I13030">Special Purpose and Application-Based Systems</topic><topic authority="SpringerSubjectCodes" authorityURI="I13049">System Performance and Evaluation</topic><topic authority="SpringerSubjectCodes" authorityURI="I14010">Programming Techniques</topic><topic authority="SpringerSubjectCodes" authorityURI="I14045">Operating Systems</topic></subject><identifier type="DOI">10.1007/3-540-54152-7</identifier><identifier type="ISBN">978-3-540-54152-3</identifier><identifier type="eISBN">978-3-540-47472-2</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">27799</identifier><identifier type="BookID">3540541527</identifier><identifier type="BookChapterCount">27</identifier><identifier type="BookVolumeNumber">506</identifier><part><date>1991</date><detail type="volume"><number>506</number><caption>vol.</caption></detail><extent unit="pages"><start>385</start><end>402</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1991</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1991</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1991</recordOrigin></recordInfo></relatedItem><identifier type="istex">21A37369D25D3F96C68D9EF3B8122264041C5ED6</identifier><identifier type="DOI">10.1007/3-540-54152-7_76</identifier><identifier type="ChapterID">Chap22</identifier><identifier type="ChapterID">22</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1991</recordOrigin></recordInfo></mods></metadata><enrichments><istex:refBibTEI uri="https://api.istex.fr/document/21A37369D25D3F96C68D9EF3B8122264041C5ED6/enrichments/refBib"><teiHeader></teiHeader><text><front></front><body></body><back><listBibl><biblStruct xml:id="b0"><analytic><title level="a" type="main">The Muse or-parallel prolog model and its performance</title><author><persName><forename type="first">K</forename><forename type="middle">A M</forename><surname>Ali</surname></persName></author><author><persName><forename type="first">R</forename><surname>Karlsson</surname></persName></author></analytic><monogr><title level="m">Proceedings of the NACLP'90</title><meeting>the NACLP'90<address><addrLine>Austin</addrLine></address></meeting><imprint><date type="published" when="1990"></date></imprint></monogr></biblStruct><biblStruct xml:id="b1"><analytic><title level="a" type="main">Logic and functional programming on distributed memory architectures</title><author><persName><forename type="first">P</forename><forename type="middle">G</forename><surname>Bosco</surname></persName></author><author><persName><forename type="first">C</forename><surname>Cecchi</surname></persName></author><author><persName><forename type="first">C</forename><surname>Moiso</surname></persName></author><author><persName><forename type="first">M</forename><surname>Porta</surname></persName></author><author><persName><forename type="first">G</forename><surname>Soft</surname></persName></author></analytic><monogr><title level="m">Proceedings of the 6 th International Conference on Logic Programming</title><meeting>the 6 th International Conference on Logic Programming<address><addrLine>Jerusalem</addrLine></address></meeting><imprint><date type="published" when="1990-06"></date><biblScope unit="page" from="325" to="339"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b2"><analytic><title level="a" type="main">The parallel ECRC prolog system PEPSys: An overview and evaluation results</title><author><persName><forename type="first">U</forename><surname>Baron</surname></persName></author><author><persName><forename type="first">J</forename><surname>Chassin De Kergommeaux</surname></persName></author><author><persName><forename type="first">M</forename><surname>Hailperin</surname></persName></author><author><persName><forename type="first">M</forename><surname>Ratcliffe</surname></persName></author><author><persName><forename type="first">P</forename><surname>Robert</surname></persName></author><author><persName><forename type="first">J</forename><forename type="middle">C</forename><surname>Syre</surname></persName></author><author><persName><forename type="first">H</forename><surname>Westphal</surname></persName></author></analytic><monogr><title level="m">Proceedings FGCS'88 International Conference on Fifth Generation COmputer Systems</title><meeting>FGCS'88 International Conference on Fifth Generation COmputer Systems<address><addrLine>Tokyo</addrLine></address></meeting><imprint><date type="published" when="1988-12"></date></imprint></monogr></biblStruct><biblStruct xml:id="b3"><analytic><title level="a" type="main">Scheduling or-parallelism: An argonne perspective</title><author><persName><forename type="first">R</forename><surname>Butler</surname></persName></author><author><persName><forename type="first">T</forename><surname>Disz</surname></persName></author><author><persName><forename type="first">E</forename><surname>Lusk</surname></persName></author><author><persName><forename type="first">R</forename><surname>Oison</surname></persName></author><author><persName><forename type="first">R</forename><surname>Overbeek</surname></persName></author><author><persName><forename type="first">R</forename><surname>Stevens</surname></persName></author></analytic><monogr><title level="m">Proceedings of the Fifth International Conference and Symposium on Logic Programming</title><editor>K. Bowen R. Kowalski</editor><meeting>the Fifth International Conference and Symposium on Logic Programming<address><addrLine>Seattle</addrLine></address></meeting><imprint><date type="published" when="1988-08"></date><biblScope unit="page" from="1590" to="1605"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b4"><analytic><title level="a" type="main">Parx: a parallel operating system for transputer-based machine</title><author><persName><forename type="first">J</forename><surname>Briat</surname></persName></author><author><persName><forename type="first">M</forename><surname>Favre</surname></persName></author><author><persName><forename type="first">D</forename><surname>Fort</surname></persName></author><author><persName><forename type="first">Y</forename><surname>Langu~</surname></persName></author><author><persName><forename type="first">M</forename><surname>Santana</surname></persName></author></analytic><monogr><title level="m">Proceedings lOth. Oceam User Group</title><meeting>lOth. Oceam User Group</meeting><imprint><date type="published" when="1989"></date></imprint></monogr></biblStruct><biblStruct xml:id="b5"><monogr><title level="m" type="main">Scheduling orparallelism in Aurora with the bristol scheduler</title><author><persName><forename type="first">Anthony</forename><surname>Beaumont</surname></persName></author><author><persName><forename type="first">Pdter</forename><surname>Muthurarnan</surname></persName></author><author><persName><surname>Szeredi</surname></persName></author><imprint><date type="published" when="1990-03"></date></imprint></monogr></biblStruct><biblStruct xml:id="b6"><monogr><title level="m" type="main">Wavefront scheduling Internal report, SICS, Gigalips project</title><author><persName><forename type="first">Per</forename><surname>Brand</surname></persName></author><imprint><date type="published" when="1988"></date></imprint></monogr></biblStruct><biblStruct xml:id="b7"><analytic><title level="a" type="main">Current status of research and development of parallel inference systems in fifth generation computer systems</title><author><persName><forename type="first">T</forename><surname>Chikayama</surname></persName></author></analytic><monogr><title level="m">Pre-conference Workshop on Parallel Logic Programming, 7 th International Conference on Logic Programming, ICLP'90</title><meeting><address><addrLine>Eilat</addrLine></address></meeting><imprint><date type="published" when="1990"></date></imprint></monogr></biblStruct><biblStruct xml:id="b8"><analytic><title level="a" type="main">A study of non blocking switching networks</title><author><persName><forename type="first">Clos</forename><surname>Charles</surname></persName></author></analytic><monogr><title level="m">Tutorial Intereonnexion Networks for parallel and Distribued Proeessslng</title><editor>Chuan- Lin Wu and Tse-Yun Fen</editor><imprint><publisher>IEEE Computer Society Press</publisher><date type="published" when="1953"></date><biblScope unit="page" from="406" to="424"></biblScope></imprint></monogr><note>republished. from The Bell System Technical Journal</note></biblStruct><biblStruct xml:id="b9"><analytic><title level="a" type="main">Scheduling or-parallelism in Aurora</title><author><persName><forename type="first">A</forename><surname>Calderwood</surname></persName></author><author><persName><forename type="first">P</forename><surname>Szeredi</surname></persName></author></analytic><monogr><title level="m">Proceedings of the 6 th International Conference on Logic Programming</title><meeting>the 6 th International Conference on Logic Programming<address><addrLine>Lisbon</addrLine></address></meeting><imprint><date type="published" when="1989-06"></date></imprint></monogr></biblStruct><biblStruct xml:id="b10"><analytic><title level="a" type="main">The development and application of a low cost high performance multiprocessor machine</title><author><persName><forename type="first">J</forename><forename type="middle">G</forename><surname>Harp</surname></persName></author><author><persName><forename type="first">C</forename><forename type="middle">R</forename><surname>Jesshope</surname></persName></author><author><persName><forename type="first">T</forename><surname>Muntean</surname></persName></author><author><persName><forename type="first">C</forename><surname>Whitby-Stevens</surname></persName></author></analytic><monogr><title level="m">Proceedings ESPRIT'86: Results and Achievements</title><meeting>ESPRIT'86: Results and Achievements</meeting><imprint><publisher>Elsevier Science Publishers</publisher><date type="published" when="1986"></date></imprint></monogr></biblStruct><biblStruct xml:id="b11"><analytic><title level="a" type="main">The Aurora or-parallel prolog system</title><author><persName><forename type="first">E</forename><surname>Lusk</surname></persName></author><author><persName><forename type="first">R</forename><surname>Butler</surname></persName></author><author><persName><forename type="first">T</forename><surname>Disz</surname></persName></author><author><persName><forename type="first">R</forename><surname>Olson</surname></persName></author><author><persName><forename type="first">R</forename><surname>Overbeek</surname></persName></author><author><persName><forename type="first">R</forename><surname>Stevens</surname></persName></author><author><persName><forename type="first">D</forename><forename type="middle">H D</forename><surname>Warren</surname></persName></author><author><persName><forename type="first">A</forename><surname>Calderwodd</surname></persName></author><author><persName><forename type="first">P</forename><surname>Szeredi</surname></persName></author><author><persName><forename type="first">S</forename><surname>Haridi</surname></persName></author><author><persName><forename type="first">P</forename><surname>Brand</surname></persName></author><author><persName><forename type="first">M</forename><surname>Carlson</surname></persName></author><author><persName><forename type="first">A</forename><surname>Ciepielewski</surname></persName></author><author><persName><forename type="first">B</forename><surname>Hansman</surname></persName></author></analytic><monogr><title level="m">Proceedings FGCS'88</title><meeting>FGCS'88<address><addrLine>Tokyo</addrLine></address></meeting><imprint><date type="published" when="1988-12"></date></imprint></monogr></biblStruct><biblStruct xml:id="b12"><monogr><title level="m" type="main">Kabu wake parallel inference mechanism and its ewluation Michel Raynal. Networks and Distributed Computation. Concepts, Tools and Algorithms. Computer Systems Series The family of concurrent logic programming languages, acre computing surveys</title><author><persName><forename type="first">H</forename><surname>Masuzawa</surname></persName></author><imprint><date type="published" when="1986-11"></date><publisher>IEEE The MIT Press</publisher><biblScope unit="page" from="955" to="962"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b13"><analytic><title level="a" type="main">Task granularity analysis in logic programs</title><author><persName><forename type="first">M</forename><surname>Hermenegildo</surname></persName></author><author><persName><forename type="first">S</forename><forename type="middle">K</forename><surname>Debray</surname></persName></author><author><persName><forename type="first">N-W</forename><surname>Lin</surname></persName></author></analytic><monogr><title level="m">Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation, White Plains</title><meeting>the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation, White Plains<address><addrLine>New York</addrLine></address></meeting><imprint><date type="published" when="1990"></date></imprint></monogr></biblStruct><biblStruct xml:id="b14"><monogr><title level="m" type="main">Mesures de performance des communications du meganode & 128 transputers An Abstract Prolog Instruction Set</title><author><persName><forename type="first">A</forename><surname>Touzene</surname></persName></author><author><persName><forename type="first">B</forename><surname>Plateau</surname></persName></author><imprint><date type="published" when="1983"></date><pubPlace>LGLIMAG, projet CMaP, 46, avenue Fdlix Viallet, 38031 Grenoble Cddex, France</pubPlace></imprint></monogr></biblStruct><biblStruct xml:id="b15"><analytic><title level="a" type="main">The SI~I model for or-parallel execution of prolog. Abstract design and implementation issues The PEPSys model: Combining backtracking, and-and or-parallelism</title><author><persName><forename type="first">D</forename><forename type="middle">H D H</forename><surname>Warren</surname></persName></author><author><persName><forename type="first">P</forename><surname>Westphal</surname></persName></author><author><persName><forename type="first">J</forename><surname>Robert</surname></persName></author><author><persName><forename type="first">J.-C</forename><surname>Chassin</surname></persName></author><author><persName><surname>Syre</surname></persName></author></analytic><monogr><title level="m">4 th Symposium on Logic Programming~ pages 4 th Symposium on Logic Programming</title><meeting><address><addrLine>San Fransisco ; San Fransisco</addrLine></address></meeting><imprint><date type="published" when="1987-09"></date><biblScope unit="page" from="46" to="53"></biblScope></imprint></monogr></biblStruct></listBibl></back></text></istex:refBibTEI></enrichments></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/OperaV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000051 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000051 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= OperaV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:21A37369D25D3F96C68D9EF3B8122264041C5ED6
|texte= Scheduling of OR-parallel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor
}}
| This area was generated with Dilib version V0.6.21. |  |