Algorithms for finding maximum and selecting median on a processor array with separable global buses
Citations Over Time
Abstract
Abstract A problem has been considered in which the maximum among N data should be determined by providing a global bus in a processor array. As a solution to this problem, various kinds of global bus configurations have been proposed from the viewpoint of improving the computation time. This paper considers the processor array with global buses, which includes several switching units and can be separated by the switching control from the processors. Parallel algorithms are constructed which can solve efficiently the semigroup computation such as maximum determination and the median selection problems. The computational complexity of the proposed algorithm is evaluated to indicate that the proposed method has an asymptotically desirable property. Furthermore, to verify that the separable global buses can be embedded efficiently in a VLSI chip, the area‐time complexity is evaluated as a performance measure for the VLSI circuit. Comparing the result with the case of the processor arrays with the traditional global bus configuration, the proposed algorithms are shown to be more VLSI‐oriented.