JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 4,79-94 ( 1987) Vision Algorithms for Hypercube Machines*

Several commercial hypercube parallel processors with the potential to deliver mas-sive parallelism cost-effectively have been announced recently. They open the door to a wide variety of application areas that could benefit from parallelism. Computer vision is one of these application areas. This paper develops a general model for hyper-cube machines, and uses it to show how vision algorithms can be executed on hyper-cubes. In particular, the steps in the problem of thick-film inspection are used as a concrete example. The time needed to complete a typical inspection is used to demon-strate the performance of hypercube machines. Experimental results from a hyper-cube machine illustrate the potential use of such machines. Q 1987 AC&III & press, I~C. 1. INTR~DUCD~N Simple computer vision (CV) problems such as inspecting a printed circuit can easily require the processing of 10 Mbyte of data in a few seconds. If the inspection task is at all complex the processing power required runs into billions of operations per second. Therefore, in practice only a reduced ver-sion of such problems is implemented. The required level of processing power is possible only with a high degree of parallelism. In the past there have been numerous proposals for massively parallel ma-chines. Examples of such machines include the Illiac IV [2], which consists of 256 processors organized as four 8 X 8 arrays; Cytocomputers [ 171, which employ a number of identical processing elements that are cascaded in series to form a pipeline of processing stages; the Massively Parallel Processor (MPP) [3], which employs a 128 X 128 array of processors interconnected in a nearest-neighbor topology; the Pyramid Machine [22], in which th