Finding minimum in PRAM model

Question

Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.

Answer 1

Let us start with a solution using $n$ processors and then we optimize the solution to use $O(n/\log n)$ of them. Assume first that $n$ is a power of $2$, i.e. $2^k$ for some $k \in \mathbb{Z}$. Imagine a perfect binary tree where the leaves are the elements of the array. In each step we will process one level of the tree in a bottom up manner, where for each node in the tree we will compute the minimum of all elements contained in the leaves of its subtree and write this minimum in the node.

In the first step each node represent one element and hence is the minimum of it self. Now in each further step we go one level up in the tree, half of the processors retire and the other half, each will be responsible for one node. Note that the minimum of leaves in a subtree rooted at some node, is the minimum between the minimum of elements in its right subtree and the minimum of elements in its left subtree. Hence, a processor responsible for a node $M$, it only compares the numbers written on the left child and the right child of this node and write the minimum between them in this node. When we reach the top of the tree, we will have exactly one processor that will compare the values written in both children of the root and write the minimum of them in the root.

Since the depth of a perfect binary tree of $2^k$ leaves is exactly $k$, the algorithm finishes in $\log n$ steps. Since we started with $n$ processors and the number of used processors kept cutting down, $n$ processors are enough for the whole job.

Now assuming $n$ is not a power of two, then there is a $k$ such that $n < 2^k < 2n$. Try to prove this claim as an exercise. Now using this claim, given an array of $n$ elements, we can use $2n$ processors to build an array of $2^k$ elements in constant time by adding very large numbers to the array (adding numbers equal to the first number of the array suffice since we are looking for the minimum) and run the algorithm as described above.

Now we optimize the number of processors using a preprocessing technique. Assuming we started with $c \cdot n/ \log n$ processors for some constant $c$ (2 is enough here). Let us start by completing the array into a power of two as above and cut the array into chunks, each of size $\log n$. We will have at most $O(n / \log n)$ of them. Each processor can find the minimum in a chunk sequentially in $O(\log n)$ time. Let us build a new array $A'$ of length $O(n / \log n)$, where the processor responsible for the $i$-th chunk writes the minimum in the $i$-th position of the array. We end up with an array of size $O(n / \log n)$ and with $c \cdot n / \log n$ processors we can proceed as above in $O(\log(n/\log n) = O(\log n)$ steps.

In total we get an algorithm with $O(\log n)$ time and $O(n / \log n)$ processors.