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 algorithm and Anderson & Miller's 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. 1 Introduction List ranking is a fundamental operation in many algorithms for graph theory and computer vision problems. Given a linked lists of n cells, list ranking determines the distance of each cell from the head of the list. On a sequential machine, this problem ca..