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
Average case analysis of greedy routing algorithms on arrays
Full text PdfPdf (1.07 MB)
Source ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the second annual ACM symposium on Parallel algorithms and architectures table of contents
Island of Crete, Greece
Pages: 2 - 10  
Year of Publication: 1990
ISBN:0-89791-370-1
Author
F. T. Leighton  Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts
Sponsors
IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 39,   Citation Count: 34
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/97444.97448
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
W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987  [doi>10.1109/TC.1987.1676939]
 
2
N.Kahale. Personal Communication, 1990.
 
3
P. Kermani and L. Kleinrock. Virtual cut-through: a new computer communications switching technique. Computer Networks, 3(4):267-286, 1979.
 
4
D. Krizanc , S. Rajasekaran , T. Tsantilas, Optimal routing algorithms for mesh-connected processor arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
 
5
M. Kunde, Routing and sorting on mesh-connected arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
6
M. Kunde , T. Tensi, Multi-packet-routing on mesh connected arrays, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.336-343, June 18-21, 1989, Santa Fe, New Mexico, United States  [doi>10.1145/72935.72971]
7
T. Leighton , F. Makedon , I. G. Tollis, A 2n-2 step algorithm for routing in an nxn array with constant size queues, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.328-335, June 18-21, 1989, Santa Fe, New Mexico, United States  [doi>10.1145/72935.72970]
8
J. Y. Ngai , C. L. Setiz, A framework for adaptive routing in multicomputer networks, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.1-9, June 18-21, 1989, Santa Fe, New Mexico, United States  [doi>10.1145/72935.72936]
9
L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States  [doi>10.1145/800076.802479]

CITED BY  34
Andrei Broder , Eli Upfal, Dynamic deflection routing on arrays (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.348-355, May 22-24, 1996, Philadelphia, Pennsylvania, United States
Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001
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
Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States
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
Kazuo Iwama , Eiji Miyano, A (2.954 + ε)n oblivious routing algorithm on 2D meshes, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.186-195, July 09-13, 2000, Bar Harbor, Maine, United States
Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States
Claire Kenyon , Yuval Rabani , Alistair Sinclair, Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.351-358, January 28-30, 1996, Atlanta, Georgia, United States
Costas Busch , Maurice Herlihy , Roger Wattenhofer, Routing without flow control, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.11-20, July 2001, Crete Island, Greece
Gustavo D. Pifarré , Luis Gravano , Sergio A. Felperin , Jorge L. C. Sanz, Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.278-290, July 21-24, 1991, Hilton Head, South Carolina, United States
Pablo E. Berman , Luis Gravano , Gustavo D. Pifarré , Jorge L. C. Sanz, Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.3-12, June 29-July 01, 1992, San Diego, California, United States
José G. Delgado-Frias , Jabulani Nyathi , Laxmi Bhuyan, A wave-pipelined router architecture using ternary associative memory, Proceedings of the 10th Great Lakes symposium on VLSI, p.67-70, March 02-04, 2000, Chicago, Illinois, United States
Andrei Z. Broder , Alan M. Frieze , Eli Upfal, A general approach to dynamic packet routing with bounded buffers, Journal of the ACM (JACM), v.48 n.2, p.324-349, March 2001
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
Sergio Felperin , Prabhakar Raghavan , Eli Upfal, A Theory of Wormhole Routing in Parallel Computers, IEEE Transactions on Computers, v.45 n.6, p.704-713, June 1996
Torsten Suel, Improved bounds for routing and sorting on multi-dimensional meshes, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.26-35, June 27-29, 1994, Cape May, New Jersey, United States
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
Jop F. Sibeyn, Faster deterministic sorting through better sampling, Theoretical Computer Science, v.290 n.3, p.1829-1850, 3 January 2003
Michael Mitzenmacher, Bounds on the greedy routing algorithm for array networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.346-353, June 27-29, 1994, Cape May, New Jersey, United States
S. A. Felperin , L. Gravano , G. D. Pifarré , J. L. C. Sanz, Fully-adaptive routing: packet switching performance and wormhole algorithms, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.654-663, November 18-22, 1991, Albuquerque, New Mexico, United States
Uriel Feige, Nonmonotonic phenomena in packet routing, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.583-591, May 01-04, 1999, Atlanta, Georgia, United States
Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.162-169, June 24-26, 1996, Padua, Italy
Nabil Kahale , Tom Leighton, Greedy dynamic routing on arrays, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.558-566, January 22-24, 1995, San Francisco, California, United States
Douglas H. Summerville , José G. Delgado-Frias , Stamatis Vassiliadis, A Flexible Bit-Pattern Associative Router for Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.477-485, May 1996
Q. P. Gu , J. Gu, Algorithms and Average Time Bounds of Sorting on a Mesh-Connected Computer, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.308-315, March 1994
Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001
Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada
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
Luis Gravano , Gustavo D. Pifarré , Pablo E. Berman , Jorge L. C. Sanz, Adaptive Deadlock- and Livelock-Free Routing with All Minimal Paths in Torus Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.12, p.1233-1251, December 1994
G. D. Pifarré , L. Gravano , S. A. Felperin , J. L. C. Sanz, Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.247-263, March 1994
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
Eric Fleury , Pierre Fraigniaud, A General Theory for Deadlock Avoidance in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.626-638, July 1998
Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Distributed Computing, v.10 n.4, p.189-197, July 1997
Ronald I. Greenberg , Hyeong-Cheol Oh, Universal Wormhole Routing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.3, p.254-262, March 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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: Store and forward networks

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


General Terms:
Algorithms

Collaborative Colleagues:
F. T. Leighton: 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