A parallel algorithm for finding the maximum value

Abstract

A new parallel algorithm for finding the maximum value of a data set is proposed. Execution times are investigated by taking into account the effect of the overhead time of communication for four kinds of interconnection networks; cube connection array, linear array, mesh array, and three-dimensional mesh array. The optimal numbers of processors are derived in the case where the number of processors is less than the number of data. Those are O(N 1 2), O(N 2 3), O(N 3 4), and O(N), respectively, for linear array, mesh array, three-dimensional mesh array, and cube-connected arrays. © 1989.