An Efficient Algorithm for the Nearest Smallers Problem on Distributed Shared Memory Systems with Applications

We present a simple and efficient algorithm for the nearest smallers problem (NSP), [l]) on a distributed shared memory (DSM) system with applications to problems from diverse areas. We adopt the block distributed memory (BDM) model of computation as described an [2]. To the best of our knowledge this is the first known algorithm for the NSP on DSM systems. Since the NSP is fundamental in many problems, a solution for it on DSM systems implies DSM-based solutions for a variety of problems in diverse areas as discussed in this paper. Parallel algorithms known so far for the NSP are based on shared memory systems [l] and are therefore less scalable than our algorith