Language and library support for practical PRAM programming
Identifieur interne : 001475 ( Istex/Corpus ); précédent : 001474; suivant : 001476Language and library support for practical PRAM programming
Auteurs : Christoph W. Ke Ler ; Jesper Larsson Tr FfSource :
- Parallel Computing [ 0167-8191 ] ; 1999.
Abstract
We investigate the well-known Parallel Random Access Machine (PRAM) model of parallel computation as a practical parallel programming model. The two components of this project are a general-purpose PRAM programming language, called Fork95, and a library, called PAD, of fundamental, efficiently implemented parallel algorithms and data structures. We outline the main features of Fork95 as they apply to the implementation of PAD, and describe the implementation of library procedures for prefix-sums and sorting. The Fork95 compiler generates code for the SB-PRAM, a hardware emulation of the PRAM, which is currently being completed at the University of Saarbrücken. Both language and library can immediately be used with this machine. The project is, however, of independent interest. The programming environment can help the algorithm designer to evaluate the practicality of new parallel algorithms, and can furthermore be used as a tool for teaching and communication of parallel algorithms.
Url:
DOI: 10.1016/S0167-8191(98)00092-1
Links to Exploration step
ISTEX:7840E7C5D751C2190E7534928231C12C8B877F3BLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Language and library support for practical PRAM programming</title><author><name sortKey="Ke Ler, Christoph W" sort="Ke Ler, Christoph W" uniqKey="Ke Ler C" first="Christoph W." last="Ke Ler">Christoph W. Ke Ler</name><affiliation><mods:affiliation>FB 4 Informatik, Universität Trier, D-54286 Trier, Germany</mods:affiliation></affiliation></author><author><name sortKey="Tr Ff, Jesper Larsson" sort="Tr Ff, Jesper Larsson" uniqKey="Tr Ff J" first="Jesper Larsson" last="Tr Ff">Jesper Larsson Tr Ff</name><affiliation><mods:affiliation>Technische Universität München, Lehrstuhl für Effiziente Algorithmen, D-80290 München, Germany</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7840E7C5D751C2190E7534928231C12C8B877F3B</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0167-8191(98)00092-1</idno><idno type="url">https://api.istex.fr/document/7840E7C5D751C2190E7534928231C12C8B877F3B/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001475</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001475</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Language and library support for practical PRAM programming</title><author><name sortKey="Ke Ler, Christoph W" sort="Ke Ler, Christoph W" uniqKey="Ke Ler C" first="Christoph W." last="Ke Ler">Christoph W. Ke Ler</name><affiliation><mods:affiliation>FB 4 Informatik, Universität Trier, D-54286 Trier, Germany</mods:affiliation></affiliation></author><author><name sortKey="Tr Ff, Jesper Larsson" sort="Tr Ff, Jesper Larsson" uniqKey="Tr Ff J" first="Jesper Larsson" last="Tr Ff">Jesper Larsson Tr Ff</name><affiliation><mods:affiliation>Technische Universität München, Lehrstuhl für Effiziente Algorithmen, D-80290 München, Germany</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Parallel Computing</title><title level="j" type="abbrev">PARCO</title><idno type="ISSN">0167-8191</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">25</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="105">105</biblScope><biblScope unit="page" to="135">135</biblScope></imprint><idno type="ISSN">0167-8191</idno></series><idno type="istex">7840E7C5D751C2190E7534928231C12C8B877F3B</idno><idno type="DOI">10.1016/S0167-8191(98)00092-1</idno><idno type="PII">S0167-8191(98)00092-1</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0167-8191</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We investigate the well-known Parallel Random Access Machine (PRAM) model of parallel computation as a practical parallel programming model. The two components of this project are a general-purpose PRAM programming language, called Fork95, and a library, called PAD, of fundamental, efficiently implemented parallel algorithms and data structures. We outline the main features of Fork95 as they apply to the implementation of PAD, and describe the implementation of library procedures for prefix-sums and sorting. The Fork95 compiler generates code for the SB-PRAM, a hardware emulation of the PRAM, which is currently being completed at the University of Saarbrücken. Both language and library can immediately be used with this machine. The project is, however, of independent interest. The programming environment can help the algorithm designer to evaluate the practicality of new parallel algorithms, and can furthermore be used as a tool for teaching and communication of parallel algorithms.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>Christoph W. Keßler</name><affiliations><json:string>FB 4 Informatik, Universität Trier, D-54286 Trier, Germany</json:string></affiliations></json:item><json:item><name>Jesper Larsson Träff</name><affiliations><json:string>Technische Universität München, Lehrstuhl für Effiziente Algorithmen, D-80290 München, Germany</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Parallel programming languages</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Parallel software libraries</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Programming environments</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Compilers</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>PRAM model</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>We investigate the well-known Parallel Random Access Machine (PRAM) model of parallel computation as a practical parallel programming model. The two components of this project are a general-purpose PRAM programming language, called Fork95, and a library, called PAD, of fundamental, efficiently implemented parallel algorithms and data structures. We outline the main features of Fork95 as they apply to the implementation of PAD, and describe the implementation of library procedures for prefix-sums and sorting. The Fork95 compiler generates code for the SB-PRAM, a hardware emulation of the PRAM, which is currently being completed at the University of Saarbrücken. Both language and library can immediately be used with this machine. The project is, however, of independent interest. The programming environment can help the algorithm designer to evaluate the practicality of new parallel algorithms, and can furthermore be used as a tool for teaching and communication of parallel algorithms.</abstract><qualityIndicators><score>6.752</score><pdfVersion>1.2</pdfVersion><pdfPageSize>544 x 743 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>5</keywordCount><abstractCharCount>997</abstractCharCount><pdfWordCount>10542</pdfWordCount><pdfCharCount>64114</pdfCharCount><pdfPageCount>31</pdfPageCount><abstractWordCount>146</abstractWordCount></qualityIndicators><title>Language and library support for practical PRAM programming</title><pii><json:string>S0167-8191(98)00092-1</json:string></pii><refBibs><json:item><author><json:item><name>F. Abolhassan</name></json:item><json:item><name>R. Drefenstedt</name></json:item><json:item><name>J. Keller</name></json:item><json:item><name>W.J. Paul</name></json:item><json:item><name>D. Scheerer</name></json:item></author><host><volume>36</volume><pages><last>762</last><first>756</first></pages><issue>8</issue><author></author><title>The Computer Journal</title></host><title>On the physical design of PRAMs</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>Y. Ben-Asher</name></json:item><json:item><name>D.G. Feitelson</name></json:item><json:item><name>L. Rudolph</name></json:item></author><host><volume>26</volume><pages><last>612</last><first>581</first></pages><issue>5</issue><author></author><title>Software – Practice and Experience</title></host><title>ParC – an extension of C for shared memory parallel processing</title></json:item><json:item><author><json:item><name>G.E. Blelloch</name></json:item></author><host><volume>39</volume><pages><last>97</last><first>85</first></pages><issue>3</issue><author></author><title>Communications of the ACM</title></host><title>Programming parallel algorithms</title></json:item><json:item><author><json:item><name>G.E. Blelloch</name></json:item><json:item><name>J.C. Hardwick</name></json:item><json:item><name>J. Sipelstein</name></json:item><json:item><name>M. Zagha</name></json:item><json:item><name>S. Chatterjee</name></json:item></author><host><volume>21</volume><pages><last>14</last><first>4</first></pages><author></author><title>Journal of Parallel and Distributed Computing</title></host><title>Implementation of a portable nested data-parallel language</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>R. Cole</name></json:item><json:item><name>U. Vishkin</name></json:item></author><host><volume>70</volume><pages><last>53</last><first>32</first></pages><author></author><title>Information and Control</title></host><title>Deterministic coin tossing with applications to optimal parallel list ranking</title></json:item><json:item><author><json:item><name>D. Cross</name></json:item><json:item><name>R. Drefenstedt</name></json:item><json:item><name>J. Keller</name></json:item></author><host><volume>45</volume><pages><last>67</last><first>63</first></pages><issue>2</issue><author></author><title>Information Processing Letters</title></host><title>Reduction of network cost and wiring in Ranade's butterfly routing</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>T. Hagerup</name></json:item><json:item><name>A. Schmitt</name></json:item><json:item><name>H. Seidl</name></json:item></author><host><volume>8</volume><pages><last>393</last><first>379</first></pages><author></author><title>Future Generation Computer Systems</title></host><title>FORK: A high-level language for PRAMs</title></json:item><json:item><author><json:item><name>T. Hagerup</name></json:item><json:item><name>C. Rüb</name></json:item></author><host><volume>33</volume><pages><last>185</last><first>181</first></pages><author></author><title>Information Processing Letters</title></host><title>Optimal merging and sorting on the EREW PRAM</title></json:item><json:item><author><json:item><name>T.J. Harris</name></json:item></author><host><volume>26</volume><pages><last>206</last><first>187</first></pages><issue>2</issue><author></author><title>Computing Surveys</title></host><title>A survey of PRAM simulation techniques</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>T.-S. Hsu</name></json:item><json:item><name>V. Ramachandran</name></json:item></author><host><volume>162</volume><pages><last>322</last><first>297</first></pages><issue>2</issue><author></author><title>Theoretical Computer Science</title></host><title>Efficient massively parallel implementation of some combinatorial algorithms</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>J. Keller</name></json:item><json:item><name>T. Walle</name></json:item></author><host><volume>55</volume><pages><last>200</last><first>195</first></pages><issue>4</issue><author></author><title>Information Processing Letters</title></host><title>A note on implementing combining networks</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>C.W. Keßler</name></json:item><json:item><name>H. Seidl</name></json:item></author><host><volume>25</volume><pages><last>50</last><first>17</first></pages><issue>1</issue><author></author><title>International Journal of Parallel Programming</title></host><title>The Fork95 parallel programming language: Design, implementation, application</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>C.P. Kruskal</name></json:item><json:item><name>L. Rudolph</name></json:item><json:item><name>M. Snir</name></json:item></author><host><volume>C34</volume><pages><last>968</last><first>965</first></pages><issue>10</issue><author></author><title>IEEE Transactions on Computers</title></host><title>The power of parallel prefix</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>D. Lenoski</name></json:item><json:item><name>J. Laudon</name></json:item><json:item><name>K. Gharachorloo</name></json:item><json:item><name>W.-D. Weber</name></json:item><json:item><name>A. Gupta</name></json:item><json:item><name>J. Hennessy</name></json:item><json:item><name>M. Horowitz</name></json:item><json:item><name>M.S. Lam</name></json:item></author><host><volume>25</volume><pages><last>79</last><first>63</first></pages><issue>3</issue><author></author><title>IEEE Computer</title></host><title>The Stanford DASH multiprocessor</title></json:item><json:item><author><json:item><name>C. León</name></json:item><json:item><name>C. Rodrı́guez</name></json:item><json:item><name>F. Garcı́a</name></json:item><json:item><name>F. de Sande</name></json:item></author><host><volume>9</volume><pages><last>179</last><first>163</first></pages><issue>3</issue><author></author><title>Concurrency: Practice and Experience</title></host><title>A PRAM oriented programing system</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>A.G. Ranade</name></json:item></author><host><volume>42</volume><pages><last>326</last><first>307</first></pages><author></author><title>Journal of Computer and System Sciences</title></host><title>How to emulate shared memory</title></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>L.G. Valiant</name></json:item></author><host><volume>33</volume><pages><last>111</last><first>103</first></pages><issue>8</issue><author></author><title>Communications of the ACM</title></host><title>A bridging model for parallel computation</title></json:item><json:item><author><json:item><name>U. Vishkin</name></json:item></author><host><volume>13</volume><pages><last>501</last><first>489</first></pages><author></author><title>Journal of Algorithms</title></host><title>A parallel blocking flow algorithm for acyclic networks</title></json:item><json:item><host><author></author></host></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>25</volume><pii><json:string>S0167-8191(00)X0047-6</json:string></pii><pages><last>135</last><first>105</first></pages><issn><json:string>0167-8191</json:string></issn><issue>2</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Parallel Computing</title><publicationDate>1999</publicationDate></host><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1016/S0167-8191(98)00092-1</json:string></doi><id>7840E7C5D751C2190E7534928231C12C8B877F3B</id><score>0.6989527</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/7840E7C5D751C2190E7534928231C12C8B877F3B/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/7840E7C5D751C2190E7534928231C12C8B877F3B/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/7840E7C5D751C2190E7534928231C12C8B877F3B/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Language and library support for practical PRAM programming</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>©1999 Elsevier Science B.V.</p></availability><date>1999</date></publicationStmt><notesStmt><note>This work was partially supported by ESPRIT LTR Project no. 20244-ALCOM-IT.</note><note>This article is the full version of a short paper that appeared at the 5th Euromicro Workshop on Parallel and Distributed Processing, London, UK, 1997.</note><note type="content">Fig. 1: The programming model of Fork95 is a CRCW PRAM, a homogeneous shared-memory MIMD machine which works synchronously on the instruction level. Uniform memory access time, the possibility of concurrent read resp. concurrent write access to the same memory location within the same clock cycle, and atomic fetch&op operators are assumed. Private address subspaces are embedded into the shared memory by handling private addresses relative to a BASE pointer.</note><note type="content">Fig. 2: The SB-PRAM hardware system components.</note><note type="content">Fig. 3: A map of PRAM algorithms for graph problems.</note><note type="content">Table 1: Some basic operations of PAD</note><note type="content">Table 2: Efficiency of the parallel prefix implementations.</note><note type="content">Table 3: Sorting results.</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Language and library support for practical PRAM programming</title><author xml:id="author-1"><persName><forename type="first">Christoph W.</forename><surname>Keßler</surname></persName><affiliation>FB 4 Informatik, Universität Trier, D-54286 Trier, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Jesper Larsson</forename><surname>Träff</surname></persName><note type="biography">This author was supported by DFG, SFB 124-D6, VLSI Entwurfsmethoden und Parallelität. The work was done while this author was at the Max-Planck-Institut für Informatik, Saarbrücken, Germany. E-mail: traeff@informatik.tu-muenchen.de</note><affiliation>Technische Universität München, Lehrstuhl für Effiziente Algorithmen, D-80290 München, Germany</affiliation></author></analytic><monogr><title level="j">Parallel Computing</title><title level="j" type="abbrev">PARCO</title><idno type="pISSN">0167-8191</idno><idno type="PII">S0167-8191(00)X0047-6</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999"></date><biblScope unit="volume">25</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="105">105</biblScope><biblScope unit="page" to="135">135</biblScope></imprint></monogr><idno type="istex">7840E7C5D751C2190E7534928231C12C8B877F3B</idno><idno type="DOI">10.1016/S0167-8191(98)00092-1</idno><idno type="PII">S0167-8191(98)00092-1</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1999</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>We investigate the well-known Parallel Random Access Machine (PRAM) model of parallel computation as a practical parallel programming model. The two components of this project are a general-purpose PRAM programming language, called Fork95, and a library, called PAD, of fundamental, efficiently implemented parallel algorithms and data structures. We outline the main features of Fork95 as they apply to the implementation of PAD, and describe the implementation of library procedures for prefix-sums and sorting. The Fork95 compiler generates code for the SB-PRAM, a hardware emulation of the PRAM, which is currently being completed at the University of Saarbrücken. Both language and library can immediately be used with this machine. The project is, however, of independent interest. The programming environment can help the algorithm designer to evaluate the practicality of new parallel algorithms, and can furthermore be used as a tool for teaching and communication of parallel algorithms.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Parallel programming languages</term></item><item><term>Parallel software libraries</term></item><item><term>Programming environments</term></item><item><term>Compilers</term></item><item><term>PRAM model</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1998-04-10">Modified</change><change when="1999">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/7840E7C5D751C2190E7534928231C12C8B877F3B/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: ce:floats; body; tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"><istex:entity SYSTEM="gr1" NDATA="IMAGE" name="gr1"></istex:entity><istex:entity SYSTEM="gr2" NDATA="IMAGE" name="gr2"></istex:entity><istex:entity SYSTEM="gr3" NDATA="IMAGE" name="gr3"></istex:entity></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>PARCO</jid><aid>1369</aid><ce:pii>S0167-8191(98)00092-1</ce:pii><ce:doi>10.1016/S0167-8191(98)00092-1</ce:doi><ce:copyright year="1999" type="full-transfer">Elsevier Science B.V.</ce:copyright></item-info><head><ce:title>Language and library support for practical PRAM programming<ce:footnote id="FN1"><ce:label>1</ce:label><ce:note-para>This work was partially supported by ESPRIT LTR Project no. 20244-ALCOM-IT.</ce:note-para></ce:footnote><ce:cross-ref refid="FN1"><ce:sup>1</ce:sup></ce:cross-ref><ce:footnote id="FN2"><ce:label>2</ce:label><ce:note-para>This article is the full version of a short paper that appeared at the 5th Euromicro Workshop on Parallel and Distributed Processing, London, UK, 1997.</ce:note-para></ce:footnote><ce:cross-ref refid="FN2"><ce:sup>2</ce:sup></ce:cross-ref></ce:title><ce:author-group><ce:author><ce:given-name>Christoph W.</ce:given-name><ce:surname>Keßler</ce:surname><ce:cross-ref refid="AFF1">a</ce:cross-ref><ce:cross-ref refid="CORR1">*</ce:cross-ref></ce:author><ce:author><ce:given-name>Jesper Larsson</ce:given-name><ce:surname>Träff</ce:surname><ce:cross-ref refid="AFF2">b</ce:cross-ref><ce:cross-ref refid="FN3"><ce:sup>3</ce:sup></ce:cross-ref><ce:cross-ref refid="FN3"><ce:sup>3</ce:sup></ce:cross-ref></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>FB 4 Informatik, Universität Trier, D-54286 Trier, Germany</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>Technische Universität München, Lehrstuhl für Effiziente Algorithmen, D-80290 München, Germany</ce:textfn></ce:affiliation><ce:correspondence id="CORR1"><ce:label>*</ce:label><ce:text>Corresponding author. E-mail: kessler@psi.uni-trier.de</ce:text></ce:correspondence><ce:footnote id="FN3"><ce:label>3</ce:label><ce:note-para>This author was supported by DFG, SFB 124-D6, VLSI Entwurfsmethoden und Parallelität. The work was done while this author was at the Max-Planck-Institut für Informatik, Saarbrücken, Germany. E-mail: traeff@informatik.tu-muenchen.de</ce:note-para></ce:footnote></ce:author-group><ce:date-received day="15" month="7" year="1997"></ce:date-received><ce:date-revised day="10" month="4" year="1998"></ce:date-revised><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>We investigate the well-known Parallel Random Access Machine (PRAM) model of parallel computation as a <ce:italic>practical parallel programming model</ce:italic>. The two components of this project are a general-purpose PRAM programming language, called Fork95, and a library, called PAD, of fundamental, efficiently implemented parallel algorithms and data structures. We outline the main features of Fork95 as they apply to the implementation of PAD, and describe the implementation of library procedures for prefix-sums and sorting. The Fork95 compiler generates code for the SB-PRAM, a hardware emulation of the PRAM, which is currently being completed at the University of Saarbrücken. Both language and library can immediately be used with this machine. The project is, however, of independent interest. The programming environment can help the algorithm designer to evaluate the practicality of new parallel algorithms, and can furthermore be used as a tool for teaching and communication of parallel algorithms.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords class="keyword"><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Parallel programming languages</ce:text></ce:keyword><ce:keyword><ce:text>Parallel software libraries</ce:text></ce:keyword><ce:keyword><ce:text>Programming environments</ce:text></ce:keyword><ce:keyword><ce:text>Compilers</ce:text></ce:keyword><ce:keyword><ce:text>PRAM model</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Language and library support for practical PRAM programming</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Language and library support for practical PRAM programming</title></titleInfo><name type="personal"><namePart type="given">Christoph W.</namePart><namePart type="family">Keßler</namePart><affiliation>FB 4 Informatik, Universität Trier, D-54286 Trier, Germany</affiliation><description>Corresponding author. E-mail: kessler@psi.uni-trier.de</description><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Jesper Larsson</namePart><namePart type="family">Träff</namePart><affiliation>Technische Universität München, Lehrstuhl für Effiziente Algorithmen, D-80290 München, Germany</affiliation><description>This author was supported by DFG, SFB 124-D6, VLSI Entwurfsmethoden und Parallelität. The work was done while this author was at the Max-Planck-Institut für Informatik, Saarbrücken, Germany. E-mail: traeff@informatik.tu-muenchen.de</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued><dateModified encoding="w3cdtf">1998-04-10</dateModified><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">We investigate the well-known Parallel Random Access Machine (PRAM) model of parallel computation as a practical parallel programming model. The two components of this project are a general-purpose PRAM programming language, called Fork95, and a library, called PAD, of fundamental, efficiently implemented parallel algorithms and data structures. We outline the main features of Fork95 as they apply to the implementation of PAD, and describe the implementation of library procedures for prefix-sums and sorting. The Fork95 compiler generates code for the SB-PRAM, a hardware emulation of the PRAM, which is currently being completed at the University of Saarbrücken. Both language and library can immediately be used with this machine. The project is, however, of independent interest. The programming environment can help the algorithm designer to evaluate the practicality of new parallel algorithms, and can furthermore be used as a tool for teaching and communication of parallel algorithms.</abstract><note type="footnote">This work was partially supported by ESPRIT LTR Project no. 20244-ALCOM-IT.</note><note type="footnote">This article is the full version of a short paper that appeared at the 5th Euromicro Workshop on Parallel and Distributed Processing, London, UK, 1997.</note><note type="content">Fig. 1: The programming model of Fork95 is a CRCW PRAM, a homogeneous shared-memory MIMD machine which works synchronously on the instruction level. Uniform memory access time, the possibility of concurrent read resp. concurrent write access to the same memory location within the same clock cycle, and atomic fetch&op operators are assumed. Private address subspaces are embedded into the shared memory by handling private addresses relative to a BASE pointer.</note><note type="content">Fig. 2: The SB-PRAM hardware system components.</note><note type="content">Fig. 3: A map of PRAM algorithms for graph problems.</note><note type="content">Table 1: Some basic operations of PAD</note><note type="content">Table 2: Efficiency of the parallel prefix implementations.</note><note type="content">Table 3: Sorting results.</note><subject><genre>Keywords</genre><topic>Parallel programming languages</topic><topic>Parallel software libraries</topic><topic>Programming environments</topic><topic>Compilers</topic><topic>PRAM model</topic></subject><relatedItem type="host"><titleInfo><title>Parallel Computing</title></titleInfo><titleInfo type="abbreviated"><title>PARCO</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">199902</dateIssued></originInfo><identifier type="ISSN">0167-8191</identifier><identifier type="PII">S0167-8191(00)X0047-6</identifier><part><date>199902</date><detail type="volume"><number>25</number><caption>vol.</caption></detail><detail type="issue"><number>2</number><caption>no.</caption></detail><extent unit="issue pages"><start>105</start><end>216</end></extent><extent unit="pages"><start>105</start><end>135</end></extent></part></relatedItem><identifier type="istex">7840E7C5D751C2190E7534928231C12C8B877F3B</identifier><identifier type="DOI">10.1016/S0167-8191(98)00092-1</identifier><identifier type="PII">S0167-8191(98)00092-1</identifier><accessCondition type="use and reproduction" contentType="copyright">©1999 Elsevier Science B.V.</accessCondition><recordInfo><recordContentSource>ELSEVIER</recordContentSource><recordOrigin>Elsevier Science B.V., ©1999</recordOrigin></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001475 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001475 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:7840E7C5D751C2190E7534928231C12C8B877F3B
|texte= Language and library support for practical PRAM programming
}}
| This area was generated with Dilib version V0.6.31. |  |