Abstract | ||
---|---|---|
We consider the problem of routing packets on an n \Theta \Delta \Delta \Delta \Theta n MIMDmesh-connected array of processors augmented with row and column buses.We give lower bounds and randomized algorithms for the problem of routing k-permutations (where each processor is the source and destination ofexactly k packets) on a d-dimensional mesh with buses, which we call the(k; d)-routing problem.We give a general class of "hard" permutations which we use to provelower bounds for the... |
Year | DOI | Venue |
---|---|---|
1997 | 10.1007/PL00009164 | Algorithmica |
Keywords | Field | DocType |
Key words. Parallel computation,Algorithms,Packet routing,Meshes,Buses,Lower bounds,Randomization,Coloring. | Randomized algorithm,Polygon mesh,Dynamic Source Routing,Computer science,Network packet,Parallel computing,Packet routing,MIMD | Journal |
Volume | Issue | ISSN |
18 | 3 | 0178-4617 |
Citations | PageRank | References |
6 | 0.49 | 20 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael Kaufmann | 1 | 361 | 25.45 |
Rajeev Raman | 2 | 1550 | 110.81 |
Jop F. Sibeyn | 3 | 583 | 60.47 |