Title :
Optimal number of processors for finding the maximum value on multiprocessor systems
Author :
Horiguchi, Susumu ; Shigei, Y.
Author_Institution :
Dept. of Inf. Sci., Tohoku Univ., Sendai, Japan
Abstract :
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
Keywords :
multiprocessor interconnection networks; parallel algorithms; parallel machines; trees (mathematics); 3-D arrays; binary tree routing scheme; cluster multiprocessor system; communication overhead; cube-connected arrays; interconnection networks; linear arrays; maximum value; mesh arrays; minimum value; synchronized parallel computation; time complexities; Binary trees; Computer applications; Concurrent computing; Information science; Multiprocessing systems; Multiprocessor interconnection networks; Parallel algorithms; Parallel processing; Very large scale integration; Writing;
Conference_Titel :
Computer Software and Applications Conference, 1988. COMPSAC 88. Proceedings., Twelfth International
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-0873-0
DOI :
10.1109/CMPSAC.1988.17192
