DocumentCode :
1426137
Title :
Solving fundamental problems on sparse-meshes
Author :
Sibeyn, Jop F.
Author_Institution :
Max-Planck-Inst. fur Inf., Saarbrucken, Germany
Volume :
11
Issue :
12
fYear :
2000
fDate :
12/1/2000 12:00:00 AM
Firstpage :
1324
Lastpage :
1332
Abstract :
A sparse-mesh, which has PUs on the diagonal of a two-dimensional grid only, is a cost effective distributed memory machine. Variants of this machine have been considered before, but none are as simple and pure as a sparse-mesh. Various fundamental problems (routing, sorting, list ranking) are analyzed, proving that sparse-meshes have great potential. It is shown that on a two-dimensional n×n sparse-mesh, which has n PUs, for h=ω(nε·log n), h-relations can be routed in (h+o(h))/ε steps. The results are extended for higher dimensional sparse-meshes. On a d-dimensional n x···x n sparse-mesh, with h=ω(nε ·log n), h-relations are routed in (6·(d-1)/ε-4)·(h+o(h)) steps
Keywords :
multiprocessor interconnection networks; parallel algorithms; distributed memory machine; list-ranking; meshes; networks; parallel computation; routing; sorting; sparse-meshes; Computer Society; Computer networks; Concurrent computing; Costs; Delay; Hardware; Hypercubes; Routing; Sorting; Very large scale integration;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.895796
Filename :
895796
Link To Document :
بازگشت