Parallel Algorithms and Architectures for Discrete Relaxation Technique

Abstract

Three parallel implementations based on three alternate sequential approaches are presented. The first design is a systolic array based on the known sequential method. An execution time of O(n/sup 2/m/sup 2/) is achieved with nm processing elements (PEs), with each PE composed of simple logic elements. The second design employs broadcast bus feature to speed up the execution of an alternate sequential method. Linear speedup is achieved by using nm processing elements. The sequential method has an execution time of O(n/sup 2/m/sup 2/) and the proposed parallel design runs in O(nm) time. The third design is a modified approach which is well suited for implementation on general-purpose machines. These designs achieve superior performance compared with the existing designs in terms of their simplicity, execution time, and domain of applications. Using the proposed designs, an efficient parallel implementation of stereo matching based on linear segments as primitives is derived.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>