Chin-Laung Lei and Horng-Twu Liaw*
Department of Electrical Engineering
National Taiwan University
Taipei, Taiwan 106, R.O.C.
*Department of Information Management
The World College of Journalism and Communications
Taipei, Taiwan 116, R.O.C.
In this paper, efficient parallel algorithms are proposed to find the majority element, with size n, in shared-memory and message-passing parallel systems. In a shared-memory system, the time complexity of our last proposed algorithmis is O(log n ) by using n/log n processors. Hence, it is cost optimal. Because these proposed algorithms do not require reading from or writing into the same memory location, they can be implemented on an exclusive-read, exclusive-write (EREW) model. In a message-passing system, we take into account the effect of communication time for three kinds of interconnection networks; cube connection array, linear array, and mesh array. Furthermore, even if the only comparisons allowed between elements are tests of equality, we can find a solution using our proposed algorithms.
Keywords: majority element, parallel algorithm, shared-memory system, message-passing system, cube-connection array, linear array, mesh array, selection problem, equality
Received March 19, 1991; revised April 26, 1993.
Communicated by Chin-Chen Chang.