Applications of BSR model of computation for subsegment problems

摘要

We investigate the BSR (Broadcast with Selective Reduction) model of computation for problems related with subsegments (basically, inputs are arrays containing elements and outputs are "some contiguous part" of inputs), namely the MSSP (Maximal Sum Subsegment Problem, 1D and 2D versions) and LIS (Longest Increasing Sequence). The BSR model of computation introduced by Akl et al. (1989) is more powerful than any CRCW PRAM and yet requires no more resources for implementation than an EREW PRAM. In our solution, we need to add a new reduction operator in the basic brick of the interconnection unit. The implementation of this operator is straightforward and does not require more resource than those in the original BSR implementation; no fundamental architectural piece of the basic model is changed.