Parallel algorithms for the all nearest neighbors of binary image on the BSP model
In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n x n binary image on the Bulk-Synchronous Parallel (BSP) model. The BSP model is an asynchronous parallel computing model, where its communication features are abstracted by two parameters L and g: L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth. We propose two parallel algorithms for the ail nearest neighbor problems based on two distance metrics. The first algorithm is for L-p distance, and the second algorithm is for weighted distance. Both two algorithms run in O(n(2)/p + L) computation time and in O(g n/root p + L) communication time using p (1 less than or equal to p less than or equal to n) processors and in O(n(2)/p + (d + L) log p/n/log (d + 1)) computation time and in O(g n/root p + (gd + L) log p/n/log (d+1)) communication time using p (n < p less than or equal to n(2)) processors on the BSP model, for any integer d (1 less than or equal to d less than or equal to p/n).
parallel algorithm all nearest neighbors bsp model