Routing on meshes in optimum time and with really small queues
- ,
- Jop F. Sibeyn
- University of Colorado Denver,
- University of Warsaw,
- Martin Luther University Halle-Wittenberg
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Related Event
Title
International Parallel and Distributed Processing Symposium, IPDPS 2003
Event type
ConferenceDate
04/22/2003 - 04/26/2003Location
NiceFrance
Abstract
We consider permutation routing problems on 2D and 3D mesh-connected computers with side length n. Our main result is a deterministic online algorithm routing on 2D meshes, operating in worst-case time T = 2n + O(1) and with queue size Q = 3. We also develop offline routing algorithms with performance bounds T = 2n - 1 and Q = 2 for 2D meshes, and T = 3n - 2 and Q = 4 for 3D meshes. We also show that is it possible to route most of the permutations on 2D meshes offline in time T = 2n - 2 with Q = 1.
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Original language
English (US)Article number
1213148Publication milestones
- Published - 01/01/2003
Publication status
Published - 01/01/2003
Publisher
Institute of Electrical and Electronics Engineers Inc.Publication series
- Publication series name: Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
ISBN (Electronic)
0769519261, 9780769519265Publication IDs
- Scopus: 84947289877
Host publication title
Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003Publication metrics
Metrics
SciVal
FWCI
0.27
SciVal
Author count
2
SciVal
citations
3
SciVal
Paper percentile
41
Fractional count
1
Fractional count
0.50
Fractional count
1
Fractional count
0.50
Fractional count
1
Fractional count
1
PlumX, opens in new tab
Citation count
3
Captures
3