SCALABLE PARALLEL IMPLEMENTATIONS OF LIST RANKING ON FINE-GRAINED MACHINES

Citation
Jn. Patel et al., SCALABLE PARALLEL IMPLEMENTATIONS OF LIST RANKING ON FINE-GRAINED MACHINES, IEEE transactions on parallel and distributed systems, 8(10), 1997, pp. 1006-1018
Citations number
12
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
ISSN journal
10459219
Volume
8
Issue
10
Year of publication
1997
Pages
1006 - 1018
Database
ISI
SICI code
1045-9219(1997)8:10<1006:SPIOLR>2.0.ZU;2-D
Abstract
We present analytical and experimental results for fine-grained list r anking algorithms. We compare the scalability of two representative al gorithms on random lists, then address the question of how the localit y properties of image edge lists can be used to improve the performanc e of this highly data-dependent operation. Starting with Wyllie's algo rithm and Anderson and Miller's randomized algorithm as bases, we use the spatial locality of edge links to derive scalable algorithms desig ned to exploit the characteristics of image edges. Tested on actual an d synthetic edge data, this approach achieves significant speedup on t he MasPar MP-I and MP-2, compared to the standard list ranking algorit hms. The modified algorithms exhibit good scalability and are robust a cross a wide variety of image types. We also show that load balancing on fine grained machines performs well only for large problem to machi ne size ratios.