Loading...
Please wait, while we are loading the content...
Matching the bisection bound for routing and sorting on the mesh (extended abstract).
| Content Provider | CiteSeerX |
|---|---|
| Author | Kaufmann, Michael Rajasekaran, Sanguthevar Sibeyn, Jop F. |
| Abstract | In this paper we present randomized algorithms for k-k routing, k-k sorting, and cut through routing on the mesh connected processor array. In these three prob-lems, each processor is assumed to contain k packets at the beginning and k packets are destined for any proces-sor node with k ≥ 1. We give two different algorithms for k-k routing that run in kn2 +o(kn) and k2 n+o(kn) routing steps respectively. We also show that k-k sorting can be accomplished within k2 n + n + o(kn) steps and that cut through routing can be done in kn |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Bisection Bound K-k Sorting K-k Routing Processor Array Proces-sor Node Different Algorithm |
| Content Type | Text |
| Resource Type | Article |
