Periodic merging networks
Identifieur interne : 001211 ( Istex/Corpus ); précédent : 001210; suivant : 001212Periodic merging networks
Auteurs : Mirosław Kutyłowski ; Krzysztof Lory ; Brigitte OesterdiekhoffSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1996.
Abstract
Abstract: We consider the problem of merging two sorted sequences on constant degree networks using comparators only. The classical solution to the problem are the networks based on Batcher's Odd-Even Merge and Bitonic Merge running in log(2n) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present new merging networks that have a novel property of being periodic: for some (small) constant k, each processing unit of the network performs the same operations at steps t and t+tk (as long as t+k does not exceed the runtime.) The only operations executed are compare-exchange operations, just like in the case of the Batcher's networks. The architecture of the networks is very simple, easy to be laid out. The runtimes achieved are c · log n, for a small constant c.
Url:
DOI: 10.1007/BFb0009510
Links to Exploration step
ISTEX:957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1BLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Periodic merging networks</title><author><name sortKey="Kutylowski, Miroslaw" sort="Kutylowski, Miroslaw" uniqKey="Kutylowski M" first="Mirosław" last="Kutyłowski">Mirosław Kutyłowski</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: mirekk@uni-paderborn.de</mods:affiliation></affiliation></author><author><name sortKey="Lory, Krzysztof" sort="Lory, Krzysztof" uniqKey="Lory K" first="Krzysztof" last="Lory">Krzysztof Lory</name><affiliation><mods:affiliation>Institute of Computer Science, University of Wrocław, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>Dept. of Computer Science, University of Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: lorys@ti.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Oesterdiekhoff, Brigitte" sort="Oesterdiekhoff, Brigitte" uniqKey="Oesterdiekhoff B" first="Brigitte" last="Oesterdiekhoff">Brigitte Oesterdiekhoff</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: brigitte@uni-paderborn.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1007/BFb0009510</idno><idno type="url">https://api.istex.fr/document/957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001211</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001211</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Periodic merging networks</title><author><name sortKey="Kutylowski, Miroslaw" sort="Kutylowski, Miroslaw" uniqKey="Kutylowski M" first="Mirosław" last="Kutyłowski">Mirosław Kutyłowski</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: mirekk@uni-paderborn.de</mods:affiliation></affiliation></author><author><name sortKey="Lory, Krzysztof" sort="Lory, Krzysztof" uniqKey="Lory K" first="Krzysztof" last="Lory">Krzysztof Lory</name><affiliation><mods:affiliation>Institute of Computer Science, University of Wrocław, Poland</mods:affiliation></affiliation><affiliation><mods:affiliation>Dept. of Computer Science, University of Trier, D-54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: lorys@ti.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Oesterdiekhoff, Brigitte" sort="Oesterdiekhoff, Brigitte" uniqKey="Oesterdiekhoff B" first="Brigitte" last="Oesterdiekhoff">Brigitte Oesterdiekhoff</name><affiliation><mods:affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: brigitte@uni-paderborn.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1996</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B</idno><idno type="DOI">10.1007/BFb0009510</idno><idno type="ChapterID">35</idno><idno type="ChapterID">Chap35</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: We consider the problem of merging two sorted sequences on constant degree networks using comparators only. The classical solution to the problem are the networks based on Batcher's Odd-Even Merge and Bitonic Merge running in log(2n) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present new merging networks that have a novel property of being periodic: for some (small) constant k, each processing unit of the network performs the same operations at steps t and t+tk (as long as t+k does not exceed the runtime.) The only operations executed are compare-exchange operations, just like in the case of the Batcher's networks. The architecture of the networks is very simple, easy to be laid out. The runtimes achieved are c · log n, for a small constant c.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Mirosław Kutyłowski</name><affiliations><json:string>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</json:string><json:string>E-mail: mirekk@uni-paderborn.de</json:string></affiliations></json:item><json:item><name>Krzysztof Loryś</name><affiliations><json:string>Institute of Computer Science, University of Wrocław, Poland</json:string><json:string>Dept. of Computer Science, University of Trier, D-54286, Trier, Germany</json:string><json:string>E-mail: lorys@ti.uni-trier.de</json:string></affiliations></json:item><json:item><name>Brigitte Oesterdiekhoff</name><affiliations><json:string>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</json:string><json:string>E-mail: brigitte@uni-paderborn.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: We consider the problem of merging two sorted sequences on constant degree networks using comparators only. The classical solution to the problem are the networks based on Batcher's Odd-Even Merge and Bitonic Merge running in log(2n) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present new merging networks that have a novel property of being periodic: for some (small) constant k, each processing unit of the network performs the same operations at steps t and t+tk (as long as t+k does not exceed the runtime.) The only operations executed are compare-exchange operations, just like in the case of the Batcher's networks. The architecture of the networks is very simple, easy to be laid out. The runtimes achieved are c · log n, for a small constant c.</abstract><qualityIndicators><score>6.209</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.28 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>805</abstractCharCount><pdfWordCount>4577</pdfWordCount><pdfCharCount>21420</pdfCharCount><pdfPageCount>10</pdfPageCount><abstractWordCount>136</abstractWordCount></qualityIndicators><title>Periodic merging networks</title><chapterId><json:string>35</json:string><json:string>Chap35</json:string></chapterId><refBibs><json:item><host><author><json:item><name> By Lemma 7</name></json:item></author><title>Steps A and D have no affect anymore, Steps B and C mimic Odd-Even Transposition Sort of q items. Since q steps of Odd-Even Transposition Sort suffice to sort q items [7], relocating the sorted columns requires at most q horizontal steps, that is, 2q steps of our algorithm. Concluding, the algorithm needs together at most 10q steps</title></host></json:item><json:item><author><json:item><name>Kenneth,E Batcher</name></json:item></author><host><pages><last>314</last><first>307</first></pages><author></author><title>AFIPS Conf. Proc. 32</title><publicationDate>1968</publicationDate></host><title>Sorting networks and their applications</title><publicationDate>1968</publicationDate></json:item><json:item><author><json:item><name>Ronald,I Becker</name></json:item><json:item><name>David Nassimi</name></json:item><json:item><name>Yehoshua Perl</name></json:item></author><host><pages><last>364</last><first>356</first></pages><author></author><title>Proc. 5thACM-SPAA</title><publicationDate>1993</publicationDate></host><title>The new class of g-chain periodic sorters</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>Gianfranco Bilardi</name></json:item></author><host><volume>38</volume><pages><last>1403</last><first>1396</first></pages><author></author><title>IEEE Transactions on Computers</title><publicationDate>1989</publicationDate></host><title>Merging and sorting networks with the topology of the Omega network</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>Allan Borodin</name></json:item><json:item><name>John,E Hopcroft</name></json:item></author><host><volume>30</volume><pages><last>145</last><first>130</first></pages><issue>1</issue><author></author><title>J. Comput. Syst. Sci</title><publicationDate>1985</publicationDate></host><title>Routing, merging, and sorting on parallel models of computation</title><publicationDate>1985</publicationDate></json:item><json:item><author><json:item><name>Martin Dowd</name></json:item><json:item><name>Yehoshua Perl</name></json:item><json:item><name>Larry Rudolph</name></json:item><json:item><name>Michael Saks</name></json:item></author><host><volume>36</volume><pages><last>757</last><first>738</first></pages><author></author><title>Journal oftheACM</title><publicationDate>1989</publicationDate></host><title>The periodic balanced sorting network</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>Marcin Kik</name></json:item><json:item><name>Mirostaw Kutytowski</name></json:item><json:item><name>Grzegorz Stachowiak</name></json:item></author><host><pages><last>2121</last><first>201</first></pages><author></author><title>Proc. 11th STACS</title><publicationDate>1994</publicationDate></host><title>Periodic constant depth sorting networks</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>Donald,E Knuth</name></json:item></author><host><author></author><title>The Art of Computer Programming</title><publicationDate>1973</publicationDate></host><title>Sorting and Searching</title><publicationDate>1973</publicationDate></json:item><json:item><author><json:item><name>Mirostaw Kutylowski</name></json:item><json:item><name>Krzysztof Loryg</name></json:item><json:item><name>Brigitte Oesterdiekhoff</name></json:item><json:item><name>Rolf Wanka</name></json:item></author><host><pages><last>380</last><first>369</first></pages><author></author><title>Proc. 35th IEEE-FOCS</title><publicationDate>1994</publicationDate></host><title>Fast and feasible periodic sorting networks of constant depth</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>Peter Bro Miltersen</name></json:item><json:item><name>Mike Paterson</name></json:item><json:item><name>Jun Tarui</name></json:item></author><host><pages><last>246</last><first>236</first></pages><author></author><title>Proc. 33rd IEEE-FOCS</title><publicationDate>1992</publicationDate></host><title>The asymptotic complexity of merging networks</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>David Nassimi</name></json:item><json:item><name>Yehoshua Perl</name></json:item><json:item><name>Ronald,I Becker</name></json:item></author><host><pages><last>432</last><first>424</first></pages><author></author><title>Proc. 8th IPPS</title><publicationDate>1994</publicationDate></host><title>The generalized class of g-chain periodic sorting networks</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>Yehoshua Perl</name></json:item></author><host><volume>25</volume><pages><last>271</last><first>257</first></pages><author></author><title>Discrete Applied Mathematics</title><publicationDate>1989</publicationDate></host><title>Better understanding of Batcher's merging networks</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>Uwe Schwiegelshohn</name></json:item></author><host><pages><last>264</last><first>257</first></pages><author></author><title>International Conference on Systolic Arrays</title><publicationDate>1988</publicationDate></host><title>A shortperiodic two-dimensional systolic sorting algorithm</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>Robert Sedgewick</name></json:item></author><host><volume>7</volume><pages><last>272</last><first>239</first></pages><author></author><title>SlAM J. Comput</title><publicationDate>1978</publicationDate></host><title>Data movement in odd-even merging</title><publicationDate>1978</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1996</copyrightDate></serie><host><editor><json:item><name>Tetsuo Asano</name></json:item><json:item><name>Yoshihide Igarashi</name></json:item><json:item><name>Hiroshi Nagamochi</name></json:item><json:item><name>Satoru Miyano</name></json:item><json:item><name>Subhash Suri</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Computer Graphics</value></json:item><json:item><value>Computational Mathematics and Numerical Analysis</value></json:item></subject><isbn><json:string>978-3-540-62048-8</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Algorithms and Computation</title><bookId><json:string>3540620486</json:string></bookId><volume>1178</volume><pages><last>345</last><first>336</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-49633-5</json:string></eisbn><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/BFb0009475</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1996</copyrightDate><doi><json:string>10.1007/BFb0009510</json:string></doi><id>957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B</id><score>0.6112251</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Periodic merging networks</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1996</p></availability><date>1996</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Periodic merging networks</title><author xml:id="author-1"><persName><forename type="first">Mirosław</forename><surname>Kutyłowski</surname></persName><email>mirekk@uni-paderborn.de</email><affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Krzysztof</forename><surname>Loryś</surname></persName><email>lorys@ti.uni-trier.de</email><affiliation>Institute of Computer Science, University of Wrocław, Poland</affiliation><affiliation>Dept. of Computer Science, University of Trier, D-54286, Trier, Germany</affiliation></author><author xml:id="author-3"><persName><forename type="first">Brigitte</forename><surname>Oesterdiekhoff</surname></persName><email>brigitte@uni-paderborn.de</email><affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation></author></analytic><monogr><title level="m">Algorithms and Computation</title><title level="m" type="sub">7th International Symposium, ISAAC '96 Osaka, Japan, December 16–18, 1996 Proceedings</title><idno type="pISBN">978-3-540-62048-8</idno><idno type="eISBN">978-3-540-49633-5</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/BFb0009475</idno><idno type="book-ID">3540620486</idno><idno type="book-title-ID">46821</idno><idno type="book-volume-number">1178</idno><idno type="book-chapter-count">45</idno><editor><persName><forename type="first">Tetsuo</forename><surname>Asano</surname></persName></editor><editor><persName><forename type="first">Yoshihide</forename><surname>Igarashi</surname></persName></editor><editor><persName><forename type="first">Hiroshi</forename><surname>Nagamochi</surname></persName></editor><editor><persName><forename type="first">Satoru</forename><surname>Miyano</surname></persName></editor><editor><persName><forename type="first">Subhash</forename><surname>Suri</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-10-11"></date><biblScope unit="volume">1178</biblScope><biblScope unit="page" from="336">336</biblScope><biblScope unit="page" to="345">345</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><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1996</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B</idno><idno type="DOI">10.1007/BFb0009510</idno><idno type="ChapterID">35</idno><idno type="ChapterID">Chap35</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1996</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We consider the problem of merging two sorted sequences on constant degree networks using comparators only. The classical solution to the problem are the networks based on Batcher's Odd-Even Merge and Bitonic Merge running in log(2n) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present new merging networks that have a novel property of being periodic: for some (small) constant k, each processing unit of the network performs the same operations at steps t and t+tk (as long as t+k does not exceed the runtime.) The only operations executed are compare-exchange operations, just like in the case of the Batcher's networks. The architecture of the networks is very simple, easy to be laid out. The runtimes achieved are c · log n, for a small constant c.</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>I16021</label><label>I16013</label><label>I13022</label><label>I22013</label><label>M1400X</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Computer Communication Networks</term></item><item><term>Computer Graphics</term></item><item><term>Computational Mathematics and Numerical Analysis</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-10-11">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-21">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B/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><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540620486</BookID><BookTitle>Algorithms and Computation</BookTitle><BookSubTitle>7th International Symposium, ISAAC '96 Osaka, Japan, December 16–18, 1996 Proceedings</BookSubTitle><BookVolumeNumber>1178</BookVolumeNumber><BookDOI>10.1007/BFb0009475</BookDOI><BookTitleID>46821</BookTitleID><BookPrintISBN>978-3-540-62048-8</BookPrintISBN><BookElectronicISBN>978-3-540-49633-5</BookElectronicISBN><BookChapterCount>45</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I16013" Priority="2" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I13022" Priority="3" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I22013" Priority="4" Type="Secondary">Computer Graphics</BookSubject><BookSubject Code="M1400X" Priority="5" Type="Secondary">Computational Mathematics and Numerical Analysis</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Tetsuo</GivenName><FamilyName>Asano</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Yoshihide</GivenName><FamilyName>Igarashi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Hiroshi</GivenName><FamilyName>Nagamochi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Satoru</GivenName><FamilyName>Miyano</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Subhash</GivenName><FamilyName>Suri</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap35" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>35</ChapterID><ChapterDOI>10.1007/BFb0009510</ChapterDOI><ChapterSequenceNumber>35</ChapterSequenceNumber><ChapterTitle Language="En">Periodic merging networks</ChapterTitle><ChapterCategory>Session 8b: Invited Presentation</ChapterCategory><ChapterFirstPage>336</ChapterFirstPage><ChapterLastPage>345</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1996</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>10</Month><Day>11</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>3540620486</BookID><BookTitle>Algorithms and Computation</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Mirosław</GivenName><FamilyName>Kutyłowski</FamilyName></AuthorName><Contact><Email>mirekk@uni-paderborn.de</Email></Contact></Author><Author AffiliationIDS="Aff2 Aff3"><AuthorName DisplayOrder="Western"><GivenName>Krzysztof</GivenName><FamilyName>Loryś</FamilyName></AuthorName><Contact><Email>lorys@ti.uni-trier.de</Email></Contact></Author><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Brigitte</GivenName><FamilyName>Oesterdiekhoff</FamilyName></AuthorName><Contact><Email>brigitte@uni-paderborn.de</Email></Contact></Author><Affiliation ID="Aff1"><OrgDivision>Heinz Nixdorf Institute and Department of Mathematics & Computer Science</OrgDivision><OrgName>University of Paderborn</OrgName><OrgAddress><Postcode>D-33095</Postcode><City>Paderborn</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Institute of Computer Science</OrgDivision><OrgName>University of Wrocław</OrgName><OrgAddress><Country>Poland</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgDivision>Dept. of Computer Science</OrgDivision><OrgName>University of Trier</OrgName><OrgAddress><Postcode>D-54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We consider the problem of merging two sorted sequences on constant degree networks using comparators only. The classical solution to the problem are the networks based on Batcher's Odd-Even Merge and Bitonic Merge running in log(2<Emphasis Type="Italic">n</Emphasis>) time. Due to the obvious log <Emphasis Type="Italic">n</Emphasis> lower bound for the runtime, this is time-optimal.</Para><Para>We present new merging networks that have a novel property of being periodic: for some (small) constant <Emphasis Type="Italic">k</Emphasis>, each processing unit of the network performs the same operations at steps <Emphasis Type="Italic">t</Emphasis> and <Emphasis Type="Italic">t+tk</Emphasis> (as long as <Emphasis Type="Italic">t+k</Emphasis> does not exceed the runtime.) The only operations executed are compare-exchange operations, just like in the case of the Batcher's networks. The architecture of the networks is very simple, easy to be laid out. The runtimes achieved are <Emphasis Type="Italic">c</Emphasis> · log <Emphasis Type="Italic">n</Emphasis>, for a small constant <Emphasis Type="Italic">c</Emphasis>.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>Partially supported by KBN grants 8 S503 002 07, 2 P301 034 07, DFG-Sonderforschungsbereich 376 “Massive Parallelität”, DFG Leibniz Grant Me872/6-1 and EU ESPRIT Long Term Research Project 20244 (ALCOM-IT); this research was partially done while the second author visited University of Paderborn</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Periodic merging networks</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Periodic merging networks</title></titleInfo><name type="personal"><namePart type="given">Mirosław</namePart><namePart type="family">Kutyłowski</namePart><affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation><affiliation>E-mail: mirekk@uni-paderborn.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Krzysztof</namePart><namePart type="family">Loryś</namePart><affiliation>Institute of Computer Science, University of Wrocław, Poland</affiliation><affiliation>Dept. of Computer Science, University of Trier, D-54286, Trier, Germany</affiliation><affiliation>E-mail: lorys@ti.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Brigitte</namePart><namePart type="family">Oesterdiekhoff</namePart><affiliation>Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University of Paderborn, D-33095, Paderborn, Germany</affiliation><affiliation>E-mail: brigitte@uni-paderborn.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-10-11</dateIssued><copyrightDate encoding="w3cdtf">1996</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: We consider the problem of merging two sorted sequences on constant degree networks using comparators only. The classical solution to the problem are the networks based on Batcher's Odd-Even Merge and Bitonic Merge running in log(2n) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present new merging networks that have a novel property of being periodic: for some (small) constant k, each processing unit of the network performs the same operations at steps t and t+tk (as long as t+k does not exceed the runtime.) The only operations executed are compare-exchange operations, just like in the case of the Batcher's networks. The architecture of the networks is very simple, easy to be laid out. The runtimes achieved are c · log n, for a small constant c.</abstract><relatedItem type="host"><titleInfo><title>Algorithms and Computation</title><subTitle>7th International Symposium, ISAAC '96 Osaka, Japan, December 16–18, 1996 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Tetsuo</namePart><namePart type="family">Asano</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Yoshihide</namePart><namePart type="family">Igarashi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Hiroshi</namePart><namePart type="family">Nagamochi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Satoru</namePart><namePart type="family">Miyano</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Subhash</namePart><namePart type="family">Suri</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1996</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="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic><topic authority="SpringerSubjectCodes" authorityURI="M1400X">Computational Mathematics and Numerical Analysis</topic></subject><identifier type="DOI">10.1007/BFb0009475</identifier><identifier type="ISBN">978-3-540-62048-8</identifier><identifier type="eISBN">978-3-540-49633-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">46821</identifier><identifier type="BookID">3540620486</identifier><identifier type="BookChapterCount">45</identifier><identifier type="BookVolumeNumber">1178</identifier><part><date>1996</date><detail type="volume"><number>1178</number><caption>vol.</caption></detail><extent unit="pages"><start>336</start><end>345</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1996</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><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1996</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, 1996</recordOrigin></recordInfo></relatedItem><identifier type="istex">957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B</identifier><identifier type="DOI">10.1007/BFb0009510</identifier><identifier type="ChapterID">35</identifier><identifier type="ChapterID">Chap35</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1996</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1996</recordOrigin></recordInfo></mods></metadata></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 001211 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001211 | 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:957AC6C4A810F26B5A31B4BB26D97DD77D0FCD1B
|texte= Periodic merging networks
}}
| This area was generated with Dilib version V0.6.31. |  |