Fundamental data movement operations and its applications on a hyper-bus broadcast network

A hyper-bus broadcast network (HBBN) consists of processors only sharing by some global buses, and there are no local links between processors. Based on such an architecture, we will exploit several efficient time parallel al gorithms for solving the well-known fundamental data movement problems whic h had been extensively studied by researchers and widely applied to the fie ld of image processing, digitized geometry and computer graphics. These inc lude the leftmost one problem, the prefix maxima/minima problem, the m-cont our problem, the all nearest neighbor problem and the all nearest smaller v alues problem, respectively. Note that the proposed algorithms not only can be implemented on the HBBN but also can be easily modified to run on other broadcast-based networks with the same time and processor complexities. (C ) 1999 Elsevier Science B.V. All rights reserved.