Sorting on PRAMs with reconfigurable buses (Q1198059)

We propose a new model of computation called the B-PRAM, which is a PRAM augmented with reconfigurable buses that provide additional channels of communication. We prove that the OR of \(n\) bits can be computed on an EREW B-PRAM in \(O(1)\) time, thus showing that the addition of reconfigurable buses makes the model strictly more powerful that the CREW PRAM. We also show that \(n\) \(m=O(\log n)\)-bit numbers can be sorted (integer sorting) in: (i) \(O(\log n)\) time on an EREW B-PRAM with \(n/\log n\) processors and \(O(n^ \varepsilon\)) buses, for any arbitrarily small constant \(\varepsilon>0\); (ii) \(O(\log n/\log\log n)\) time on a Common CRCW B-PRAM with \({{n\log\log n}\over {\log n}}\) processors and \(O(n^ \varepsilon)\) buses, for any arbitrarily small constant \(\varepsilon>0\). The above results for integer sorting are the best possible for the PRAM and have not been achieved.