Scalable parallel list ranking of image edges on fine-grained machines

We present analytical and experimental results for fine-grained list ranking algorithms, with the objective of examining how the locality properties of image edge lists can be used to improve the performance of this highly data-dependent operation. Starting with Wyllie´s (1979) algorithm and Anderson and Miller´s (1990) randomized algorithm as bases, we use the spatial locality of edge links to derive scalable algorithms designed to exploit the characteristics of image edges. Tested on actual and synthetic edge data, this approach achieves significant speedup on the MasPar MP-1 and MP-2, compared to the standard list ranking algorithms. The modified algorithms exhibit good scalability and are robust across a wide variety of images