Sorting on PRAMs with reconfigurable buses (Q1198059): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4773298 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3798228 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal bounds for decision problems on the CRCW PRAM / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improved deterministic parallel integer sorting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Constant time sorting on a processor array with a reconfigurable bus system / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:35, 16 May 2024
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
0 references