Deterministic permutation routing on meshes
- Bogdan S. Chlebus(corresponding author),
- Michael Kaufmann,
- Jop F. Sibeyn
- University of Warsaw
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Related Event
Title
Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
Event type
ConferenceDate
12/01/1993 - 12/04/1993Location
Dallas, TX, USA
Abstract
We present new deterministic algorithms for routing permutations on a two-dimensional n×n MIMD mesh. One algorithm runs in the optimal time 2·n-2, while the maximal number of packets stored in a processing unit is bounded to 81. Another algorithm runs in near-optimal time, 2·n+O(1), and has maximal queue length only 31.
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Original language
English (US)Pages from-to (Number of pages)
Pages 814-821 (8 pages)Publication milestones
- Published - 12/01/1993
Publication status
Published - 12/01/1993
Publisher
Publ by IEEEPublication series
- Publication series name: Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
ISBN (Print)
081864222XPublication IDs
- Scopus: 0027885682
Host publication title
Proceedings of the 5th IEEE Symposium on Parallel and Distributed ProcessingAccess to documents
Publication metrics
Metrics
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
PlumX
Citation count
10