DocumentCode :
3296556
Title :
Routing algorithms on a mesh-connected computer
Author :
Gu, Qian Ping ; Gu, Jun
Author_Institution :
Dept. of Electr. & Comput. Eng., Calgary Univ., Alta., Canada
fYear :
1992
fDate :
19-21 Oct 1992
Firstpage :
524
Lastpage :
527
Abstract :
The authors present two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with a queue size of 28, solves the 1-1 routing problem on an n×n mesh-connected computer in 2n+O(1) steps. This improves the previous result of queue size 75. The second algorithm solves the problem in 2n-2 steps with queue size 12t s/s where ts is the time for sorting an s×s mesh into a row major order for all s⩾1. This result improves the previous result of size 18.67 ts/s. Both algorithms have important applications in reducing the hardware cost on a mesh-connected computer
Keywords :
multiprocessor interconnection networks; parallel algorithms; parallel processing; 1-1 routing problems; hardware cost; mesh-connected computer; queue size; routing algorithms; sorting; Algorithm design and analysis; Application software; Concurrent computing; Costs; Gallium arsenide; Hardware; Neck; Parallel algorithms; Routing; Sorting;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Frontiers of Massively Parallel Computation, 1992., Fourth Symposium on the
Conference_Location :
McLean, VA
Print_ISBN :
0-8186-2772-7
Type :
conf
DOI :
10.1109/FMPC.1992.234863
Filename :
234863
Link To Document :
بازگشت