bugGNU Octave - Bugs: bug #65413, Missing function: pagesvd

 
 

bug #65413: Missing function: pagesvd

Submitter:  None
Submitted:  Mon 04 Mar 2024 06:41:40 PM UTC
   
 
Category:  Octave Function Severity:  1 - Wish
Priority:  5 - Normal Item Group:  Feature Request
Status:  Patch Submitted Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 16 Mar 2024 07:36:16 PM UTC, comment #9: 

OpenBLAS implementations are internally parallelized, but it doesn't help much with small matrices. Turning off the internal OpenBLAS parallelization - openblas_set_num_threads(1) - and using explicit OpenMP parallel loops means each SVD is done on a single core.

For the use cases it is meant for, it's a big win.

>> A=rand(50,50,100000);
>> tic;[U S V]=pagesvd(A);toc
Elapsed time is 4.410267 seconds.

>>
>> A=rand(50,50);
>> tic;for k=1:100000;[U S V]=svd(A);end;toc
Elapsed time is 64.020166 seconds.


Anonymous
Fri 15 Mar 2024 09:13:43 PM UTC, comment #8: 

but wouldn't that be restricted to parallel performance of the operation on a single 'page' of the array?  A quick search on the openblas svd api just mentioned operation on a matrix. is anything other than calling for separate svd calculations per page possible then within that framework?

Nicholas Jankowski <nrjank>
Group Member
Fri 15 Mar 2024 08:55:22 PM UTC, comment #7: 

At its core, the SVD calculation uses BLAS, which is often OpenBLAS, and that can already take advantage of parallel execution.  So it's not clear to me that explicitly using threads to execute separate SVD calculations for each page of an N-d array would be helpful if OpenBLAS is already using multiple cores/threads efficiently.

John W. Eaton <jwe>
Group administrator
Fri 15 Mar 2024 08:30:00 PM UTC, comment #6: 

mcode could handle a 'parfor' implementation of the paged functions. it would have no effect right now and would just be to establish compatible implementation because parfor exists pretty much as just a wrapper to for.  But if parallel pools are enabled in core octave it would be in place to take advantage of that.

So, syntax compatibility with potential future parallelization could be written now fairly quickly.  Actual implementation will need someone to put a compiled solution together, and yes ideally that would include some sort of parallelized code.

Nicholas Jankowski <nrjank>
Group Member
Fri 15 Mar 2024 07:58:09 PM UTC, comment #5: 

Implementing as an m-file can't capture the important feature of parallelizing individual SVD calls onto single cores. This is what gives the (rather large) speedup.

Anonymous
Thu 07 Mar 2024 06:53:33 PM UTC, comment #4: 

There is a similar request for improvement of the movXXX functions.  These all depend on a common function called movfun() which is an m-file.  Promoting movfun() to a C++ function to take advantage of fast for loops, while leaving individual functions like movemean, movmax as m-files would be a good architecture.

I think jwe's suggestion in comment #2 to have a similar architecture with a pagefun() function that is called by m-files which do the work of validating inputs and providing a place to put a docstring is a good one.

And yes, performance of for loops for these sorts of functions is very bad.

Rik <rik5>
Group administrator
Thu 07 Mar 2024 12:05:19 AM UTC, comment #3: 

Some of those would be fairly easy to vectorize, most others less so. All of them can be simply implemented as for loops of the underlying function over dim3 to achieve compatibility, but even with preallocation that would probably have rather terrible performance in m code.  I think for efficiency any that are already compiled functions would probably be best ‘paged’ as compiled for loops.  (Built in C code, not mex)

Nicholas Jankowski <nrjank>
Group Member
Wed 06 Mar 2024 09:51:41 PM UTC, comment #2: 

I guess we'll start to see feature requests for other "page" functions like pagectranspose, pageeig, pageinv, pagemldivide, pagemrdivide, pagemtimes, pagenorm, and pagetranspose.  Are there any others?  Maybe they could all share some common code to handle the iteration over pages?

I'm not sure I see why these functions would have to be built in to the interpreter.  Why not just define them as .m files?  In any case, I'd prefer to avoid adding any MEX functions to core Octave.

John W. Eaton <jwe>
Group administrator
Mon 04 Mar 2024 07:15:50 PM UTC, comment #1: 

Thank you for the contribution.  The Octave maintainers are working quite hard on getting the 9.1 release out.  Once that is done we can hopefully return to this item.  In general, LAPACK and BLAS are required for Octave so that shouldn't be an issue.

Rik <rik5>
Group administrator
Mon 04 Mar 2024 06:41:40 PM UTC, original submission:  

The function pagesvd (and various others in the pagexxx family) was introduced in Matlab 2021. It's used to do lots of small svd calculations in parallel. E.g. do svd on N 4x4 matrices

``

>> N=100;
>> A=rand(4,4,N);
>> [U S V]=pagesvd(A,'econ');
>> whos

  Name      Size               Bytes  Class     Attributes

  A         4x4x100            12800  double             
  N         1x1                    8  double             
  S         4x4x100            12800  double             
  U         4x4x100            12800  double             
  V         4x4x100            12800  double           
``
I have a self-written implementation that uses calls to LAPACKC and OPENBLAS. It may be too tied to these libraries for general use on all platforms but gives an outline for how to do it. Just putting it out there :)

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #55781:  pagesvd.cpp added by None (9KiB - text/x-c++src)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2024-03-06 jwe Item GroupNone Feature Request
    2024-03-04 rik5 CategoryNone Octave Function
        Severity3 - Normal 1 - Wish
        StatusNone Patch Submitted
        Release8.4.0 dev
    2024-03-04 None Attached File- Added pagesvd.cpp, #55781

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code