Bug 798 - fix Ripple to use parallel prefix sum rather than a serial gate chain
Summary: fix Ripple to use parallel prefix sum rather than a serial gate chain
Status: CONFIRMED
Alias: None
Product: Libre-SOC's first SoC
Classification: Unclassified
Component: Source Code (show other bugs)
Version: unspecified
Hardware: Other Linux
: --- enhancement
Assignee: Jacob Lifshay
URL:
Depends on:
Blocks:
 
Reported: 2022-04-05 20:45 BST by Jacob Lifshay
Modified: 2022-05-05 05:27 BST (History)
2 users (show)

See Also:
NLnet milestone: ---
total budget (EUR) for completion of task and all subtasks: 0
budget (EUR) for this task, excluding subtasks' budget: 0
parent task for budget allocation:
child tasks for budget allocation:
The table of payments (in EUR) for this task; TOML format:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Comment 2 Jacob Lifshay 2022-04-09 04:07:23 BST 
I implemented both the non-work-efficient and the work-efficient parallel prefix sum algorithms.

I also added code to render the graph of operations done by the algorithms.

graphs in tests:
https://git.libre-soc.org/?p=nmutil.git;a=blob;f=src/nmutil/test/test_prefix_sum.py;h=63aa68ee94c998102f40d3c16ab161c40f08dcb3;hb=7ebe1cc2294de816b2d2809ce84492ae6aecb5d1

I ran out of time today so I'll get to adding more tests and using it in Ripple another day.

Note that Ripple can't actually be used in TestEqualLeadingZeroCount since it's not general enough. prefix_sum is though.
Comment 3 Luke Kenneth Casson Leighton 2022-04-09 06:53:38 BST 
niice, i love them, should work really well with the sphinx ascii-renderer
plugin.  i did some minor whitespace cleanup, {code} {semicolon} {docstring}
looks really good, i feel.

for Ripple do keep that around for a while unless writing a unit test which
then shows equivalence for its replacement, both michael and i were in a
hurry and used higher-up unit tests (unit tests that *use* Ripple),
apologies for that.
Comment 4 Jacob Lifshay 2022-05-05 04:53:52 BST 
Just noticed that both RippleLSB and RippleMSB set start_lsb=True, one of them is wrong.
Comment 5 Luke Kenneth Casson Leighton 2022-05-05 05:04:21 BST 
(In reply to Jacob Lifshay from comment #4)
> Just noticed that both RippleLSB and RippleMSB set start_lsb=True, one of
> them is wrong.

https://git.libre-soc.org/?p=nmutil.git;a=commitdiff;h=d5eb78c004feb45f660e47c34f2aa5203d0475f1

one of these...  MSB one should be False.
Comment 6 Jacob Lifshay 2022-05-05 05:27:06 BST 
(In reply to Luke Kenneth Casson Leighton from comment #5)
> (In reply to Jacob Lifshay from comment #4)
> > Just noticed that both RippleLSB and RippleMSB set start_lsb=True, one of
> > them is wrong.
> 
> https://git.libre-soc.org/?p=nmutil.git;a=commitdiff;
> h=d5eb78c004feb45f660e47c34f2aa5203d0475f1
> 
> one of these...  MSB one should be False.

changed. RippleMSB is not used anywhere (at least couldn't find any other mentions in all the git repos I have on my computer) and has no tests...

commit b5e82ab5d2012b9da8acf4d11169450d70ba4f2e (HEAD -> master, origin/master, origin/HEAD)
Author: Jacob Lifshay <programmerjake@gmail.com>
Date:   Wed May 4 21:24:08 2022 -0700

    fix RippleMSB
    
    TODO: add tests
    
    https://bugs.libre-soc.org/show_bug.cgi?id=798#c5