Optimal number of processors for finding the maximum value on multiprocessor systems
S. Horiguchi, Yoshiharu Shigei · 2003
Models for synchronized parallel computation are described, in which processors are interconnected by networks. These models are used to solve the problem of finding the maximum value, the minimum value, or both values in parallel. The proposed algorithm is based on the binary tree routing scheme. The time complexities are investigated by taking account of the communication overhead. The optimal number of processors for a fixed number of data is analytically obtained. This number depends significantly on the types of interconnection networks. Results are presented for linear, mesh, three-dimensional, and cube-connected arrays. Execution times are investigated and are measured using a cluster multiprocessor system.>