| Finding all nearest smaller values on a distributed memory machine | |
| Author: | Jyrki Katajainen |
| Published in: | Proceedings of the Computing: The 2nd Australasian Theory Symposium, Australian Computer Science Communications 18,3, Computer Science Association (Australia) (1996), 100-107 |
| Full text: |  PS (165 kB) |
| Abstract: | Let A = [aj]j=1n 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 aj, j ∈ {1, 2,…, n}, the elements ai and ak such that i = max{h ∈ {1,…, j} ∣ ah < aj} and k = min{h ∈ {j,…, n} ∣ ah < aj}, 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 ∈ {1, 2,…, O(n / log2 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, Ω(log2 n) is a lower bound for the time complexity of the problem with any number of processors and that, on a hypercube, any O(log2 n) algorithm must use Ω(n) processors. |
| Related: |  HTML (Technical report) |
| BibLATEX: | @inproceedings{Kat1996bC,
author = {Jyrki Katajainen},
title = {Finding all nearest smaller values on a distributed memory machine},
booktitle = {Proceedings of the Computing: The 2nd Australasian Theory
Symposium},
series = {Australian Computer Science Communications},
volume = {18},
number = {3},
publisher = {Computer Science Association (Australia)},
year = {1996},
pages = {100--107},
}
|