Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re: Fast sliding submatrix sums with PDL (inspired by PWC 248 task 2)

by etj (Curate)
on Feb 15, 2024 at 20:45 UTC ( [id://11157717]=note: print w/replies, xml ) Need Help??

in reply to Fast sliding submatrix sums with PDL (inspired by PWC 248 task 2)

A belated note. This:
pp_def('sms_WxH_pdlpp_4loops', Pars => 'a(m,n); [o]b(p,q);', OtherPars => 'PDL_Indx par_sm_w; PDL_Indx par_sm_h;', RedoDimsCode => '$SIZE(p) = $SIZE(m) - $COMP(par_sm_w) + 1; $SIZE(q) = $SIZE(n) - $COMP(par_sm_h) + 1;', Code => ' PDL_Indx i, j, k, l, w, h, W, H; w = $COMP(par_sm_w); h = $COMP(par_sm_h); W = $SIZE(m); H = $SIZE(n); for (i = 0; i < H - h + 1; i++) { for (j = 0; j < W - w + 1; j++) { for (k = 0; k < w; k++) { for (l = 0; l < h; l++) { $b(p=>j, q=>i) += $a(m=>j+k, n=>i+l); } } } } ', );
Can use PP features much better (untested, illustrative):
pp_def('sms_WxH_pdlpp_4loops', Pars => 'a(m,n); [o]b(p,q);', OtherPars => 'PDL_Indx par_sm_w => w; PDL_Indx par_sm_h => h;', RedoDimsCode => '$SIZE(p) = $SIZE(m) - $SIZE(w) + 1; $SIZE(q) = $SIZE(n) - $SIZE(h) + 1;', Code => 'loop(q,p,w,h) %{ $b() += $a(m=>p+w, n=>q+h); %}', );
Features used above: OtherPars can set $SIZE of dims not otherwise used. When something is a $SIZE, you can loop() over it. If an index (named dim) is indexed by a variable of the same name, it can be omitted (as for $b() above). Obviously I used the fact that you can give several loops at once, which is very neat. Finally, your loop conditions were recalculating the expressions used to set $SIZE(p) etc.

Looking at the loop(), I suspect you want to switch the w and h loops to do everything as much as possible on the fastest-moving dimension. This algorithm would probably benefit a lot from tiling for maximum cache-hitting, which should probably become a proper PP feature. If someone wants to open a PDL issue with suggestions as to what the syntax would look like, it will probably get implemented and used on matmult.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11157717]
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others examining the Monastery: (2)
As of 2024-06-25 01:12 GMT
Find Nodes?
    Voting Booth?

    No recent polls found

    erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.