Finding all nearest smaller values on a distributed memory machine

Jyrki Katajainen
Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen East, Denmark
jyrki@diku.dk

Abstract

Let $A = [a_j]_{j=1}^{n}$ be a sequence of $n$ elements drawn from some totally ordered set. In the all nearest smaller values problem the task is to find for each $a_j, j \in \{1,2,\ldots,n\}$, the elements $a_i$ and $a_k$ such that $i=\max\{h\in \{1,\ldots,j\} \mid a_h < a_j\}$ and $k=\min\{h\in \{j,\ldots,n\} \mid$ $a_h < a_j\}$, if such elements exist. In this paper it is shown that this problem can be solved in $O(n/q)$ time and $O(n)$ space with $q$ processors on a distributed memory machine, provided that $q \in \{1,2,\ldots,O(n/\log_2 n)\}$. More precisely, the machine considered consists of $q$ processors and $q$ memory modules connected by a communication network, which allows every processor to access any memory module in constant time if only every memory module is accessed by at most one processor at a time. The result proved complements the earlier known results showing that, on a CREW PRAM, $\Omega(\log_2 n)$ is a lower bound for the time complexity of the problem with any number of processors and that, on a hypercube, any $O(\log_2 n)$ algorithm must use $\Omega(n)$ processors.

Conference Home Page