[Libre-soc-bugs] [Bug 1078] svp64 counting sort demo

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=1078

--- Comment #1 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Luke Kenneth Casson Leighton from comment #0)

>     for i = 0 to length(input) - 1 do
>         j = key(input[i])
>         count[j] = count[j] + 1

    svindex on keys
    sv.addi *count, *count, 1 # Indexed on count

>     for i = 1 to k do
>         count[i] = count[i] + count[i - 1]

    sv.add/mr *count+1, *count+1, *count
    (or use parallel prefix sum)

>     for i = length(input) - 1 down to 0 do
>         j = key(input[i])
>         count[j] = count[j] - 1
>         output[count[j]] = input[i]

VF mode, 2 stages:

    svindex on keys
    sv.addi/mrr *count, *count, -1 # Indexed on count
    sv.addi/mrr *countcopy, *count # Indexed only on count

2nd stage:

    svindex on countcopy:
    sv.addi *countcopy, *input, 0 # Indexed on countcopy

first step is doing a histogram. next is cumulative sum of histogram
counts.  then find unique areas. finally copy.

-- 
You are receiving this mail because:
You are on the CC list for the bug.