Sorting numbers using limited systolic coprocessors (Q579941)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sorting numbers using limited systolic coprocessors |
scientific article |
Statements
Sorting numbers using limited systolic coprocessors (English)
0 references
1987
0 references
The problem of sorting numbers on a random access machine augmented by systolic coprocessors with a small number of processing elements is discussed. A probabilistic algorithm is presented sorting n given numbers in time 0(n log n/log p(n)) with probability at least \(e^{-16/(3 \log^ 2 n)}\to 1\), assuming that the number p(n) of processing elements satisfies \(n\geq p(n)\geq 9 \log^ 2 n\).
0 references
parallel computation
0 references
sorting
0 references
random access machine
0 references
systolic coprocessors
0 references
probabilistic algorithm
0 references