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
Multi-packet-routing on mesh connected arrays
Full text PdfPdf (735 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: 336 - 343  
Year of Publication: 1989
ISBN:0-89791-323-X
Authors
M. Kunde  Institut für Informatik, TU München, Arcisstr. 21, D-8000 München 2
T. Tensi  Institut für Informatik, TU München, Arcisstr. 21, D-8000 München 2
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): 13,   Citation Count: 4
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.72971
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
Dharma P Agrawal , Virendra K Janakiram , Girish C Pathak, Evaluating the performance of multicomputer configurations, Computer, v.19 n.5, p.23-37, May 1986
 
2
M. Kunde, Optimal sorting on multi-dimensionally mesh-connected computers, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.408-419, February 1987, Passau, Germany
 
3
[KND88a] Kunde, M.: Routing and Sorting on Mesh-Connected Arrays, in: J. H. Reif (ed.): VLSI Algorithms and Architectures, Proceedings of the 3rd AWOC 88, LNCS 319, pp. 423-433.
 
4
M. Kunde, Parallel routing on multi-dimensional grids of processors, Proceedings of the conference on CONPAR 88, p.687-694, October 1989, UMIST, Manchester, United Kingdom
 
5
D. Krizanc , S. Rajasekaran , T. Tsantilas, Optimal routing algorithms for mesh-connected processor arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
 
6
[LMT89] Leighton, T., Makedon, F., Tollis, I.: A 2n - 2 Step Algorithm for Routing in an n × n Array With Constant Size Queues, these proceedings.
 
7
[MSS86] Ma, Y., Sen, S., Scherson, I. D.: The distance bound for sorting on mesh-connected processor arrays is tight, Proceedings FOCS 86, pp. 255-263.
 
8
[NS79] Nassimi, D., Sahni, S.: Bitonic sort on a mesh-connected parallel computer, IEEE Trans. Comput. C-28 (1979), pp. 2-7.
 
9
Sanguthevar Rajasekaran , Thanasis Tsantilas, An optimal randomized routing algorithm for the mesh and a class of efficient mesh-like routing networks, Proc. of the seventh conference on Foundations of software technology and theoretical computer science, p.226-241, December 1987, Pune, India
10
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]
 
11
Quentin F. Stout , Bruce Wagar, Intensive hypercube communication. Prearranged communication in link-bound machines, Journal of Parallel and Distributed Computing, v.10 n.2, p.167-181, Oct. 1990  [doi>10.1016/0743-7315(90)90026-L]
12
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]
13
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  4
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
S. N. Bhatt , G. Pucci , A. Ranade , A. L. Rosenberg, Scattering and Gathering Messages in Networks of Processors, IEEE Transactions on Computers, v.42 n.8, p.938-949, August 1993
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
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:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling; Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations


General Terms:
Algorithms, Design, Performance

Collaborative Colleagues:
M. Kunde: colleagues
T. Tensi: 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