More Web Proxy on the site http://driver.im/

article

Fast periodic correction networks

Author:

Grzegorz StachowiakAuthors Info & Claims

Theoretical Computer Science, Volume 354, Issue 3

Pages 354 - 366

https://doi.org/10.1016/j.tcs.2005.11.031

Published: 04 April 2006 Publication History

Abstract

We consider the problem of sorting N-element inputs differing from already sorted sequences by t small changes. To perform this task we construct a constant depth comparator network that is applied periodically. The two constructions for this problem made, by previous authors required O(log n + t) iterations of the network. Our construction requires O(log n + (log log N)²(log t)³) iterations which makes it asymptotically faster for t > log N.

References

[1]

{1} M. Ajtai, J. Komlós, E. Szemerédi, Sorting in c log n parallel steps, Combinatorica 3 (1983) 1-19.]]

Digital Library

[2]

{2} K.E. Batcher, Sorting networks and their applications, in: AFIPS Conf. Proc. 32 (1968) 307-314.]]

[3]

{3} M. Dowd, Y. Perl, M. Saks, L. Rudolph, The periodic balanced sorting network, J. ACM 36 (1989) 738-757.]]

Digital Library

[4]

{4} M. Kik, Periodic correction networks, EUROPAR 2000 proc. Lecture Notes in Computer Science, Springer, Berlin, 1900, pp. 471-478.]]

[5]

{5} M. Kik, M. Kutyłowski, M. Piotrów, Correction networks, in: Proc. 1999 ICPP, pp. 40-47.]]

[6]

{6} M. Kik, M. Kutyłowski, G. Stachowiak, Periodic constant depth sorting networks, Proc. 11th STACS, 1994, pp. 201-212.]]

[7]

{7} D.E. Knuth, The Art of Computer Programming, vol. 3, second ed., Addison Wesley, Reading, MA, 1975.]]

[8]

{8} J. Krammer, Lösung von Datentransportproblemen in integrierten Schaltungen, Dissertation, TU München, 1991.]]

[9]

{9} K. Loryś, M. Kutyłowski, B. Oesterdiekoff, R. Wanka, Fast and feasible periodic sorting networks of constant depth, Proc. 35 IEEE-FOCS, 1994, pp. 369-380.]]

[10]

{10} B. Oesterdiekoff, On the minimal period of fast periodic sorting networks, Technical Report TR-RI-95-167, University of Paderborn, 1995.]]

[11]

{11} M. Piotrów, Depth optimal sorting networks resistant to k passive faults, in: Proc. Seventh SIAM Symp. Discrete Algorithms, 1996, pp. 242-251 (also accepted for SIAM J. Comput.).]]

[12]

{12} M. Piotrów, Periodic random-fault-tolerant correction networks, Proc. 13th SPAA, ACM, 2001, pp. 298-305.]]

[13]

{13} L. Rudolph, A robust sorting network, IEEE Trans. Comput. 34 (1985) 326-336.]]

Digital Library

[14]

{14} M. Schimmler, C. Starke, A correction network for N-sorters, SIAM J. Comput. 18 (1989) 1179-1197.]]

Digital Library

[15]

{15} U. Schwiegelsohn, A shortperiodic two-dimensional systolic sorting algorithm, in: Internat. Conf. Systolic Arrays, Computer Society Press, Baltimore, 1988, pp. 257-264.]]

[16]

{16} G. Stachowiak, Fibonacci correction networks, in: M. Halldórsson (Ed.), Algorithm Theory--SWAT 2000, Lecture Notes in Computer Science, vol. 1851, Springer, Berlin, 2000, pp. 535-548.]]

Index Terms

Fast periodic correction networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Faster 3-periodic merging networks
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of ...
Breaking the /spl Theta/(nlog/sup 2/ n) barrier for sorting with faults
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

We study the problem of constructing a sorting circuit, network, or PRAM algorithm that is tolerant to faults. For the most part, we focus on fault patterns that are random, e.g., where the result of each comparison is independently faulty with ...
Some minimum merging networks

Let M(m, n) be the minimum number of comparators which constructs an (m, n)-merging network. Batcher's odd-even merge, which is a merging network constructed by his algorithm, provides the best upper bound for M(m, n) to date. Recently Iwata (Inform. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 354, Issue 3

Foundations of computation theory (FCT 2003)

4 April 2006

122 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 04 April 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents