Block Lanczos with a reordering pass - Page 2

fivemack · 2010-02-01, 16:03

I get

Code:

using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (4 threads)
memory use: 879.8 MB
linear algebra at 0.0%, ETA 17h49m46197 dimensions (0.0%, ETA 17h49m)    
linear algebra completed 2845775 of 2846197 dimensions (100.0%, ETA 0h 0m)    
lanczos halted after 45009 iterations (dim = 2845971)
recovered 32 nontrivial dependencies
BLanczosTime: 60345

using a version of msieve obtained by downloading lanczos-opt.tgz from msieve.sourceforge.org and building it. So no messages about the partitioning, and a couple of percent slower than the last time I ran this matrix.

jasonp · 2010-02-01, 17:16

There is a lanczos-opt directory at the top level that should not be there; are you sure you zipped up branches/lanczos-opt ? (The note about the partitioning should occur right after the initial matrix build and right before the text you quote)

I also spent some time yesterday feeding the matrix to a high-quality graph partitioning library (Metis is really nice), and it appeared to do quite a good job. Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.

Andi47 · 2010-02-01, 18:05

Quote:

Originally Posted by jasonp

There is a lanczos-opt directory at the top level that should not be there; are you sure you zipped up branches/lanczos-opt ? (The note about the partitioning should occur right after the initial matrix build and right before the text you quote)

I also spent some time yesterday feeding the matrix to a high-quality graph partitioning library (Metis is really nice), and it appeared to do quite a good job. Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.

Do you mean SVN184 which should not be there?

Is SVN185 part of the lanczos-opt brach or is it the main "branch"?

jasonp · 2010-02-01, 20:32

SVN 185 was a fix to branches/lanczos-opt; the repository copy in SVN 184 actually does not have the reordering code at all.

You can go to 'SVN Browse' in the 'Develop' menu on sourceforge, then click on a particular revision number and see exactly which files in the repository are affected.

Andi47 · 2010-02-06, 07:36

matrix step of a c133 with 1.43:

Code:

Fri Feb  5 06:41:40 2010  Msieve v. 1.43
Fri Feb  5 06:41:40 2010  random seeds: 35296e5c f31b436b
Fri Feb  5 06:41:40 2010  factoring 5335366387062594103281599506619078830675568770597674764072096981029494235489350569590888813457656823560321885511353040519174462222557 (133 digits)
Fri Feb  5 06:41:41 2010  no P-1/P+1/ECM available, skipping
Fri Feb  5 06:41:41 2010  commencing number field sieve (133-digit input)
Fri Feb  5 06:41:41 2010  R0: -43590657298344915874817701
Fri Feb  5 06:41:41 2010  R1:  467844431521753
Fri Feb  5 06:41:41 2010  A0:  3052516397340263636960237838715200
Fri Feb  5 06:41:41 2010  A1:  29100578051888094818724416280
Fri Feb  5 06:41:41 2010  A2:  36523592624186545117942
Fri Feb  5 06:41:41 2010  A3: -123602480596394341
Fri Feb  5 06:41:41 2010  A4: -18461007596
Fri Feb  5 06:41:41 2010  A5:  33900
Fri Feb  5 06:41:41 2010  skew 863842.14, size 7.089820e-13, alpha -7.025253, combined = 4.837199e-11
Fri Feb  5 06:41:41 2010  
Fri Feb  5 06:41:41 2010  commencing relation filtering
Fri Feb  5 06:41:41 2010  estimated available RAM is 1985.8 MB
Fri Feb  5 06:41:41 2010  commencing duplicate removal, pass 1
Fri Feb  5 06:44:27 2010  found 3339904 hash collisions in 14676617 relations
Fri Feb  5 06:45:06 2010  added 62981 free relations
Fri Feb  5 06:45:06 2010  commencing duplicate removal, pass 2
Fri Feb  5 06:45:46 2010  found 3492350 duplicates and 11247248 unique relations

<snip>

Feb  5 06:55:03 2010  commencing linear algebra
Fri Feb  5 06:55:04 2010  read 1428636 cycles
Fri Feb  5 06:55:08 2010  cycles contain 4538304 unique relations
Fri Feb  5 06:56:02 2010  read 4538304 relations
Fri Feb  5 06:56:10 2010  using 20 quadratic characters above 134217690
Fri Feb  5 06:56:42 2010  building initial matrix
Fri Feb  5 06:58:32 2010  memory use: 595.5 MB
Fri Feb  5 06:58:34 2010  read 1428636 cycles
Fri Feb  5 06:58:42 2010  matrix is 1428459 x 1428636 (435.0 MB) with weight 135788023 (95.05/col)
Fri Feb  5 06:58:42 2010  sparse part has weight 96885657 (67.82/col)
Fri Feb  5 06:59:07 2010  filtering completed in 2 passes
Fri Feb  5 06:59:07 2010  matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb  5 06:59:07 2010  sparse part has weight 96880921 (67.84/col)
Fri Feb  5 06:59:24 2010  read 1428021 cycles
Fri Feb  5 06:59:26 2010  matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb  5 06:59:26 2010  sparse part has weight 96880921 (67.84/col)
Fri Feb  5 06:59:26 2010  saving the first 48 matrix rows for later
Fri Feb  5 06:59:27 2010  matrix is 1427796 x 1428021 (418.5 MB) with weight 108661836 (76.09/col)
Fri Feb  5 06:59:27 2010  sparse part has weight 95415355 (66.82/col)
Fri Feb  5 06:59:27 2010  matrix includes 64 packed rows
Fri Feb  5 06:59:27 2010  using block size 65536 for processor cache size 4096 kB
Fri Feb  5 06:59:36 2010  commencing Lanczos iteration (2 threads)
Fri Feb  5 06:59:36 2010  memory use: 415.9 MB
Fri Feb  5 06:59:47 2010  linear algebra at 0.1%, ETA 5h13m
Fri Feb  5 12:58:11 2010  lanczos halted after 22580 iterations (dim = 1427795)
Fri Feb  5 12:58:15 2010  recovered 29 nontrivial dependencies
Fri Feb  5 12:58:15 2010  BLanczosTime: 21792

Same c133 on the same C2D laptop with SVN185:

Code:

Fri Feb  5 22:20:34 2010  Msieve v. 1.44
Fri Feb  5 22:20:34 2010  random seeds: eeced92d 786ed506
Fri Feb  5 22:20:34 2010  factoring 5335366387062594103281599506619078830675568770597674764072096981029494235489350569590888813457656823560321885511353040519174462222557 (133 digits)

<snip>

Fri Feb  5 22:33:54 2010  commencing linear algebra
Fri Feb  5 22:33:55 2010  read 1428636 cycles
Fri Feb  5 22:33:59 2010  cycles contain 4538304 unique relations
Fri Feb  5 22:34:53 2010  read 4538304 relations
Fri Feb  5 22:35:02 2010  using 20 quadratic characters above 134217690
Fri Feb  5 22:35:34 2010  building initial matrix
Fri Feb  5 22:37:25 2010  memory use: 595.5 MB
Fri Feb  5 22:37:27 2010  read 1428636 cycles
Fri Feb  5 22:37:35 2010  matrix is 1428459 x 1428636 (435.0 MB) with weight 135788023 (95.05/col)
Fri Feb  5 22:37:35 2010  sparse part has weight 96885657 (67.82/col)
Fri Feb  5 22:38:00 2010  filtering completed in 2 passes
Fri Feb  5 22:38:00 2010  matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb  5 22:38:00 2010  sparse part has weight 96880921 (67.84/col)
Fri Feb  5 22:38:18 2010  read 1428021 cycles
Fri Feb  5 22:38:19 2010  matrix is 1427844 x 1428021 (434.9 MB) with weight 135765621 (95.07/col)
Fri Feb  5 22:38:19 2010  sparse part has weight 96880921 (67.84/col)
Fri Feb  5 22:38:19 2010  saving the first 48 matrix rows for later
Fri Feb  5 22:38:20 2010  matrix is 1427796 x 1428021 (418.5 MB) with weight 108661836 (76.09/col)
Fri Feb  5 22:38:20 2010  sparse part has weight 95415355 (66.82/col)
Fri Feb  5 22:38:20 2010  matrix includes 64 packed rows
Fri Feb  5 22:38:20 2010  using block size 65536 for processor cache size 4096 kB
Fri Feb  5 22:38:29 2010  commencing Lanczos iteration (2 threads)
Fri Feb  5 22:38:29 2010  memory use: 415.9 MB
Fri Feb  5 22:38:40 2010  linear algebra at 0.1%, ETA 5h12m
Sat Feb  6 04:44:09 2010  lanczos halted after 22579 iterations (dim = 1427795)
Sat Feb  6 04:44:14 2010  recovered 29 nontrivial dependencies
Sat Feb  6 04:44:14 2010  BLanczosTime: 22220

Seems SVN185 is slower.

debrouxl · 2010-02-06, 09:55

I made some tests on C149_113_58 (SNFS difficulty 200) on Core 2 Duo T7200, 2 GB RAM (but that didn't work out, see below) and Core 2 Duo T7600, 3 GB RAM:

SVN185:

Code:

Msieve v. 1.44
Thu Feb  4 18:02:13 2010
random seeds: c08d3a90 82f55b5b
factoring 58726049878536391557011831786679470473096960150546862137088288968129115887237799139638233172513763094056500204963331970846586616031413324264998772683 (149 digits)
searching for 15-digit factors
commencing number field sieve (149-digit input)
R0: -624332378391008467754527498760580235264
R1:  38358611506121121577937
A0:  1442897
A1:  0
A2:  0
A3:  0
A4:  0
A5:  195112
skew 1.49, size 1.169368e-14, alpha -1.135403, combined = 6.064487e-12

commencing linear algebra
read 3259953 cycles
cycles contain 10103761 unique relations
read 10103761 relations
using 20 quadratic characters above 536870768
building initial matrix
memory use: 1326.4 MB
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
filtering completed in 1 passes
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
permuting matrix for faster multiplies
matrix is 3259753 x 3259953
sparse core is 2313986 x 1549672
graph has 11341062 edges
memory use: 160.22 MB
max edge weight is 36
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
saving the first 48 matrix rows for later
matrix is 3259705 x 3259953 (960.0 MB) with weight 242856059 (74.50/col)
sparse part has weight 219071221 (67.20/col)
matrix includes 64 packed rows
using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (2 threads)
memory use: 975.0 MB
linear algebra at 0.0%, ETA 33h37m59953 dimensions (0.0%, ETA 33h37m)
^Cnear algebra completed 6836 of 3259953 dimensions (0.2%, ETA 33h18m)
received signal 2; shutting down

lanczos halted after 111 iterations (dim = 7024)
BLanczosTime: 976
elapsed time 00:16:17

trunk (SVN 189, I think):

Code:

Msieve v. 1.44
Thu Feb  4 18:19:19 2010
random seeds: 4c27aea9 6f01d9ad
factoring 58726049878536391557011831786679470473096960150546862137088288968129115887237799139638233172513763094056500204963331970846586616031413324264998772683 (149 digits)
searching for 15-digit factors
commencing number field sieve (149-digit input)
R0: -624332378391008467754527498760580235264
R1:  38358611506121121577937
A0:  1442897
A1:  0
A2:  0
A3:  0
A4:  0
A5:  195112
skew 1.49, size 1.169368e-14, alpha -1.135403, combined = 6.064487e-12

commencing linear algebra
read 3259953 cycles
cycles contain 10103761 unique relations
read 10103761 relations
using 20 quadratic characters above 536870768
building initial matrix
memory use: 1326.4 MB
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
filtering completed in 1 passes
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
read 3259953 cycles
matrix is 3259753 x 3259953 (1002.3 MB) with weight 304669742 (93.46/col)
sparse part has weight 226894247 (69.60/col)
saving the first 48 matrix rows for later
matrix is 3259705 x 3259953 (960.0 MB) with weight 242856059 (74.50/col)
sparse part has weight 219071221 (67.20/col)
matrix includes 64 packed rows
using block size 65536 for processor cache size 4096 kB
commencing Lanczos iteration (2 threads)
memory use: 974.9 MB
linear algebra at 0.0%, ETA 33h18m59953 dimensions (0.0%, ETA 33h18m)
^Cnear algebra completed 7343 of 3259953 dimensions (0.2%, ETA 33h35m)
received signal 2; shutting down

lanczos halted after 119 iterations (dim = 7530)
BLanczosTime: 806
elapsed time 00:13:28

I guess I need to mention that despite the "memory use: 974.9 MB" and "memory use: 975.0 MB"; traces, consistent wrt. each other, the memory consumption of the reordering-enabled binary was at least 700 MB (!) higher than that of the other binary.
On the T7200 with 2 GB RAM, the reordering-enabled binary was killed by Linux's OOM killer before it could display "commencing Lanczos iteration (2 threads)", so I switched to the T7600.

jasonp, if you think that it would be useful for testing the algorithm (all of our tasks are beyond 2M cycles), I can send you how to get the raw sieving data of the RSALS grid

debrouxl · 2010-02-07, 08:00

For some reason, I can't seem to be allowed to edit my own posts (even after logging out and logging back in), so I'm creating a new post.
[EDIT: the Edit button appears on this post right after I've made it - is there a time limit ?]

Quote:

Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.

If the total memory requirements of the other graph partitioning code are lower than the requirements of the rest of the msieve LA pass, it can remain a valid option (barring e.g. licensing issues, of course).

10metreh · 2010-02-07, 08:33

Quote:

Originally Posted by debrouxl

[EDIT: the Edit button appears on this post right after I've made it - is there a time limit ?]

Yes there is: 1 hour (unless you're a moderator).

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve with MPI block Lanczos	jasonp	Msieve	104	2013-06-17 11:28
block wiedemann and block lanczos	ravlyuchenko	Msieve	5	2011-05-09 13:16
Why is lanczos hard to distribute?	Christenson	Factoring	39	2011-04-08 09:44
Lanczos error	Andi47	Msieve	7	2009-01-11 19:33
Msieve Lanczos scalability	Jeff Gilchrist	Msieve	1	2009-01-02 09:32

2010-02-01, 17:16	#13
jasonp Tribal Bullet Oct 2004 6725₈ Posts	There is a lanczos-opt directory at the top level that should not be there; are you sure you zipped up branches/lanczos-opt ? (The note about the partitioning should occur right after the initial matrix build and right before the text you quote) I also spent some time yesterday feeding the matrix to a high-quality graph partitioning library (Metis is really nice), and it appeared to do quite a good job. Unfortunately, multilevel graph partitioning with simultaneous constraints takes around 6x the memory use of my crappy code, so it's a non-starter for really big problems.

2010-02-01, 20:32	#15
jasonp Tribal Bullet Oct 2004 3,541 Posts	SVN 185 was a fix to branches/lanczos-opt; the repository copy in SVN 184 actually does not have the reordering code at all. You can go to 'SVN Browse' in the 'Develop' menu on sourceforge, then click on a particular revision number and see exactly which files in the repository are affected.