Parallel algorithms for the all nearest neighbors of binary image on the bulk-synchronous parallel model

Parallel algorithms for the all nearest neighbors of binary image on the bulk-synchronous parallel model

0.00 Avg rating0 Votes
Article ID: iaor2001952
Country: Japan
Volume: E83-D
Issue: 1
Start Page Number: 151
End Page Number: 158
Publication Date: Feb 2000
Journal: IEICE Transactions on Information and Systems
Authors: , , , ,
Keywords: computational analysis: parallel computers, optimization
Abstract:

In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n × 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 all nearest neighbor problems based on two distance metrics. The first algorithm is for Lp distance, and the second algorithm is for weighted distance. Both algorithms run in O[(n2/p) + L] computation time and in O[g(n/√(p)) + L] communication time using p (1 ≤ p ≤ n) processors and in O[(n2/p) + (d + L) (log (p/n)/log(d+1))] computation time and in O[g (n/√(p)) + (gd + L) (log (p/n)/log(d+1))] communication time using p (n < pn2) processors on the BSP model, for any integer d (1 ≤ d ≤ p/n).

Reviews

Required fields are marked *. Your email address will not be published.