Sorting on PRAMs with reconfigurable buses (Q1198059)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sorting on PRAMs with reconfigurable buses |
scientific article |
Statements
Sorting on PRAMs with reconfigurable buses (English)
0 references
16 January 1993
0 references
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.
0 references
reconfigurable bus systems
0 references
EREW B-PRAM
0 references
sorting
0 references