ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
A 2n-2 step algorithm for routing in an nxn array with constant size queues
Full text PdfPdf (824 KB)
Source ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the first annual ACM symposium on Parallel algorithms and architectures table of contents
Santa Fe, New Mexico, United States
Pages: 328 - 335  
Year of Publication: 1989
ISBN:0-89791-323-X
Authors
T. Leighton  Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
F. Makedon  Department of Computer Science, University of Texas at Dallas, Richardson, TX
I. G. Tollis  Department of Computer Science, University of Texas at Dallas, Richardson, TX
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 4,   Downloads (12 Months): 19,   Citation Count: 24
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/72935.72970
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990  [doi>10.1109/12.53599]
 
2
Danny Krizanc , Sanguthevar Rajasekaran , Thanasis Tsantilas, Optimal Routing Algorithms for Mesh-Connected Processor Arrays, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.411-422, June 28-July 01, 1988
 
3
3) M. Kunde, "Routing and Sorting on Mesh-Connected Arrays," VLSI Algorithms and Architectures: Proc. AWOC '88, Lecture Notes in Computer Science #319, Springer-Verlag, pp. 423-433.
4
C P Schnorr , A Shamir, An optimal sorting algorithm for mesh connected computers, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.255-263, May 28-30, 1986, Berkeley, California, United States  [doi>10.1145/12130.12156]
5
C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977  [doi>10.1145/359461.359481]

CITED BY  24
Christos Kaklamanis , Danny Krizanc , Satish Rao, Simple path selection for optimal routing on processor arrays, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.23-30, June 29-July 01, 1992, San Diego, California, United States
Stephen Alstrup , Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Direct routing on trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.342-349, January 25-27, 1998, San Francisco, California, United States
Christos Kaklamanis , Danny Krizanc , Lata Narayanan , Thanasis Tsantilas, Randomized sorting and selection on mesh-connected processor arrays (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.17-28, July 21-24, 1991, Hilton Head, South Carolina, United States
F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece
Christos Kaklamanis , Danny Krizanc, Optimal sorting on mesh-connected processor arrays, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.50-59, June 29-July 01, 1992, San Diego, California, United States
Michael Kaufmann , Jop F. Sibeyn , Torsten Suel, Derandomizing algorithms for routing and sorting on meshes, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.669-679, January 23-25, 1994, Arlington, Virginia, United States
Fillia Makedon , Adonios Simvonis, Many-to-one packet routing on the mesh, Proceedings of the 19th annual conference on Computer Science, p.280-288, April 1991, San Antonio, Texas, United States
M. Brady , D. Brown , P. McGuinness, Disjoint paths through a 3-dimensional grid, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.224-233, July 02-06, 1990, Island of Crete, Greece
Ralf Rehrmann , Burkhard Monien , Reinhard Lüling , Ralf Diekmann, On the communication throughput of buffered multistage interconnection networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.152-161, June 24-26, 1996, Padua, Italy
Donald D. Chinn , Tom Leighton , Martin Tompa, Minimal adaptive routing on the mesh with bounded queue size, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.354-363, June 27-29, 1994, Cape May, New Jersey, United States
Christos Kaklamanis , Danny Krizanc , Satish Rao, Hot-potato routing on processor arrays, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.273-282, June 30-July 02, 1993, Velen, Germany
Michael Kaufmann , Sanguthevar Rajasekaran , Jop F. Sibeyn, Matching the bisection bound for routing and sorting on the mesh, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.31-40, June 29-July 01, 1992, San Diego, California, United States
Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico
M. Herbordt , C. Weems , J. Corbett, Message-passing algorithms for a SIMD torus with coteries, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.11-20, July 02-06, 1990, Island of Crete, Greece
Manfred Kunde, Balanced routing: towards the distance bound on grids, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.260-271, July 21-24, 1991, Hilton Head, South Carolina, United States
Sanguthevar Rajasekaran, Mesh Connected Computers with Fixed and Reconfigurable Buses: Packet Routing and Sorting, IEEE Transactions on Computers, v.45 n.5, p.529-539, May 1996
Robert Cypher , Luis Gravano, Storage-Efficient, Deadlock-Free Packet Routing Algorithms for Torus Networks, IEEE Transactions on Computers, v.43 n.12, p.1376-1385, December 1994
Alan Roberts , Antonios Symvonis, A General Method for Deflection Worm Routing on Meshes Based on Packet Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.781-789, August 1997
Antonios Symvonis , Jonathon Tidswell, An Empirical Study of Off-Line Permutation Packet Routing on Two-Dimensional Meshes Based on the Multistage Routing Method, IEEE Transactions on Computers, v.45 n.5, p.619-625, May 1996
F. Makedon , A. Symvonis, An Efficient Heuristic for Permutation Packet Routing on Meshes with Low Buffer Requirements, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.270-276, March 1993
Qian-Ping Gu , Jun Gu, Two Packet Routing Algorithms on a Mesh-Connected Computer, IEEE Transactions on Parallel and Distributed Systems, v.6 n.4, p.436-440, April 1995
Daniel Golovin , Anupam Gupta , Bruce M. Maggs , Florian Oprea , Michael K. Reiter, Quorum placement in networks: minimizing network congestion, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
Martin C. Herbordt , Charles C. Weems , James C. Corbett, Message-passing algorithms for a SIMD torus with coteries, ACM SIGARCH Computer Architecture News, v.19 n.1, p.69-78, March 1991
Kevin Chiew , Yingjiu Li, Multistage off-line permutation packet routing on a mesh: an approach with elementary mathematics, Journal of Computer Science and Technology, v.24 n.1, p.175-180, January 2009

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**


General Terms:
Algorithms, Design, Performance, Theory

Collaborative Colleagues:
T. Leighton: colleagues
F. Makedon: colleagues
I. G. Tollis: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player