Nimrod Megiddo, Uzi Vishkin
Theoretical Computer Science
A model for synchronized parallel computation is described in which all p processors have access to a common memory. This model is used to solve the problems of finding the maximum, merging, and sorting by p processors. The main results are: 1. Finding the maximum of n elements (1 < p ≤ n) within a depth of O( n p + log logp); (optimal for p ≤ n log log n). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of O( n p + log n) for p ≤ n (optimal for p ≤ n log n), O( logm logp n) for p ≥ n(= O(k) if p = m 1 kn, k > 1). 3. Sorting n elements within a depth of O( n plogn + lognlogp) for p ≤ n, (optimal for p ≤ n log n). O( log2n logp n) + logn) for p ≥ n (= O(k logn) if p = n1+ 1 k, k > 1). The depth of O(klogn) for p = n1+ 1 k processors was also achieved by Hirschberg (Comm. ACM21, No. 8 1978, 657-661) and Preparata IEEE Trans ComputersC-27 (July 1978), 669-673). Our algorithm is substantially simpler. All the elementary operations including allocation of processors to their jobs are taken into account in deriving the depth complexity and not only comparisons. © 1981.
Nimrod Megiddo, Uzi Vishkin
Theoretical Computer Science
Yossi Shiloach
Information Processing Letters
Dorit Naishlos, Joseph Nuzman, et al.
Theory of Computing Systems
Bengt Aspvall, Yossi Shiloach
Linear Algebra and Its Applications