Expose multithreaded fflas-ffpack features

[gh-ZHG2017]

Dense linear algebra mod small p uses fflas-ffpack over float or double. This library support multithreading for some routines:

• matrix-matrix multiplication
• PLUQ decomposition
• etc.

This ticket proposes to expose these parallel variants to Sage user.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e7f4be4

Add ParSeqHelper to Sage

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​22e592e

fixing indents and templated parallel helper

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​eae88f5

fgemm aggregated into SageMaths with no more compile time error but not yet find out how to run it with more threads

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​01de1e1

Compile and link flags added for enable openmp but no multithreading found

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fff3992	remove MMHelperAlgo
​d81e3c1	Merge branch 'u/gh-ZHG2017/expose_multithreaded_fflas_ffpack_features' of git://trac.sagemath.org/sage into t/27444/expose_multithreaded_fflas_ffpack_features
​86c2038	parallel fgemm working by patching fflas-ffpack

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​449b103

fix const error

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​397c108

fix error

[Clément Pernet]

For the record: matrix multiplication over finite field works in parallel. The following experiment is on a 12 cores Intel skylake-x server:

pernet@retourdest:~/soft/sage$ export OMP_NUM_THREADS=12;./sage 
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.7.beta7, Release Date: 2019-03-10               │
│ Using Python 2.7.15. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: a=random_matrix(GF(11),10000)
sage: time b=a*a
CPU times: user 23.3 s, sys: 405 ms, total: 23.7 s
Wall time: 3.3 s

while on the same machine, on master we get:

sage: a=random_matrix(GF(11),10000)
sage: time b=a*a
CPU times: user 18.4 s, sys: 211 ms, total: 18.6 s
Wall time: 18.7 s

The speed-up of 6 for a 12 core machine is below what a self-standing fflas-ffpack achieves. We need to investigate the reasons: alignment, strassen-winograd threshold, numa placement, etc.

[Erik Bray]

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​58a5309

Using Sage Parallelism() to let user choose number of threads for fgemm

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​421c853

Multithreaded fgemv using SageMath Parallelism() seems to be working

[Erik Bray]

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bd8b2a0	fix 32 compilation failure for linbox-rank
​ddacbf0	upgrade to linbox-1.6.3 fflas-ffpack-2.4.1 and givaro-4.1.1
​f2d1f29	upgrade to fflas-ffpack-2.4.2 fixing testsuite errors with echlon forms
​7848156	upgrade do fflas-ffpack 2.4.3 fixing an error in charpoly autotune
​c391252	Merge branch 't/26932/upgrade_to_givaro_4_1_0_fflas_ffpack_2_4_0_linbox_1_6_0' into t/27444/expose_multithreaded_fflas_ffpack_features
​2d552b9	pRank pDet and pReducedRowEchelonForm added with multithreading which also have been tested and cleaned up for code review

[Clément Pernet]

I confirm that the branch successfullly parallizes det, rank and echelonize. However, in the current version of the branch, the matrix product is no longer parallelized. Could you revert the call to pfgemm?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6ca42e2

Added back pfgemm with the same parallelism like pDet

[Clément Pernet]

I pushed a fix to a misplaced "noefd" algorithm specification. This seems to fix the broken doctests.

---

New commits:

​b386197	Merge branch 'develop' into t/27444/expose_multithreaded_fflas_ffpack_features
​371d63c	fix noefd default algorithm

[Luca De Feo]

I'm curious about these:

if m*n > 100000: sig_on()

Any reason not to always call sig_on()?

[Luca De Feo]

Docs need updating.

In parallelism.py:

EXAMPLES:

The number of processes is initialized to 1 (no parallelization) for each field (only tensor computations are implemented at the moment):

Also, it would be good to document in the matrix reference the availability of parallelism, like it is done in ​http://doc.sagemath.org/html/en/reference/tensor_free_modules/sage/tensor/modules/free_module_tensor.html#sage.tensor.modules.free_module_tensor.FreeModuleTensor.disp

[Luca De Feo]

Otherwise, I confirm there is no regression with Python 3. If you can fix the docs, this ticket is good for me.

[Clément Pernet]

Replying to defeo:

I'm curious about these:

if m*n > 100000: sig_on()

Any reason not to always call sig_on()?

I guess the reason is to avoid the overhead of using the sigs when the call is with a tiny instance which runs almost instantly and will therefore have no chance of being interrupted.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e432cb0

fixing the doc

[Clément Pernet]

@defeo: Doc fixed in the above commit. Should be good to go now.

[Luca De Feo]

The ticket has no authors?

[Frédéric Chapoton]

and no milestone ?

[Erik Bray]

I don't think this ticket should have removed --disable-openmp from the fflas_ffpack build without mention, because now it requires OpenMP support in any modules which link to it, and this doesn't seem to work properly.